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.


2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Apr 24, 2020 at 10:41
  • 1
    $\begingroup$ "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. $\endgroup$
    – Sal_99
    Jul 12, 2020 at 11:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – Frentos
    Jul 15, 2020 at 2:48
  • 1
    $\begingroup$ @uditnarayanpandey: Thanks, I've removed the redundant remark between the last two bullet points. $\endgroup$
    – Frentos
    Jul 15, 2020 at 2:57
  • $\begingroup$ @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. $\endgroup$
    – Sal_99
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.