Notice that it is possible that \(n=r\text{,}\) in which case we get the unique solution \(\vect{c}\text{.}\)
First,
\(\linearsystem{A}{\vect{b}}\) is equivalent to the linear system of equations that has the matrix
\(B\) as its augmented matrix (
Theorem REMES), so we need only show that
\(S\) is the solution set for the system with
\(B\) as its augmented matrix. The conclusion of this theorem is that the solution set is equal to the set
\(S\text{,}\) so we will apply
Definition SE.
We begin by showing that every element of \(S\) is indeed a solution to the system. Let \(\alpha_1,\,\alpha_2,\,\alpha_3,\,\ldots,\,\alpha_{n-r}\) be one choice of the scalars used to describe elements of \(S\text{.}\) So an arbitrary element of \(S\text{,}\) which we will consider as a proposed solution is
\begin{equation*}
\vect{x}=
\vect{c}+\alpha_1\vect{u}_1+\alpha_2\vect{u}_2+\alpha_3\vect{u}_3+\cdots+\alpha_{n-r}\vect{u}_{n-r}\text{.}
\end{equation*}
When \(r+1\leq\ell\leq m\text{,}\) row \(\ell\) of the matrix \(B\) is a zero row, so the equation represented by that row is always true, no matter which solution vector we propose. So concentrate on rows representing equations \(1\leq\ell\leq r\text{.}\) We evaluate equation \(\ell\) of the system represented by \(B\) with the proposed solution vector \(\vect{x}\) and refer to the value of the left-hand side of the equation as \(\beta_\ell\)
\begin{equation*}
\beta_\ell=
\matrixentry{B}{\ell 1}\vectorentry{\vect{x}}{1}+
\matrixentry{B}{\ell 2}\vectorentry{\vect{x}}{2}+
\matrixentry{B}{\ell 3}\vectorentry{\vect{x}}{3}+
\cdots+
\matrixentry{B}{\ell n}\vectorentry{\vect{x}}{n}\text{.}
\end{equation*}
Since \(\matrixentry{B}{\ell d_{i}}=0\) for all \(1\leq i\leq r\text{,}\) except that \(\matrixentry{B}{\ell d_{\ell}}=1\text{,}\) we see that \(\beta_\ell\) simplifies to
\begin{equation*}
\beta_\ell=
\vectorentry{\vect{x}}{d_{\ell}}+
\matrixentry{B}{\ell f_1}\vectorentry{\vect{x}}{f_1}+
\matrixentry{B}{\ell f_2}\vectorentry{\vect{x}}{f_2}+
\matrixentry{B}{\ell f_3}\vectorentry{\vect{x}}{f_3}+
\cdots+
\matrixentry{B}{\ell f_{n-r}}\vectorentry{\vect{x}}{f_{n-r}}\text{.}
\end{equation*}
Notice that for \(1\leq i\leq n-r\)
\begin{align*}
\vectorentry{\vect{x}}{f_i}
&=
\vectorentry{\vect{c}}{f_i}+
\alpha_1\vectorentry{\vect{u}_1}{f_i}+
\alpha_2\vectorentry{\vect{u}_2}{f_i}+
\cdots+
\alpha_i\vectorentry{\vect{u}_i}{f_i}+
\cdots+
\alpha_{n-r}\vectorentry{\vect{u_{n-r}}}{f_i}\\
&=
0+
\alpha_1(0)+
\alpha_2(0)+
\cdots+
\alpha_i(1)+
\cdots+
\alpha_{n-r}(0)\\
&=\alpha_i\text{.}
\end{align*}
So \(\beta_\ell\) simplifies further, and we expand the first term
\begin{align*}
\beta_\ell
&=
\vectorentry{\vect{x}}{d_{\ell}}+
\matrixentry{B}{\ell f_1}\alpha_1+
\matrixentry{B}{\ell f_2}\alpha_2+
\matrixentry{B}{\ell f_3}\alpha_3+
\cdots+
\matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\
&=
\vectorentry{
\vect{c}+
\alpha_1\vect{u}_1+
\alpha_2\vect{u}_2+
\alpha_3\vect{u}_3+
\cdots+
\alpha_{n-r}\vect{u}_{n-r}
}{d_{\ell}}
+\\
&\quad\quad
\matrixentry{B}{\ell f_1}\alpha_1+
\matrixentry{B}{\ell f_2}\alpha_2+
\matrixentry{B}{\ell f_3}\alpha_3+
\cdots+
\matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\
&=
\vectorentry{\vect{c}}{d_{\ell}}+
\alpha_1\vectorentry{\vect{u}_1}{d_{\ell}}+
\alpha_2\vectorentry{\vect{u}_2}{d_{\ell}}+
\alpha_3\vectorentry{\vect{u}_3}{d_{\ell}}+
\cdots+
\alpha_{n-r}\vectorentry{\vect{u_{n-r}}}{d_{\ell}}
+\\
&\quad\quad
\matrixentry{B}{\ell f_1}\alpha_1+
\matrixentry{B}{\ell f_2}\alpha_2+
\matrixentry{B}{\ell f_3}\alpha_3+
\cdots+
\matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\
&=
\matrixentry{B}{\ell,{n+1}}+\\
&\quad\quad
\alpha_1(-\matrixentry{B}{\ell f_1})+
\alpha_2(-\matrixentry{B}{\ell f_2})+
\alpha_3(-\matrixentry{B}{\ell f_3})+
\cdots+
\alpha_{n-r}(-\matrixentry{B}{\ell f_{n-r}})
+\\
&\quad\quad
\matrixentry{B}{\ell f_1}\alpha_1+
\matrixentry{B}{\ell f_2}\alpha_2+
\matrixentry{B}{\ell f_3}\alpha_3+
\cdots+
\matrixentry{B}{\ell f_{n-r}}\alpha_{n-r}\\
&=
\matrixentry{B}{\ell,{n+1}}\text{.}
\end{align*}
So \(\beta_\ell\) began as the left-hand side of equation \(\ell\) of the system represented by \(B\) and we now know it equals \(\matrixentry{B}{\ell,{n+1}}\text{,}\) the constant term for equation \(\ell\) of this system. So the arbitrarily chosen vector from \(S\) makes every equation of the system true, and therefore is a solution to the system. So all the elements of \(S\) are solutions to the system.
For the second half of the proof, assume that \(\vect{x}\) is a solution vector for the system having \(B\) as its augmented matrix. For convenience and clarity, denote the entries of \(\vect{x}\) by \(x_i\text{,}\) in other words, \(x_i=\vectorentry{\vect{x}}{i}\text{.}\) We desire to show that this solution vector is also an element of the set \(S\text{.}\) Begin with the observation that a solution vector’s entries makes equation \(\ell\) of the system true for all \(1\leq\ell\leq m\text{,}\)
\begin{equation*}
\matrixentry{B}{\ell,1}x_1+
\matrixentry{B}{\ell,2}x_2+
\matrixentry{B}{\ell,3}x_3+
\cdots+
\matrixentry{B}{\ell,n}x_n=
\matrixentry{B}{\ell,n+1}\text{.}
\end{equation*}
When \(\ell\leq r\text{,}\) the pivot columns of \(B\) have zero entries in row \(\ell\) with the exception of column \(d_\ell\text{,}\) which will contain a \(1\text{.}\) So for \(1\leq\ell\leq r\text{,}\) equation \(\ell\) simplifies to
\begin{equation*}
1x_{d_\ell}+
\matrixentry{B}{\ell,f_1}x_{f_1}+
\matrixentry{B}{\ell,f_2}x_{f_2}+
\matrixentry{B}{\ell,f_3}x_{f_3}+
\cdots+
\matrixentry{B}{\ell,f_{n-r}}x_{f_{n-r}}=
\matrixentry{B}{\ell,n+1}\text{.}
\end{equation*}
This allows us to write,
\begin{align*}
\vectorentry{\vect{x}}{d_\ell}
&=
x_{d_\ell}\\
&=
\matrixentry{B}{\ell,n+1}
-\matrixentry{B}{\ell,f_1}x_{f_1}
-\matrixentry{B}{\ell,f_2}x_{f_2}
-\matrixentry{B}{\ell,f_3}x_{f_3}
-\cdots
-\matrixentry{B}{\ell,f_{n-r}}x_{f_{n-r}}\\
&=
\vectorentry{\vect{c}}{d_\ell}
+x_{f_1}\vectorentry{\vect{u}_1}{d_\ell}
+x_{f_2}\vectorentry{\vect{u}_2}{d_\ell}
+x_{f_3}\vectorentry{\vect{u}_3}{d_\ell}
+\cdots
+x_{f_{n-r}}\vectorentry{\vect{u}_{n-r}}{d_\ell}\\
&=
\vectorentry{
\vect{c}
+x_{f_1}\vect{u}_1
+x_{f_2}\vect{u}_2
+x_{f_3}\vect{u}_3
+\cdots
+x_{f_{n-r}}\vect{u}_{n-r}
}{d_\ell}\text{.}
\end{align*}
This tells us that the entries of the solution vector \(\vect{x}\) corresponding to dependent variables (indices in \(D\)), are equal to those of a vector in the set \(S\text{.}\) We still need to check the other entries of the solution vector \(\vect{x}\) corresponding to the free variables (indices in \(F\)) to see if they are equal to the entries of the same vector in the set \(S\text{.}\) To this end, suppose \(i\in F\) and \(i=f_j\text{.}\) Then
\begin{align*}
\vectorentry{\vect{x}}{i}
&=x_{i}=x_{f_j}\\
&=
0+
0x_{f_1}+
0x_{f_2}+
0x_{f_3}+
\cdots+
0x_{f_{j-1}}+
1x_{f_j}+
0x_{f_{j+1}}+
\cdots+
0x_{f_{n-r}}\\
&=
\vectorentry{\vect{c}}{i}+
x_{f_1}\vectorentry{\vect{u}_1}{i}+
x_{f_2}\vectorentry{\vect{u}_2}{i}+
x_{f_3}\vectorentry{\vect{u}_3}{i}+
\cdots+
x_{f_j}\vectorentry{\vect{u}_j}{i}+
\cdots+
x_{f_{n-r}}\vectorentry{\vect{u}_{n-r}}{i}\\
&=\vectorentry{
\vect{c}
+x_{f_1}\vect{u}_1
+x_{f_2}\vect{u}_2
+\cdots
+x_{f_{n-r}}\vect{u}_{n-r}
}{i}\text{.}
\end{align*}
So entries of
\(\vect{x}\) and
\(\vect{c} +x_{f_1}\vect{u}_1 +x_{f_2}\vect{u}_2 +\cdots +x_{f_{n-r}}\vect{u}_{n-r}\) are equal and therefore by
Definition CVE they are equal vectors. Since
\(x_{f_1},\,x_{f_2},\,x_{f_3},\,\ldots,\,x_{f_{n-r}}\) are scalars, this shows us that
\(\vect{x}\) qualifies for membership in
\(S\text{.}\) So the set
\(S\) contains all of the solutions to the system.
