Understanding a proof of RREF uniqueness

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.

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.

• i think that from the fact that $x_{n+1}=0$ instead of saying that $B$ and $C$ would have last column not entirely $0$ conclusion should be that the last column must have a leading entry of 1. Apr 24, 2020 at 10:41
• "because columns in RREF matrices are either all zeroes or have exactly one 1, and we just ruled out all zeroes." But as far as I know, this is not always true. Jul 12, 2020 at 11:14
• @Sal_99: You're correct - the remark I'd written following the last bullet point was nonsense! I've corrected it, although am not very happy with my remark: I've just mimicked the cited proof in assuming connections between RREF matrices and free variables in homogeneous solution sets that have presumably been proven elsewhere. established. Jul 15, 2020 at 2:48
• @uditnarayanpandey: Thanks, I've removed the redundant remark between the last two bullet points. Jul 15, 2020 at 2:57
• @frentos, I guess the cited proof is making use of the fact that a variable whose column does have a leading 1 in the RREF can act as a free parameter, assuming the system is consistent( we have a homogeneous system so we know ours is ). This, as far as I've seen, comes from how the RREF is defined. Jul 16, 2020 at 8:12

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.