TOPICS
Search

Gaussian Elimination

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

Ax=b.
(1)

More generally, Gaussian elimination applies to matrices over any field, including a finite field (Shoup 2009). For a dense n×n matrix, the standard algorithm uses O(n^3) arithmetic operations, while pivoting determines which element is used (Golub and Van Loan 2013). The row eliminations associated with a given pivot can be performed in parallel. De Laurentis and Franklin (2026) describe a parallel CUDA implementation over finite fields, the real numbers, and the complex numbers.

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. Continuing the process by normalizing each pivot and eliminating entries both above and below it produces reduced row-echelon form and is usually called Gauss-Jordan elimination.

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, Echelon Form, Elementary Row and Column Operations, Gauss-Jordan Elimination, LU Decomposition, Matrix Equation, Pivot Element, Pivoting, 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.De Laurentis, G. and Franklin, J. "Linac: Linear Algebra with CUDA over Finite Fields." 25 May 2026. https://arxiv.org/abs/2605.25863.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.Golub, G. H. and Van Loan, C. F. "General Linear Systems." Ch. 3 in Matrix Computations, 4th ed. Baltimore, MD: Johns Hopkins University Press, 2013.Shoup, V. "Matrices." Ch. 14 in A Computational Introduction to Number Theory and Algebra, 2nd ed. Cambridge, England: Cambridge University Press, pp. 377-398, 2009.

Referenced on Wolfram|Alpha

Gaussian Elimination

Cite this as:

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

Subject classifications