In this section we are going to do an extended example on solutions to a homogeneous matrix equation $A\mathbf{x}=\mathrm{\U0001d7ce}$, where $A$ is some fixed $m\times n$ matrix with entries from a field $\mathbb{F}$. We will prove that the fundamental solutions constructed in 3.11.1 are a basis of the nullspace $N(A)$.

Here is a recap of how the fundamental solutions to $A\mathbf{x}=\mathrm{\U0001d7ce}$ are obtained. First do row operations to $A$ until we reach
a matrix $R$ in row reduced echelon form, and recall that the solutions
to $A\mathbf{x}=\mathrm{\U0001d7ce}$ are exactly the same as the solutions to
$R\mathbf{x}=\mathrm{\U0001d7ce}$, that is, $N(A)=N(R)$. ^{1}^{1}
1
It is not true
that the column space $C(A)$ equals $C(R)$. Row operations don’t change
the nullspace but they can change the column space. Let $r$ be the number of nonzero rows in
$R$, which is the number of columns containing a leading entry, and let
$k$ be the number of columns with no leading entry, so that $r+k=n$. Let the numbers of the columns with a leading entry be $$ and the columns with no leading entry be $$. Returning to the example

$$R=\left(\begin{array}{ccccc}0& 1& 2& 0& 3\\ 0& 0& 0& 1& 4\\ 0& 0& 0& 0& 0\end{array}\right)$$ |

we have $m=3,n=5,r=2,{c}_{1}=2,{c}_{2}=4,{d}_{1}=1,{d}_{2}=3,{d}_{3}=5$. In general, there are $k$ fundamental solutions ${\mathbf{s}}_{1},\mathrm{\dots},{\mathbf{s}}_{k}$ defined by

$${\mathbf{s}}_{j}={\mathbf{e}}_{{d}_{j}}-\sum _{i=1}^{r}{r}_{i,{d}_{j}}{\mathbf{e}}_{{c}_{i}}$$ |

where ${\mathbf{e}}_{l}$ is the column vector with a 1 at position $l$ and zeros elsewhere and $R=({r}_{ij})$. In other words, the row ${d}_{j}$ entry of ${\mathbf{s}}_{j}$ is 1, the entry in row ${c}_{i}$ is $-{r}_{i,{d}_{j}}$ for $1\u2a7di\u2a7dr$, and all other entries are 0. In the example,

$${\mathbf{s}}_{1}=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\end{array}\right),{\mathbf{s}}_{2}=\left(\begin{array}{c}0\\ -2\\ 1\\ 0\\ 0\end{array}\right),{\mathbf{s}}_{3}=\left(\begin{array}{c}0\\ -3\\ 0\\ -4\\ 1\end{array}\right).$$ |

It’s useful to record a general lemma.

(The easy linear independence criterion). Suppose some column vectors ${\mathbf{v}}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{\mathbf{v}}_{k}$ have the property that for each $i$, ${\mathbf{v}}_{i}$ has a nonzero entry in a row where all the other ${\mathbf{v}}_{j}$s have zero. Then ${\mathbf{v}}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{\mathbf{v}}_{k}$ is linearly independent.

For example, if

$${\mathbf{v}}_{1}=\left(\begin{array}{c}1\\ 0\\ 0\\ 3\end{array}\right),{\mathbf{v}}_{2}=\left(\begin{array}{c}4\\ 5\\ 0\\ 0\end{array}\right),{\mathbf{v}}_{3}=\left(\begin{array}{c}7\\ 0\\ 8\\ 0\end{array}\right)$$ |

then ${\mathbf{v}}_{1}$ has a nonzero entry in row 4 while the other two vectors are zero in row 4, ${\mathbf{v}}_{2}$ has a nonzero entry in row 2 while the other two vectors are zero in row 2, and ${\mathbf{v}}_{3}$ has a nonzero entry in row 3 while the other two vectors are zero in row 3, so these three vectors meet the easy linear independence criterion.

Suppose that

$$\sum _{i=1}^{k}{\lambda}_{i}{\mathbf{v}}_{i}=\mathrm{\U0001d7ce}.$$ | (4.6) |

There is a row, say row $j$, where ${\mathbf{v}}_{1}$ has a nonzero entry ${v}_{1j}$ and all of ${\mathbf{v}}_{2},\mathrm{\dots},{\mathbf{v}}_{k}$ are zero. Comparing the entries of row $j$ in (4.6) gives ${\lambda}_{1}{v}_{1j}=0$ and so ${\lambda}_{1}=0$. A similar argument shows all the other ${\lambda}_{i}$ are zero, so the vectors are linearly independent. ∎

To illustrate the proof, return to the example above. Suppose

$$a{\mathbf{v}}_{1}+b{\mathbf{v}}_{2}+c{\mathbf{v}}_{3}=\mathrm{\U0001d7ce}.$$ |

Rather than write out the resulting vector, just think about what appears in row 4 on the left hand side. Vectors ${\mathbf{v}}_{2}$ and ${\mathbf{v}}_{3}$ are zero there, so we just get $3a=0$ and so $a=0$. Considering row 2 shows $b=0$ and considering row 3 shows $c=0$, therefore they are linearly independent.

The fundamental solutions to $A\mathit{}\mathbf{x}\mathrm{=}\mathrm{\U0001d7ce}$ are linearly independent.

Apply the easy linear independence lemma above, using row ${d}_{i}$ for ${\mathbf{s}}_{i}$. The criterion applies because no ${d}_{i}$ is equal to any ${c}_{j}$ or any other ${d}_{j}$. ∎

It is also true that the fundamental solutions span the null space $N(A)$, so that they are a basis. We could do a direct proof of this now, but it would be messy. Instead we will return to it later when we have the technology to make it easy.