# Rank–nullity theorem

{{#invoke:Hatnote|hatnote}}Template:Main other {{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}

In mathematics, the rank–nullity theorem of linear algebra, in its simplest form, states that the rank and the nullity of a matrix add up to the number of columns of the matrix. Specifically, if A is an m-by-n matrix (with m rows and n columns) over some field, then[1]

${\displaystyle \operatorname {rk} (A)+\operatorname {nul} (A)=n.}$

This applies to linear maps as well. Let V and W be vector spaces over some field and let T : VW be a linear map. Then the rank of T is the dimension of the image of T and the nullity of T is the dimension of the kernel of T, so we have

${\displaystyle \operatorname {dim} (\operatorname {im} (T))+\operatorname {dim} (\operatorname {ker} (T))=\operatorname {dim} (V),}$

or, equivalently,

${\displaystyle \operatorname {rk} (T)+\operatorname {nul} (T)=\operatorname {dim} (V).}$

One can refine this statement (via the splitting lemma or the below proof) to be a statement about an isomorphism of spaces, not just dimensions.

More generally, one can consider the image, kernel, coimage, and cokernel, which are related by the fundamental theorem of linear algebra.

## Proofs

We give two proofs. The first proof uses notations for linear transformations, but can be easily adapted to matrices by writing T(x) = Ax, where A is m × n. The second proof looks at the homogeneous system Ax = 0 associated with an m × n matrix A of rank r and shows explicitly that there exist a set of nr linearly independent solutions that span the null space of A.

First proof: Suppose ${\displaystyle \{\mathbf {u} _{1},\ldots ,\mathbf {u} _{m}\}}$ forms a basis of ker T. We can extend this to form a basis of V: ${\displaystyle \{{\mathbf {u} }_{1},\ldots ,{\mathbf {u} }_{m},{\mathbf {w} }_{1},\ldots ,{\mathbf {w} }_{n}\}}$. Since the dimension of ker T is m and the dimension of V is m + n, it suffices to show that the dimension of im T is n.

Let us see that ${\displaystyle \{T\mathbf {w} _{1},\ldots ,T\mathbf {w} _{n}\}}$ is a basis of im T. Let v be an arbitrary vector in V. There exist unique scalars such that:

${\displaystyle {\mathbf {v} }=a_{1}{\mathbf {u} }_{1}+\cdots +a_{m}{\mathbf {u} }_{m}+b_{1}{\mathbf {w} }_{1}+\cdots +b_{n}{\mathbf {w} }_{n}}$
${\displaystyle \Rightarrow T\mathbf {v} =a_{1}T\mathbf {u} _{1}+\cdots +a_{m}T\mathbf {u} _{m}+b_{1}T\mathbf {w} _{1}+\cdots +b_{n}T\mathbf {w} _{n}}$
${\displaystyle \Rightarrow T\mathbf {v} =b_{1}T\mathbf {w} _{1}+\cdots +b_{n}T\mathbf {w} _{n}\;\;\because T\mathbf {u} _{i}=0}$

We only now need to show that this list is not redundant; that is, that ${\displaystyle \{T\mathbf {w} _{1},\ldots ,T\mathbf {w} _{n}\}}$ are linearly independent. We can do this by showing that a linear combination of these vectors is zero if and only if the coefficient on each vector is zero. Let:

${\displaystyle c_{1}T{\mathbf {w} }_{1}+\cdots +c_{n}T{\mathbf {w} }_{n}=0\Leftrightarrow T\{c_{1}{\mathbf {w} }_{1}+\cdots +c_{n}{\mathbf {w} }_{n}\}=0}$
${\displaystyle \therefore c_{1}{\mathbf {w} }_{1}+\cdots +c_{n}{\mathbf {w} }_{n}\in \operatorname {ker} \;T}$

Then, since ui span ker T, there exists a set of scalars di such that:

${\displaystyle c_{1}{\mathbf {w} }_{1}+\cdots +c_{n}{\mathbf {w} }_{n}=d_{1}{\mathbf {u} }_{1}+\cdots +d_{m}{\mathbf {u} }_{m}}$

But, since ${\displaystyle \{{\mathbf {u} }_{1},\ldots ,{\mathbf {u} }_{m},{\mathbf {w} }_{1},\ldots ,{\mathbf {w} }_{n}\}}$ form a basis of V, all ci, di must be zero. Therefore, ${\displaystyle \{T\mathbf {w} _{1},\ldots ,T\mathbf {w} _{n}\}}$ is linearly independent and indeed a basis of im T. This proves that the dimension of im T is n, as desired.

In more abstract terms, the map T : V → im T splits.

Second proof: Let A be an m × n matrix with r linearly independent columns (i.e. rank of A is r). We will show that: (i) there exists a set of nr linearly independent solutions to the homogeneous system Ax = 0, and (ii) that every other solution is a linear combination of these nr solutions. In other words, we will produce an n × (nr) matrix X whose columns form a basis of the null space of A.

Without loss of generality, assume that the first r columns of A are linearly independent. So, we can write A = [A1:A2], where A1 is m × r with r linearly independent column vectors and A2 is m × (nr), each of whose nr columns are linear combinations of the columns of A1. This means that A2 = A1 B for some r × (nr) matrix B (see rank factorization) and, hence, A = [A1:A1B]. Let ${\displaystyle \displaystyle {\mathbf {X} }={\begin{pmatrix}-{\mathbf {B} }\\{\mathbf {I} }_{n-r}\end{pmatrix}}}$, where ${\displaystyle \mathbf {I} _{n-r}}$ is the (nr) × (nr) identity matrix. We note that X is an n × (nr) matrix that satisfies

${\displaystyle \mathbf {A} \mathbf {X} =[\mathbf {A} _{1}:\mathbf {A} _{1}\mathbf {B} ]{\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}=-\mathbf {A} _{1}\mathbf {B} +\mathbf {A} _{1}\mathbf {B} =\mathbf {O} \;.}$

Therefore, each of the nr columns of X are particular solutions of Ax = 0. Furthermore, the nr columns of X are linearly independent because Xu = 0 will imply u = 0:

${\displaystyle \mathbf {X} \mathbf {u} =\mathbf {0} \Rightarrow {\begin{pmatrix}-\mathbf {B} \\\mathbf {I} _{n-r}\end{pmatrix}}\mathbf {u} =\mathbf {0} \Rightarrow {\begin{pmatrix}-\mathbf {B} \mathbf {u} \\\mathbf {u} \end{pmatrix}}={\begin{pmatrix}\mathbf {0} \\\mathbf {0} \end{pmatrix}}\Rightarrow \mathbf {u} =\mathbf {0} \;.}$

Therefore, the column vectors of X constitute a set of nr linearly independent solutions for Ax = 0.

We next prove that any solution of Ax = 0 must be a linear combination of the columns of X For this, let ${\displaystyle \displaystyle {\mathbf {u} }={\begin{pmatrix}{\mathbf {u} }_{1}\\{\mathbf {u} }_{2}\end{pmatrix}}}$ be any vector such that Au = 0. Note that since the columns of A1 are linearly independent, A1x = 0 implies x = 0. Therefore,

${\displaystyle {\mathbf {A} }{\mathbf {u} }={\mathbf {0} }\Rightarrow [{\mathbf {A} }_{1}:{\mathbf {A} }_{1}{\mathbf {B} }]{\begin{pmatrix}{\mathbf {u} }_{1}\\{\mathbf {u} }_{2}\end{pmatrix}}={\mathbf {0} }\Rightarrow {\mathbf {A} }_{1}({\mathbf {u} }_{1}+{\mathbf {B} }{\mathbf {u} }_{2})={\mathbf {0} }\Rightarrow {\mathbf {u} }_{1}+{\mathbf {B} }{\mathbf {u} }_{2}={\mathbf {0} }\Rightarrow {\mathbf {u} }_{1}=-{\mathbf {B} }{\mathbf {u} }_{2}}$
${\displaystyle \Rightarrow \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 u that is a solution of Ax = 0 must be a linear combination of the nr special solutions given by the columns of X. And we have already seen that the columns of X are linearly independent. Hence, the columns of X constitute a basis for the null space of A. Therefore, the nullity of A is nr. Since r equals rank of A, it follows that rk(A) + nul(A) = n. QED.

## Reformulations and generalizations

This theorem is a statement of the first isomorphism theorem of algebra to 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 → UVR → 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.

${\displaystyle 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 → V1V2 → ... → Vr → 0

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

${\displaystyle \sum _{i=1}^{r}(-1)^{i}\dim(V_{i})=0.}${{ safesubst:#invoke:Unsubst||date=__DATE__ |\$B=

{{#invoke:Category handler|main}}{{#invoke:Category handler|main}}[citation needed] }}

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 : VW, where V and W are finite-dimensional, is defined by

index T = dim(ker T) − dim(coker T).

Intuitively, dim(ker T) is the number of independent solutions x of the equation Tx = 0, and dim(coker T) is the number of independent restrictions that have to be put on y to make Tx = y solvable. The rank–nullity theorem for finite-dimensional vector spaces is equivalent to the statement

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.

## Notes

1. Template:Harvtxt, page 199.

## References

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}.