Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

The rank-nullity theorem

by , PhD

The rank-nullity theorem states that the dimension of the domain of a linear function is equal to the sum of the dimensions of its range (i.e., the set of values in the codomain that the function actually takes) and kernel (i.e., the set of values in the domain that are mapped to the zero vector in the codomain).

Table of Contents

Linear function

First of all, we need to define a linear map $f:S
ightarrow T$ between two vector spaces $S$ and $T$, that is, a function such that[eq1]for any two vectors $s_{1},s_{2}in S$ and any two scalars $lpha _{1}$ and $lpha _{2}$.

Domain

The set $S$ is called the domain of $f$.

Being a vector space, the domain $S$ has a dimension, denoted by[eq2]which is equal to the number of elements of a basis of $S$ (any basis; remember that all the bases of a space have the same number of elements).

Rank

The range (or image) of $f$ is the subset of the codomain $T$ that comprises all the values taken by $fleft( s
ight) $ as $s$ varies over $S$:[eq3]

As we proved in the lecture on the range of a linear map, $QTR{rm}{range}f$ is a subspace of $T$. Its dimension is called rank and is denoted by[eq4]

Nullity

The null space (or kernel) of $f$ is the subset of the domain $S$ that comprises all the values mapped by $f$ into the zero vector of $T$:[eq5]

As we proved in the lecture on the null space of a linear map, $QTR{rm}{null}f$ is a subspace of $T$. Its dimension is called nullity and is denoted by[eq6]

The theorem

Here comes one of the most important theorems in linear algebra, called rank-nullity theorem.

Proposition Let $S$ and $T$ be two linear spaces. Let $f:S
ightarrow T$ be a linear map. If [eq7] is finite, then [eq8]

Proof

Let [eq9]and choose a basis [eq10] for $QTR{rm}{null}f$. Let[eq11]and choose a basis [eq12] for $S$. By the basis extension theorem, we can form a new basis for $S$ that contains [eq10]:[eq14]possibly after re-numbering the vectors of the basis [eq15]. Any $sin S$ can be uniquely written as a linear combination of the basis above:[eq16]where [eq17] are scalars. Then, we have[eq18]where in step $rame{A}$ we have used the fact that [eq10] belong to the null space of $f$ and, as a consequence, [eq20]. The equation just derived holds for any $sin S$, which implies that $QTR{rm}{range}f$ is spanned by the $N-K$ vectors[eq21]We need to prove that these vectors are linearly independent. By contradiction, suppose they are not. Then, they can be linearly combined so as to obtain the zero vector:[eq22]where [eq23] are the coefficients of the linear combination (not all equal to zero). By the linearity of $f$, we have that[eq24]which means that the vector[eq25]belongs to $QTR{rm}{null}f$. Since [eq10] is a basis for $QTR{rm}{null}f$, we can write the latter vector as a linear combination of [eq27] with coefficients [eq28]:[eq29]or[eq30]Thus, there is a linear combination of the basis of $S$, with coefficients not all equal to zero, that gives the zero vector as a result. This is impossible because the elements of a basis are linearly independent. Therefore, we have arrived at a contradiction, which means that the $N-K$ vectors[eq31]must be linearly independent. We have already proved that they span $QTR{rm}{range}f$. So, we conclude that they are a basis for $QTR{rm}{range}f$. Hence,[eq32]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

As we demonstrated in the lecture on linear maps, a linear map $f:S
ightarrow T$ is completely specified by the values taken by $f$ on a basis for $S$.

Let [eq33] be a basis for $S$ and [eq34] be a basis for $T$.

Specify the function $f$ as follows:[eq35]

Find the dimensions of $S$ and $QTR{rm}{range}f$ and then use the rank-nullity theorem to find the nullity of $f$.

Solution

Since there are three vectors in the basis $B$, we have that[eq36]Any vector $sin S$ can be written as a linear combination[eq37]where [eq38] are scalars. The transformed vectors[eq39]can be written as linear combinations of $c_{1}$ and $c_{3}$. As a consequence, [eq40] is a basis for $QTR{rm}{range}f$. Therefore,[eq41]To conclude, we get[eq42]

How to cite

Please cite as:

Taboga, Marco (2017). "The rank-nullity theorem", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/rank-nullity-theorem.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.