Proof of Theorem FS

First, $\nsp{A}=\nsp{B}$ since $B$ is row-equivalent to $A$ (Theorem REMES). The zero rows of $B$ represent equations that are always true in the homogeneous system $\homosystem{B}$, so the removal of these equations will not change the solution set. Thus, in turn, $\nsp{B}=\nsp{C}$.

Second, $\rsp{A}=\rsp{B}$ since $B$ is row-equivalent to $A$ (Theorem REMRS). The zero rows of $B$ contribute nothing to the span that is the row space of $B$, so the removal of these rows will not change the row space. Thus, in turn, $\rsp{B}=\rsp{C}$.

Third, we prove the set equality $\csp{A}=\nsp{L}$ with Definition SE. Begin by showing that $\csp{A}\subseteq\nsp{L}$. Choose $\vect{y}\in\csp{A}\subseteq\complex{m}$. Then there exists a vector $\vect{x}\in\complex{n}$ such that $A\vect{x}=\vect{y}$ (Theorem CSCS). Then for $1\leq k\leq m-r$, \begin{align*} \vectorentry{L\vect{y}}{k} &=\vectorentry{J\vect{y}}{r+k} &&\text{$L$ a submatrix of $J$}\\ &=\vectorentry{B\vect{x}}{r+k} &&\knowl{./knowls/theorem.PEEF.knowl}{\text{Theorem PEEF}}\\ &=\vectorentry{\zeromatrix\vect{x}}{k} &&\text{Zero matrix a submatrix of $B$}\\ &=\vectorentry{\zerovector}{k} &&\knowl{./knowls/theorem.MMZM.knowl}{\text{Theorem MMZM}} \end{align*}

So, for all $1\leq k\leq m-r$, $\vectorentry{L\vect{y}}{k}=\vectorentry{\zerovector}{k}$. So by Definition CVE we have $L\vect{y}=\zerovector$ and thus $\vect{y}\in\nsp{L}$.

Now, show that $\nsp{L}\subseteq\csp{A}$. Choose $\vect{y}\in\nsp{L}\subseteq\complex{m}$. Form the vector $K\vect{y}\in\complex{r}$. The linear system $\linearsystem{C}{K\vect{y}}$ is consistent since $C$ is in reduced row-echelon form and has no zero rows (Theorem PEEF). Let $\vect{x}\in\complex{n}$ denote a solution to $\linearsystem{C}{K\vect{y}}$.

Then for $1\leq j\leq r$, \begin{align*} \vectorentry{B\vect{x}}{j} &=\vectorentry{C\vect{x}}{j} &&\text{$C$ a submatrix of $B$}\\ &=\vectorentry{K\vect{y}}{j} &&\text{$\vect{x}$ a solution to $\linearsystem{C}{K\vect{y}}$}\\ &=\vectorentry{J\vect{y}}{j} &&\text{$K$ a submatrix of $J$}\\ \end{align*}

And for $r+1\leq k\leq m$, \begin{align*} \vectorentry{B\vect{x}}{k} &=\vectorentry{\zeromatrix\vect{x}}{k-r} &&\text{Zero matrix a submatrix of $B$}\\ &=\vectorentry{\zerovector}{k-r} &&\knowl{./knowls/theorem.MMZM.knowl}{\text{Theorem MMZM}}\\ &=\vectorentry{L\vect{y}}{k-r} &&\text{$\vect{y}$ in $\nsp{L}$}\\ &=\vectorentry{J\vect{y}}{k} &&\text{$L$ a submatrix of $J$}\\ \end{align*}

So for all $1\leq i\leq m$, $\vectorentry{B\vect{x}}{i}=\vectorentry{J\vect{y}}{i}$ and by Definition CVE we have $B\vect{x}=J\vect{y}$. From Theorem PEEF we know then that $A\vect{x}=\vect{y}$, and therefore $\vect{y}\in\csp{A}$ (Theorem CSCS). By Definition SE we now have $\csp{A}=\nsp{L}$.

Fourth, we prove the set equality $\lns{A}=\rsp{L}$ with Definition SE. Begin by showing that $\rsp{L}\subseteq\lns{A}$. Choose $\vect{y}\in\rsp{L}\subseteq\complex{m}$. Then there exists a vector $\vect{w}\in\complex{m-r}$ such that $\vect{y}=\transpose{L}\vect{w}$ (Definition RSM, Theorem CSCS). Then for $1\leq i\leq n$, \begin{align*} \vectorentry{\transpose{A}\vect{y}}{i} &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\vectorentry{\vect{y}}{k} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\vectorentry{\transpose{L}\vect{w}}{k} &&\text{Definition of $\vect{w}$}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\sum_{\ell=1}^{m-r}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{m}\sum_{\ell=1}^{m-r}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/property.DCN.knowl}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m-r}\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/property.CACN.knowl}{\text{Property CACN}}\\ &=\sum_{\ell=1}^{m-r}\left(\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\right)\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/property.DCN.knowl}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m-r}\left(\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{J}}{k,r+\ell}\right)\vectorentry{\vect{w}}{\ell} &&\text{$L$ a submatrix of $J$}\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{A}\transpose{J}}{i,r+\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{\left(JA\right)}}{i,r+\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/theorem.MMT.knowl}{\text{Theorem MMT}}\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{i,r+\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/theorem.PEEF.knowl}{\text{Theorem PEEF}}\\ &=\sum_{\ell=1}^{m-r}0\vectorentry{\vect{w}}{\ell} &&\text{Zero rows in $B$}\\ &=0 &&\knowl{./knowls/property.ZCN.knowl}{\text{Property ZCN}}\\ &=\vectorentry{\zerovector}{i} &&\knowl{./knowls/definition.ZCV.knowl}{\text{Definition ZCV}} \end{align*}

Since $\vectorentry{\transpose{A}\vect{y}}{i}=\vectorentry{\zerovector}{i}$ for $1\leq i\leq n$, Definition CVE implies that $\transpose{A}\vect{y}=\zerovector$. This means that $\vect{y}\in\nsp{\transpose{A}}$.

Now, show that $\lns{A}\subseteq\rsp{L}$. Choose $\vect{y}\in\lns{A}\subseteq\complex{m}$. The matrix $J$ is nonsingular (Theorem PEEF), so $\transpose{J}$ is also nonsingular (Theorem MIT) and therefore the linear system $\linearsystem{\transpose{J}}{\vect{y}}$ has a unique solution. Denote this solution as $\vect{x}\in\complex{m}$. We will need to work with two “halves” of $\vect{x}$, which we will denote as $\vect{z}$ and $\vect{w}$ with formal definitions given by \begin{align*} \vectorentry{z}{j}&=\vectorentry{x}{i} & &1\leq j\leq r, &&& \vectorentry{w}{k}&=\vectorentry{x}{r+k} & &1\leq k\leq m-r \end{align*}

Now, for $1\leq j\leq r$, \begin{align*} \vectorentry{\transpose{C}\vect{z}}{j} &=\sum_{k=1}^{r}\matrixentry{\transpose{C}}{jk}\vectorentry{\vect{z}}{k} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{C}}{jk}\vectorentry{\vect{z}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\zeromatrix}{j\ell}\vectorentry{\vect{w}}{\ell} &&\knowl{./knowls/definition.ZM.knowl}{\text{Definition ZM}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{z}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{j,r+\ell}\vectorentry{\vect{w}}{\ell} &&\text{$C$, $\zeromatrix$ submatrices of $B$}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{j,r+\ell}\vectorentry{\vect{x}}{r+\ell} &&\text{Definitions of $\vect{z}$ and $\vect{w}$}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k} &&\text{Re-index second sum}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k} &&\text{Combine sums}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{\left(JA\right)}}{jk}\vectorentry{\vect{x}}{k} &&\knowl{./knowls/theorem.PEEF.knowl}{\text{Theorem PEEF}}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}\transpose{J}}{jk}\vectorentry{\vect{x}}{k} &&\knowl{./knowls/theorem.MMT.knowl}{\text{Theorem MMT}}\\ &=\sum_{k=1}^{m}\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m}\sum_{k=1}^{m}\matrixentry{\transpose{A}}{j\ell}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k} &&\knowl{./knowls/property.CACN.knowl}{\text{Property CACN}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\left(\sum_{k=1}^{m}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k}\right) &&\knowl{./knowls/property.DCN.knowl}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\vectorentry{\transpose{J}\vect{x}}{\ell} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\vectorentry{\vect{y}}{\ell} &&\text{Definition of $\vect{x}$}\\ &=\vectorentry{\transpose{A}\vect{y}}{j} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\vectorentry{\zerovector}{j} &&\text{$\vect{y}\in\lns{A}$} \end{align*}

So, by Definition CVE, $\transpose{C}\vect{z}=\zerovector$ and the vector $\vect{z}$ gives us a linear combination of the columns of $\transpose{C}$ that equals the zero vector. In other words, $\vect{z}$ gives a relation of linear dependence on the the rows of $C$. However, the rows of $C$ are a linearly independent set by Theorem BRS. According to Definition LICV we must conclude that the entries of $\vect{z}$ are all zero, i.e. $\vect{z}=\zerovector$.

Now, for $1\leq i\leq m$, we have \begin{align*} \vectorentry{\vect{y}}{i} &=\vectorentry{\transpose{J}\vect{x}}{i} &&\text{Definition of $\vect{x}$}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k} &&\text{Break apart sum}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{z}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{w}}{k-r} &&\text{Definition of $\vect{z}$ and $\vect{w}$}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}0+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{J}}{i,r+\ell}\vectorentry{\vect{w}}{\ell} &&\text{$\vect{z}=\zerovector$, re-index}\\ &=0+\sum_{\ell=1}^{m-r}\matrixentry{\transpose{L}}{i,\ell}\vectorentry{\vect{w}}{\ell} &&\text{$L$ a submatrix of $J$}\\ &=\vectorentry{\transpose{L}\vect{w}}{i} &&\knowl{./knowls/theorem.EMP.knowl}{\text{Theorem EMP}}\\ \end{align*}

So by Definition CVE, $\vect{y}=\transpose{L}\vect{w}$. The existence of $\vect{w}$ implies that $\vect{y}\in\rsp{L}$, and therefore $\lns{A}\subseteq\rsp{L}$. So by Definition SE we have $\lns{A}=\rsp{L}$.