4 Linear algebra 4.10 Basis and dimension examples 4.12 Extending to a basis

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)$ . ¹¹ 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}<c_{2}<\cdots<c_{r}$ and the columns with no leading entry be $d_{1}<d_{2}<\cdots<d_{k}$ . 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.