Proof of Theorem BS

To prove that $T$ is linearly independent, begin with a relation of linear dependence on $T$, \begin{equation*} \zerovector= \alpha_1\vect{v}_{d_1}+\alpha_2\vect{v}_{d_2}+\alpha_3\vect{v}_{d_3}+\ldots+\alpha_r\vect{v}_{d_r} \end{equation*} and we will try to conclude that the only possibility for the scalars $\alpha_i$ is that they are all zero. Denote the non-pivot columns of $B$ by $F=\set{\scalarlist{f}{n-r}}$. Then we can preserve the equality by adding a big fat zero to the linear combination, \begin{equation*} \zerovector= \alpha_1\vect{v}_{d_1}+\alpha_2\vect{v}_{d_2}+\alpha_3\vect{v}_{d_3}+\ldots+\alpha_r\vect{v}_{d_r}+ 0\vect{v}_{f_1}+0\vect{v}_{f_2}+0\vect{v}_{f_3}+\ldots+0\vect{v}_{f_{n-r}} \end{equation*}

By Theorem SLSLC, the scalars in this linear combination (suitably reordered) are a solution to the homogeneous system $\homosystem{A}$. But notice that this is the solution obtained by setting each free variable to zero. If we consider the description of a solution vector in the conclusion of Theorem VFSLS, in the case of a homogeneous system, then we see that if all the free variables are set to zero the resulting solution vector is trivial (all zeros). So it must be that $\alpha_i=0$, $1\leq i\leq r$. This implies by Definition LICV that $T$ is a linearly independent set.

The second conclusion of this theorem is an equality of sets (Definition SE). Since $T$ is a subset of $S$, any linear combination of elements of the set $T$ can also be viewed as a linear combination of elements of the set $S$. So $\spn{T}\subseteq\spn{S}=W$. It remains to prove that $W=\spn{S}\subseteq\spn{T}$.

For each $k$, $1\leq k\leq n-r$, form a solution $\vect{x}$ to $\homosystem{A}$ by setting the free variables as follows: \begin{align*} x_{f_1}&=0 & x_{f_2}&=0 & x_{f_3}&=0 & \ldots& & x_{f_k}&=1 & \ldots& & x_{f_{n-r}}&=0 \end{align*}

By Theorem VFSLS, the remainder of this solution vector is given by, \begin{align*} x_{d_1}&=-\matrixentry{B}{1,f_k} & x_{d_2}&=-\matrixentry{B}{2,f_k} & x_{d_3}&=-\matrixentry{B}{3,f_k} & \dots& & x_{d_r}&=-\matrixentry{B}{r,f_k} \end{align*}

From this solution, we obtain a relation of linear dependence on the columns of $A$, \begin{equation*} -\matrixentry{B}{1,f_k}\vect{v}_{d_1} -\matrixentry{B}{2,f_k}\vect{v}_{d_2} -\matrixentry{B}{3,f_k}\vect{v}_{d_3} -\ldots -\matrixentry{B}{r,f_k}\vect{v}_{d_r} +1\vect{v}_{f_k} =\zerovector \end{equation*} which can be arranged as the equality \begin{equation*} \vect{v}_{f_k}= \matrixentry{B}{1,f_k}\vect{v}_{d_1}+ \matrixentry{B}{2,f_k}\vect{v}_{d_2}+ \matrixentry{B}{3,f_k}\vect{v}_{d_3}+ \ldots+ \matrixentry{B}{r,f_k}\vect{v}_{d_r} \end{equation*}

Now, suppose we take an arbitrary element, $\vect{w}$, of $W=\spn{S}$ and write it as a linear combination of the elements of $S$, but with the terms organized according to the indices in $D$ and $F$, \begin{align*} \vect{w}&= \alpha_1\vect{v}_{d_1}+ \alpha_2\vect{v}_{d_2}+ \ldots+ \alpha_r\vect{v}_{d_r}+ \beta_1\vect{v}_{f_1}+ \beta_2\vect{v}_{f_2}+ \ldots+ \beta_{n-r}\vect{v}_{f_{n-r}} \end{align*}

From the above, we can replace each $\vect{v}_{f_j}$ by a linear combination of the $\vect{v}_{d_i}$, \begin{align*} \vect{w}&= \alpha_1\vect{v}_{d_1}+ \alpha_2\vect{v}_{d_2}+ \ldots+ \alpha_r\vect{v}_{d_r}+\\ &\beta_1\left( \matrixentry{B}{1,f_1}\vect{v}_{d_1}+ \matrixentry{B}{2,f_1}\vect{v}_{d_2}+ \matrixentry{B}{3,f_1}\vect{v}_{d_3}+ \ldots+ \matrixentry{B}{r,f_1}\vect{v}_{d_r} \right)+\\ &\beta_2\left( \matrixentry{B}{1,f_2}\vect{v}_{d_1}+ \matrixentry{B}{2,f_2}\vect{v}_{d_2}+ \matrixentry{B}{3,f_2}\vect{v}_{d_3}+ \ldots+ \matrixentry{B}{r,f_2}\vect{v}_{d_r} \right)+\\ &\quad\quad\vdots\\ &\beta_{n-r}\left( \matrixentry{B}{1,f_{n-r}}\vect{v}_{d_1}+ \matrixentry{B}{2,f_{n-r}}\vect{v}_{d_2}+ \matrixentry{B}{3,f_{n-r}}\vect{v}_{d_3}+ \ldots+ \matrixentry{B}{r,f_{n-r}}\vect{v}_{d_r} \right)\\ \end{align*} With repeated applications of several of the properties of Theorem VSPCV we can rearrange this expression as, \begin{align*} =&\ \left( \alpha_1+ \beta_1\matrixentry{B}{1,f_1}+ \beta_2\matrixentry{B}{1,f_2}+ \beta_3\matrixentry{B}{1,f_3}+ \ldots+ \beta_{n-r}\matrixentry{B}{1,f_{n-r}} \right)\vect{v}_{d_1}+\\ &\left(\alpha_2+ \beta_1\matrixentry{B}{2,f_1}+ \beta_2\matrixentry{B}{2,f_2}+ \beta_3\matrixentry{B}{2,f_3}+ \ldots+ \beta_{n-r}\matrixentry{B}{2,f_{n-r}} \right)\vect{v}_{d_2}+\\ &\quad\quad\vdots\\ &\left(\alpha_r+ \beta_1\matrixentry{B}{r,f_1}+ \beta_2\matrixentry{B}{r,f_2}+ \beta_3\matrixentry{B}{r,f_3}+ \ldots+\beta_{n-r}\matrixentry{B}{r,f_{n-r}} \right)\vect{v}_{d_r} \end{align*} This mess expresses the vector $\vect{w}$ as a linear combination of the vectors in \begin{equation*} T=\set{\vect{v}_{d_1},\,\vect{v}_{d_2},\,\vect{v}_{d_3},\,\ldots\,\vect{v}_{d_r}} \end{equation*} thus saying that $\vect{w}\in\spn{T}$. Therefore, $W=\spn{S}\subseteq\spn{T}$.