Uniqueness of Reduced Echelon Form

$\newenvironment {prompt}{}{} \newcommand {\Sec }[2]{\section {#1}} \newcommand {\trademark }[0]{{R\!\!\!\!\!\bigcirc }} \newcommand {\EXER }[0]{\section *{Exercises}} \newcommand {\CEXER }[0]{} \newcommand {\TEXER }[0]{} \newcommand {\R }[0]{\mbox {$\Bbb {R}$}} \newcommand {\C }[0]{\mbox {$\Bbb {C}$}} \newcommand {\Z }[0]{\mbox {$\Bbb {Z}$}} \newcommand {\N }[0]{\mbox {$\Bbb {N}$}} \newcommand {\D }[0]{\mbox {{\bf D}}} \newcommand {\setmin }[0]{\;\mbox {--}\;} \newcommand {\Matlab }[0]{{M\small {AT\-LAB}} } \newcommand {\Matlabp }[0]{{M\small {AT\-LAB}}} \newcommand {\computer }[0]{\Matlab Instructions} \newcommand {\half }[0]{\mbox {$\frac {1}{2}$}} \newcommand {\compose }[0]{\raisebox {.15ex}{\mbox {{\scriptsize $\circ $}}}} \newcommand {\AND }[0]{\quad \mbox {and}\quad } \newcommand {\vect }[2]{\left (\begin {array}{c} #1_1 \\ \vdots \\ #1_{#2}\end {array}\right )} \newcommand {\mattwo }[4]{\left (\begin {array}{rr} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\mattwoc }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\vectwo }[2]{\left (\begin {array}{r} #1 \\ #2\end {array}\right )} \newcommand {\vectwoc }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\inv }[0]{^{-1}} \newcommand {\CC }[0]{{\cal C}} \newcommand {\CCone }[0]{\CC ^1} \newcommand {\Span }[0]{{\rm span}} \newcommand {\rank }[0]{{\rm rank}} \newcommand {\trace }[0]{{\rm tr}} \newcommand {\RE }[0]{{\rm Re}} \newcommand {\IM }[0]{{\rm Im}} \newcommand {\nulls }[0]{{\rm null\;space}} \newcommand {\dps }[0]{\displaystyle } \newcommand {\arraystart }[0]{\renewcommand {\arraystretch }{1.8}} \newcommand {\arrayfinish }[0]{\renewcommand {\arraystretch }{1.2}} \newcommand {\Start }[1]{\vspace {0.08in}\noindent {\bf Section~\ref {#1}}} \newcommand {\exer }[1]{\noindent {\bf \ref {#1}}} \newcommand {\ans }[0]{} \newcommand {\matthree }[9]{\left (\begin {array}{rrr} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\cvectwo }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\cmatthree }[9]{\left (\begin {array}{ccc} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\vecthree }[3]{\left (\begin {array}{r} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cvecthree }[3]{\left (\begin {array}{c} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cmattwo }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\thehelp }[0]{\thesection .\arabic {equation}} \newcommand {\matlabEquation }[0]{\let \oldtheequation \theequation \renewcommand {\theequation }{\oldtheequation *}\begin {equation}} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$ $% This file was *autogenerated* from uniquenessOfReducedEchelonForm.sagetex.sage with % sagetex.py version 2015/08/26 v3.0-92d9f7a %f9c36d1cd74c2fd8a638145e01a131ea% md5sum of corresponding .sage file (minus "goboom","current_tex_line",and pause/unpause lines)$

In this section we prove Theorem ??, which states that every matrix is row equivalent to precisely one reduced echelon form matrix.

Proof of Theorem ??: Suppose that $E$ and $F$ are two $m\times n$ reduced echelon matrices that are row equivalent to $A$ . Since elementary row operations are invertible, the two matrices $E$ and $F$ are row equivalent. Thus, the systems of linear equations associated to the $m\times (n+1)$ matrices $(E|0)$ and $(F|0)$ must have exactly the same set of solutions. It is the fact that the solution sets of the linear equations associated to $(E|0)$ and $(F|0)$ are identical that allows us to prove that $E=F$ .

Begin by renumbering the variables $x_1,\ldots ,x_n$ so that the equations associated to $(E|0)$ have the form:

$\begin{equation} \label{e1-ell2a} \begin{array}{rcl} x_1 & = & - a_{1,\ell+1}x_{\ell+1} - \cdots - a_{1,n}x_n\\ x_2 & = & - a_{2,\ell+1}x_{\ell+1} - \cdots - a_{2,n}x_n\\ \vdots & & \vdots \\ x_\ell & = & - a_{\ell,\ell+1}x_{\ell+1} - \cdots - a_{\ell,n}x_n. \end{array} \end{equation}$ In this form, pivots of $E$ occur in the columns $1,\ldots ,\ell$ . We begin by showing that the matrix $F$ also has pivots in columns $1,\ldots ,\ell$ . Moreover, there is a unique solution to these equations for every choice of numbers $x_{\ell +1},\ldots ,x_n$ .

Suppose that the pivots of $F$ do not occur in columns $1,\ldots ,\ell$ . Then there is a row in $F$ whose first nonzero entry occurs in a column $k>\ell$ . This row corresponds to an equation $x_k = c_{k+1}x_{k+1} + \cdots + c_nx_n.$ Now, consider solutions that satisfy $x_{\ell +1} = \cdots = x_{k-1} = 0 \AND x_{k+1} = \cdots = x_n = 0.$ In the equations associated to the matrix $(E|0)$ , there is a unique solution associated with every number $x_k$ ; while in the equations associated to the matrix $(F|0)$ , $x_k$ must be zero to be a solution. This argument contradicts the fact that the $(E|0)$ equations and the $(F|0)$ equations have the same solutions. So the pivots of $F$ must also occur in columns $1,\ldots ,\ell$ , and the equations associated to $F$ must have the form:

$\begin{equation} \label{e1-ell2b} \begin{array}{rcl} x_1 & = & - \hat{a}_{1,\ell+1}x_{\ell+1} - \cdots - \hat{a}_{1,n}x_n \\ x_2 & = & - \hat{a}_{2,\ell+1}x_{\ell+1} - \cdots - \hat{a}_{2,n}x_n \\ \vdots & & \vdots \\ x_\ell & = & - \hat{a}_{\ell,\ell+1}x_{\ell+1} - \cdots - \hat{a}_{\ell,n}x_n \end{array} \end{equation}$ where $\hat {a}_{i,j}$ are scalars.

To complete this proof, we show that $a_{i,j}=\hat {a}_{i,j}$ . These equalities are verified as follows. There is just one solution to each system (??) and (??) of the form $x_{\ell +1}=1,\; x_{\ell +2}=\cdots =x_n=0.$ These solutions are $(-a_{1,\ell +1}, \ldots , -a_{\ell ,\ell +1},1,0,\cdots ,0)$ for (??) and $(-\hat {a}_{1,\ell +1},\ldots ,-\hat {a}_{\ell ,\ell +1},1,0\cdots ,0)$ for (??). It follows that $a_{j,\ell +1}=\hat {a}_{j,\ell +1}$ for $j=1,\ldots ,\ell$ . Complete this proof by repeating this argument. Just inspect solutions of the form $x_{\ell +1}=0,\; x_{\ell +2}=1,\; x_{\ell +3}=\cdots = x_n=0$ through $x_{\ell +1}=\cdots = x_{n-1}=0,\; x_n=1.$