1.2 Row reduction and echelon forms

Big idea

Elimination becomes an algorithm here. Instead of stopping when the answer happens to be visible, you drive every matrix to one standard shape and read the answer off mechanically. The shape is the reduced echelon form, and the striking fact is that a matrix has only one of them, no matter which route you take.

That uniqueness is what makes the form worth defining. Any two people who reduce the same matrix correctly end up with the same grid, so the positions of the leading entries are a property of the matrix itself rather than an accident of your arithmetic. Those positions are the pivot positions, and nearly every question in the chapter turns into a question about where the pivots are.

The payoff for solving systems is a clean split of the unknowns. Unknowns with a pivot are determined; unknowns without one can be anything. Writing the determined ones in terms of the free ones is the parametric description of the solution set, which is the standard way to answer “infinitely many” with something concrete.

Decoder

Two forms, one letter apart in name, easy to mix up.

Echelon form asks for three things. Any row of all zeros sits below every nonzero row. The leading entry of a row (its first nonzero entry, reading left to right) sits strictly to the right of the leading entry of the row above. Everything below a leading entry is zero. The picture is a staircase descending to the right.

Reduced echelon form asks for two more. Every leading entry is $1$. Every leading $1$ is the only nonzero entry in its column, so the entries above it are cleared as well as the ones below.

A pivot position is a location in the original matrix that ends up holding a leading $1$ in the reduced echelon form. A pivot column is a column that contains one. Because the reduced form is unique, so are the pivot positions. The word pivot also gets used for the nonzero entry you divide by while reducing, which is the same spot before you scale it.

One caution on vocabulary. Echelon form is not unique: different legal choices give different staircases with the same shape. Reduced echelon form is unique. When a statement says “the” echelon form it is relying on the reduced one.

Definitions and results

Echelon form. Zero rows at the bottom; each leading entry strictly right of the one above; zeros below each leading entry.

Reduced echelon form. Echelon form, plus every leading entry equal to $1$, plus zeros above as well as below each leading $1$.

Uniqueness of the reduced form. Every matrix is row equivalent to exactly one matrix in reduced echelon form. Echelon forms, by contrast, are not unique.

Pivot position and pivot column. A pivot position is an entry of the matrix that holds a leading $1$ in its reduced echelon form. The column containing it is a pivot column. Each row holds at most one pivot, and each column holds at most one, so the number of pivots is at most the smaller of the row count and the column count.

The row reduction algorithm. Work left to right in two phases.

Forward phase: find the leftmost column that is not all zeros, swap a nonzero entry into the top position of the block you are working on, use it to clear every entry below it, then cover that row and repeat on what remains. This reaches an echelon form and shows you the pivot positions.

Backward phase: starting from the rightmost pivot and moving left, scale each pivot row so the pivot is $1$ and clear the entries above it. This reaches the reduced echelon form.

Basic and free variables. Apply the algorithm to the augmented matrix of a system. An unknown whose column is a pivot column is a basic variable. An unknown whose column has no pivot is a free variable.

Parametric description. If the system is consistent, solve each nonzero row for its basic variable and push the free variables to the right-hand side. Every choice of values for the free variables yields exactly one solution, and every solution arises this way. The free variables are the parameters.

Existence and uniqueness, stated with pivots. A system is consistent exactly when the last column of the augmented matrix is not a pivot column, which is the same as saying no row reads $0 = c$ with $c$ nonzero. A consistent system has one solution when there are no free variables, and infinitely many when there is at least one.

Worked examples

Reducing to the unique form

Take the system with augmented matrix

$$ \begin{bmatrix} 2 & 4 & 6 \\ 1 & 3 & 5 \end{bmatrix} $$

where the last column holds the constants. Scale row 1 by $\tfrac{1}{2}$, then subtract row 1 from row 2:

$$ \begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 2 \end{bmatrix} $$

That is an echelon form. For the reduced form, clear above the pivot in column 2 by subtracting $2$ times row 2 from row 1:

$$ \begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \end{bmatrix} $$

Both columns of the coefficient part are pivot columns, so both unknowns are basic and there are no free variables. The solution is $x_1 = -1$, $x_2 = 2$.

Check in the original: $2(-1) + 4(2) = 6$ and $-1 + 3(2) = 5$.

One free variable

Reduce

$$ \begin{bmatrix} 1 & 2 & -1 & 2 \\ 2 & 5 & -1 & 5 \\ 3 & 7 & -2 & 7 \end{bmatrix} $$

Subtract $2$ times row 1 from row 2 and $3$ times row 1 from row 3:

$$ \begin{bmatrix} 1 & 2 & -1 & 2 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{bmatrix} $$

Subtract row 2 from row 3, then subtract $2$ times row 2 from row 1:

$$ \begin{bmatrix} 1 & 0 & -3 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

Pivots sit in columns 1 and 2, so $x_1$ and $x_2$ are basic and $x_3$ is free. The last column is not a pivot column, so the system is consistent. Reading the rows:

$$ x_1 = 3x_3, \quad x_2 = 1 - x_3, \quad x_3 \text{ free} $$

Check with $x_3 = 1$, which gives $(3, 0, 1)$: $3 + 0 - 1 = 2$, $6 + 0 - 1 = 5$, $9 + 0 - 2 = 7$. All three original equations hold.

Two free variables

Reduce the augmented matrix of a system in four unknowns:

$$ \begin{bmatrix} 1 & 2 & -1 & 3 & 5 \\ 2 & 4 & -1 & 8 & 12 \end{bmatrix} $$

Subtract $2$ times row 1 from row 2:

$$ \begin{bmatrix} 1 & 2 & -1 & 3 & 5 \\ 0 & 0 & 1 & 2 & 2 \end{bmatrix} $$

Add row 2 to row 1 to clear above the second pivot:

$$ \begin{bmatrix} 1 & 2 & 0 & 5 & 7 \\ 0 & 0 & 1 & 2 & 2 \end{bmatrix} $$

Pivots sit in columns 1 and 3. So $x_1$ and $x_3$ are basic, and $x_2$ and $x_4$ are free:

$$ x_1 = 7 - 2x_2 - 5x_4, \quad x_3 = 2 - 2x_4, \quad x_2 \text{ and } x_4 \text{ free} $$

Check with $x_2 = 1$ and $x_4 = 1$, which gives $(0, 1, 0, 1)$: $0 + 2 - 0 + 3 = 5$ and $0 + 4 - 0 + 8 = 12$. Both hold.

Notice what changed and what did not. Every matrix here has the same reduced echelon form no matter which legal operations you pick, and the count of free variables is fixed by the pivot pattern rather than by your choices.

Practice

The first drill is the algorithm itself. You reduce a matrix and report its reduced echelon form, or identify the pivot columns.

The second drill starts from a system with free variables and asks for the parametric description: which variables are basic, which are free, and the formula for each basic one.

Videos

The MIT lecture runs elimination on a small system and names the pivots as they appear. Watch how a zero in a pivot spot forces a row swap, and what it means when no swap can fix it.

Quiz

Five items on reducing matrices and describing solution sets.