[Math] Understanding a proof of RREF uniqueness

linear algebra

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.

Best Answer

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.

Related Question