Let
\(A\) be an
\(m\times n\) matrix. Using Gauss-Jordan elimination, we can row reduce
\(A\) to matrix
\(U\) in reduced row echelon form. Suppose
\(A\) is also row equivalent to the matrix
\(U'\) in reduced row echelon form. Then
\(U\) and
\(U'\) are row equivalent, since the row equivalence relation is symmetric and transitive (
Remark 2.4.17). Thus it suffices to show that if
\(U\) and
\(U'\) are row equivalent matrices in reduced row echelon form, then
\(U=U'\text{.}\) We do so by induction on
\(n\text{.}\) The base step is trivial, since there is only one
\(m\times 1\) matrix in reduced row echelon form.
For the induction step we assume that any two row equivalent
\(m\times n\) matrices in reduced row echelon form are equal. Suppose by contradiction that
\(U=[u_{ij}]\) and
\(U'=[u'_{ij}]\) are row equivalent
\(m\times (n+1)\) matrices in reduced row echelon form, and that
\(U\ne U'\text{.}\) By
Corollary 2.4.16 there is an invertible matrix
\(Q\) such that
\(QU=U'\text{.}\) The first
\(n\) columns of
\(U\) and
\(U'\) form matrices
\(V\) and
\(V'\text{,}\) respectively, that are in reduced row echelon form, as one easily checks. Furthermore,
\(V\) and
\(V'\) are row equivalent: indeed, using
Theorem 2.1.24 we see that
\(QU=U'\) implies
\(QV=V'\text{.}\) By the induction hypothesis we must have
\(V=V'\text{,}\) and thus
\(U\) and
\(U'\) can only differ in their last column.
We claim that \(U\) and \(U'\) must both have a leading one in the last column. To see why, consider the matrix equation \(U\boldx=\boldzero\text{,}\) where \(\boldx=[x_j]\) is a \((n+1)\times 1 \) column vector. Since \(QU=U'\text{,}\) we have
\begin{align*}
U\boldx=\boldzero \amp\implies QU\boldx=Q\boldzero \\
\amp\implies U'\boldx=\boldzero \amp (U'=QU) \text{,}
\end{align*}
and thus
\begin{equation*}
U\boldx=\boldzero\implies U\boldx-U'\boldx=\boldzero\implies (U-U')\boldx=\boldzero\text{.}
\end{equation*}
Because \(U\) and \(U'\) differ in at most their last column, the first \(n\) columns of \(U-U'\) are zero columns, and thus we have
\begin{equation}
(U-U')\boldx=[x_{n+1}(u_{i(n+1)}-u'_{i(n+1)})]=\boldzero\text{.}\tag{2.17}
\end{equation}
Since
\(U\ne U'\text{,}\) there is some
\(1\leq i\leq m\) such that
\(u_{i(n+1)}\ne u'_{i(n+1)}\text{.}\) Since
\(x_{n+1}(u_{i(n+1)}-u'_{i(n+1)})=0\) by
(2.17), we must have
\(x_{n+1}=0\text{.}\) We have shown that for any
\(\boldx=[x_j]\) satisfying
\(U\boldx=\boldzero\text{,}\) we must have
\(x_{n+1}=0\text{.}\) It follows from
Procedure 1.3.6 that
\(U\) must have a leading in its last column, since otherwise the variable
\(x_{n+1}\) in the system
\(U\boldx=0\) would be free, and could assume any value. To see that
\(U'\) also has a leading one in the last column, we use the same argument, starting with the equation
\(Q^{-1}U'=U\text{.}\)
To summarize, starting with row equivalent matrices
\(U\) and
\(U'\) in reduced row echelon form, and assuming by contradiction that
\(U\ne U'\text{,}\) we conclude that (a) the first
\(n\) columns of
\(U\) and
\(U'\) are equal and form matrices in reduced row echelon form, and (b) the last columns of
\(U\) and
\(U'\) have leading ones. Since
\(U\) and
\(U'\) are in reduced row echelon form, and since the first
\(n\) columns of
\(U\) and
\(U'\) are equal, we see that the leading ones in the last columns of
\(U\) and
\(U'\) must occur in the same row: namely, the first zero row of
\(V=V'\text{.}\) It follows that
\(U=U'\text{,}\) a contradiction.
