Rank–nullity theorem

"Rank theorem" redirects here. For the rank theorem of multivariable calculus, see constant rank theorem.

Rank–nullity theorem

The rank-nullity theorem is a fundamental theorem in linear algebra which relates the dimensions of a linear map's kernel and image with the dimension of its domain.

Stating the theorem

Let $V$, $W$ be vector spaces, where $V$ is finite dimensional. Let $T\colon V\to W$ be a linear transformation. Then

$\operatorname {Rank} (T)+\operatorname {Nullity} (T)=\dim V$,

where

$\operatorname {Rank} (T):=\dim \operatorname {Im} T$ and $\operatorname {Nullity} (T):=\dim \operatorname {Ker} T$.

One can refine this theorem via the splitting lemma to be a statement about an isomorphism of spaces, not just dimensions.

Matrices

Since $\operatorname {Mat} _{m\times n}(\mathbb {F} )\cong \operatorname {Hom} (\mathbb {F} ^{n},\mathbb {F} ^{m})$, matrices immediately come to mind when discussing linear maps. In the case of an $m\times n$ matrix, the dimension of the domain is $n$, the number of columns in the matrix. Thus the Rank-Nullity Theorem for a given matrix $M\in \operatorname {Mat} _{m\times n}(\mathbb {F} )$ immediately becomes

$\operatorname {Rank} (M)+\operatorname {Nullity} (M)=n$.

Proofs

Here we provide two proofs. The first operates in the general case, using linear maps. The second proof looks at the homogeneous system $\mathbf {Ax} =\mathbf {0}$ for $\mathbf {A} \in \operatorname {Mat} _{m\times n}(\mathbb {F} )$ with rank $r$ and shows explicitly that there exists a set of $n-r$ linearly independent solutions that span the kernel of $\mathbf {A}$.

While the theorem requires that the domain of the linear map be finite-dimensional, there is no such assumption on the codomain. This means that there are linear maps not given by matrices for which the theorem applies. Despite this, the first proof is not actually more general than the second: since the image of the linear map is finite-dimensional, we can represent the map from its domain to its image by a matrix, prove the theorem for that matrix, then compose with the inclusion of the image into the full codomain.

First proof

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

As $\operatorname {Ker} T\subset V$ is a subspace, there exists a basis for it. Suppose $\dim \operatorname {Ker} T=k$ and let

${\mathcal {K}}:=\{v_{1},\ldots ,v_{k}\}\subset \operatorname {Ker} (T)$

be such a basis.

We may now, by the Steinitz exchange lemma, extend ${\mathcal {K}}$ with $n-k$ linearly independent vectors $w_{1},\ldots ,w_{n-k}$ to form a full basis of $V$.

Let

${\mathcal {S}}:=\{w_{1},\ldots ,w_{n-k}\}\subset V\setminus \operatorname {Ker} (T)$

such that

${\mathcal {B}}:={\mathcal {K}}\cup {\mathcal {S}}=\{v_{1},\ldots ,v_{k},w_{1},\ldots ,w_{n-k}\}\subset V$

is a basis for $V$.

From this, we know that

$\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}})$.

We now claim that $T({\mathcal {S}})$ is a basis for $\operatorname {Im} T$. By definition, $T({\mathcal {S}})$ is generating; it remains to be shown that it is also linearly independent to conclude that it is a basis.

Let

$\sum _{j=1}^{n-k}\alpha _{j}T(w_{j})=0_{W}$

for some $\alpha _{j}\in \mathbb {F}$.

Thus, owing to the linearity of $T$, it follows that

$T\left(\sum _{j=1}^{n-k}\alpha _{j}w_{j}\right)=0_{W}\implies \left(\sum _{j=1}^{n-k}\alpha _{j}w_{j}\right)\in \operatorname {Ker} T=\operatorname {Span} {\mathcal {K}}\subset V$.

This is a contradiction to ${\mathcal {B}}$ being a basis, unless all $\alpha _{j}$ are equal to zero. This shows that $T({\mathcal {S}})$ is linearly independent, and more specifically that it is a basis for $\operatorname {Im} T$.

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

Finally we may state that

$\operatorname {Rank} (T)+\operatorname {Nullity} (T)=\dim \operatorname {Im} T+\dim \operatorname {Ker} T=|T({\mathcal {S}})|+|{\mathcal {K}}|=(n-k)+k=n=\dim V$.

This concludes our proof.

Second proof

Let $\mathbf {A} \in \operatorname {Mat} _{m\times n}(\mathbb {F} )$ with $r$ linearly independent columns (i.e. $\operatorname {Rank} (\mathbf {A} )=r$). We will show that:

1. There exists a set of $n-r$ linearly independent solutions to the homogeneous system $\mathbf {Ax} =\mathbf {0}$.
2. That every other solution is a linear combination of these $n-r$ solutions.

To do this, we will produce a matrix $\mathbf {X} \in \operatorname {Mat} _{n\times (n-r)}(\mathbb {F} )$ whose columns form a basis of the null space of $\mathbf {A}$.

Without loss of generality, assume that the first $r$ columns of $\mathbf {A}$ are linearly independent. So, we can write

$\mathbf {A} ={\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{2}\end{pmatrix}}$,

where

$\mathbf {A} _{1}\in \operatorname {Mat} _{m\times r}(\mathbb {F} )$ with $r$ linearly independent column vectors, and

$\mathbf {A} _{2}\in \operatorname {Mat} _{m\times (n-r)}(\mathbb {F} )$, each of whose $n-r$ columns are linear combinations of the columns of $\mathbf {A} _{1}$.

This means that $\mathbf {A} _{2}=\mathbf {A} _{1}\mathbf {B}$ for some $\mathbf {B} \in \operatorname {Mat} _{r\times (n-r)}$ (see rank factorization) and, hence,

$\mathbf {A} ={\begin{pmatrix}\mathbf {A} _{1}&\mathbf {A} _{1}\mathbf {B} \end{pmatrix}}$.

Let

$\mathbf {X} ={\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}$,

where $\mathbf {I} _{n-r}$ is the $(n-r)\times (n-r)$ identity matrix. We note that $\mathbf {X} \in \operatorname {Mat} _{n\times (n-r)}(\mathbb {F} )$ satisfies

$\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 $n-r$ columns of $\mathbf {X}$ are particular solutions of $\mathbf {Ax} =\mathbf {0} _{\mathbb {F} ^{m}}$.

Furthermore, the $n-r$ columns of $\mathbf {X}$ are linearly independent because $\mathbf {Xu} =\mathbf {0} _{\mathbb {F} ^{n}}$ will imply $\mathbf {u} =\mathbf {0} _{\mathbb {F} ^{n}}$ for $\mathbf {u} \in \mathbb {F} ^{n-r}$:

$\mathbf {X} \mathbf {u} =\mathbf {0} _{\mathbb {F} ^{n}}\implies {\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}\mathbf {u} =\mathbf {0} _{\mathbb {F} ^{n}}\implies {\begin{pmatrix}-\mathbf {B} \mathbf {u} \\\mathbf {u} \end{pmatrix}}={\begin{pmatrix}\mathbf {0} _{\mathbb {F} ^{r}}\\\mathbf {0} _{\mathbb {F} ^{n-r}}\end{pmatrix}}\implies \mathbf {u} =\mathbf {0} _{\mathbb {F} ^{n-r}}.$

Therefore, the column vectors of $\mathbf {X}$ constitute a set of $n-r$ linearly independent solutions for $\mathbf {Ax} =\mathbf {0} _{\mathbb {F} ^{m}}$.

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

For this, let

$\mathbf {u} ={\begin{pmatrix}\mathbf {u} _{1}\\\mathbf {u} _{2}\end{pmatrix}}\in \mathbb {F} ^{n}$

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

Therefore,

${\begin{array}{rcl}\mathbf {A} \mathbf {u} &=&\mathbf {0} _{\mathbb {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} _{\mathbb {F} ^{r}}\\\implies \mathbf {u} _{1}&=&-\mathbf {B} \mathbf {u} _{2}\end{array}}$

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

Reformulations and generalizations

This theorem is a statement of the first isomorphism theorem of algebra for the case of vector spaces; it generalizes to the splitting lemma.

In more modern language, the theorem can also be phrased as follows: if

0 → U → V → R → 0

is a short exact sequence of vector spaces, then

$\dim(U)+\dim(R)=\dim(V)$.

Here R plays the role of im T and U is ker T, i.e.

$0\rightarrow \ker T~{\overset {Id}{\rightarrow }}~V~{\overset {T}{\rightarrow }}~\operatorname {im} T\rightarrow 0$

In the finite-dimensional case, this formulation is susceptible to a generalization: if

0 → V₁ → V₂ → ... → V_r → 0

is an exact sequence of finite-dimensional vector spaces, then

$\sum _{i=1}^{r}(-1)^{i}\dim(V_{i})=0.$

The rank–nullity theorem for finite-dimensional vector spaces may also be formulated in terms of the index of a linear map. The index of a linear map $T\in \operatorname {Hom} (V,W)$, where $V$ and $W$ are finite-dimensional, is defined by

$\operatorname {index} T=\dim \operatorname {Ker} (T)-\dim \operatorname {Coker} T$.

Intuitively, $\dim \operatorname {Ker} T$ is the number of independent solutions $v$ of the equation $Tv=0$, and $\dim \operatorname {Coker} T$ is the number of independent restrictions that have to be put on $w$ to make $Tv=w$ solvable. The rank–nullity theorem for finite-dimensional vector spaces is equivalent to the statement

$\operatorname {index} T=\dim V-\dim W$.

We see that we can easily read off the index of the linear map $T$ from the involved spaces, without any need to analyze $T$ in detail. This effect also occurs in a much deeper result: the Atiyah–Singer index theorem states that the index of certain differential operators can be read off the geometry of the involved spaces.

References

• Banerjee, Sudipto; Roy, Anindya (2014), Linear Algebra and Matrix Analysis for Statistics, Texts in Statistical Science (1st ed.), Chapman and Hall/CRC, ISBN 978-1420095388
• Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8.