Gauss–Jordan elimination: Information from Answers.com

In linear algebra, Gauss–Jordan elimination is a version of Gaussian elimination that puts zeros both above and below each pivot element as it goes from the top row of the given matrix to the bottom. Gauss–Jordan elimination is considerably less efficient than Gaussian elimination with backsubstitution when solving a system of linear equations. However, it is well suited for calculating the matrix inverse. Every matrix has a reduced row echelon form, and both algorithms are guaranteed to produce it.

It is named in after Carl Friedrich Gauss and Wilhelm Jordan, because it is a modification of Gaussian elimination as described by Jordan in 1887. However, the method also appears in an article by Clasen published in the same year. Jordan and Clasen probably discovered Gauss–Jordan elimination independently (Althoen & McLaughlin 1987).

In computer science, Gauss-Jordan elimination as an algorithm has a time complexity of $O (n 3)$ .

Application to finding inverses

If Gauss–Jordan elimination is applied on a square matrix, it can be used to calculate the matrix's inverse. This can be done by augmenting the square matrix with the identity matrix of the same dimensions, and through the following matrix operations:

$[ A I ] \Rightarrow A^{-1} [ A I ] \Rightarrow [ I A^{-1} ].$

If the original square matrix, $A$ , is given by the following expression:

$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}.$

Then, after augmenting by the identity, the following is obtained:

$[ A I ] = \begin{bmatrix} 2 & -1 & 0 & 1 & 0 & 0\\ -1 & 2 & -1 & 0 & 1 & 0\\ 0 & -1 & 2 & 0 & 0 & 1 \end{bmatrix}.$

By performing elementary row operations on the $[A I]$ matrix until it reaches reduced row echelon form, the following is the final result:

$[ I A^{-1} ] = \begin{bmatrix} 1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\ 0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\ 0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{bmatrix}.$

The matrix augmentation can now be undone, which gives the following:

$I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\qquad A^{-1} = \begin{bmatrix} \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\ \frac{1}{2} & 1 & \frac{1}{2}\\ \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \end{bmatrix}.$

$A^{-1} =\frac{1}{4} \begin{bmatrix} 3 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 3 \end{bmatrix}=\frac{1}{det(A)} \begin{bmatrix} 3 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 3 \end{bmatrix}.$

A matrix is non-singular (meaning that it has an inverse matrix) if and only if the identity matrix can be obtained using only elementary row operations.

References

Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history", The American Mathematical Monthly 94 (2): 130–142, doi:10.2307/2322413, ISSN 0002-9890 .
Lipschutz, Seymour, and Lipson, Mark. "Schaum's Outlines: Linear Algebra". Tata McGraw–Hill edition. Delhi 2001. pp. 69–80.
Strang, Gilbert (2003), Introduction to Linear Algebra (3rd ed.), Wellesley, Massachusetts: Wellesley-Cambridge Press, pp. 74–76, ISBN 978-0-9614088-9-3 .

External links

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Gaussian reduction (mathematics)
	Wilhelm Jordan
	Lie group decomposition

	Write a c language program that solves linear equations using gauss-jordan elimination method? Read answer...
	Solve the following systems of simultaneous linear equations using Gauss elimination method and Gauss-Seidel Method? Read answer...
	Where is the gauss blaster in fallout 3? Read answer...

	Solve 4x plus y-z equals 1 solve using Gauss Elimination Gauss Jordan Gauss Seider and Gauss Jacobi Methods?
	Write a c function that solves system of linear equations using Gauss-Jordan Elimination method?
	Using gauss or jordan gauss elimination X plus 2y plus 2z equals 9 and x plus y plus z equals 9 and 3x-y plus 3z equals 10?