Anybody knows a proof of Uniqueness of the Reduced Echelon Form Theorem?

Question

The book has no proof showing each matrix is row equivalent to one and only one reduced echelon matrix. Does anybody know how to prove this theorem?

"Theorem Uniqueness of the Reduced Echelon Form
Each matrix is row equivalent to one and only one reduced echelon matrix"
Source: Linear Algebra and Its Applications, David, C. Lay.

[EDIT I think the following can be a proof that each echelon matrix is reduced to only one reduced echelon matrix, but how to show a matrix that is not in echelon form is reduced to only one reduced echelon matrix?]

In a $m×n$ matrix in echelon form of a linear system for some positive integers m, n, let the leading entries $(■)$ have any nonzero value, and the starred entries $(☆)$ have any value including zero.

Leading entries $■$s in $R_1$ and $R_2$ in an echelon matrix can become leading 1 in a reduced echelon matrix through dividing them by $■$, and the entry ☆ in $R_1$ above $■$ in $R_2$ can be $0$ by subtracting a multiple of $■$.

So $R_1$ and $R_2$ in a matrix in echelon form becomes as follows:
$\begin{array}{rcl} R_1\space & [■ ☆\cdots ☆☆☆☆]\\ R_2\space & [0 ■\cdots ☆☆☆☆]\end{array} \qquad ~ \begin{array}{rcl} R_1\space & [1 0\cdots ☆☆☆☆]\\R_2 &[0 1\cdots ☆☆☆☆] \end{array}$

For all integers k with $2≤k<m$, $R_k$, $R_{k+1}$ in the echelon matrix can be expressed as
$R_{k}\space$ $[0 \cdots 0 ■☆☆\cdots ☆]$
$R_{k+1}$ $[0 \cdots 0 0 ■☆\cdots ☆]$.

Subtracting a multiple of leading entry of $R_{k+1}$ from $R_k$ can make the entry above leading $■$ in $R_{k+1}$ be zero, and the leading $■$s in $R_k$, $R_{k+1}$ can be 1 through dividing the rows by leading entry $■$s.

So the rows in echelon matrix become the following in reduced $m×n$ echelon matrix:
$\begin{array}{rcl} R_{k}\space & [0 \cdots 0 ■☆☆\cdots ☆]\\ R_{k+1} & [0 \cdots 0 0 ■☆\cdots ☆]\\ \end{array} \qquad \begin{array}{rcl} R_{k} & [0 \cdots 0 1 0 ☆\cdots ☆]\\ R_{k+1} & [0 \cdots 0 0 1 ☆\cdots ☆]\\ \end{array}$

Hence, it's found that leading 1s in reduced echelon form of $m×n$ matrix of a linear system correspond to the locations of the leading non-zero values in a $m×n$ matrix in echelon form of the linear system.

Answer 1

When you perform elementary row operations, then linear relations between columns don't change. More precisely, if $A=[a_1\;a_2\;\dots\;a_n]$ is a matrix (given with its columns $a_i$) and $B$ is obtained by $A$ by performing elementary row operations, if $1\le i_1,i_2,\dots,i_j,p\le n$ are column indices, then $$ b_p=\alpha_1b_{i_1}+\alpha_2b_{i_2}+\dots+\alpha_jb_{i_j} \quad\text{if and only if}\quad a_p=\alpha_1a_{i_1}+\alpha_2a_{i_2}+\dots+\alpha_ja_{i_j} $$ This follows from the fact that performing row operations is the same as multiplying $A$ on the left by invertible matrices. So $B=FA$ for some invertible matrix $F$ and proving the above results is easy.

In particular, a set of columns of $B$ is linearly independent if and only if the corresponding set of columns of $A$ is linearly independent.

If $U=[u_1\;u_2\;\dots\;u_n]$ is a reduced row echelon form for $A$, let $u_{i_1},u_{i_2},\dots,u_{i_j}$ be the pivot columns, with $i_1<i_2<\dots<i_j$.

Note that if $i_j<p<i_{j+1}$, then $u_p$ is a linear combination of $u_{i_1},\dots,u_{i_j}$ and the coefficients of the linear combination are determined by $u_p$: if $$ u_p=\begin{bmatrix}\alpha_1\\\alpha_2\\\vdots\\\alpha_m\end{bmatrix} $$ then $\alpha_i=0$ if $i>i_j$ and $$ u_p=\alpha_1u_{i_1}+\alpha_2u_{i_2}+\dots+\alpha_{i_j}u_{i_j} $$ Therefore $$ a_p=\alpha_1a_{i_1}+\alpha_2a_{i_2}+\dots+\alpha_{i_j}a_{i_j} $$ and this linear combination is unique, because the set of columns $$ \{a_{i_1},a_{i_2},\dots,a_{i_j}\} $$ is linearly independent.

Thus the position of the pivot columns in $U$ is uniquely determined by the columns of $A$ and the coefficients on the non-pivot columns are likewise determined by the linear relations between the columns of $A$.

Answer 2

I just read the previous answer and saw it is the same as this one, my apologies. I think that answer is the best possible one.

But just to justify this answer I cooked up another one for you. Notice that all row equivalent matrices have the same row space, and the rows of the reduced form are a particularly nice basis for that space. Namely they reveal that the row space projects isomorphically onto the coordinate subspace spanned by the pivot variables, and the rows of the reduced form are precisely those vectors that correspond under that isomorphism with the standard basis of the coordinate subspace spanned by the pivot variables. For a matrix of rank r, there may be more than one r dimensional coordinate subspace that the row space projects to isomorp-hically, but the pivot variables span the one of lexicographically minimal sequence of coordinate indices. That proves uniqueness. I.e. to find the rows of the reduced form just project the row space onto the earliest r dimensional coordinate subspace that is an isomorphism, and pull back the standard basis.