4 Linear algebra 4.16 The rank-nullity theorem 4.18 Column space basis

4.17 Matrix nullspace basis

We are ready to prove that the fundamental solutions of $A\mathbf{x}=\mathbf{0}$ are a basis for $N(A)$ . We use the notation of Section 4.11 where we proved the fundamental solutions were linearly independent: $A$ is a $m\times n$ matrix, $R$ is a RREF matrix obtained by doing row operations to $A$ , the number of columns of $R$ with a leading entry is $r$ and the number of columns with no leading entry is $k$ , so $r+k=n$ . There are $k$ fundamental solutions to $A\mathbf{x}=\mathbf{0}$ , and we showed in Lemma 4.11.2 that these are linearly independent.

Theorem 4.17.1.

The fundamental solutions to $A\mathbf{x}=\mathbf{0}$ are a basis of the nullspace $N(A)$ .

Proof.

Consider the linear map $T_{R}:\mathbb{F}^{n}\to\mathbb{F}^{m}$ . The kernel of $T_{R}$ , which is the nullspace $N(R)$ , contains the $k$ fundamental solutions, which are linearly independent, so $\dim\ker T_{R}\geqslant k$ by Corollary 4.13.1.

The image of $T_{R}$ , which is the column space $C(R)$ , contains each of the $r$ columns of $R$ which contain a leading entry. These are standard basis vectors (by definition of RREF), so by Corollary 4.13.1 again $\dim\operatorname{im}T_{R}\geqslant r$ .

We know that $k+r=n$ , and the rank-nullity theorem says that $\dim\ker T_{R}+\dim\operatorname{im}T_{R}=n$ . So $\dim\ker T_{R}=k$ and $\dim\operatorname{im}T_{R}=r$ (if $\dim\ker T_{R}$ were strictly larger than $k$ , for example, then $\dim\ker T_{R}+\dim\operatorname{im}T_{R}$ would be strictly larger than $k+r=n$ , a contradiction).

The fundamental solutions are now $k$ linearly independent elements of the vector space $\ker T_{R}=N(R)$ , which has dimension $k$ . By 4.13.4, they are a basis of $N(R)$ . This completes the proof, because $N(A)=N(R)$ by Theorem 3.9.1. ∎