Solving linear systems — Gaussian elimination with partial pivoting: Visual walkthrough

Step 1 — What is a system of equations, as a picture?

WHAT. A linear system is a set of equations where each unknown appears by itself, multiplied by a plain number (no squares, no products of unknowns). We write two of them:

coefficient of x_{1} 2 x_{1} + coefficient of x_{2} 1 x_{2} = right-hand side b_{1} 8

WHY care about the picture. Each equation with two unknowns is a straight line in the plane. Solving the system means finding the single point $(x_{1}, x_{2})$ that lies on both lines at once — where they cross.

PICTURE. Two lines, one blue, one orange; the green dot where they meet is the solution $x$ . That crossing point is the only thing we are hunting for.

Figure — Solving linear systems — Gaussian elimination with partial pivoting

Step 2 — The one move that never changes the answer

WHAT. We are allowed exactly three moves on rows, called elementary row operations: (1) swap two rows, (2) scale a row by a nonzero number, (3) add a multiple of one row to another. The star of the show is move (3):

Row_{i} \leftarrow Row_{i} - m \cdot Row_{k} .

Read it aloud: "the new row $i$ is the old row $i$ minus $m$ copies of row $k$ ." Here $m$ is just some number we get to choose.

WHY it's legal. Each row is a line. Move (3) tilts line $i$ but keeps it passing through the same crossing point, because at the solution both equations already hold, so any combination of them still holds there.

PICTURE. The orange line rotates as we change $m$ , but it pivots around the green solution dot — the intersection never moves. That invariance is the entire licence for what follows.

Step 3 — Choosing $m$ so a number becomes zero

WHAT. We want to erase the first unknown $x_{1}$ from the second equation — i.e. make the bottom-left number become $0$ . Using the naming rule, the pivot (top-left) entry is $a_{11}$ (row 1, column 1) and the one we want to kill is $a_{21}$ (row 2, column 1). After the move, the new bottom-left entry is:

what we want gone a_{21} - m \cdot the pivot a_{11} .

Set that to zero and solve for $m$ :

a_{21} - m a_{11} = 0 ⟹ m = \frac{a _{21}}{a _{11}} .

WHY divide. The only value of $m$ that cancels $a_{21}$ exactly is "how many pivots fit into $a_{21}$ " — that's a division. We call this $m$ the multiplier.

PICTURE. A vertical bar of height $a_{21}$ next to a bar of height $a_{11}$ ; the fraction $m$ is the scaling factor that makes $m \cdot a_{11}$ line up exactly with $a_{21}$ , so their difference is flush zero.

Step 4 — Why the pivot must not be tiny (the whole reason for pivoting)

WHAT. Look again at $m = a_{21} / a_{11}$ . The pivot $a_{11}$ sits in the denominator. If $a_{11}$ is a tiny number like $0.0003$ , then $m$ becomes enormous.

WHY that's dangerous. A huge $m$ multiplies every entry of the pivot row before subtracting. Your calculator only keeps a fixed number of digits (see Round-off Error in Floating Point), so a huge multiplier magnifies the little rounding smudges into large errors — the answer rots. This is the story of the parent note's cautionary $0.0003$ example.

PICTURE. Two curves of $m$ against the pivot size: as the pivot shrinks toward zero, $m$ shoots up a vertical wall. The red danger zone is the tiny-pivot region we must avoid.

Step 5 — The swap, in a picture

WHAT. In the system $[2 - 3 1 - 1 8 - 11]$ column 1 has $∣2∣$ and $∣ - 3∣$ . The bigger magnitude is $∣ - 3∣ = 3$ , sitting in row 2. So here the winning row is $p = 2$ : partial pivoting says swap row $k = 1$ and row $p = 2$ so the strong pivot moves up top.

$[- 3 2 - 1 1 - 11 8] .$

WHY the whole row. A row is one complete equation. If you swap only part of it, you've mixed two different equations — garbage. Bar included, always.

PICTURE. Two horizontal row-blocks trading places along a curved arrow; the strong pivot $- 3$ (green) rises to the diagonal, the weak $2$ (gray) drops down to be eliminated next.

Step 6 — Eliminate: watch the zero appear

WHAT. With pivot $a_{11} = - 3$ and target $a_{21} = 2$ , the multiplier is $m_{21} = \frac{2}{- 3} = - \frac{2}{3} \approx - 0.667.$

Now update row 2 = row 2 $- m_{21} \cdot$ row 1, every column (exact fractions first, decimal after):

a_{21} a_{22} b_{2} : 2 - (- \frac{2}{3}) (- 3) = 0 (the target zero), : 1 - (- \frac{2}{3}) (- 1) = \frac{1}{3} \approx 0.333, : 8 - (- \frac{2}{3}) (- 11) = \frac{2}{3} \approx 0.667.

$[- 3 0 - 1 \frac{1}{3} - 11 \frac{2}{3}] .$

WHY it works. By construction $m_{21}$ was chosen to make the first entry vanish; the other entries just come along for the ride.

PICTURE. The bottom row before and after: the leading number melts to $0$ (red → gray), and the row becomes an equation in $x_{2}$ alone. That is the staircase forming.

Step 7 — Climb back up (back-substitution)

WHAT. The bottom equation now reads $\frac{1}{3} x_{2} = \frac{2}{3}$ , which has one unknown. Solve it, then rise to the row above and plug the known value in.

x_{2} = \frac{2/3}{1/3} = 2, x_{1} = \frac{b _{1} - a _{12} x _{2}}{a _{11}} = \frac{- 11 - ( - 1 ) ( 2 )}{- 3} = 3.

Here $a_{12} = - 1$ (row 1, column 2) is the coefficient of the already-known $x_{2}$ in the top row, so the bracket $b_{1} - a_{12} x_{2}$ is a pure number before we divide by the pivot.

WHY bottom-up. Only the last row is a one-unknown equation. Solve it first, then each higher row has exactly one new unknown left. Going top-down leaves unknowns trapped in the bracket.

PICTURE. A literal staircase: the bottom step is solved ( $x_{2} = 2$ ), an upward arrow carries that value into the top step, which then yields $x_{1} = 3$ . Check: top equation $- 3 (3) - 1 (2) = - 11$ . ✓

Step 8 — The degenerate case: when the column is all zeros

WHAT. Suppose at some step every candidate entry in column $k$ (rows $k$ down to $n$ ) is $0$ . Then there is nothing to swap up: the largest magnitude available is $0$ itself, so the pivot is unavoidably $0$ . The matrix $A$ is then singular — see Determinants and Condition Number and Numerical Stability.

WHY it splits into two pictures. A zero pivot does not always mean "no answer". Look at what the offending row says after elimination. It has all-zero coefficients on the left, so it reads $0 = c_{i}$ for some number $c_{i}$ . Two very different things can happen:

Coincident lines (infinitely many solutions): the row became $0 = 0$ . It is a true-but-empty statement carrying no new information. The two equations were the same line. The unknown that lost its pivot becomes a free variable — you may set it to any value $t$ , and the other unknowns follow. The answer is a whole line of points, written e.g. $x_{1} = 5 - t, x_{2} = t$ .
Inconsistent (no solution): the row became $0 = (nonzero)$ , e.g. $0 = 4$ . That is a flat lie — no numbers make it true. The lines are parallel but apart and never cross.

HOW to detect it. After forward elimination, scan for any row whose left part is all zeros: if its $c_{i} = 0$ it signals a free variable (coincident); if its $c_{i} \neq = 0$ it signals inconsistency (no solution).

PICTURE. Left panel: two coincident lines lying exactly on top of each other — every point is a solution, the free variable slides along them. Right panel: two parallel lines apart — no crossing, the " $0 =$ nonzero" contradiction.

The one-picture summary

WHAT. One figure compressing the entire journey: start with a full square block $[A ∣ b]$ ; partial pivoting pulls the biggest entry to the diagonal (green); elimination paints the below-diagonal region to zeros (gray triangle), turning $A$ into the triangular $U$ and $b$ into $c$ ; back-substitution climbs the staircase from the bottom to reveal $x$ . This is exactly the machinery behind LU Decomposition and the twin routines in Back-substitution and Forward-substitution.

Recall Feynman: the whole walkthrough in plain words

Picture a stack of number-rows, each one really an equation. Two equations are two lines on paper, and the answer is where they cross. First trick: I'm allowed to subtract one row from another as many times as I like — this tilts a line but keeps it going through the crossing point, so the answer never budges. I use that to erase the first variable from the lower rows: I subtract just the right amount, and the exact amount is "the number I want gone divided by the number on the diagonal." But dividing by a tiny diagonal number makes a giant multiplier, and a giant multiplier smears my calculator's few digits into big errors and wrecks the answer — so before dividing I look down the column, grab the biggest number, and swap its whole row up to the top. Biggest pivot means the multiplier is never larger than one, so nothing explodes. Repeat column by column until the block is a triangle of numbers with zeros in the lower-left — that triangle is $U$ , and the right-hand side it dragged along is $c$ . Now the bottom equation has only one unknown — solve it — then step up one row, plug in what I just found, solve the next, and keep climbing. If ever a whole column below the diagonal is all zeros, there's no pivot to grab: if the leftover row says $0 = 0$ the two lines are the same and one variable is free (a whole line of answers); if it says $0 =$ some nonzero number, the lines are parallel and there is no answer at all. That's Gaussian elimination with partial pivoting, start to finish.

Recall

After forward elimination, what shape is the matrix, and what do we call it? ::: Upper-triangular — zeros everywhere below the diagonal; we name that triangular block $U$ and its transformed right-hand side $c$ . Why must the pivot be the largest-magnitude entry in the column? ::: A tiny pivot makes a huge multiplier that amplifies round-off error; the biggest pivot keeps every $∣ m_{ik} ∣ \leq 1$ . In Step 6, what multiplier zeroed the entry $2$ under pivot $- 3$ ? ::: $m_{21} = 2/ (- 3) = - \frac{2}{3} \approx - 0.667$ (the decimal is rounded). What solution did the $2 \times 2$ walkthrough give? ::: $x_{1} = 3, x_{2} = 2$ . A zero pivot with leftover row $0 = 0$ means what? ::: Coincident equations — a free variable and infinitely many solutions (a whole line). A zero pivot with leftover row $0 =$ nonzero means what? ::: An inconsistent system — parallel lines, no solution.