<div class="proof" id="proof-REMRS" acro="REMRS" titletext="">
<h5 class="proof">
<span class="type">Proof of Theorem</span> <span class="acro">REMRS</span>
</h5>
<p>Two matrices are row-equivalent (<a class="knowl" acro="REM" type="Definition" title="Row-Equivalent Matrices" knowl="./knowls/definition.REM.knowl">Definition REM</a>) if one can be obtained from another by a sequence of (possibly many) row operations.  We will prove the theorem for two matrices that differ by a single row operation, and then this result can be applied repeatedly to get the full statement of the theorem.  The row spaces of $A$ and $B$ are spans of the columns of their transposes.  For each row operation we perform on a matrix, we can define an analogous operation on the columns.  Perhaps we should call these <em class="term">column operations</em>.  Instead, we will still call them row operations, but we will apply them to the columns of the transposes.</p>

<p>Refer to the columns of $\transpose{A}$ and $\transpose{B}$ as $\vect{A}_i$ and $\vect{B}_i$, $1\leq i\leq m$.  The row operation that switches rows will just switch columns of the transposed matrices.  This will have no effect on the possible linear combinations formed by the columns.</p>

<p>Suppose that $\transpose{B}$ is formed from $\transpose{A}$ by multiplying column $\vect{A}_t$ by $\alpha\neq 0$.  In other words, $\vect{B}_t=\alpha\vect{A}_t$, and $\vect{B}_i=\vect{A}_i$ for all $i\neq t$.  We need to establish that two sets are equal, $\csp{\transpose{A}}=\csp{\transpose{B}}$.  We will take a generic element of one and show that it is contained in the other.
\begin{align*}
\beta_1\vect{B}_1+
&amp;
\beta_2\vect{B}_2+
\beta_3\vect{B}_3+
\cdots+
\beta_t\vect{B}_t+
\cdots+
\beta_m\vect{B}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\beta_3\vect{A}_3+
\cdots+
\beta_t\left(\alpha\vect{A}_t\right)+
\cdots+
\beta_m\vect{A}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\beta_3\vect{A}_3+
\cdots+
\left(\alpha\beta_t\right)\vect{A}_t+
\cdots+
\beta_m\vect{A}_m
\end{align*}

says that $\csp{\transpose{B}}\subseteq\csp{\transpose{A}}$.  Similarly,
\begin{align*}
\gamma_1\vect{A}_1+
&amp;
\gamma_2\vect{A}_2+
\gamma_3\vect{A}_3+
\cdots+
\gamma_t\vect{A}_t+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{A}_1+
\gamma_2\vect{A}_2+
\gamma_3\vect{A}_3+
\cdots+
\left(\frac{\gamma_t}{\alpha}\alpha\right)\vect{A}_t+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{A}_1+
\gamma_2\vect{A}_2+
\gamma_3\vect{A}_3+
\cdots+
\frac{\gamma_t}{\alpha}\left(\alpha\vect{A}_t\right)+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{B}_1+
\gamma_2\vect{B}_2+
\gamma_3\vect{B}_3+
\cdots+
\frac{\gamma_t}{\alpha}\vect{B}_t+
\cdots+
\gamma_m\vect{B}_m
\end{align*}

says that $\csp{\transpose{A}}\subseteq\csp{\transpose{B}}$.   So $\rsp{A}=\csp{\transpose{A}}=\csp{\transpose{B}}=\rsp{B}$ when a single row operation of the second type is performed.</p>

<p>Suppose now that $\transpose{B}$ is formed from $\transpose{A}$ by replacing $\vect{A}_t$ with $\alpha\vect{A}_s+\vect{A}_t$ for some $\alpha\in\complex{\null}$ and $s\neq t$.  In other words, $\vect{B}_t=\alpha\vect{A}_s+\vect{A}_t$, and $\vect{B}_i=\vect{A}_i$ for $i\neq t$.
\begin{align*}
\beta_1\vect{B}_1+
&amp;
\beta_2\vect{B}_2+
\cdots+
\beta_s\vect{B}_s+
\cdots+
\beta_t\vect{B}_t+
\cdots+
\beta_m\vect{B}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\cdots+
\beta_s\vect{A}_s+
\cdots+
\beta_t\left(\alpha\vect{A}_s+\vect{A}_t\right)+
\cdots+
\beta_m\vect{A}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\cdots+
\beta_s\vect{A}_s+
\cdots+
\left(\beta_t\alpha\right)\vect{A}_s+\beta_t\vect{A}_t+
\cdots+
\beta_m\vect{A}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\cdots+
\beta_s\vect{A}_s+\left(\beta_t\alpha\right)\vect{A}_s+
\cdots+
\beta_t\vect{A}_t+
\cdots+
\beta_m\vect{A}_m\\
&amp;=
\beta_1\vect{A}_1+
\beta_2\vect{A}_2+
\cdots+
\left(\beta_s+\beta_t\alpha\right)\vect{A}_s+
\cdots+
\beta_t\vect{A}_t+
\cdots+
\beta_m\vect{A}_m
\end{align*}

says that $\csp{\transpose{B}}\subseteq\csp{\transpose{A}}$.  Similarly,

\begin{align*}
\gamma_1&amp;\vect{A}_1+
\gamma_2\vect{A}_2+
\cdots+
\gamma_s\vect{A}_s+
\cdots+
\gamma_t\vect{A}_t+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{A}_1+
\gamma_2\vect{A}_2+
\cdots+
\gamma_s\vect{A}_s+
\cdots+
\left(-\alpha\gamma_t\vect{A}_s + \alpha\gamma_t\vect{A}_s\right)+\gamma_t\vect{A}_t+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{A}_1+
\gamma_2\vect{A}_2+
\cdots+
\left(-\alpha\gamma_t+\gamma_s\right)\vect{A}_s+
\cdots+
\gamma_t\left(\alpha\vect{A}_s+\vect{A}_t\right)+
\cdots+
\gamma_m\vect{A}_m\\
&amp;=
\gamma_1\vect{B}_1+
\gamma_2\vect{B}_2+
\cdots+
\left(-\alpha\gamma_t+\gamma_s\right)\vect{B}_s+
\cdots+
\gamma_t\vect{B}_t+
\cdots+
\gamma_m\vect{B}_m
\end{align*}

says that $\csp{\transpose{A}}\subseteq\csp{\transpose{B}}$.  So $\rsp{A}=\csp{\transpose{A}}=\csp{\transpose{B}}=\rsp{B}$ when a single row operation of the third type is performed.</p>

<p>So the row space of a matrix is preserved by each row operation, and hence row spaces of row-equivalent matrices are equal sets.</p>

</div>