RREF uniqueness and well-defined rank

Proof of the finite real matrix product laws

Let $m,n,p,q$ be positive integers, let $A\in\mathbb R^{m\times n}$, $B\in\mathbb R^{n\times p}$, and $C\in\mathbb R^{p\times q}$. All the following arguments use the row-by-column definition and finite real sums. For any output position $(i,\ell)$,

$$\begin{aligned} ((AB)C)_{i\ell} &=\sum_{k=1}^{p}\left(\sum_{j=1}^{n}a_{ij}b_{jk}\right)c_{k\ell}\\ &=\sum_{j=1}^{n}a_{ij}\left(\sum_{k=1}^{p}b_{jk}c_{k\ell}\right) =(A(BC))_{i\ell}. \end{aligned}$$

The middle equality only reorders two finite sums and uses real distributivity. Both products are $m\times q$, so equality at every position proves associativity. No factor has changed its order.

For $D\in\mathbb R^{n\times p}$, the same definition gives

$$[A(B+D)]_{ik}=\sum_{j=1}^{n}a_{ij}(b_{jk}+d_{jk}) =(AB)_{ik}+(AD)_{ik}.$$

For $E\in\mathbb R^{m\times n}$, it gives

$$[(A+E)B]_{ik}=\sum_{j=1}^{n}(a_{ij}+e_{ij})b_{jk} =(AB)_{ik}+(EB)_{ik}.$$

Thus both distributive laws hold with the displayed matching sizes. For every real scalar $c$,

$$[(cA)B]_{ik}=\sum_j(ca_{ij})b_{jk} =c\sum_j a_{ij}b_{jk} =\sum_j a_{ij}(cb_{jk})=[A(cB)]_{ik},$$

proving $(cA)B=c(AB)=A(cB)$ by entrywise equality. In particular, for $x,y\in\mathbb R^n$ and real $s,t$,

$$[A(sx+ty)]_i=\sum_j a_{ij}(sx_j+ty_j) =s(Ax)_i+t(Ay)_i.$$

This proves the matrix-vector linearity used when comparing solutions of the same linear system. All identities concern compatible finite real matrices; they do not assert commutativity or cancellation of arbitrary matrix factors.

Build the elementary matrix from the identity

Suppose an elementary row operation $\rho$ is meant to act on matrices with $p$ rows. Start with the identity matrix $I_p$, apply the same elementary row operation to $I_p$, and call the result $E_\rho$. All scalars are taken from the underlying field of the matrices; in particular, every nonzero scaling factor $c$ has a reciprocal $1/c$ in that field.

Definition

Elementary row-operation matrix

The elementary row-operation matrix associated with an elementary row operation $\rho$ on $p$-row matrices is the $p \times p$ matrix obtained by applying $\rho$ to $I_p$.

This matrix is also called an elementary matrix. The longer name keeps its connection with the specified row operation visible.

Equivalently,

$$E_\rho = \rho(I_p).$$

The reason this definition is useful is the following theorem.

Theorem

Elementary row operations are left multiplication

Let $A$ be any matrix with $p$ rows. If $\rho$ is one elementary row operation and $\rho(A)$ denotes the result of applying it to $A$, then

$$\rho(A) = E_\rho A.$$

So applying that elementary row operation to $A$ is the same as multiplying $A$ on the left by the elementary row-operation matrix obtained from the same operation on $I_p$.

The multiplication must be on the left. Row operations change rows by mixing rows. Left multiplication forms new rows of $A$ as linear combinations of old rows of $A$. Right multiplication would instead mix columns.

The dimensions make the same point. If $A$ is $p \times n$, then $E_\rho$ is $p \times p$, so $E_\rho A$ is defined and remains $p \times n$. There is no assumption that $A$ is square. By contrast, a column-operation matrix acting on these same $n$ columns would have size $n \times n$ and multiply on the right.

Why left multiplication performs the operation

Proof

Verify the three elementary cases row by row

Write the rows of an arbitrary $p \times n$ matrix $A$ as $a_1,a_2,\ldots,a_p$, and let $e_k^{\mathsf T}$ denote row $k$ of $I_p$. The basic identity

$$e_k^{\mathsf T}A=a_k$$

says that a row of a left multiplier selects the corresponding row of $A$. Now check the three elementary operations.

1. For $R_i\leftrightarrow R_j$, the matrix $E_\rho$ has row $i$ equal to $e_j^{\mathsf T}$, row $j$ equal to $e_i^{\mathsf T}$, and every other row $k$ equal to $e_k^{\mathsf T}$. Thus the rows of $E_\rho A$ are the rows of $A$ with precisely rows $i$ and $j$ exchanged.

2. For $R_i\leftarrow cR_i$, where $c\ne0$, row $i$ of $E_\rho$ is $c e_i^{\mathsf T}$ and all other rows are unchanged. Hence row $i$ of the product is

   $$(c e_i^{\mathsf T})A=c a_i,$$

   while row $k$ remains $a_k$ for $k\ne i$.

3. For $R_j\leftarrow R_j+cR_i$, where $i\ne j$, row $j$ of $E_\rho$ is $e_j^{\mathsf T}+c e_i^{\mathsf T}$ and every other row is unchanged. Therefore the new row $j$ is

   $$(e_j^{\mathsf T}+c e_i^{\mathsf T})A=a_j+c a_i,$$

   exactly as prescribed.

These cases exhaust the elementary row operations, so they prove $E_\rho A=\rho(A)$ for every compatible $A$. The proof does not claim that an arbitrary manipulation of rows has such an elementary matrix; $\rho$ must be one of the three operations just checked.

Acting on an augmented matrix

Suppose $Ax=b$ is represented by the augmented matrix $[A\mid b]$. An elementary row operation must act on the full augmented matrix, not separately on whichever entries happen to be convenient. The multiplication identity is

$$E_\rho[A\mid b]=[E_\rho A\mid E_\rho b].$$

Thus the coefficients and the right-hand side undergo the same combination of rows. A vector $x$ satisfies $Ax=b$ if and only if it satisfies $E_\rho Ax=E_\rho b$: the forward implication follows by multiplying the equation by $E_\rho$, and the reverse implication follows by applying the reverse elementary operation. This is the precise reason the solution set is preserved.

Changing only $A$ while leaving $b$ fixed, or changing only $b$, generally produces a different system. The augmentation bar is therefore a visual separator, not a boundary at which a row operation may stop.

A sequence of elementary row operations becomes one matrix product

The real payoff is not just representing one elementary row operation. A whole sequence of elementary row operations becomes one product of elementary row-operation matrices.

Theorem

A sequence of elementary row operations as a product

Suppose

$$A_1 \xrightarrow{\rho_1} A_2 \xrightarrow{\rho_2} A_3 \xrightarrow{\rho_3} \cdots \xrightarrow{\rho_k} A_{k+1}.$$

Then

$$A_{k+1} = E_{\rho_k}E_{\rho_{k-1}}\cdots E_{\rho_2}E_{\rho_1}A_1.$$

Here every $\rho_j$ is an elementary row operation on matrices with the same number of rows. The product represents the whole sequence, although the product itself need not be a single elementary row-operation matrix.

The order in this formula is important. The first row operation appears closest to $A_1$, because it is applied first:

$$A_2 = E_{\rho_1}A_1, \qquad A_3 = E_{\rho_2}A_2 = E_{\rho_2}E_{\rho_1}A_1.$$

Worked example

Two row operations combined

Let

$$A = \begin{bmatrix} 1 & 0 & 1\\ 0 & 2 & 1\\ 1 & 0 & 0 \end{bmatrix}.$$

Apply

$$\rho_1:\ R_2 \leftarrow R_2 + R_1, \qquad \rho_2:\ R_1 \leftarrow R_1 + 2R_2.$$

The corresponding row-operation matrices are

$$E_{\rho_1} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}, \qquad E_{\rho_2} = \begin{bmatrix} 1 & 2 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}.$$

After both operations, the result is

$$E_{\rho_2}E_{\rho_1}A = \begin{bmatrix} 3&2&0\\ 1&1&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&1\\ 0&2&1\\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 3&4&5\\ 1&2&2\\ 1&0&0 \end{bmatrix}.$$

Instead of multiplying $E_{\rho_2}E_{\rho_1}$ directly, you can also obtain this combined matrix by applying the same two elementary row operations to $I_3$ in the same order. The final numerical matrix also confirms that the second operation uses the already-updated row $2$.

Reverse row operations and inverses

Every elementary row operation has a reverse operation:

• the reverse of $R_j \leftarrow R_j + cR_i$ is $R_j \leftarrow R_j - cR_i$;
• the reverse of $R_i \leftarrow cR_i$, with $c \ne 0$, is $R_i \leftarrow (1/c)R_i$;
• the reverse of a row swap is the same row swap.

This gives a precise matrix statement.

Theorem

Elementary row-operation matrices are invertible

Every elementary row-operation matrix is invertible. Its inverse is the elementary row-operation matrix corresponding to the reverse elementary row operation.

Proof

Why the reverse matrix is a two-sided inverse

Let $E_\rho$ represent an elementary row operation $\rho$, and let $E_{\rho^{-1}}$ represent the reverse elementary operation. For every matrix $X$ with $p$ rows, applying $\rho$ and then reversing it restores $X$. By the left-multiplication theorem,

$$E_{\rho^{-1}}E_\rho X=X.$$

This statement holds for every such $X$; in particular, put $X=I_p$ to obtain $E_{\rho^{-1}}E_\rho=I_p$. Reversing first and then applying $\rho$ similarly gives $E_\rho E_{\rho^{-1}}=I_p$. Hence

$$E_\rho^{-1}=E_{\rho^{-1}}.$$

Concretely, a swap is its own inverse, scaling by $c\ne0$ is undone by scaling by $1/c$, and adding $c$ times row $i$ to row $j$ is undone by adding $-c$ times row $i$ to row $j$.

For example, if

$$E = \begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

performs $R_2 \leftarrow R_2 + 3R_1$, then

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

performs $R_2 \leftarrow R_2 - 3R_1$.

This is the algebraic reason elementary row operations are reversible, and it explains why row reduction is so closely connected to invertible matrices.

Proof

Undo the last operation first

Let $E_1,\ldots,E_k$ encode a chronological chain on matrices with $p$ rows, so its combined multiplier is $J=E_k\cdots E_1$. Each inverse $E_j^{-1}$ represents the reverse of the corresponding elementary operation. To recover the input, the first move must undo $E_k$, because that was the last change made to the rows. The remaining reverse moves undo $E_{k-1},\ldots,E_1$ in that order. Consequently the reverse multiplier is

$$K=E_1^{-1}E_2^{-1}\cdots E_k^{-1}.$$

There are two orders to distinguish: the time order of the reverse operations starts with $E_k^{-1}$, while the written product places that first action nearest the matrix being restored. For three steps, associativity gives

$$KJ=E_1^{-1}E_2^{-1}(E_3^{-1}E_3)E_2E_1 =E_1^{-1}(E_2^{-1}E_2)E_1=I_p.$$

The other product $JK$ cancels adjacent inverse pairs starting with $E_1E_1^{-1}$ and also equals $I_p$. The same successive cancellation works for any finite chain. No factors have been commuted, and the argument does not require the matrix being transformed to be square.

Apply this reading to the earlier two-operation example. Its combined multiplier is $E_{\rho_2}E_{\rho_1}$, so its inverse is $E_{\rho_1}^{-1}E_{\rho_2}^{-1}$. Starting from the final matrix, first subtract twice the current second row from the first, recovering $[1\ 0\ 1]$ as the first row. Then subtract that recovered first row from the second, recovering $[0\ 2\ 1]$. Reversing the chain means restoring the intermediate states, which explains the order without a memorized rule.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

Finite basis existence and extension, without a counting assumption

Let $V$ be a real vector space supplied with a finite spanning list $t_1,\ldots,t_N$. First prove that every independent list $u_1,\ldots,u_k$ has length at most $N$. After $j$ insertions, maintain a spanning list consisting of $u_1,\ldots,u_j$ and $N-j$ surviving old vectors. Expand $u_{j+1}$ in this list. Some coefficient on a surviving old vector is nonzero; otherwise $u_{j+1}$ would be in the span of the earlier $u_i$, contradicting independence. Solve for that old vector and replace it by $u_{j+1}$. The new list spans the same space and keeps every earlier insertion. If $k>N$, after $N$ steps the first $N$ independent vectors already span $V$, contradicting independence of $u_{N+1}$. This proves the bound, including $N=0$.

Every subspace $W$ has a finite basis. Start with the empty independent list. If its current span is not $W$, choose one vector of $W$ outside that span. A relation with nonzero coefficient on the new vector would express it in the old span, so the enlarged list remains independent. The proved bound permits at most $N$ additions; therefore the process stops with an independent spanning list for $W$. If $W=\{0\}$, it stops immediately with the empty basis. Starting instead with any given independent list in $W$ proves that list extends to a basis of $W$. Only a bounded finite selection is used. Finally, if two bases have sizes $p,q$, use each as the finite spanning list in the bound to obtain $p\le q$ and $q\le p$. Thus basis size, called dimension, is well-defined. This supplies the existence, extension and dimension facts used in rank–nullity.

This optional proof note works over the real numbers. The argument also works over any field, because it uses only field arithmetic and invertible row operations. It establishes a structural fact; it does not prescribe a new elimination algorithm.

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

Theorem

Uniqueness of RREF

Let $A$ be any matrix. Suppose $B$ and $C$ are both reduced row-echelon forms. If $B$ is row-equivalent to $A$ and $C$ is row-equivalent to $A$, then

$$B = C.$$

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

Theorem

Equivalent form

If $B$ and $C$ are reduced row-echelon forms of the same size and $B$ is row-equivalent to $C$, then $B=C$.

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$.

Theorem

Preservation of column relations

Suppose

$$c_j=\alpha_1c_{k_1}+\alpha_2c_{k_2}+\cdots+\alpha_nc_{k_n}.$$

Then

$$b_j=\alpha_1b_{k_1}+\alpha_2b_{k_2}+\cdots+\alpha_nb_{k_n}.$$

Conversely, any relation among the corresponding $b$ columns gives the same relation among the corresponding $c$ columns.

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.

More explicitly, distributivity gives

$$G\left(\sum_{i=1}^n\alpha_i c_{k_i}\right) =\sum_{i=1}^n\alpha_i Gc_{k_i}.$$

The coefficients stay the same, even though the column vectors usually change. Applying $G^{-1}$ proves the reverse implication. Consequently, if a column could be expressed using earlier columns on only one side, transporting that expression back would give a contradiction on the other side. This justifies preserving a failure of membership in an earlier span, as well as preserving an equation.

What RREF columns look like

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

$$d_1\lt d_2\lt \cdots\lt 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.

To see why only earlier pivots are needed, inspect a row whose pivot occurs after column $j$: every entry of that row through column $j$ is zero. The zero rows contribute nothing either. Thus a free column has nonzero entries only in rows whose pivots have already appeared. If there are no earlier pivots, the sum is empty and the column is zero. Conversely, at the $k$-th pivot, every earlier column has zero $k$-th entry, whereas $e_k$ has entry $1$ there. No combination of earlier columns can produce this pivot.

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.

Proof

Full proof of RREF uniqueness

Let $P(r)$ be the statement:

If $B$ and $C$ are RREF matrices of the same size, $B$ is row-equivalent to $C$, and $C$ has exactly $r$ pivot columns, then $B=C$.

We prove $P(r)$ for all $r\ge 0$.

Base case. Suppose $C$ has no pivot columns. Then $C$ has no nonzero rows, so $C$ is the zero matrix. Since $B$ is row-equivalent to $C$, we can write $B=GC$ for some invertible matrix $G$. Hence $B=G0=0$, so $B=C$.

Induction step. Assume $P(s)$ is true. Let $C$ have $s+1$ pivot columns, located at

$$d_1\lt d_2\lt \cdots\lt d_s\lt d_{s+1}.$$

Split both matrices at the last pivot column:

$$B=[B^\flat\ B^\natural], \qquad C=[C^\flat\ C^\natural],$$

where $B^\flat$ and $C^\flat$ contain all columns strictly to the left of column $d_{s+1}$.

Deleting a suffix of columns from an RREF leaves an RREF: rows whose pivots are retained keep their leading $1$s and cleared pivot columns; rows whose pivots are deleted become zero rows, and they already occur below the retained pivot rows. This reasoning applies separately to both left blocks, without assuming that their pivot counts agree.

The same elementary row-operation chain taking $C$ to $B$ also acts on their left blocks: restricting columns commutes with each row operation. In particular, $B^\flat=GC^\flat$, with the same invertible $p\times p$ multiplier as before. Hence the left blocks are row-equivalent, and $C^\flat$ has exactly $s$ pivots. When the prefix has positive width, the induction hypothesis applies and gives

$$B^\flat=C^\flat.$$

If $d_{s+1}=1$, there are no columns in either prefix and necessarily $s=0$. Their equality is then vacuous; we need not apply the induction hypothesis to a matrix with no columns. If $s=0$ but $d_1\gt1$, both prefixes are ordinary zero matrices by the base case. Thus leading zero columns and the empty prefix are both covered.

So the two matrices already agree in every column before $d_{s+1}$.

Now compare column $d_{s+1}$. In $C$, this pivot column is not a linear combination of the columns to its left. Row-equivalence preserves this non-combination statement, so the $d_{s+1}$-th column of $B$ is not a linear combination of the columns of $B$ to its left.

Since the left blocks are already equal, the first $s$ pivot columns of $B$ are exactly

$$e_1,e_2,\ldots,e_s.$$

If this column had zero entries below row $s$, it would equal the combination of $e_1,\ldots,e_s$ given by its first $s$ entries, contradicting the preceding non-combination statement. Therefore it has a nonzero entry below row $s$.

Take the first such row. Its earlier entries are all zero because the prefixes agree. Its pivot is therefore in column $d_{s+1}$. This row must be row $s+1$: an intervening row would either be zero above a nonzero row, or have a pivot farther right above a pivot farther left. Both violate echelon order. Finally, the reduced conditions normalize this pivot to $1$ and clear every other entry in its column. Thus

$$b_{d_{s+1}}=e_{s+1}=c_{d_{s+1}}.$$

It remains to compare columns to the right of $d_{s+1}$. Every such column of $C$ is free, since $d_{s+1}$ was its last pivot. Let $\ell\gt d_{s+1}$. Its entries in the pivot rows give the unique expression

$$c_\ell = \gamma_{1\ell}c_{d_1} +\cdots+ \gamma_{s\ell}c_{d_s} +\gamma_{s+1,\ell}c_{d_{s+1}}.$$

Row-equivalence preserves this relation, so

$$b_\ell = \gamma_{1\ell}b_{d_1} +\cdots+ \gamma_{s\ell}b_{d_s} +\gamma_{s+1,\ell}b_{d_{s+1}}.$$

But the pivot columns of $B$ and $C$ have now been shown to be the same. Therefore $b_\ell=c_\ell$.

Every column of $B$ equals the corresponding column of $C$, so $B=C$. This proves $P(s+1)$, and the induction is complete.

Proof X-Ray

What each induction step is allowed to know

The induction parameter is the pivot count of $C$ alone. We do not assume that $B$ has the same count; proving equality will establish that fact. Restricting to the prefix creates a smaller case while preserving row-equivalence. Equality of that prefix fixes the first $s$ pivot rows. The next column is forced by an invariant non-combination statement and the RREF conditions. Finally, every remaining column of $C$ is already a combination of its now-matched pivots, so transporting those exact coefficients leaves no room for an additional pivot or a different free entry in $B$.

A concrete miniature version

Worked example

Forced columns in a two-pivot RREF

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.

Worked example

Leading zero columns do not interrupt the proof

Consider

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

Suppose $B$ is an RREF row-equivalent to $C$. Since $c_1=0$, transport gives $b_1=0$. Column $c_2$ is nonzero, so invertibility prevents $b_2$ from vanishing; as the first nonzero RREF column, it must be $e_1$. Next, $c_3=-2c_2$ forces $b_3=-2e_1$.

Column $c_4=e_2$ cannot lie in the span of the first three columns, because they have second entry zero. Therefore $b_4$ is the next pivot column and equals $e_2$. Finally,

$$c_5=3c_2+4c_4\quad\Longrightarrow\quad b_5=3b_2+4b_4=c_5.$$

This proves $B=C$ without choosing an elimination path. For the induction split at the last pivot, the left block has width $3$ and exactly one pivot; the original leading zero column remains in that prefix. Both matrices have rank $2$ once the uniqueness theorem has justified that definition.

Worked example

A singular multiplier can lose a column direction

Take

$$C=I_2,\qquad G=\begin{bmatrix}1&0\\0&0\end{bmatrix},\qquad B=GC=\begin{bmatrix}1&0\\0&0\end{bmatrix}.$$

Both $B$ and $C$ are RREF matrices, but they are different. This does not contradict uniqueness: $G$ is singular, and $B=GC$ alone does not establish row-equivalence. The columns of $C$ satisfy no nontrivial relation, whereas $b_2=0$ is a new relation with coefficient vector $(0,1)$. Any invertible matrix taking $C$ to $B$ would transport that relation backward to $c_2=0$, which is false. Hence no such invertible multiplier exists.

The forward transport of any existing relation still works for this singular $G$ by distributivity. What fails is the converse and, with it, preservation of non-combination. The corrected rule requires an invertible left multiplier. The pivot counts here are $2$ and $1$, illustrating exactly the information that a non-reversible operation can destroy.

Rank is now well defined

Definition

Rank

For any matrix $A$, the rank of $A$, written $\operatorname{rank}(A)$, is the number of pivot columns in the unique RREF row-equivalent to $A$.

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

Common mistake

Do not claim ordinary REF is unique

The uniqueness theorem is about RREF, not arbitrary row-echelon form. Before normalizing pivots and clearing entries above them, many different REF outputs can occur.

Common mistake

Do not define rank from a chosen reduction path

It is acceptable to compute rank by row reduction, but the definition is not "whatever pivot count I happened to get." The uniqueness theorem guarantees that all legal RREF paths give the same pivot count.

Common mistake

Do not forget the role of column relations

The proof does not say that row operations preserve the actual column space. They generally do not. The key preserved information is the pattern of linear relations among corresponding columns.

Quick checks

Checkpoint

If two RREF matrices are row-equivalent to the same matrix, what can you conclude?

Use the uniqueness theorem, not another row reduction.

Solution · Answer

They must be equal. A row-equivalence class contains exactly one RREF.

Checkpoint

How does RREF uniqueness justify the definition of rank used here?

Mention the number of pivot columns.

Solution · Answer

Rank is defined as the number of pivot columns in the RREF. If the RREF were not unique, different reduction paths might give different pivot counts. Since the RREF is unique, the pivot count is independent of the path.

Checkpoint

If the unique RREF row-equivalent to $A$ has pivot columns $1$, $3$, and $5$, what is $\operatorname{rank}(A)$?

Count the pivot columns, not the free columns.

Solution · Answer

The rank is $3$, because there are three pivot columns.

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.

Solution · Guided solution for exercise 1

The pivot columns are columns $1$ and $3$:

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

The free columns are columns $2$ and $4$. From their entries in the pivot rows,

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

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$.

Solution · Guided solution for exercise 2

Since $c_1$ is the first pivot column, the first column of $B$ must be $b_1=e_1=c_1$. The relation $c_2=4c_1$ is preserved, so $b_2=4b_1=4c_1=c_2$.

The third column of $C$ is not a combination of the columns to its left, so the third column of $B$ is forced to be the next pivot column:

$$b_3=e_2=c_3.$$

Finally, $c_4=2c_1-3c_3$ is preserved, so

$$b_4=2b_1-3b_3=2c_1-3c_3=c_4.$$

Thus every column agrees, and $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}.$$

Solution · Guided solution for exercise 3

They are row-equivalent, and both have a row-echelon shape, but $E_2$ is not reduced row-echelon form because its leading entry is $2$, not $1$.

RREF uniqueness says that the reduced row-echelon representative is unique. It does not say that every intermediate REF representative is unique.

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.