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:高斯-約當消去法]]