Gaussian Elimination

Gaussian elimination reduces Ax⃗=b⃗A\vec{x} = \vec{b} to echelon form by row operations, then solves it by back substitution.

Forward Elimination

The pivot element of a column is the entry used to eliminate the other entries in that column.

Provided a11≠0a_{11} \neq 0, eliminate x1x_1 from equations 22 through nn using

Rj−aj1a11R1→Rj,j=2,3,…,nR_j - \frac{a_{j1}}{a_{11}} R_1 \to R_j, \quad j = 2, 3, \ldots, n

More generally, eliminate xix_i below row ii, for i=1,2,…,n−1i = 1, 2, \ldots, n-1, using

Rj−aji(i)aii(i)Ri→Rj,j=i+1,i+2,…,nR_j - \frac{a_{ji}^{(i)}}{a_{ii}^{(i)}} R_i \to R_j, \quad j = i+1, i+2, \ldots, n

provided aii(i)≠0a_{ii}^{(i)} \neq 0. This reduces [A∣b⃗][A \mid \vec{b}] to upper triangular form

(a11a12⋯a1nb1(1)0a22(1)⋯a2nb2(2)⋮⋱⋮⋮00⋯ann(n−1)bn(n−1))\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1^{(1)} \\ 0 & a_{22}^{(1)} & \cdots & a_{2n} & b_2^{(2)} \\ \vdots & & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & a_{nn}^{(n-1)} & b_n^{(n-1)} \end{pmatrix}

Back Substitution

Once [A∣b⃗][A \mid \vec{b}] is upper triangular, solve from the last row upward. The last row has only xnx_n

xn=bn(n−1)ann(n−1)x_n = \frac{b_n^{(n-1)}}{a_{nn}^{(n-1)}}

Then substitute the solved unknowns into each row above

xi=bi(i−1)−∑j=i+1naij(i−1)xjaii(i−1),i=n−1,n−2,…,1x_i = \frac{b_i^{(i-1)} - \sum\limits_{j=i+1}^{n} a_{ij}^{(i-1)}x_j}{a_{ii}^{(i-1)}}, \quad i = n-1, n-2, \ldots, 1

Pivoting

Pivoting is interchanging rows or columns to place a larger entry in the pivot position. The system stays equivalent.

Partial Pivoting

At stage ii, find the row p≥ip \geq i maximizing ∣aji(i)∣|a_{ji}^{(i)}| for j≥ij \geq i, then swap Ri↔RpR_i \leftrightarrow R_p before eliminating. This keeps every multiplier at or below 11 in magnitude.

Scaled Partial Pivoting

Partial pivoting can pick a poor pivot when an entry is large only because its row is large. Scaled partial pivoting compares entries relative to their row. Before elimination begins, compute the scale factor of each row

sj=max⁡1≤k≤n∣ajk∣s_j = \max_{1 \leq k \leq n} |a_{jk}|

At stage ii, pick the first row p≥ip \geq i maximizing ∣aji(i)∣sj\frac{|a_{ji}^{(i)}|}{s_j} and swap Ri↔RpR_i \leftrightarrow R_p. The scale factors sjs_j are computed once and carried along with their rows during swaps.

Complete Pivoting

At stage ii, search the entire remaining submatrix for the entry maximizing ∣ajk(i)∣|a_{jk}^{(i)}| over j≥ij \geq i and k≥ik \geq i. Swap its row into row ii and its column into column ii before eliminating.

Pitfalls

Zero Pivot

If aii(i)=0a_{ii}^{(i)} = 0, the multiplier divides by zero even when the system has a unique solution. Swap in a row below with a non-zero entry in that column.

Small Pivot

A small pivot inflates the multipliers aji(i)aii(i)\frac{a_{ji}^{(i)}}{a_{ii}^{(i)}}, which amplifies rounding error through every later stage.

Ill Conditioning

A problem is ill-conditioned iff a small change in any of its elements causes a large change in its solution. Otherwise the problem is well-conditioned.

Round-off errors slightly change AA and b⃗\vec{b}. In an ill-conditioned system this gives large errors in the solution, and pivoting cannot prevent it.

Consider

(1111.0001)(xy)=(22.0001)\begin{pmatrix} 1 & 1 \\ 1 & 1.0001 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}2\\2.0001\end{pmatrix}

with solution x=1,y=1x = 1, y = 1. Changing b2b_2 from 2.00012.0001 to 2.00022.0002, a change of 0.00010.0001, gives

(1111.0001)(xy)=(22.0002)\begin{pmatrix} 1 & 1 \\ 1 & 1.0001 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}2\\2.0002\end{pmatrix}

with solution x=0,y=2x = 0, y = 2. A 0.00010.0001 change in b2b_2 moved xx and yy by 11 each. The coefficient matrix is nearly singular, det⁡=0.0001\det = 0.0001.

The condition number quantifies this sensitivity.

Cost

MethodTimeSpace
Forward eliminationO(n3)O(n^3)O(n2)O(n^2)
Back substitutionO(n2)O(n^2)O(n2)O(n^2)

Space is for the augmented matrix [A∣b⃗][A \mid \vec{b}], since elimination is done in place. The O(n3)O(n^3) elimination is repeated for every new b⃗\vec{b}, which LU decomposition avoids.

Worked Examples

Example 1

Solve using Gaussian elimination without pivoting.

2x1+x2−x3=8−3x1−x2+2x3=−11−2x1+x2+2x3=−3\begin{aligned} 2x_1 + x_2 - x_3 &= 8 \\ -3x_1 - x_2 + 2x_3 &= -11 \\ -2x_1 + x_2 + 2x_3 &= -3 \end{aligned}
Solution Reveal Hide
1 /
[21−18−3−12−11−212−3]\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]

The pivot is a11=2a_{11} = 2.

m21=−32=−1.5,m31=−22=−1m_{21} = \frac{-3}{2} = -1.5, \quad m_{31} = \frac{-2}{2} = -1→R3+R1R2+1.5R1[21−1800.50.510215]\xrightarrow[R_3 + R_1]{R_2 + 1.5R_1} \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 2 & 1 & 5 \end{array}\right]

The pivot is a22(1)=0.5a_{22}^{(1)} = 0.5.

m32=20.5=4m_{32} = \frac{2}{0.5} = 4→R3−4R2[21−1800.50.5100−11]\xrightarrow{R_3 - 4R_2} \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 0 & -1 & 1 \end{array}\right]
x3=1−1=−1x_3 = \frac{1}{-1} = -1x2=1−0.5(−1)0.5=3x_2 = \frac{1 - 0.5(-1)}{0.5} = 3x1=8−1(3)−(−1)(−1)2=2x_1 = \frac{8 - 1(3) - (-1)(-1)}{2} = 2x⃗=(2,3,−1)T\vec{x} = (2, 3, -1)^T

Example 2

Solve using Gaussian elimination with partial pivoting.

3x2+x3=92x1+2x2−x3=34x1+2x2+x3=11\begin{aligned} 3x_2 + x_3 &= 9 \\ 2x_1 + 2x_2 - x_3 &= 3 \\ 4x_1 + 2x_2 + x_3 &= 11 \end{aligned}
Solution Reveal Hide
1 /
[031922−1342111]\left[\begin{array}{ccc|c} 0 & 3 & 1 & 9 \\ 2 & 2 & -1 & 3 \\ 4 & 2 & 1 & 11 \end{array}\right]

Column 1 has magnitudes ∣0∣|0|, ∣2∣|2|, and ∣4∣|4|. The largest is ∣a31∣=4|a_{31}| = 4 in R3R_3, so swap R1↔R3R_1 \leftrightarrow R_3.

→R1↔R3[4211122−130319]\xrightarrow{R_1 \leftrightarrow R_3} \left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 2 & 2 & -1 & 3 \\ 0 & 3 & 1 & 9 \end{array}\right]m21=24=0.5,m31=0m_{21} = \frac{2}{4} = 0.5, \quad m_{31} = 0→R2−0.5R1[4211101−1.5−2.50319]\xrightarrow{R_2 - 0.5R_1} \left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 1 & -1.5 & -2.5 \\ 0 & 3 & 1 & 9 \end{array}\right]

Column 2 below row 1 has magnitudes ∣1∣|1| and ∣3∣|3|. The largest is ∣a32(1)∣=3|a_{32}^{(1)}| = 3 in R3R_3, so swap R2↔R3R_2 \leftrightarrow R_3.

→R2↔R3[42111031901−1.5−2.5]\xrightarrow{R_2 \leftrightarrow R_3} \left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 3 & 1 & 9 \\ 0 & 1 & -1.5 & -2.5 \end{array}\right]m32=13m_{32} = \frac{1}{3}→R3−13R2[42111031900−116−112]\xrightarrow{R_3 - \frac{1}{3}R_2} \left[\begin{array}{ccc|c} 4 & 2 & 1 & 11 \\ 0 & 3 & 1 & 9 \\ 0 & 0 & -\frac{11}{6} & -\frac{11}{2} \end{array}\right]
x3=−11/2−11/6=3x_3 = \frac{-11/2}{-11/6} = 3x2=9−1(3)3=2x_2 = \frac{9 - 1(3)}{3} = 2x1=11−2(2)−1(3)4=1x_1 = \frac{11 - 2(2) - 1(3)}{4} = 1x⃗=(1,2,3)T\vec{x} = (1, 2, 3)^T

Example 3

Solve using Gaussian elimination with scaled partial pivoting.

4x1+100x2−50x3=54x1+x2+2x3=42x1−x3=1\begin{aligned} 4x_1 + 100x_2 - 50x_3 &= 54 \\ x_1 + x_2 + 2x_3 &= 4 \\ 2x_1 - x_3 &= 1 \end{aligned}
Solution Reveal Hide
1 /
[4100−5054112420−11]\left[\begin{array}{ccc|c} 4 & 100 & -50 & 54 \\ 1 & 1 & 2 & 4 \\ 2 & 0 & -1 & 1 \end{array}\right]s1=max⁡{4,100,50}=100,s2=max⁡{1,1,2}=2,s3=max⁡{2,0,1}=2s_1 = \max\{4, 100, 50\} = 100, \quad s_2 = \max\{1, 1, 2\} = 2, \quad s_3 = \max\{2, 0, 1\} = 2

Compare the scaled magnitudes in column 1.

∣a11∣s1=4100=0.04,∣a21∣s2=12=0.5,∣a31∣s3=22=1\frac{|a_{11}|}{s_1} = \frac{4}{100} = 0.04, \quad \frac{|a_{21}|}{s_2} = \frac{1}{2} = 0.5, \quad \frac{|a_{31}|}{s_3} = \frac{2}{2} = 1

Partial pivoting would keep R1R_1 since ∣4∣|4| is largest in column 1, but scaled partial pivoting picks R3R_3 with ratio 11 and swaps R1↔R3R_1 \leftrightarrow R_3. The scale factors move with their rows to become (s3,s2,s1)=(2,2,100)(s_3, s_2, s_1) = (2, 2, 100).

→R1↔R3[20−1111244100−5054]\xrightarrow{R_1 \leftrightarrow R_3} \left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 1 & 1 & 2 & 4 \\ 4 & 100 & -50 & 54 \end{array}\right]m21=12=0.5,m31=42=2m_{21} = \frac{1}{2} = 0.5, \quad m_{31} = \frac{4}{2} = 2→R3−2R1R2−0.5R1[20−11012.53.50100−4852]\xrightarrow[R_3 - 2R_1]{R_2 - 0.5R_1} \left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 1 & 2.5 & 3.5 \\ 0 & 100 & -48 & 52 \end{array}\right]

Compare the remaining rows in column 2 using their original scale factors s2=2s_2 = 2 and s1=100s_1 = 100.

∣a22(1)∣s2=12=0.5,∣a32(1)∣s1=100100=1\frac{|a_{22}^{(1)}|}{s_2} = \frac{1}{2} = 0.5, \quad \frac{|a_{32}^{(1)}|}{s_1} = \frac{100}{100} = 1

Swap R2↔R3R_2 \leftrightarrow R_3.

→R2↔R3[20−110100−4852012.53.5]\xrightarrow{R_2 \leftrightarrow R_3} \left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 100 & -48 & 52 \\ 0 & 1 & 2.5 & 3.5 \end{array}\right]m32=1100=0.01m_{32} = \frac{1}{100} = 0.01→R3−0.01R2[20−110100−4852002.982.98]\xrightarrow{R_3 - 0.01R_2} \left[\begin{array}{ccc|c} 2 & 0 & -1 & 1 \\ 0 & 100 & -48 & 52 \\ 0 & 0 & 2.98 & 2.98 \end{array}\right]
x3=2.982.98=1x_3 = \frac{2.98}{2.98} = 1x2=52−(−48)(1)100=1x_2 = \frac{52 - (-48)(1)}{100} = 1x1=1−(−1)(1)2=1x_1 = \frac{1 - (-1)(1)}{2} = 1x⃗=(1,1,1)T\vec{x} = (1, 1, 1)^T

Example 4

Solve using Gaussian elimination with complete pivoting.

2x1−x2+x3=3x1+x2+4x3=15x1+2x2−2x3=−1\begin{aligned} 2x_1 - x_2 + x_3 &= 3 \\ x_1 + x_2 + 4x_3 &= 15 \\ x_1 + 2x_2 - 2x_3 &= -1 \end{aligned}
Solution Reveal Hide
1 /

The initial variable order is (x1,x2,x3)(x_1, x_2, x_3).

[2−1131141512−2−1]\left[\begin{array}{ccc|c} 2 & -1 & 1 & 3 \\ 1 & 1 & 4 & 15 \\ 1 & 2 & -2 & -1 \end{array}\right]

The largest entry in magnitude across the entire coefficient matrix is ∣a23∣=4|a_{23}| = 4 at row 2, column 3. Swap R1↔R2R_1 \leftrightarrow R_2 and C1↔C3C_1 \leftrightarrow C_3. The variable order becomes (x3,x2,x1)(x_3, x_2, x_1).

→R1↔R2,  C1↔C3[411151−123−221−1]\xrightarrow{R_1 \leftrightarrow R_2,\; C_1 \leftrightarrow C_3} \left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 1 & -1 & 2 & 3 \\ -2 & 2 & 1 & -1 \end{array}\right]m21=14=0.25,m31=−24=−0.5m_{21} = \frac{1}{4} = 0.25, \quad m_{31} = \frac{-2}{4} = -0.5→R3+0.5R1R2−0.25R1[411150−1.251.75−0.7502.51.56.5]\xrightarrow[R_3 + 0.5R_1]{R_2 - 0.25R_1} \left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & -1.25 & 1.75 & -0.75 \\ 0 & 2.5 & 1.5 & 6.5 \end{array}\right]

In the remaining 2×22 \times 2 submatrix, the largest entry in magnitude is ∣2.5∣|2.5| at row 3, column 2. Swap R2↔R3R_2 \leftrightarrow R_3. The variable order stays (x3,x2,x1)(x_3, x_2, x_1).

→R2↔R3[4111502.51.56.50−1.251.75−0.75]\xrightarrow{R_2 \leftrightarrow R_3} \left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & 2.5 & 1.5 & 6.5 \\ 0 & -1.25 & 1.75 & -0.75 \end{array}\right]m32=−1.252.5=−0.5m_{32} = \frac{-1.25}{2.5} = -0.5→R3+0.5R2[4111502.51.56.5002.52.5]\xrightarrow{R_3 + 0.5R_2} \left[\begin{array}{ccc|c} 4 & 1 & 1 & 15 \\ 0 & 2.5 & 1.5 & 6.5 \\ 0 & 0 & 2.5 & 2.5 \end{array}\right]

Back substitution in the permuted order (x3,x2,x1)(x_3, x_2, x_1).

x1=2.52.5=1x_1 = \frac{2.5}{2.5} = 1x2=6.5−1.5(1)2.5=2x_2 = \frac{6.5 - 1.5(1)}{2.5} = 2x3=15−1(2)−1(1)4=3x_3 = \frac{15 - 1(2) - 1(1)}{4} = 3

Restoring the original variable order gives x⃗=(1,2,3)T\vec{x} = (1, 2, 3)^T.

Wolfram Mathematica notebooks

A companion notebook for this note. Open it in Mathematica and evaluate the cells to reproduce the worked example.

The summary notebook defines every function used in this module, with documentation and no examples, as a starting point for your own problems.

Written by November 6, 2026 4 min read
Was this helpful?