Gaussian Elimination

The Algorithm at a Glance

Gaussian elimination is the systematic procedure for solving linear systems. Starting from the augmented matrix [A|b], it applies a sequence of simple row operations to transform the matrix into an upper-triangular form — called Row Echelon Form — from which the solution can be recovered by back substitution. An extended version of the algorithm continues further, producing Reduced Row Echelon Form, where the solution can be read off immediately with no substitution required.

The algorithm is not just a manual technique. It is the foundation for nearly every numerical linear algebra library — from MATLAB's backslash operator to NumPy's linalg.solve. Understanding it gives you insight into why solvers behave as they do, and what can go wrong when a matrix is nearly singular.

Elementary Row Operations

The key insight behind Gaussian elimination is that certain operations on the rows of an augmented matrix do not change its solution set. These are the three elementary row operations:

Swap

Rᵢ ↔ Rⱼ

Exchange two rows. Reordering equations never changes which x satisfies them all.

Scale

cRᵢ → Rᵢ

Multiply a row by a nonzero scalar c. Scaling an equation preserves its solution set.

Add Multiple

Rᵢ + cRⱼ → Rᵢ

Add c times one row to another. This is the core elimination step — used to zero out entries below (and above) a pivot.

Elementary Row Operations

R_i \leftrightarrow R_j, \quad cR_i \to R_i \; (c \neq 0), \quad R_i + cR_j \to R_i

All three operations are reversible, so they preserve the solution set of the system. The most powerful is the third: adding a multiple of one row to another is what creates the zeros that simplify the system.

The Augmented Matrix as Starting Point

Before elimination begins, write the system as its augmented matrix [A|b]. The vertical bar separates the coefficient matrix A on the left from the right-hand side vector b on the right. Every row operation applied to [A|b] simultaneously transforms both halves, maintaining the equivalence between the matrix and the original system of equations.

Why work with the matrix?

Writing equations out in full — with x₁, x₂, x₃ symbols — is tedious and error-prone. The augmented matrix strips away the variable names and exposes only the numbers that matter. Row operations become clean, mechanical steps rather than algebraic manipulations, which is exactly why computers use this representation.

Row Echelon Form

The goal of the forward elimination phase is to reach Row Echelon Form (REF). A matrix is in REF if it satisfies three conditions:

All zero rows (if any) are at the bottom.
The first nonzero entry in each nonzero row — called the leading entry or pivot — lies strictly to the right of the pivot in the row above.
All entries below a pivot in the same column are zero.

This creates a staircase pattern descending from top-left to bottom-right. The positions of the pivots are called pivot positions, and the columns containing them are pivot columns. Columns without pivots correspond to free variables — the unknowns that can take any value when the system has infinitely many solutions.

Row Echelon Form — Example

\begin{pmatrix}2 & 1 & -1 \\ 0 & 3 & 2 \\ 0 & 0 & 5\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}8\\11\\-1\end{pmatrix}

The pivots are 2, 3, and 5 — each lies to the right of and below the previous pivot. All entries below each pivot are zero. This upper-triangular structure allows back substitution to proceed from the last equation upward.

Reduced Row Echelon Form

REF is sufficient for back substitution, but continuing the elimination process — now working upward to zero out entries above each pivot, and scaling each pivot to 1 — yields Reduced Row Echelon Form (RREF). RREF has two additional requirements beyond REF:

Every pivot equals exactly 1 (achieved by scaling the pivot row).
Every entry above a pivot is also zero (achieved by adding multiples of pivot rows to the rows above).

In RREF, the solution can be read directly: each pivot variable is expressed solely in terms of free variables (if any exist), with no substitution required. For a system with a unique solution, the RREF of the augmented matrix has the form [I|x*], where I is the identity and x* is the solution vector.

Reduced Row Echelon Form — Solution

\left[\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}\right]

Each pivot column contains exactly one 1 and zeros everywhere else. The augmented column on the right gives the unique solution directly: x₁ = 2, x₂ = 3, x₃ = −1. No back substitution needed.

Back Substitution

If you stop at REF rather than continuing to RREF, you recover the solution via back substitution. The process is straightforward: the last nonzero row of the REF gives the value of the last pivot variable directly. Substitute that value into the second-to-last equation to find the next pivot variable. Continue upward until all variables are determined.

For a 3×3 system in REF with pivots a, d, f, the steps are:

Read x₃ from the last row: fx₃ = r₃, so x₃ = r₃/f.
Substitute x₃ into the second row to find x₂.
Substitute x₂ and x₃ into the first row to find x₁.

Back substitution has O(n²) cost for an n×n system — cheaper than the O(n³) forward elimination phase — making the total cost of solving Ax = b dominated by the elimination step.

Step-by-Step Worked Example

Let us solve the system whose REF and RREF appear in the equations above:

2x₁ + x₂ − x₃ = 8
−3x₁ − x₂ + 2x₃ = −11
−2x₁ + x₂ + 2x₃ = −3

Step 1 — Write the augmented matrix

Arrange the coefficients and right-hand sides into [A|b]:

Starting Matrix

[ 2, 1, −1 | 8 ] / [ −3, −1, 2 | −11 ] / [ −2, 1, 2 | −3 ]

Step 2 — Eliminate below the first pivot (pivot = 2, column 1)

Use R₁ to zero out the entries below it in column 1. Apply R₂ ← R₂ + (3/2)R₁ and R₃ ← R₃ + R₁. After these operations the first column has zeros below the pivot and the matrix has an upper-triangular start.

Step 3 — Eliminate below the second pivot (column 2)

The second pivot is the entry now sitting in row 2, column 2. Use it to zero out the entry in row 3, column 2 via R₃ ← R₃ − (appropriate multiple)·R₂. After this step the matrix is in REF, matching the upper-triangular form shown in the equation block above.

Step 4 — Back substitution

From the last row: 5x₃ = −5, so x₃ = −1. Substituting into the second row: 3x₂ + 2(−1) = 11, so x₂ = 13/3 — wait, let us use exact values. With the pivots as shown (2, 3, 5) and right-hand sides (8, 11, −1 after elimination), back substitution gives x₃ = −1, then x₂ = 3, then x₁ = 2. This matches the RREF solution [2, 3, −1]ᵀ.

Sanity Check

Always verify by substituting x = [2, 3, −1]ᵀ back into the original equations: 2(2) + 3 − (−1) = 8 ✓, −3(2) − 3 + 2(−1) = −11 ✓, −2(2) + 3 + 2(−1) = −3 ✓.

Partial Pivoting for Numerical Stability

In exact arithmetic, Gaussian elimination always works (as long as the system has a solution). In floating-point arithmetic, problems arise when a pivot is zero or very small: dividing by a tiny number amplifies rounding errors, causing the computed solution to be wildly inaccurate even though no exact-arithmetic mistake was made.

Partial pivoting addresses this by always choosing the largest-magnitude entry in the current column as the pivot, swapping rows if necessary before eliminating. This keeps all multipliers (c = entry/pivot) bounded in magnitude by 1, which prevents error amplification during the elimination phase.

In practice, virtually all numerical solvers use partial pivoting as a default. The trade-off is a small bookkeeping overhead (tracking row swaps via a permutation vector), but the gain in stability is essential for reliable computation.

No Pivoting

Use pivot as-is

Simple but fragile. A zero or near-zero pivot causes division by zero or catastrophic cancellation.

Partial Pivoting

Swap rows within column

Choose the largest entry in the current column. Keeps multipliers ≤ 1. Default in LAPACK, NumPy, MATLAB.

Full Pivoting

Swap rows and columns

Maximally stable but expensive. Rarely needed in practice; used for rank-revealing factorizations.

Key Takeaways

Gaussian elimination uses three elementary row operations — swap, scale, and add multiples — to transform an augmented matrix [A|b] without changing its solution set. The forward elimination phase produces Row Echelon Form, a staircase pattern with zeros below each pivot. Continuing upward yields Reduced Row Echelon Form, where the solution is read off directly. For large systems, back substitution on the REF is computationally equivalent. Partial pivoting — choosing the largest available pivot — is essential for numerical stability in floating-point arithmetic. Next, we explore what the shape of the RREF reveals about the types of solutions a system can have.