Gauss–Jordan elimination
5134689
213361651
2008-05-19T00:12:10Z
Katanada
6015359
/* External links */
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. In other words, Gauss-Jordan elimination brings a matrix to [[reduced row echelon form]], whereas Gaussian elimination takes it only as far as [[row echelon form]]. Every matrix has a reduced row echelon form, and this algorithm is guaranteed to produce it.
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]].
It is named in honor of [[Carl Friedrich Gauss]] and [[Wilhelm Jordan]].
== Application to finding inverses ==
If Gauss–Jordan elimination is applied on a [[square matrix]], it can be used to calculate the matrix's [[inverse matrix|inverse]]. This can be done by [[augmented matrix|augmenting]] the square matrix with the [[identity matrix]] of the same dimensions, and through the following matrix operations:
:<math>[ A I ] \Longrightarrow
A^{-1} [ A I ] \Longrightarrow
[ I A^{-1} ].
</math>
If the original square matrix, <math>A</math>, is given by the following expression:
:<math> A =
\begin{bmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{bmatrix}.
</math>
Then, after augmenting by the identity, the following is obtained:
:<math> [ A I ] =
\begin{bmatrix}
2 & -1 & 0 & 1 & 0 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{bmatrix}.
</math>
By performing [[elementary row operations]] on the <math>[ A I ]</math> matrix until <math>A</math> reaches [[reduced row echelon form]], the following is the final result:
:<math> [ 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}.
</math>
The matrix augmentation can now be undone, which gives the following:
:<math> 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}.
</math>
A matrix is [[non-singular matrix|non-singular]] (meaning that it has an inverse matrix) [[iff]] the identity matrix can be obtained using only elementary row operations.
== References ==
* Lipschutz, Seymour, and Lipson, Mark. "Schaum's Outlines: Linear Algebra". Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
* {{cite book | author = Strang, Gilbert | title = Introduction to Linear Algebra | edition = 3rd edition | year = 2003 | location = [[Wellesley, Massachusetts]] | publisher = Wellesley-Cambridge Press | pages = 74-76}}
== External links ==
*[http://users.powernet.co.uk/kienzle/octave/matcompat/scripts/linear-algebra/rref.m Algorithm for Gauss-Jordan elimination in Matlab]
*[http://elonen.iki.fi/code/misc-notes/python-gaussj/index.html Algorithm for Gauss-Jordan elimination in Python]
*[http://www.cs.berkeley.edu/~wkahan/MathH110/gji.pdf Algorithm for Gauss-Jordan elimination in Basic]
*[http://math.fullerton.edu/mathews/n2003/GaussianJordanMod.html Module for Gauss-Jordan Elimination]
*[http://vivaldi.ucsd.edu:8080/~kcheng/ece155/hwsoln/Gaussian-Jordan.pdf Example of Gauss-Jordan Elimination "Step-by-Step"]
{{mathapplied-stub}}
[[Category:Numerical linear algebra]]
[[id:Eliminasi Gauss-Jordan]]
[[de:Gauß-Jordan-Algorithmus]]
[[is:Gauß-Jordan eyðing]]
[[he:אלימינציית גאוס-ג'ורדן]]
[[nl:Gauss-Jordaneliminatie]]
[[pt:Eliminação de Gauss-Jordan]]
[[ru:Метод Гаусса — Жордана]]
[[zh:高斯-約當消去法]]