Proof of Theorem VFSLS

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$, 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$. So an arbitrary element of $S$, 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} \end{equation*}

When $r+1\leq\ell\leq m$, 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$. 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} \end{equation*}

Since $\matrixentry{B}{\ell d_{i}}=0$ for all $1\leq i\leq r$, except that $\matrixentry{B}{\ell d_{\ell}}=1$, 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}} \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 \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}} \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}}$, 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$, in other words, $x_i=\vectorentry{\vect{x}}{i}$. We desire to show that this solution vector is also an element of the set $S$. Begin with the observation that a solution vector's entries makes equation $\ell$ of the system true for all $1\leq\ell\leq m$, \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} \end{equation*}

When $\ell\leq r$, the pivot columns of $B$ have zero entries in row $\ell$ with the exception of column $d_\ell$, which will contain a $1$. So for $1\leq\ell\leq r$, 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} \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} \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$. 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$. To this end, suppose $i\in F$ and $i=f_j$. 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} \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$. So the set $S$ contains all of the solutions to the system.