# 4.11 Fundamental solutions are linearly independent

In this section we are going to do an extended example on solutions to a homogeneous matrix equation $A\mathbf{x}=\mathbf{0}$, 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}=\mathbf{0}$ 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}=\mathbf{0}$ are exactly the same as the solutions to $R\mathbf{x}=\mathbf{0}$, that is, $N(A)=N(R)$. 11 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 $c_{1} and the columns with no leading entry be $d_{1}. Returning to the example

 $R=\begin{pmatrix}0&1&2&0&3\\ 0&0&0&1&4\\ 0&0&0&0&0\end{pmatrix}$

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},\ldots,\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\leqslant i\leqslant r$, and all other entries are 0. In the example,

 $\mathbf{s}_{1}=\begin{pmatrix}1\\ 0\\ 0\\ 0\\ 0\end{pmatrix},\mathbf{s}_{2}=\begin{pmatrix}0\\ -2\\ 1\\ 0\\ 0\end{pmatrix},\mathbf{s}_{3}=\begin{pmatrix}0\\ -3\\ 0\\ -4\\ 1\end{pmatrix}.$

It’s useful to record a general lemma.

###### Lemma 4.11.1.

(The easy linear independence criterion). Suppose some column vectors $\mathbf{v}_{1},\ldots,\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}_{1},\ldots,\mathbf{v}_{k}$ is linearly independent.

For example, if

 $\mathbf{v}_{1}=\begin{pmatrix}1\\ 0\\ 0\\ 3\end{pmatrix},\mathbf{v}_{2}=\begin{pmatrix}4\\ 5\\ 0\\ 0\end{pmatrix},\mathbf{v}_{3}=\begin{pmatrix}7\\ 0\\ 8\\ 0\end{pmatrix}$

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.

###### Proof.

Suppose that

 $\sum_{i=1}^{k}\lambda_{i}\mathbf{v}_{i}=\mathbf{0}.$ (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},\ldots,\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}=\mathbf{0}.$

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.

###### Lemma 4.11.2.

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

###### Proof.

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.