5.2 RREF uniqueness and well-defined rank

Gaussian elimination feels algorithmic, but one subtle theoretical question is still open:

If two people row-reduce the same matrix by different legal routes, why must they obtain the same RREF?

Existence says that some RREF can be reached. Uniqueness says that there is only one possible RREF. This second statement is what allows us to speak about the RREF of a matrix and to define rank without referring to a particular computation.

Before you start

This appendix uses three earlier facts.

1. Row-equivalence can be written as multiplication on the left by an invertible matrix.
2. Row-equivalence preserves linear relations among corresponding columns.
3. In an RREF matrix, pivot columns and free columns have a very rigid shape.

The proof is longer than a row-reduction calculation, but the idea is simple: compare the columns of two possible RREFs from left to right. The pivot columns are forced first, and then every free column is forced by its linear relation with the pivot columns.

The theorem

Since row-equivalence is transitive, it is enough to prove the following slightly more direct statement.

Notice the word reduced. Ordinary row-echelon form is not unique. A matrix can have many different REF outputs, but only one RREF output.

Column relations survive row-equivalence

Write the columns of two row-equivalent $p \times q$ matrices as

$$B=[b_1\ b_2\ \cdots\ b_q], \qquad C=[c_1\ c_2\ \cdots\ c_q].$$

If $B$ is row-equivalent to $C$, then there is an invertible $p \times p$ matrix $G$ such that

$$B = GC.$$

Thus $b_j = Gc_j$ for every column index j.

The converse uses $G^{-1}$. This is why invertibility of $G$ is essential: we can move column relations forward and backward between row-equivalent matrices.

What RREF columns look like

Let $C$ be an RREF matrix. Suppose its pivot columns are

$$d_1<d_2<\cdots<d_r.$$

Then the pivot columns have the standard-vector shape:

$$c_{d_1}=e_1,\quad c_{d_2}=e_2,\quad \ldots,\quad c_{d_r}=e_r,$$

where the vectors are written inside the ambient column length of $C$.

Free columns are controlled by the pivot columns to their left. If $c_j$ is a free column and the pivot columns strictly to its left are $c_{d_1},\ldots,c_{d_h}$, then

$$c_j=\gamma_{1j}c_{d_1}+\gamma_{2j}c_{d_2}+\cdots+\gamma_{hj}c_{d_h}.$$

The coefficients are not mysterious: they are exactly the entries of $c_j$ in the pivot rows.

Finally, each pivot column is genuinely new at the moment it appears:

$$c_{d_k} \quad\text{is not a linear combination of columns strictly to its left.}$$

These three observations are the engine of the uniqueness proof.

Proof by induction on the number of pivots

To avoid circularity, read "the rank of an RREF" in this proof simply as "the number of pivot columns in that RREF." Only after uniqueness is proved will we define the rank of an arbitrary matrix.

A concrete miniature version

The proof above may feel abstract because it tracks arbitrary columns. Here is the same logic in a small RREF matrix:

$$C= \begin{bmatrix} 1 & 2 & 0 & -1\\ 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

The pivot columns are columns 1 and 3. They are

$$c_1=e_1, \qquad c_3=e_2.$$

The free columns satisfy

$$c_2=2c_1, \qquad c_4=-c_1+3c_3.$$

Now suppose $B$ is another RREF matrix row-equivalent to $C$. The first pivot column cannot disappear, so $b_1=e_1$. Since the relation $c_2=2c_1$ is preserved, $b_2=2b_1=2e_1$, so the second column is forced.

The third column is not a combination of columns 1 and 2, so it must become the next pivot column of $B$: $b_3=e_2$. Finally, the relation $c_4=-c_1+3c_3$ is preserved, so

$$b_4=-b_1+3b_3=-e_1+3e_2=c_4.$$

Thus $B=C$. The entire matrix is forced column by column.

Rank is now well defined

This definition is legitimate because uniqueness has already been proved. If different row-reduction paths could end at different RREFs, then the number of pivot columns could depend on the route taken. The theorem rules out that possibility.

Rank is therefore not a memory of how you computed. It is an invariant of the matrix.

For computations, the workflow is now safe:

1. reduce $A$ to RREF;
2. mark the pivot columns of that RREF;
3. count them to get $\operatorname{rank}(A)$.

If the question asks for a basis of the column space, use the pivot positions to return to the corresponding columns of the original matrix. If the question only asks for rank, the RREF itself is enough. This distinction matters because row operations preserve column relations, but they do not usually preserve the actual column space.

Common mistakes

Quick checks

Exercises

Exercise 1

Let

$$C= \begin{bmatrix} 1&4&0&2\\ 0&0&1&-3\\ 0&0&0&0 \end{bmatrix}.$$

Identify the pivot columns and express each free column as a linear combination of the pivot columns.

Exercise 2

Suppose $B$ is an RREF matrix row-equivalent to the matrix $C$ in Exercise 1. Use column relations to explain why $B=C$.

Exercise 3

Explain why the following two row-equivalent REF matrices do not contradict RREF uniqueness:

$$E_1= \begin{bmatrix} 1&2\\ 0&0 \end{bmatrix}, \qquad E_2= \begin{bmatrix} 2&4\\ 0&0 \end{bmatrix}.$$

Related notes

Read this after 2.5 Existence of row-echelon forms and 5.1 Invertible matrices. It also supports 6.6 Column space, row space, and rank.