Understanding a proof of RREF uniqueness

Question

Base Case $(n = 1)$: Suppose $A$ has only one column. If $A$ is the all zero matrix, it is row equivalent only to itself and is in reduced row echelon form. Every nonzero matrix with one column has a nonzero entry, and all such matrices have reduced row echelon form the column vector $(1, 0,\ldots, 0)$ and no other row echelon form.

Induction Step: Suppose now that $n > 1$, that the result holds for all $m \times n$ matrices and let $A \in M_{m,n+1}$. For any $M \in M_{m,n+1}$, we let $M' \in M_{m, n}$ be obtained by removing the last column of $M$. Let $B, C$ be rref of $A$. Then $B', C'$ are in rref and row-equivalent to $A'$.

By induction $B' = C'.$ In other words $B, C$ are equal except possibly in the last column. Suppose $B \neq C: \exists i (1 \le i \le m)$ s.t. $b_{i,n+1} \neq c_{i,n+1}$. Let $x = (x_1,\ldots, x_{n + 1})$ be a vector with $Bx = 0$. Then $Cx = 0$ implying $(B - C)x = 0.$ Since $B - C$ is zero except in its last column, performing the multiplication of the $i$th row of $B - C$ by $x$ is $(b_{i, n+1} - c_{i, n+ 1})x_{n + 1} = 0$. Since $b_{i, n+1} \neq c_{i, n+ 1}$, we have that $x_{n + 1} = 0.$ Thus $x_{n + 1}$ is not a free variable for either $B$ or $C$, so in each of these matrices the last column must contain a leading entry of $1$ and have all the other entries $0$. In both $B, C$ the $1$ must lie in the first zero row of $B'$ and $C'.$ Thus $B = C.$

I am having difficulty with the part in bold. Suppose the last column is all $0$'s. Then $x_{n + 1}$ can be anything $\neq 0$ which is not allowed. Is that why the last columns of $B,C$ must contain a leading entry of $1$ and have all the other entries $0$? What about rref matrices whose last columns are made up of constants that are neither $0$, nor $1$ like the one below?

$ \begin{matrix} 1 & 0 & 0 & -5 \\ 0 & 1 & 0 & 6\\ 0 & 0 & 1 & 3\\ \end{matrix} $

Please, explain what the quoted sentence says.

Answer 1

Paraphrasing up to the point just before the tricky sentence:

• We're considering any two matrices, $B$ and $C$, that are RREFs of $A$.
• By the induction hypothesis, $B$ and $C$ are identical except maybe in the last column.
• Suppose $B\ne C$.
• Then $B-C$ is a matrix that's all zeroes except in column $n+1$ where at least one entry, for some row $i$, is not zero.
• Let $\mathbf{x}=(x_1,x_2,\cdots,x_{n+1})$ be a vector that gives $B\mathbf{x}=\mathbf{0}$ (There is always at least one such vector, $\mathbf{0}$). Then $C\mathbf{x}=\mathbf{0}$ (since the row operations that give RREFs conserve solutions), so $(B-C)\mathbf{x}=\mathbf{0}$.

You proposed: Suppose the last column is all $0$'s.

That might be true for $B$ or for $C$ (at the moment), but not for $B-C$ because at this point, by supposition, $B$ and $C$ are different.

• Expanded, $(B-C)\mathbf{x}=\mathbf{0}$ looks like $\begin{bmatrix}0&\cdots&0&d_1\\0&\cdots&0&d_2\\\vdots&\ddots&\vdots&\vdots\\0&\cdots&0&d_m\end{bmatrix}\begin{bmatrix}x_1\\\vdots\\x_{n+1}\end{bmatrix}=\begin{bmatrix}d_1x_{n+1}\\d_2x_{n+1}\\\vdots\\d_mx_{n+1}\end{bmatrix}=\begin{bmatrix}0\\0\\\vdots\\0\end{bmatrix}$
• Since we supposed $B\ne C$ with a difference in the last column on some row $i$, i.e. $d_i \ne 0$, we have $d_ix_{n+1} = 0, d_i\ne0$, so $x_{n+1}$ is forced to be $0$.

Now the tricky sentence:

• Thus $x_{n+1}$ is not a free variable for either $B$ or $C$,

This is just restating the fact that $x_{n+1}$ has been forced to $0$.

• so in each of these matrices the last column must contain a leading entry of $1$ and have all the other entries $0$

... because that's what columns in RREF matrices corresponding to non-free variables look like.

The rest of the argument just says (by rules of RREF) we don't have any choice about where to put the $1$ in the final column, so $B=C$ after all.

Answer 2

The last column of $B-C$ cannot be zero, otherwise the two matrices would have been equal to begin with, since $B'=C'$ by the induction hypothesis.

I prefer a different argument, based on how the RREF is obtained.

Consider $A=\begin{bmatrix}a_1 & a_2 & \dots & a_n\end{bmatrix}$ and $B=\begin{bmatrix}b_1 & b_2 & \dots & b_n\end{bmatrix}$ ($a_i$ and $b_i$ are the columns of $A$ and $B$).

Suppose there exists an invertible matrix $F$ such that $FA=B$.

Lemma. If $i_1<i_2<\dots<i_k$, then $a_i=\alpha_1a_{i_1}+\dots+\alpha_ka_{i_k}$ if and only if $b_i=\alpha_1b_{i_1}+\dots+\alpha_kb_{i_k}$.

The proof is easy, by taking into account that $b_i=Fa_i$. In particular, a set of columns of $B$ is linearly independent if and only if the corresponding set of columns (those with the same indexes) is linearly independent.

Now recall that the RREF $U$ of a matrix $A$ can be written as $U=FA$, for an invertible matrix $A$, because any elementary row operation can be performed via multiplication by an invertible matrix.

Call dominant a column of $U$ if it contains a leading one, nondominant otherwise. It is easy to see that a nondominant column can be written as a linear combination of the dominant columns with lower index. Moreover, the coefficients of the linear combinations are precisely the coefficients in the nondominant column. To make an example, suppose $$ U=\begin{bmatrix} 0 & 1 & 0 & -2 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 3 & 4 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ \end{bmatrix} $$ The dominant columns are number $2$, $3$, $6$ and $7$; the fourth column $u_4$ can be written as $u_4=-2u_2+3u_3$; similarly, the eighth column $u_8=3u_2+2u_3-u_6+2u_7$.

Therefore, if $A$ is the matrix we got $U$ as RREF of, we also have that $\{a_2,a_3,a_6,a_7\}$ is a maximal linearly independent set of columns of $A$ (because of the lemma) and so every other column of $A$ can be written in a unique way as a linear combination of these columns.

Moreover, the set of dominant columns in a RREF is determined by $A$ and not by the elimination process we use.

In the example, the first column of $A$ must be zero, columns $a_2$ and $a_3$ are linearly independent (because the corresponding columns in one RREF are), $a_4$ is a linear combination of $a_2$ and $a_3$. The coefficients we use for writing $a_4=\alpha a_2+\beta a_3$ must be $\alpha=-2$ and $\beta=3$, because $u_4=-2u_2+3u_3$.

It follows that the RREF is unique, because its coefficients are uniquely determined by $A$.

The example is used only to illustrate the method. It's not difficult to make a formal proof, after defining what a RREF is.