M3-T2 — Gaussian Elimination and Row Reduction

Learning objectives

After this lesson, you should be able to:

• Apply the three row operations to reduce a system to upper triangular form and solve it by back substitution.
• Justify why row operations do not change the solutions of a system.
• Explain partial pivoting and the failure it prevents.
• Read the number of solutions from the echelon form, including pivot and free variables.

Introduction and motivation

The determinant formula of the last lesson works for two equations and becomes hopeless for twenty. Elimination scales: it is the algorithm inside every numerical library that solves A x = b, from a thrust mixer to a SLAM back end. Understanding it by hand tells you what the software is doing, why it sometimes fails, and what a failure means physically.

The intuition

Solving a system by hand, you add a multiple of one equation to another to make an unknown disappear. Do that systematically: use the first equation to remove x₁ from all equations below it, use the second to remove x₂ from those below it, and so on. What remains is a staircase (upper triangular) system whose last equation has one unknown. Solve it, substitute into the one above, and climb back up.

Geometric and physical interpretation

Geometric view. Replacing equation 2 by “equation 2 minus a multiple of equation 1” swaps one line (or plane) for another that passes through the same intersection. Each row operation moves the planes without moving the point where they all meet, which is why the solution is unchanged. Physical view. Each step rewrites a physical requirement as a combination of requirements you already have, so the set of states that satisfy everything is exactly the same. After elimination the requirements are ordered so that each introduces only one new unknown.

The mathematics

[A | b]

the augmented matrix: A with the right-hand side b appended as a last column.

pivot

the first non-zero entry used to eliminate the entries below it (or above it, in reduced form).

R_i

row i of the augmented matrix.

The three row operations

• Swap two rows: Ri ↔ Rj.
• Scale a row by a non-zero number: Ri ← c Ri.
• Add a multiple of one row to another: Rj ← Rj − ℓ Ri with the multiplier ℓ = (entry to eliminate)/(pivot).

forward elimination:   [A | b]  →  [U | c]     (U upper triangular)
back substitution:     xn = cn / unn,   then  xi = ( ci − Σj>i uij xj ) / uii

What it means. Forward elimination zeroes everything below the diagonal. Back substitution solves from the last unknown upward, each step needing only values already found.

Partial pivoting

at step k: swap into the pivot position the row (from k down) whose entry in column k is largest in absolute value

What it means. Dividing by a tiny pivot creates huge multipliers that amplify rounding error. Choosing the largest available pivot keeps every multiplier at most 1 in size.

Reading the result

• Pivot in every column and a row for every unknown: unique solution.
• A row of the form 0 0 … 0 | non-zero: inconsistent, no solution.
• A column with no pivot (a free variable) and no inconsistent row: infinitely many solutions, parametrised by the free variables.

Row operations never change the solution set. Eliminate downward, back-substitute upward, and always pivot on the largest available entry.

Step-by-step derivation: row operations preserve solutions, and why pivoting matters

Row operations do not change the solutions. Each operation is multiplication of [A | b] on the left by an invertible matrix E, so the new system (EA) x = Eb has the same solutions:

1. If A x = b, multiply both sides by E: (EA) x = Eb. Every old solution is a new solution.
2. Conversely, if (EA) x = Eb, multiply by E⁻¹ to recover A x = b. Every new solution is an old one.
3. The three operations have inverses of the same kind: swapping back, scaling by 1/c, and adding the multiple back. So each is invertible and the solution set is unchanged.

Why a tiny pivot is dangerous. Consider ε x + y = 1, x + y = 2 with ε = 10⁻²⁰. The exact solution is x ≈ 1, y ≈ 1. Without pivoting, the multiplier is ℓ = 1/ε = 10²⁰:

1. Row 2 becomes (1 − ℓε) x + (1 − ℓ) y = 2 − ℓ, that is 0·x + (1 − 10²⁰) y = 2 − 10²⁰.
2. In floating point 1 − 10²⁰ and 2 − 10²⁰ both round to −10²⁰, so y = 1. The ones were lost.
3. Back substitution: ε x = 1 − y = 1 − 1 = 0, so x = 0. The computed answer is (0, 1) when the true answer is (1, 1): the error is of order 1.
4. With pivoting, rows are swapped first so the pivot is 1 and the multiplier is ε = 10⁻²⁰: row 2 becomes (1 − ε) y = 1 − 2ε, giving y = 1 and then x = 2 − y = 1. Correct.

The lesson: the algorithm can be unstable even when the problem is perfectly fine. Pivoting repairs the algorithm.

A worked example: a 3 × 3 system, step by step

Solve x + y + z = 6, 2y + 5z = −4, 2x + 5y − z = 27. The augmented matrix is the left one in the figure.

1. Column 1. The pivot is the 1 in row 1. Row 2 already has 0 below it. For row 3 the multiplier is 2: R3 ← R3 − 2R1 = (0, 3, −3 | 15).
2. Column 2. The pivot is the 2 in row 2. For row 3 the multiplier is 3/2 = 1.5: R3 ← R3 − 1.5R2 = (0, 3 − 3, −3 − 7.5 | 15 + 6) = (0, 0, −10.5 | 21).
3. Back substitution. −10.5 z = 21 gives z = −2. Then 2y + 5(−2) = −4 gives y = 3. Then x + 3 + (−2) = 6 gives x = 5.
4. Check. 5 + 3 − 2 = 6, 2·3 + 5·(−2) = −4 and 2·5 + 5·3 − (−2) = 27. ✓ The solution is (5, 3, −2).
5. Reading the cases. If instead the last row had come out as (0, 0, 0 | 21), the system would be inconsistent (no solution); as (0, 0, 0 | 0), it would have a free variable and infinitely many solutions.

The pivoting example. In double precision, eliminating [[10⁻²⁰, 1], [1, 1]] without pivoting gives (x, y) = (0, 1); with a row swap it gives (1, 1).

Robotics application

Allocation and constraint solving. The mixer of a UAV, the constraint solve of a legged robot's contact forces and the normal equations of a calibration are all solved by elimination (usually as LU, next lesson). The Navigation and SLAM tracks use the same solves inside optimisers; see nonlinear least squares, where each iteration solves a linear system built from the Jacobian.

Detecting redundancy and conflict. A zero row after elimination reveals a redundant constraint (for example two sensors reporting the same thing), and a row 0 = non-zero reveals a contradiction (two sensors disagreeing in an exactly noise-free model). Fault-detection logic often turns this observation into an automated check.

Pose-graph and bundle-adjustment solvers. Large sparse systems are solved by elimination on a clever ordering; the cost depends on how much fill-in the elimination creates, which is why ordering heuristics are a research topic. The principle is the one in this lesson.

Hand checks. When a solver returns surprising values, repeat the elimination on a tiny version of the problem. Hand elimination of a 3 × 3 is often enough to find a sign error in a model.

Engineering implications and limitations

Practical rules

• Always pivot. Library routines use partial pivoting by default. Never write a production solver without it.
• The cost is about n³/3 operations. Doubling the number of unknowns multiplies the work by about eight, which is why structure (sparsity, symmetry) matters for large problems.
• Judge singularity numerically. A pivot that is tiny compared with the others signals a nearly singular system; the solution will be sensitive. Check the condition number.
• Scale the equations. Rows with very different magnitudes make “largest pivot” a misleading rule. Normalise each row (equilibration) for stability.
• Do not decide solvability from one pivot test. Whether an element is “zero” is a tolerance decision. Rank-revealing methods (SVD or QR with pivoting) are more reliable.

Limits

Elimination is exact in exact arithmetic and backward stable (with pivoting) in floating point, but the answer can still be inaccurate if the problem is ill-conditioned. Stability of the algorithm and conditioning of the problem are separate things; Module 5 returns to this.

Common misconceptions

Engineering takeaways

1. Gaussian elimination uses three row operations (swap, scale, add a multiple) to reach an upper triangular system, then back substitution.
2. Row operations multiply by invertible matrices, so they never change the solution set.
3. Partial pivoting (largest available pivot) is required for accuracy; a tiny pivot can ruin the answer.
4. The echelon form tells you the cases: a pivot in every column (unique), a 0 = non-zero row (none), a pivotless column (infinitely many).
5. Elimination costs about n³/3 operations, which motivates the factorisation of the next lesson.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lectures on elimination and back substitution
• Michigan ROB 101: Computational Linear Algebra: LU factorisation and why we pivot
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapter on solving linear equations; the site did not load when we last checked
• Immersive Linear Algebra: chapter 5, Gaussian elimination, with interactive figures

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Elimination solves one system. If the same matrix appears with many right-hand sides, as it does in control loops and filters, redoing the elimination every time is wasteful. LU decomposition records it once.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T1: Systems of Linear Equations

  Write a set of constraints as A x = b, picture it as lines and planes meeting, and say how many solutions to expect.

• Lab
  M3-L1: Solve a Robot's Constraints

  A mobile base has wheel and speed constraints: solve for the commands, and handle systems with no solution or many.