Rank–nullity theorem

Let ${\displaystyle T:V\to W}$ be a linear transformation between two vector spaces where ${\displaystyle T}$'s domain ${\displaystyle V}$ is finite dimensional. Then $${\displaystyle \operatorname {rank} (T)~+~\operatorname {nullity} (T)~=~\dim V,}$$ where ${\textstyle \operatorname {rank} (T)}$ is the rank of ${\displaystyle T}$ (the dimension of its image) and ${\displaystyle \operatorname {nullity} (T)}$ is the nullity of ${\displaystyle T}$ (the dimension of its kernel). In other words, $${\displaystyle \dim(\operatorname {Im} T)+\dim(\operatorname {Ker} T)=\dim(\operatorname {Domain} (T)).}$$ This theorem can be refined via the splitting lemma to be a statement about an isomorphism of spaces, not just dimensions. Explicitly, since ${\displaystyle T}$ induces an isomorphism from ${\displaystyle V/\operatorname {Ker} (T)}$ to ${\displaystyle \operatorname {Im} (T),}$ the existence of a basis for ${\displaystyle V}$ that extends any given basis of ${\displaystyle \operatorname {Ker} (T)}$ implies, via the splitting lemma, that ${\displaystyle \operatorname {Im} (T)\oplus \operatorname {Ker} (T)\cong V.}$ Taking dimensions, the rank–nullity theorem follows.

Linear maps can be represented with matrices. More precisely, an ${\displaystyle m\times n}$ matrix M represents a linear map ${\displaystyle f:F^{n}\to F^{m},}$ where ${\displaystyle F}$ is the underlying field.^[5] So, the dimension of the domain of ${\displaystyle f}$ is n, the number of columns of M, and the rank–nullity theorem for an ${\displaystyle m\times n}$ matrix M is $${\displaystyle \operatorname {rank} (M)+\operatorname {nullity} (M)=n.}$$

Let ${\displaystyle V,W}$ be vector spaces over some field ${\displaystyle F,}$ and ${\displaystyle T}$ defined as in the statement of the theorem with ${\displaystyle \dim V=n}$.

As ${\displaystyle \operatorname {Ker} T\subset V}$ is a subspace, there exists a basis for it. Suppose ${\displaystyle \dim \operatorname {Ker} T=k}$ and let $${\displaystyle {\mathcal {K}}:=\{v_{1},\ldots ,v_{k}\}\subset \operatorname {Ker} (T)}$$ be such a basis.

By the Steinitz exchange lemma, there is a linearly independent set ${\displaystyle {\mathcal {S}}=\{w_{1},\ldots ,w_{n-k}\}}$ of ${\displaystyle n-k}$ vectors such that the union ${\displaystyle {\mathcal {B}}={\mathcal {K}}\cup {\mathcal {S}}=\{v_{1},\ldots ,v_{k},w_{1},\ldots ,w_{n-k}\}}$ is a basis of ${\displaystyle V}$. From this, it follows $${\displaystyle {\begin{aligned}\operatorname {Im} T&=\operatorname {Span} T({\mathcal {B}})=\operatorname {Span} \{T(v_{1}),\ldots ,T(v_{k}),T(w_{1}),\ldots ,T(w_{n-k})\}\\&=\operatorname {Span} \{T(w_{1}),\ldots ,T(w_{n-k})\}=\operatorname {Span} T({\mathcal {S}}).\end{aligned}}}$$ We now claim that ${\displaystyle T({\mathcal {S}})}$ is a basis for ${\displaystyle \operatorname {Im} T}$. The above equality already states that ${\displaystyle T({\mathcal {S}})}$ is a generating set for ${\displaystyle \operatorname {Im} T}$; it remains to be shown that it is also linearly independent to conclude that it is a basis.

To this end, consider a linear combination $${\displaystyle \sum _{j=1}^{n-k}\alpha _{j}T(w_{j})=0_{W}}$$ for some ${\displaystyle \alpha _{j}\in F}$. We must show that all the coefficients ${\displaystyle \alpha _{j}}$ are equal to ${\displaystyle 0}$. Owing to the linearity of ${\displaystyle T}$, it follows that $${\displaystyle T\left(\sum _{j=1}^{n-k}\alpha _{j}w_{j}\right)=0_{W},}$$ and therefore that $${\displaystyle \left(\sum _{j=1}^{n-k}\alpha _{j}w_{j}\right)\in \operatorname {Ker} T=\operatorname {Span} {\mathcal {K}}.}$$ Therefore, there are coefficents ${\displaystyle \beta _{1},\ldots ,\beta _{k}}$ such that ${\displaystyle \sum _{j=1}^{n-k}\alpha _{j}w_{j}=\sum _{i=1}^{k}\beta _{i}v_{i}}$, and so that ${\displaystyle \sum _{j=1}^{n-k}\alpha _{j}w_{j}-\sum _{i=1}^{k}\beta _{i}v_{i}=0_{V}}$. This last relation expresses ${\displaystyle 0_{V}}$ as a linear combination of the basis ${\displaystyle {\mathcal {B}}}$; since ${\displaystyle {\mathcal {B}}}$ is a basis, all the coefficients ${\displaystyle \alpha _{j}}$ are equal to zero. This shows that ${\displaystyle T({\mathcal {S}})}$ is linearly independent, and more specifically that it is a basis for ${\displaystyle \operatorname {Im} T}$.

To summarize, we have ${\displaystyle {\mathcal {K}}}$, a basis for ${\displaystyle \operatorname {Ker} T}$, and ${\displaystyle T({\mathcal {S}})}$, a basis for ${\displaystyle \operatorname {Im} T}$.

Finally we may state that $${\displaystyle \operatorname {Rank} (T)+\operatorname {Nullity} (T)=\dim \operatorname {Im} T+\dim \operatorname {Ker} T}$$

${\displaystyle =|T({\mathcal {S}})|+|{\mathcal {K}}|=(n-k)+k=n=\dim V.}$

This concludes our proof.

Let ${\displaystyle \mathbf {A} }$ be an ${\displaystyle m\times n}$ matrix with ${\displaystyle r}$linearly independent columns (i.e. ${\displaystyle \operatorname {Rank} (\mathbf {A} )=r}$). We will show that:

To do this, we will produce an ${\displaystyle n\times (n-r)}$ matrix ${\displaystyle \mathbf {X} }$ whose columns form a basis of the null space of ${\displaystyle \mathbf {A} }$.

Without loss of generality, assume that the first ${\displaystyle r}$ columns of ${\displaystyle \mathbf {A} }$ are linearly independent. So, we can write $${\displaystyle \mathbf {A} ={\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{2}\end{pmatrix}},}$$ where

• ${\displaystyle \mathbf {A} _{1}}$ is an ${\displaystyle m\times r}$ matrix with ${\displaystyle r}$ linearly independent column vectors, and
• ${\displaystyle \mathbf {A} _{2}}$ is an ${\displaystyle m\times (n-r)}$ matrix such that each of its ${\displaystyle n-r}$ columns is linear combinations of the columns of ${\displaystyle \mathbf {A} _{1}}$.

This means that ${\displaystyle \mathbf {A} _{2}=\mathbf {A} _{1}\mathbf {B} }$ for some ${\displaystyle r\times (n-r)}$ matrix ${\displaystyle \mathbf {B} }$ (see rank factorization) and, hence, $${\displaystyle \mathbf {A} ={\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{1}\mathbf {B} \end{pmatrix}}.}$$

Let $${\displaystyle \mathbf {X} ={\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}},}$$ where ${\displaystyle \mathbf {I} _{n-r}}$ is the ${\displaystyle (n-r)\times (n-r)}$identity matrix. So, ${\displaystyle \mathbf {X} }$ is an ${\displaystyle n\times (n-r)}$ matrix such that $${\displaystyle \mathbf {A} \mathbf {X} ={\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{1}\mathbf {B} \end{pmatrix}}{\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}=-\mathbf {A} _{1}\mathbf {B} +\mathbf {A} _{1}\mathbf {B} =\mathbf {0} _{m\times (n-r)}.}$$

Therefore, each of the ${\displaystyle n-r}$ columns of ${\displaystyle \mathbf {X} }$ are particular solutions of ${\displaystyle \mathbf {Ax} ={0}_{{F}^{m}}}$.

Furthermore, the ${\displaystyle n-r}$ columns of ${\displaystyle \mathbf {X} }$ are linearly independent because ${\displaystyle \mathbf {Xu} =\mathbf {0} _{{F}^{n}}}$ will imply ${\displaystyle \mathbf {u} =\mathbf {0} _{{F}^{n-r}}}$ for ${\displaystyle \mathbf {u} \in {F}^{n-r}}$: $${\displaystyle \mathbf {X} \mathbf {u} =\mathbf {0} _{{F}^{n}}\implies {\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}\mathbf {u} =\mathbf {0} _{{F}^{n}}\implies {\begin{pmatrix}-\mathbf {B} \mathbf {u} \\\mathbf {u} \end{pmatrix}}={\begin{pmatrix}\mathbf {0} _{{F}^{r}}\\\mathbf {0} _{{F}^{n-r}}\end{pmatrix}}\implies \mathbf {u} =\mathbf {0} _{{F}^{n-r}}.}$$ Therefore, the column vectors of ${\displaystyle \mathbf {X} }$ constitute a set of ${\displaystyle n-r}$ linearly independent solutions for ${\displaystyle \mathbf {Ax} =\mathbf {0} _{\mathbb {F} ^{m}}}$.

We next prove that any solution of ${\displaystyle \mathbf {Ax} =\mathbf {0} _{{F}^{m}}}$ must be a linear combination of the columns of ${\displaystyle \mathbf {X} }$.

For this, let $${\displaystyle \mathbf {u} ={\begin{pmatrix}\mathbf {u} _{1}\\\mathbf {u} _{2}\end{pmatrix}}\in {F}^{n}}$$

be any vector such that ${\displaystyle \mathbf {Au} =\mathbf {0} _{{F}^{m}}}$. Since the columns of ${\displaystyle \mathbf {A} _{1}}$ are linearly independent, ${\displaystyle \mathbf {A} _{1}\mathbf {x} =\mathbf {0} _{{F}^{m}}}$ implies ${\displaystyle \mathbf {x} =\mathbf {0} _{{F}^{r}}}$.

Therefore, $${\displaystyle {\begin{array}{rcl}\mathbf {A} \mathbf {u} &=&\mathbf {0} _{{F}^{m}}\\\implies {\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{1}\mathbf {B} \end{pmatrix}}{\begin{pmatrix}\mathbf {u} _{1}\\\mathbf {u} _{2}\end{pmatrix}}&=&\mathbf {A} _{1}\mathbf {u} _{1}+\mathbf {A} _{1}\mathbf {B} \mathbf {u} _{2}&=&\mathbf {A} _{1}(\mathbf {u} _{1}+\mathbf {B} \mathbf {u} _{2})&=&\mathbf {0} _{\mathbb {F} ^{m}}\\\implies \mathbf {u} _{1}+\mathbf {B} \mathbf {u} _{2}&=&\mathbf {0} _{{F}^{r}}\\\implies \mathbf {u} _{1}&=&-\mathbf {B} \mathbf {u} _{2}\end{array}}}$$$${\displaystyle \implies \mathbf {u} ={\begin{pmatrix}\mathbf {u} _{1}\\\mathbf {u} _{2}\end{pmatrix}}={\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}\mathbf {u} _{2}=\mathbf {X} \mathbf {u} _{2}.}$$

This proves that any vector ${\displaystyle \mathbf {u} }$ that is a solution of ${\displaystyle \mathbf {Ax} =\mathbf {0} }$ must be a linear combination of the ${\displaystyle n-r}$ special solutions given by the columns of ${\displaystyle \mathbf {X} }$. And we have already seen that the columns of ${\displaystyle \mathbf {X} }$ are linearly independent. Hence, the columns of ${\displaystyle \mathbf {X} }$ constitute a basis for the null space of ${\displaystyle \mathbf {A} }$. Therefore, the nullity of ${\displaystyle \mathbf {A} }$ is ${\displaystyle n-r}$. Since ${\displaystyle r}$ equals rank of ${\displaystyle \mathbf {A} }$, it follows that ${\displaystyle \operatorname {Rank} (\mathbf {A} )+\operatorname {Nullity} (\mathbf {A} )=n}$. This concludes our proof.