Jump to content

Gauss–Jordan elimination: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Reverted 1 edit by D.Lazard (talk): Self revert: I counted multiplications, not multiplications and additions. (TW)
Tag: Redirect target changed
 
(10 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{mergeto|Gaussian elimination|date=February 2013}}
#REDIRECT [[Gaussian elimination#Gauss–Jordan elimination]]


{{rcat shell|
In [[linear algebra]], '''Gauss–Jordan elimination''' is an [[algorithm]] for getting [[matrix (mathematics)|matrices]] in [[reduced row echelon form]] using [[elementary row operations]]. It is a variation of [[Gaussian elimination]]. Gaussian elimination places zeros below each [[pivot element|pivot]] in the matrix, starting with the top row and working downwards. Matrices containing zeros below each pivot are said to be in row echelon form. Gauss–Jordan elimination goes a step further by placing zeros above and below each pivot; such matrices are said to be in reduced row echelon form. Every matrix has a reduced row echelon form, and Gauss–Jordan elimination is guaranteed to find it.
{{R from merge}}

{{R with Wikidata item}}
It is named after [[Carl Friedrich Gauss]] and [[Wilhelm Jordan (geodesist)|Wilhelm Jordan]] because it is a variation of Gaussian elimination as Jordan described 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.<ref>{{Citation | last1=Althoen | first1=Steven C. | last2=McLaughlin | first2=Renate | title=Gauss–Jordan reduction: a brief history | doi=10.2307/2322413 | year=1987 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]] | issn=0002-9890 | volume=94 | issue=2 | pages=130–142 | jstor=2322413 | publisher=Mathematical Association of America}}</ref>
{{R to anchor}}

== Comparison with Gaussian elimination ==
Gauss-Jordan elimination, like [[Gaussian elimination]], is used for inverting matrices and solving systems of linear equations. Both Gauss–Jordan and Gaussian elimination have [[computational complexity theory|time complexity]] of order <math>O(n^3)</math> for an ''n'' by ''n'' [[Rank (linear algebra)|full rank]] matrix (using [[Big O Notation]]), but the order of magnitude of the number of arithmetic operations (there are roughly the same number of additions and multiplications/divisions) used in solving a ''n'' by ''n'' matrix by Gauss-Jordan elimination is <math>n^3</math>, whereas that for Gaussian elimination is <math>\tfrac{2n^3}{3}</math>. Hence, Gauss-Jordan elimination requires approximately 50% more computation steps.<ref>J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10</ref> However, the result of Gauss-Jordan elimination ([[reduced row echelon form]]) may be retrieved from the result of Gaussian elimination ([[row echelon form]]) in <math>O(n^2)</math> arithmetic operations, by proceeding from the last pivot to the first one. Thus the needed number of operations has the same order of magnitude for both eliminations.

== Application to finding inverses ==

Gauss–Jordan elimination calculates the [[inverse matrix|inverse]] of a [[square matrix]]. This can be done by [[augmented matrix|augmenting]] the square matrix with the [[identity matrix]] of the same dimensions and applying the following matrix operations, where <math>\Rightarrow</math> stands for "may be transformed by [[elementary row operation]]s into".
:<math>[ A | I ] \Rightarrow
A^{-1} [ A | I ] =
[ 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, by augmenting by the identity, the following is obtained:
:<math> [ A | I ] =
\left[ \begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>
Gauss–Jordan elimination on the <math>[ A | I ]</math> produces <math>[ I | A^{-1} ]</math>, its [[reduced row echelon form]] by simple row operations:

:<math> [ I | A^{-1} ] =
\left[ \begin{array}{rrr|rrr}
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{array} \right].
</math>

There are usually many ways to proceed to reduce the rows. What follows is one specific series of steps.

<sub>Note: below the symbolic expression rx → rx + c*ry means the elements of row x are '''replaced by''' the sum of the value of that element and a number c times the corresponding element in row y in the same column.</sub>

i) add second row, r2, to first, r1. r1 → r1 + r2
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>


ii) add r1 to r2. r2 → r2 + r1
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
0 & 3 & -2 & 1 & 2 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>


iii) add 2*r3 to r2. r2 → r2 + 2*r3
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 2 & 2\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>


iv) add r2 to r3. r3 → r3 + r2
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 2 & 2\\
0 & 0 & 4 & 1 & 2 & 3
\end{array} \right].
</math>


v) divide r3 by 4. r3 → r3 ÷ 4
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
0 & 1 & 2 & 1 & 2 & 2\\
0 & 0 & 1 & \frac {1}{4} & \frac{1}{2} & \frac {3}{4}
\end{array} \right].
</math>


vi) subtract 2*r3 from r2. r2 → r2 - 2*r3
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & -1 & 1 & 1 & 0\\
0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\
0 & 0 & 1 & \frac {1}{4} & \frac{1}{2} & \frac {3}{4}
\end{array} \right].
</math>


vii) add r3 to r1. r1 → r1 + r3
:<math>\left[ \begin{array}{rrr|rrr}
1 & 1 & 0 & \frac {5}{4} & \frac {3}{2} & \frac{3}{4}\\
0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\
0 & 0 & 1 & \frac {1}{4} & \frac{1}{2} & \frac {3}{4}
\end{array} \right].
</math>


viii) subtract r2 from r1. r1 → r1 - r2
:<math>\left[ \begin{array}{rrr|rrr}
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{array} \right] = [ I | A^{-1} ]
</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) [[if and only if]] the left hand side of row echelon form that has been obtained is the identity matrix.

==References==
{{Reflist}}
* Lipschutz, Seymour, and Lipson, Mark. "Schaum's Outlines: Linear Algebra". Tata McGraw–Hill edition. Delhi 2001. pp.&nbsp;69–80.
* {{Citation
|last1=Press
|first1=WH
|last2=Teukolsky
|first2=SA
|last3=Vetterling
|first3=WT
|last4=Flannery
|first4=BP
|year=2007
|title=Numerical Recipes: The Art of Scientific Computing
|edition=3rd
|publisher=Cambridge University Press
| publication-place=New York
|isbn=978-0-521-88068-8
|chapter=Section 2.1
|chapter-url=http://apps.nrbook.com/empanel/index.html?pg=41
}}
}}
* {{Citation | last1=Strang | first1=Gilbert | author1-link=Gilbert Strang | title=Introduction to Linear Algebra | publisher=Wellesley-Cambridge Press | location=[[Wellesley, Massachusetts]] | edition=3rd | isbn=978-0-9614088-9-3 | year=2003 | pages = 74–76}}

== External links ==
<!-- {{wikibooks |1= Linear Algebra |2= Linear Algebra/Gauss-Jordan Reduction |3= Gauss-Jordan elimination }} -->
*[http://users.powernet.co.uk/kienzle/octave/matcompat/scripts/linear-algebra/rref.m Algorithm for Gauss–Jordan elimination in Octave]
*[http://elonen.iki.fi/code/misc-notes/python-gaussj/index.html Algorithm for Gauss–Jordan elimination in Python]
*[http://lipe.advant.com.br/unicenp/gauss-jordan.php An online tool solve nxm linear systems using Gauss–Jordan elimination (source-code and mobile version included), by Felipe Santos de Andrade] (Portuguese)
*[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"]
*[http://www.idomaths.com/gauss_jordan.php Gauss–Jordan Elimination Calculator]

== See also ==
* [[Gaussian elimination]]
* [[Computational complexity of mathematical operations]]
* [[Levinson recursion]]
* [[Strassen algorithm]]
* [[Coppersmith–Winograd algorithm]]


{{Numerical linear algebra}}

{{DEFAULTSORT:Gauss–Jordan Elimination}}
[[Category:Numerical linear algebra]]
[[Category:Exchange algorithms]]

[[ar:حذف غاوس-جوردان]]
[[de:Gauß-Jordan-Algorithmus]]
[[es:Eliminación de Gauss-Jordan]]
[[fr:Élimination de Gauss-Jordan]]
[[ko:가우스-요르단 소거법]]
[[id:Eliminasi Gauss-Jordan]]
[[is:Gauß-Jordan eyðing]]
[[it:Algoritmo di Gauss-Jordan]]
[[nl:Gauss-Jordaneliminatie]]
[[pt:Eliminação de Gauss-Jordan]]
[[ru:Метод Гаусса — Жордана]]
[[uk:Метод Гауса — Жордана]]
[[zh:高斯-若爾當消元法]]

Latest revision as of 15:51, 24 October 2023

Redirect to:

Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Gauss–Jordan_elimination&oldid=1181682532"