Gaussian Elimination — Mathematics Knowledge System

Overview

Gaussian elimination is the standard systematic method for solving a system of linear equations Ax = b (or more generally for row-reducing any matrix). It transforms the augmented matrix [A | b] into upper-triangular (row echelon) form using a sequence of elementary row operations — swap two rows, scale a row by a nonzero constant, or add a multiple of one row to another — none of which change the solution set. Once the system is triangular, the last equation involves only one unknown, and back substitution unwinds the rest one variable at a time. Named after Carl Friedrich Gauss (though the technique appears far earlier, in the Chinese mathematical text The Nine Chapters on the Mathematical Art), it is the workhorse behind virtually every numerical linear-algebra routine, including LU decomposition, matrix inversion, and the structural-engineering stiffness method, and runs in O(n³) arithmetic operations for an n×n system.

Intuition

Think of the three equations in a system as three constraints stacked on top of each other. The first equation, as written, tangles all three unknowns together — but you can subtract a suitable multiple of it from the second and third equations to erase the first variable from them, leaving a smaller 2-variable system 'hiding inside' the bottom two rows. Repeat on that smaller system to erase the second variable from the last row, and you are left with one equation in one unknown — trivial to solve. Climbing back up, plugging that value into the row above reveals the next unknown, and so on. Elimination is just this cascading simplification, done with matrix rows instead of by ad hoc substitution.

Formal Definition

Definition

Given the augmented matrix [A | b] for the system Ax = b, elimination produces multipliers mᵢⱼ that zero out entries below each pivot, column by column, until the matrix is upper triangular:

[A \mid b] \;\xrightarrow{\text{row ops}}\; [U \mid c], \quad U \text{ upper triangular}

Forward elimination to row echelon form

m_{ik} = \dfrac{a_{ik}^{(k)}}{a_{kk}^{(k)}}, \qquad R_i \leftarrow R_i - m_{ik} R_k \quad (i > k)

Elimination multiplier and row update at pivot column k

x_n = \dfrac{c_n}{u_{nn}}, \qquad x_i = \dfrac{1}{u_{ii}}\Big(c_i - \sum_{j=i+1}^{n} u_{ij}x_j\Big)

Back substitution

Worked Examples

Write the augmented matrix.
$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right]$
Eliminate x from row 2: multiplier m₂₁ = −3/2 = −1.5, so R₂ ← R₂ − (−1.5)R₁ = R₂ + 1.5R₁.
$R_2 \to (0,\ 0.5,\ 0.5,\ 1)$
Eliminate x from row 3: multiplier m₃₁ = −2/2 = −1, so R₃ ← R₃ − (−1)R₁ = R₃ + R₁.
$R_3 \to (0,\ 2,\ 1,\ 5)$
Eliminate y from the new row 3 using the new row 2: multiplier m₃₂ = 2/0.5 = 4, so R₃ ← R₃ − 4R₂.
$R_3 \to (0,\ 0,\ 1 - 4(0.5),\ 5 - 4(1)) = (0,\ 0,\ -1,\ 1)$
The system is now upper triangular: 2x+y−z=8, 0.5y+0.5z=1, −z=1. Back-substitute from the bottom.
$z = -1$
Substitute z = −1 into 0.5y + 0.5z = 1.
$0.5y + 0.5(-1) = 1 \;\Rightarrow\; 0.5y = 1.5 \;\Rightarrow\; y = 3$
Substitute y = 3, z = −1 into 2x + y − z = 8.
$2x + 3 - (-1) = 8 \;\Rightarrow\; 2x = 4 \;\Rightarrow\; x = 2$

Answer: (x, y, z) = (2, 3, −1).

Practice Problems

Difficulty 3/10

Eliminate x from the system x + y = 4, 2x − y = 2 (i.e., find the resulting single equation in y after one elimination step).

Difficulty 5/10

Solve by Gaussian elimination: x + y + z = 6, 2y + 5z = −4, 2x + 5y − z = 27.

Difficulty 6/10

A structural stiffness analysis reduces a joint's equilibrium equations to Kd = F where K is the 3×3 coefficient matrix and F the load vector, matching the system 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 solved above. Why is Gaussian elimination, rather than Cramer's rule, the standard choice for such systems in practice?

Quiz

Summary

Gaussian elimination uses row operations (row swap, scaling, adding a multiple of one row to another) to reduce [A | b] to upper-triangular form.
Multipliers m_{ik} = a_{ik}/a_{kk} eliminate entries below each pivot column by column, in O(n³) total operations.
Back substitution then solves the triangular system from the last row up to the first, e.g. solving x + y + z = 6, 2y + 5z = −4, 2x + 5y − z = 27 gives (x, y, z) = (5, 3, −2).
It underlies LU decomposition, matrix inversion, and the stiffness method in structural engineering, and is vastly cheaper than Cramer's rule for large systems.

References

WebsiteWikipedia — Gaussian elimination
BookBurden, R. L. & Faires, J. D. Numerical Analysis, 10th ed. Cengage, 2015.