Proof of Theorem EOPSS
We take each equation operation in turn and show that the solution sets of the two systems are equal, using the definition of set equality (Definition SE).
- It will not be our habit in proofs to resort to saying statements are “obvious,” but in this case, it should be. There is nothing about the order in which we write linear equations that affects their solutions, so the solution set will be equal if the systems only differ by a rearrangement of the order of the equations.
- Suppose $\alpha\neq 0$ is a number. Let us choose to multiply the terms of equation $i$ by $\alpha$ to build the new system of equations,
\begin{align*}
a_{11}x_1+a_{12}x_2+a_{13}x_3+\dots+a_{1n}x_n&=b_1\\
a_{21}x_1+a_{22}x_2+a_{23}x_3+\dots+a_{2n}x_n&=b_2\\
a_{31}x_1+a_{32}x_2+a_{33}x_3+\dots+a_{3n}x_n&=b_3\\
&\vdots\\
\alpha a_{i1}x_1+\alpha a_{i2}x_2+\alpha a_{i3}x_3+\dots+\alpha a_{in}x_n&=\alpha b_i\\
&\vdots\\
a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\dots+a_{mn}x_n&=b_m
\end{align*}
Let $S$ denote the solutions to the system in the statement of the theorem, and let $T$ denote the solutions to the transformed system.
- Show $S\subseteq T$. Suppose $(x_1,\,x_2,\,\,x_3,\,\ldots,x_n)=(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in S$ is a solution to the original system. Ignoring the $i$-th equation for a moment, we know it makes all the other equations of the transformed system true. We also know that
\begin{align*}
a_{i1}\beta_1+a_{i2}\beta_2+a_{i3}\beta_3+\dots+a_{in}\beta_n&=b_i\\
\end{align*}
which we can multiply by $\alpha$ to get
\begin{align*}
\alpha a_{i1}\beta_1+\alpha a_{i2}\beta_2+\alpha a_{i3}\beta_3+\dots+\alpha a_{in}\beta_n&=\alpha b_i
\end{align*}
This says that the $i$-th equation of the transformed system is also true, so we have established that $(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in T$, and therefore $S\subseteq T$.
- Now show $T\subseteq S$. Suppose $(x_1,\,x_2,\,\,x_3,\,\ldots,x_n)=(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in T$ is a solution to the transformed system. Ignoring the $i$-th equation for a moment, we know it makes all the other equations of the original system true. We also know that
\begin{align*}
\alpha a_{i1}\beta_1+\alpha a_{i2}\beta_2+\alpha a_{i3}\beta_3+\dots+\alpha a_{in}\beta_n&=\alpha b_i
\end{align*}
which we can multiply by $\tfrac{1}{\alpha}$, since $\alpha\neq 0$, to get
\begin{align*}
a_{i1}\beta_1+a_{i2}\beta_2+a_{i3}\beta_3+\dots+a_{in}\beta_n&=b_i\\
\end{align*}
This says that the $i$-th equation of the original system is also true, so we have established that $(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in S$, and therefore $T\subseteq S$. Locate the key point where we required that $\alpha\neq 0$, and consider what would happen if $\alpha=0$.
- Suppose $\alpha$ is a number. Let us choose to multiply the terms of equation $i$ by $\alpha$ and add them to equation $j$ in order to build the new system of equations,
\begin{align*}
a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n&=b_1\\
a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n&=b_2\\
a_{31}x_1+a_{32}x_2+\dots+a_{3n}x_n&=b_3\\
&\vdots\\
(\alpha a_{i1}+a_{j1})x_1+(\alpha a_{i2}+a_{j2})x_2+\dots+(\alpha a_{in}+a_{jn})x_n&=\alpha b_i+b_{j}\\
&\vdots\\
a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n&=b_m
\end{align*}
Let $S$ denote the solutions to the system in the statement of the theorem, and let $T$ denote the solutions to the transformed system.
- Show $S\subseteq T$. Suppose $(x_1,\,x_2,\,\,x_3,\,\ldots,x_n)=(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in S$ is a solution to the original system. Ignoring the $j$-th equation for a moment, we know this solution makes all the other equations of the transformed system true. Using the fact that the solution makes the $i$-th and $j$-th equations of the original system true, we find
\begin{align*}
&(\alpha a_{i1}+a_{j1})\beta_1+(\alpha a_{i2}+a_{j2})\beta_2+\dots+(\alpha a_{in}+a_{jn})\beta_n\\
&\quad=(\alpha a_{i1}\beta_1+\alpha a_{i2}\beta_2+\dots+\alpha a_{in}\beta_n)+
(a_{j1}\beta_1+a_{j2}\beta_2+\dots+a_{jn}\beta_n)\\
&\quad=\alpha(a_{i1}\beta_1+a_{i2}\beta_2+\dots+a_{in}\beta_n)+
(a_{j1}\beta_1+a_{j2}\beta_2+\dots+a_{jn}\beta_n)\\
&\quad=\alpha b_i+b_j.
\end{align*}
This says that the $j$-th equation of the transformed system is also true, so we have established that $(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in T$, and therefore $S\subseteq T$.
- Now show $T\subseteq S$. Suppose $(x_1,\,x_2,\,\,x_3,\,\ldots,x_n)=(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in T$ is a solution to the transformed system. Ignoring the $j$-th equation for a moment, we know it makes all the other equations of the original system true. We then find
\begin{align*}
&a_{j1}\beta_1+\dots+a_{jn}\beta_n\\
&\quad\quad=a_{j1}\beta_1+\dots+a_{jn}\beta_n +\alpha b_i -\alpha b_i\\
&\quad\quad=a_{j1}\beta_1+\dots+a_{jn}\beta_n +(\alpha a_{i1}\beta_1+\dots+\alpha a_{in}\beta_n) -\alpha b_i\\
&\quad\quad=a_{j1}\beta_1+\alpha a_{i1}\beta_1+\dots+a_{jn}\beta_n+\alpha a_{in}\beta_n-\alpha b_i\\
&\quad\quad=(\alpha a_{i1}+a_{j1})\beta_1+\dots+(\alpha a_{in}+a_{jn})\beta_n -\alpha b_i\\
&\quad\quad=\alpha b_i + b_j -\alpha b_i\\
&\quad\quad=b_j
\end{align*}
This says that the $j$-th equation of the original system is also true, so we have established that $(\beta_1,\,\beta_2,\,\,\beta_3,\,\ldots,\beta_n)\in S$, and therefore $T\subseteq S$.
Why did we not need to require that $\alpha\neq 0$ for this row operation? In other words, how does the third statement of the theorem read when $\alpha=0$? Does our proof require some extra care when $\alpha=0$? Compare your answers with the similar situation for the second row operation. (See Exercise SSLE.T20.)