TOPICS
Search

Gaussian Elimination

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Gaussian elimination is a method for solving matrix equations of the form

Ax=b.
(1)

To perform Gaussian elimination starting with the system of equations

[a_(11) a_(12) ... a_(1k); a_(21) a_(22) ... a_(2k); | | ... |; a_(k1) a_(k2) ... a_(kk)][x_1; x_2; |; x_k]=[b_1; b_2; |; b_k],
(2)

compose the "augmented matrix equation"

[a_(11) a_(12) ... a_(1k); a_(21) a_(22) ... a_(2k); | | ... |; a_(k1) a_(k2) ... a_(kk)|b_1; b_2; |; b_k][x_1; x_2; |; x_k].
(3)

Here, the column vector in the variables x is carried along for labeling the matrix rows. Now, perform elementary row operations to put the augmented matrix into the upper triangular form

[a_(11)^' a_(12)^' ... a_(1k)^'; 0 a_(22)^' ... a_(2k)^'; | | ... |; 0 0 ... a_(kk)^'|b_1^'; b_2^'; |; b_k^'].
(4)

Solve the equation of the kth row for x_k, then substitute back into the equation of the (k-1)st row to obtain a solution for x_(k-1), etc., according to the formula

x_i=1/(a_(ii)^')(b_i^'-sum_(j=i+1)^ka_(ij)^'x_j).
(5)

In the Wolfram Language, RowReduce performs a version of Gaussian elimination, with the equation mx=b being solved by 

  GaussianElimination[m_?MatrixQ, v_?VectorQ] :=
    Last /@ RowReduce[Flatten /@ Transpose[{m, v}]]

LU decomposition of a matrix is frequently used as part of a Gaussian elimination process for solving a matrix equation.

A matrix that has undergone Gaussian elimination is said to be in echelon form.

For example, consider the matrix equation

[9 3 4; 4 3 4; 1 1 1][x_1; x_2; x_3]=[7; 8; 3].
(6)

In augmented form, this becomes

[9 3 4; 4 3 4; 1 1 1|7; 8; 3][x_1; x_2; x_3].
(7)

Switching the first and third rows (without switching the elements in the right-hand column vector) gives

[1 1 1; 4 3 4; 9 3 4|3; 8; 7][x_1; x_2; x_3].
(8)

Subtracting 9 times the first row from the third row gives

[1 1 1; 4 3 4; 0 -6 -5| 3; 8; -20][x_1; x_2; x_3].
(9)

Subtracting 4 times the first row from the second row gives

[1 1 1; 0 -1 0; 0 -6 -5| 3; -4; -20][x_1; x_2; x_3].
(10)

Finally, adding -6 times the second row to the third row gives

[1 1 1; 0 -1 0; 0 0 -5| 3; -4; 4][x_1; x_2; x_3].
(11)

Restoring the transformed matrix equation gives

[1 1 1; 0 -1 0; 0 0 -5][x_1; x_2; x_3]=[ 3; -4; 4],
(12)

which can be solved immediately to give x_3=-4/5, back-substituting to obtain x_2=4 (which actually follows trivially in this example), and then again back-substituting to find x_1=-1/5.

See also

Augmented Matrix, Condensation, Elementary Row and Column Operations, Echelon Form, Gauss-Jordan Elimination, LU Decomposition, Matrix Equation, Square Root Method

Explore with Wolfram|Alpha

References

Bareiss, E. H. "Multistep Integer-Preserving Gaussian Elimination." Argonne National Laboratory Report ANL-7213, May 1966.Bareiss, E. H. "Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination." Math. Comput. 22, 565-578, 1968.Garbow, B. S. "Integer-Preserving Gaussian Elimination." Program P-158 (3600F), Applied Mathematics Division, Argonne National Laboratory, Nov. 21, 1966.Gentle, J. E. "Gaussian Elimination." §3.1 in Numerical Linear Algebra for Applications in Statistics. Berlin: Springer-Verlag, pp. 87-91, 1998.

Referenced on Wolfram|Alpha

Gaussian Elimination

Cite this as:

Weisstein, Eric W. "Gaussian Elimination." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GaussianElimination.html

Subject classifications