🪜Row Reduction & Gaussian Elimination

Millwright Orin clears a column the way a miller clears a sluice: one small move at a time, always working downstream, and never disturbing what is already settled. There are exactly three row operations, and every reduction in this kingdom is a sequence of them.

Swap two rows. R1 <-> R2 Multiply a row by a number that is not zero. R2 -> 3R2 Add a multiple of one row to another row. R3 -> R3 - 2R1

Two things about that list matter more than the list itself.

First, each operation touches one row. In R3 -> R3 - 2R1, row 3 changes and row 1 does not: row 1 is only being read, the way you read a recipe without eating it. Copy every other row down unchanged, every time.

Second, every one of the three is reversible, and that is the whole reason they are allowed. Swap back, multiply by the reciprocal, add the multiple back on. If a matrix stands for a system of equations, a reversible move cannot gain or lose a single solution — so the tidy matrix at the end has exactly the same solutions as the messy one at the start.

A matrix of coefficients with the right-hand sides carried along beside it is an augmented matrix, and the bar is just where the equals sign used to be:

2x + 3y = 8 [[2, 3 | 8], x - y = 1 [1, -1 | 1]]

Gaussian elimination works downwards, one column at a time. Pick the first entry of the first column that is not zero — the pivot — and use its row to make every entry below it zero.

To clear an entry, you need a multiplier. If the pivot is p and the entry below it is e, the operation is

R(below) -> R(below) - m R(pivot), with m = e / p

because that is exactly the m for which e - mp comes out as 0. Read it as "the entry being cleared, divided by the pivot", in that order. Turning the fraction over is the usual slip, and it is easy to catch: a multiplier of 2 should visibly cancel an entry that is twice the pivot.

Work the columns left to right. Once the first column is clear below the pivot, move to the second column, take the pivot from the row below the one you just used, and clear underneath it. The result is echelon form: a staircase of leading entries stepping to the right, with zeros beneath it.

[[2, 1, -1], [[2, 1, -1], [4, 5, 3], -> [0, 3, 5], [6, 3, 0]] [0, 0, 3]]

The rows already settled at the top are never touched again while you work downwards. That is what keeps the staircase a staircase.

Echelon form is enough to solve a system by working backwards up the rows. Going one step further gives a matrix whose answer can simply be read off. A matrix is in reduced row echelon form when all four of these hold:

• ◆every leading entry — the first entry of a row that is not zero — is 1;
• ◆each column holding a leading 1 has zeros everywhere else;
• ◆the leading 1s move to the right as you go down the rows;
• ◆any rows of all zeros sit at the bottom.

Getting there from echelon form takes two more kinds of move. Divide each pivot row by its own leading entry to turn it into a 1, then use each leading 1 to clear the entries above it as well as below.

[[2, 4 | 10], [[1, 2 | 5], [[1, 0 | 1], [0, 1 | 2]] -> [0, 1 | 2]] -> [0, 1 | 2]]

The last matrix says x = 1 and y = 2, with no back-substitution left to do at all.

When a matrix is not reduced, it is worth naming which of the four conditions it breaks, because each one names its own missing step: a leading entry that is not 1 needs a division, a pivot column with something else in it needs one more subtraction, a leading 1 too far left needs a swap, and a zero row too high needs a swap as well.

A pivot is a leading 1 in the reduced form, and each pivot owns a column to itself. A column without one is a free column. Counting them is how you learn what the solution set looks like before writing a single value down.

[[1, 0 | 3], two pivots, no free column among the unknowns: [0, 1 | 5]] exactly one solution, x = 3 and y = 5

[[1, 2 | 7], one pivot, one free column: [0, 0 | 0]] a whole line of solutions

[[1, 2 | 0], the last column has taken a pivot of its own, [0, 0 | 1]] and the bottom row says 0 = 1: no solution at all

That third case is worth staring at. A pivot in the augmented column is the system telling you that the equations disagree; no arithmetic slip has happened, and there is nothing left to solve.

Two habits make row reduction much less painful. Work left to right and never go back to a column you have already cleared, or you will undo it. And check as you go: if the numbers turn into awkward fractions in a problem whose answer should be whole, the mistake is usually one operation back, in a multiplier that was turned over or a sign that was added where it should have been taken away.