A zero where you needed to divide
By now you can run Gaussian elimination by hand: pick the first diagonal entry, the pivot, and use it to wipe out everything below it in that column, then move to the next column and repeat. The earlier guides turned that process into a clean A = L U factorization, and you learned to finish a solve with forward and back substitution. Everything was tidy — as long as every pivot you reached for happened to be nonzero.
But nothing stops a pivot from being zero. Try to eliminate the first column of the matrix with rows (0, 1) and (1, 1): the very first pivot is 0, and the elimination step asks you to divide by it. The matrix is perfectly fine — it is invertible, its rows are independent, the system A x = b has a unique answer — yet the algorithm walks straight into a division by zero on step one. The breakdown is the method's, not the problem's. Swap the two rows and the obstruction vanishes instantly.
A = [ 0 1 ] pivot a_11 = 0 -> divide-by-zero on step 1
[ 1 1 ]
swap rows:
A'= [ 1 1 ] pivot a_11 = 1 -> elimination proceeds happily
[ 0 1 ]The quiet danger: tiny pivots, not just zero ones
A literal zero is the easy case — your program crashes loudly and you know to fix it. The treacherous case is a pivot that is merely small. Dividing by a tiny number produces a huge multiplier, and that multiplier scales up every entry it touches. In exact arithmetic this is harmless: the large numbers cancel back down later. But you are not in exact arithmetic. Each large intermediate value carries its own rounding error, and when the cancellation finally comes, the true digits have already been swamped — a catastrophic cancellation hiding inside an otherwise correct-looking elimination.
Here is the classic two-by-two that exposes it. Solve the system with matrix rows (1e-20, 1) and (1, 1) and right-hand side (1, 2). The exact answer is close to x = (1, 1). If you use the tiny 1e-20 as your pivot, the multiplier is 1e20; the second equation becomes 1 - 1e20 times the first, and in double precision the original '1's are rounded away entirely. You get x roughly (0, 1) — a confidently wrong answer, with no error message. Swap the rows so the pivot is 1 instead of 1e-20, redo the same arithmetic, and the answer comes out right.
Partial pivoting: the cheap fix that works
The remedy is almost embarrassingly simple. At each step, before you eliminate a column, look down that column from the diagonal onward, find the entry with the largest absolute value, and swap its row up into the pivot position. Then eliminate as usual. This is partial pivoting, and it does two jobs at once: it can never pick a zero pivot when a nonzero one exists below, and it guarantees the chosen pivot is at least as big as everything beneath it, so every multiplier has absolute value at most 1. Bounded multipliers mean rounding errors are no longer amplified out of control.
- At step k, scan column k from row k downward and find the row p whose entry has the largest absolute value.
- Swap row p with row k, so the largest available entry now sits on the diagonal as the pivot.
- Compute the multipliers (entry below the pivot divided by the pivot) — every one now has absolute value at most 1.
- Eliminate the column as usual, record the swap, and move on to step k+1.
The bookkeeping is trivial: store the row swaps in a permutation P, and the factorization quietly upgrades from A = L U to P A = L U. Nothing else about the solve changes — you apply P to the right-hand side b first, then run the same forward and back substitution as before. The cost is essentially free: finding the largest entry in a column is O(n) work per step, dwarfed by the O(n^3) of elimination itself. You pay almost nothing and you buy stability.
Growth factors and the limits of the guarantee
What does partial pivoting actually promise? The clean way to measure danger is the growth factor: the largest entry that ever appears during elimination, divided by the largest entry in the original matrix. If nothing grows, errors stay small; if the growth factor explodes, you are back in the tiny-pivot disaster, just disguised. The backward error of Gaussian elimination is, up to modest constants, proportional to this growth factor times the unit roundoff. Keep growth bounded and you have a backward stable solver — one whose computed answer is the exact answer to a matrix only a roundoff-sized nudge away from yours.
Here is the honest caveat, and it matters. Partial pivoting bounds the multipliers, but it does not bound the growth factor in theory — there are hand-crafted matrices where growth reaches 2^(n-1), an exponential blow-up that would wreck accuracy. So why does everyone trust it? Because in more than half a century of real computation, that worst case essentially never appears; on the matrices people actually solve, growth stays around modest small numbers. Partial pivoting is therefore stable in practice but not provably stable in the strict worst-case sense. That gap between theorem and experience is one of the famous open puzzles of the field, and an honest course names it rather than papering over it.
Putting it together: what pivoting really bought you
Step back and see the shape of the lesson. Pivoting did not make the algorithm more accurate in the abstract — it made it stable, which is a different and more modest promise. Recall the master rule from the conditioning rung: forward error <= condition number times backward error. Pivoting only attacks the backward-error half, the part the algorithm owns. It drives the backward error down near the unit roundoff so that elimination earns its backward-stable badge. It cannot touch the condition number, which belongs to the matrix.
So the unavoidable honesty: a perfectly pivoted, backward-stable solve will still hand you a poor answer if the matrix is ill-conditioned. If the matrix condition number is about 1e8, you should expect to lose roughly 8 of your ~16 double-precision digits no matter how careful the pivoting — the problem is eating that budget before the algorithm even starts. Pivoting guarantees you are not adding your own avoidable damage on top of that; it does not and cannot rescue an intrinsically sensitive problem. Stability is the most an algorithm can sensibly deliver, and pivoting is how Gaussian elimination delivers it.
One last reassurance for a worry you might be carrying: does swapping rows around mess up the factor-once-solve-many trick? Not at all. The permutation P is computed once during the factorization and stored alongside L and U, so all the savings of reusing the factors for many right-hand sides survive untouched. With P A = L U in hand, you are ready for the next guide, where a special class of matrices — the symmetric positive-definite ones — turns out to need no pivoting at all, and rewards you with a factorization that is twice as fast.