Math Core

Elimination works, but to handle any system, with any number of equations and unknowns, you need a precise target shape and an algorithm that always reaches it. This lesson defines echelon form and reduced echelon form, introduces pivots, and shows how the reduced form lets you read off the entire solution set, including systems with infinitely many solutions.

Echelon forms

In a matrix, a nonzero row is a row with at least one nonzero entry, and its leading entry is its leftmost nonzero entry.

Definition

Echelon form and reduced echelon form

A matrix is in (row) echelon form if

all nonzero rows are above any rows of all zeros,
each leading entry is in a column to the right of the leading entry of the row above it, and
all entries in a column below a leading entry are zero.

It is in reduced row echelon form (RREF) if, in addition,

every leading entry is $1$ , and
each leading $1$ is the only nonzero entry in its column.

Echelon form looks like a staircase descending to the right. For example, with $\ast$ standing for any number and $\blacksquare$ for any nonzero number,

\begin{bmatrix} \blacksquare & \ast & \ast & \ast \\ 0 & \blacksquare & \ast & \ast \\ 0 & 0 & 0 & \blacksquare \end{bmatrix} \qquad \begin{bmatrix} 1 & 0 & \ast & 0 \\ 0 & 1 & \ast & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

show an echelon form and the corresponding reduced echelon form.

A matrix can be row reduced to many different echelon forms (you can always scale a row, for instance). But the reduced form is special.

Uniqueness of the reduced echelon form

Each matrix is row equivalent to exactly one matrix in reduced row echelon form.

Because every echelon form of $A$ has its leading entries in the same positions as the RREF of $A$ , those positions are a property of $A$ itself.

Definition

Pivot position and pivot column

A pivot position in a matrix $A$ is a location that holds a leading $1$ in the reduced echelon form of $A$ . A pivot column is a column of $A$ that contains a pivot position. A pivot is a nonzero number in a pivot position, used during row reduction to create zeros.

The row reduction algorithm

Reaching the RREF takes two phases.

Forward phase (produces an echelon form):

Start with the leftmost nonzero column. This is a pivot column; its top position is a pivot position.
If necessary, interchange rows so that a nonzero entry sits in the pivot position.
Use replacement operations to create zeros in every position below the pivot.
Cover the row containing the pivot (and all rows above it) and repeat steps 1 to 3 on the submatrix that remains.

Backward phase (produces the RREF):

Starting with the rightmost pivot and working up and to the left, scale each pivot row to make the pivot $1$ , then create zeros above it with replacements.

Doing the zeros above the pivots only at the end, from right to left, saves work: each backward step touches a column that is already mostly zeros.

Worked example: Reducing to RREF

Row reduce the augmented matrix of $x_1 + 2x_2 - x_3 = 3$ , $\;2x_1 + 5x_2 + x_3 = 10$ , $\;3x_1 + 7x_2 + x_3 = 15$ , and solve.

Forward phase. The pivot in column 1 is the top-left $1$ . Use $R_2 - 2R_1$ and $R_3 - 3R_1$ , then $R_3 - R_2$ :

\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 10 \\ 3 & 7 & 1 & 15 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 4 \\ 0 & 1 & 4 & 6 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & 1 & 2 \end{array}\right].

Backward phase. Clear column 3 with $R_2 - 3R_3$ and $R_1 + R_3$ , then column 2 with $R_1 - 2R_2$ :

\left[\begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 0 & 0 & 9 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 2 \end{array}\right].

The RREF says directly $x_1 = 9$ , $x_2 = -2$ , $x_3 = 2$ .

Basic variables, free variables and parametric solutions

When the RREF of an augmented matrix is consistent but not every variable column has a pivot, the system has infinitely many solutions. Variables whose columns are pivot columns are basic variables; the others are free variables. Each nonzero row of the RREF expresses one basic variable in terms of the free ones, and the free variables may take any values.

Worked example: A parametric description

Solve the system whose augmented matrix is $\left[\begin{array}{cccc|c} 1 & 2 & 0 & 1 & 5 \\ 2 & 4 & 1 & 4 & 13 \\ 1 & 2 & 1 & 3 & 8 \end{array}\right]$ .

$R_2 - 2R_1$ and $R_3 - R_1$ both produce $[\,0 \;\; 0 \;\; 1 \;\; 2 \mid 3\,]$ , and then $R_3 - R_2$ gives a zero row:

\left[\begin{array}{cccc|c} 1 & 2 & 0 & 1 & 5 \\ 0 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].

This is already the RREF. The pivot columns are 1 and 3, so $x_1$ and $x_3$ are basic and $x_2$ , $x_4$ are free. Reading the rows:

\begin{cases} x_1 = 5 - 2x_2 - x_4 \\ x_2 \text{ is free} \\ x_3 = 3 - 2x_4 \\ x_4 \text{ is free.} \end{cases}

Every choice of $x_2$ and $x_4$ gives a solution. For instance, $x_2 = 1$ and $x_4 = 2$ give $x_1 = 1$ , $x_3 = -1$ . You can confirm $(1, 1, -1, 2)$ in the original second equation: $2 + 4 - 1 + 8 = 13$ .

Existence and uniqueness

The RREF, or even any echelon form, answers the two basic questions about a system at a glance.

Existence and uniqueness theorem

A linear system is consistent if and only if the rightmost column of its augmented matrix is not a pivot column, that is, an echelon form has no row of the form $[\,0 \;\; \cdots \;\; 0 \mid b\,]$ with $b \ne 0$ .

If the system is consistent, it has

a unique solution when there are no free variables (every variable column is a pivot column), and
infinitely many solutions when there is at least one free variable.

Worked example: Deciding from an echelon form

Is the system with augmented matrix $\left[\begin{array}{cccc|c} 1 & 3 & -2 & 0 & 4 \\ 2 & 6 & -1 & 3 & 11 \\ -1 & -3 & 5 & 3 & 1 \end{array}\right]$ consistent?

$R_2 - 2R_1$ gives $[\,0 \;\; 0 \;\; 3 \;\; 3 \mid 3\,]$ and $R_3 + R_1$ gives $[\,0 \;\; 0 \;\; 3 \;\; 3 \mid 5\,]$ . Then $R_3 - R_2$ gives $[\,0 \;\; 0 \;\; 0 \;\; 0 \mid 2\,]$ . The last column is a pivot column, so the system is inconsistent, even though it has more unknowns than equations.

Common mistake

"More unknowns than equations" does not guarantee infinitely many solutions; the system can still be inconsistent, as the last example shows. What it does guarantee is that a consistent system of that shape has a free variable, because there are more variable columns than there can be pivots.

Tip

You only need an echelon form, not the full RREF, to decide consistency and to count free variables. Save the backward phase for when you need the actual solution.

Practice

Practice 1

Which matrix is in reduced row echelon form?

Practice 2

How many pivot positions does $A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 7 \\ 3 & 6 & 10 \end{bmatrix}$ have?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

Row reduce to solve $x_1 + x_2 + x_3 = 4$ , $\;2x_1 + 3x_2 + x_3 = 4$ , $\;x_1 - x_2 + 2x_3 = 9$ . Give $(x_1, x_2, x_3)$ .

Enter a point like (2, -3)

Practice 4

The augmented matrix of a system has been reduced to $\left[\begin{array}{cccc|c} 1 & 0 & -2 & 0 & 3 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 4 \end{array}\right]$ . How many free variables does the system have?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

For the system in the previous problem, if $x_3 = 2$ , what is $x_1$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

An echelon form of the augmented matrix of a system is $\left[\begin{array}{ccc|c} 2 & -1 & 4 & 1 \\ 0 & 3 & 5 & -2 \\ 0 & 0 & 0 & 6 \end{array}\right]$ . Which describes the system?

Practice 7

Row reduce the augmented matrix $\left[\begin{array}{cccc|c} 1 & -2 & 1 & 0 & 3 \\ 2 & -4 & 3 & 1 & 8 \\ 0 & 0 & 1 & 1 & 2 \end{array}\right]$ and describe the solutions in terms of the free variables. If $x_2 = 1$ and $x_4 = 3$ , what is $x_1$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.