# 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. ∎