Row Reduction and Echelon Forms

Row reduction is simply the elimination you already know from algebra, done on the rows of the augmented matrix instead of on the written-out equations, until the matrix is as simple as it can get. That's the name: you work on rows, and you reduce the matrix to a simpler shape. It's good for solving any system at all, no matter how many equations and unknowns, and it's exactly what computers do. The target shape above looks cryptic, but it's just three kinds of entries: the $1$s (the pivots, one per row, each further right than the one above), the $0$s (entries we've cleared out on purpose) and the $*$s (numbers that come out to whatever they come out to). Read it as equations and the first row pins down $x_1$ (in terms of $x_3$), the second pins down $x_2$, and the bottom row says $0 = 0$. A few new words, but it's just tidy elimination; bear with it.

Echelon form is the staircase shape (échelon is French for a rung of a ladder). It means three things:

• nonzero rows sit above any rows of all zeros;
• each row's leading entry (its first nonzero number) is to the right of the leading entry in the row above;
• everything below a leading entry is zero.

Reduced echelon form goes one step further: every leading entry is $1$, with zeros above it too, so each pivot sits alone in its column.

Pivots are the positions of the leading entries. Columns with pivots correspond to basic variables; columns without a pivot belong to free variables, which can take any value. Think about why that makes sense. A pivot in a column means some row says "this variable equals (stuff)", so that variable gets decided. A column with no pivot never gets its own equation, so nothing pins it down: you choose its value, and the basic variables adjust to match.

Reading the answer:

• A row $[0\;0\;\cdots\;0 \mid b]$ with $b \ne 0$ means $0 = b$: inconsistent, no solution.
• Otherwise consistent: unique if there are no free variables, infinitely many if there are.

Notice these are the same three cases from the last lesson: lines that never meet, lines that cross once, and lines that lie on top of each other.

A common mistake. It's tempting to think a row of all zeros, $[0\;0\;\cdots\;0 \mid 0]$, means there's no solution, because a row of nothing looks like something went wrong. It isn't: it says $0 = 0$, which is always true. It just means one of the equations was redundant. Only a nonzero number on the right of an otherwise all-zero row signals trouble.

The algorithm. Work left to right: create a pivot, then clear everything below it. When you reach the bottom you're in echelon form. Then sweep back upward, clearing above each pivot, to get the reduced form. There's an animation further down that shows why none of these steps moves the solution.

Gaussian elimination is the workhorse inside every numerical linear algebra library, solving systems with millions of unknowns in engineering simulations.