Rank–nullity theorem explained

The rank–nullity theorem is a theorem in linear algebra, which asserts:

• the number of columns of a matrix is the sum of the rank of and the nullity of ; and
• the dimension of the domain of a linear transformation is the sum of the rank of (the dimension of the image of) and the nullity of (the dimension of the kernel of).^{[1] [2] [3] [4]}

It follows that for linear transformations of vector spaces of equal finite dimension, either injectivity or surjectivity implies bijectivity.

Stating the theorem

Linear transformations

Let

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

Matrices

Linear maps can be represented with matrices. More precisely, an

m x n matrix represents a linear map f:F ^{n\to} F ^{m,} where F is the underlying field.^[5] So, the dimension of the domain of f is, the number of columns of, and the rank–nullity theorem for an m x n matrix is$$\backslash operatorname(M)\; +\; \backslash operatorname(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

Ax = 0 , where A is a m x n with rank r, and shows explicitly that there exists a set of n - r linearly independent solutions that span the null space of 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 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$$\backslash mathcal\; :=\; \backslash \; \backslash subset\; \backslash operatorname(T)$$be such a basis.

We may now, by the Steinitz exchange lemma, extend

l{K} with n - k linearly independent vectors w _{1,} \ldots, w _{n-k} to form a full basis of V .

Let$$\backslash mathcal\; :=\; \backslash \; \backslash subset\; V\; \backslash setminus\; \backslash operatorname(T)$$such that$$\backslash mathcal\; :=\; \backslash mathcal\; \backslash cup\; \backslash mathcal\; =\; \backslash \; \backslash subset\; V$$is a basis for

V .From this, we know that$$\backslash operatorname\; T\; =\; \backslash operatornameT(\backslash mathcal)\; =\; \backslash operatorname\backslash$$= \operatorname{Span}\{T(w _{1),} \ldots, T(w _{n-k} )\} = \operatorname{Span}T( l{S}) . We now claim that T( l{S}) is a basis for \operatorname{Im} T .The above equality already states that T( l{S}) is a generating set for \operatorname{Im} T ; it remains to be shown that it is also linearly independent to conclude that it is a basis.

Suppose

T( l{S}) is not linearly independent, and let$$\backslash sum\_^\; \backslash alpha\; \_j\; T(w\_j)\; =\; 0\_W$$for some \alpha _{j} \in F .

Thus, owing to the linearity of

T , it follows that$$T\; \backslash left(\backslash sum\_^\; \backslash alpha\; \_j\; w\_j\; \backslash right)\; =\; 0\_W\; \backslash implies\; \backslash left(\backslash sum\_^\; \backslash alpha\; \_j\; w\_j\; \backslash right)\; \backslash in\; \backslash operatorname\; T\; =\; \backslash operatorname\; \backslash mathcal\; \backslash subset\; V\; .$$This is a contradiction to l{B} being a basis, unless all \alpha _{j} are equal to zero. This shows that T( l{S}) is linearly independent, and more specifically that it is a basis for \operatorname{Im}T .

To summarize, we have

l{K} , a basis for \operatorname{Ker}T , and T( l{S}) , a basis for \operatorname{Im}T .

Finally we may state that$$\backslash operatorname(T)\; +\; \backslash operatorname(T)\; =\; \backslash dim\; \backslash operatorname\; T\; +\; \backslash dim\; \backslash operatornameT$$

= |T( l{S})| + | l{K}| = (n - k) + k = n = \dim V . This concludes our proof.

Second proof

Let

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

To do this, we will produce an

n x (n - r) 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 writewhereA _{1} is an m x r matrix with r linearly independent column vectors, andA _{2} is an m x (n - r) matrix such that each of its n - r columns is linear combinations of the columns of A _{1} .

This means that

A _{2} = A _{1B} for some r x (n - r) matrix B (see rank factorization) and, hence,

Let$$\backslash mathbf\; =\; \backslash begin\; -\backslash mathbf\; \backslash \backslash \; \backslash mathbf\_\; \backslash end,$$where

I _{n-r} is the (n - r) x (n - r) identity matrix. So, X is an n x (n - r) matrix such that

Therefore, each of the

n - r columns of X are particular solutions of Ax = { 0 } ^{m} _{{F} }.

Furthermore, the

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

We next prove that any solution of

Ax = 0 ^{m} _{{F} } must be a linear combination of the columns of X .

For this, let$$\backslash mathbf\; =\; \backslash begin\; \backslash mathbf\_1\; \backslash \backslash \; \backslash mathbf\_2\backslash end\; \backslash in\; ^$$

be any vector such that

Au = 0 ^{m} _{{F} }. Since the columns of A _{1} are linearly independent, A _{1x} = 0 ^{m} _{{F} } implies x = 0 ^{r} _{{F} }.

Therefore,$$\backslash implies\; \backslash mathbf\; =\; \backslash begin\; \backslash mathbf\_1\; \backslash \backslash \; \backslash mathbf\_2\; \backslash end=\; \backslash begin\; -\backslash mathbf\; \backslash \backslash \; \backslash mathbf\_\; \backslash end\backslash mathbf\_2=\; \backslash mathbf\backslash mathbf\_2.$$

This proves that any vector

u that is a solution of Ax = 0 must be a linear combination of the n - r 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 n - r . Since r equals rank of A , it follows that \operatorname{Rank}( A ) + \operatorname{Nullity}( A ) = n . This concludes our proof.

A third fundamental subspace

When

T: V \to W is a linear transformation between two finite-dimensional subspaces, with n = \dim(V) and m = \dim(W) (so can be represented by an m x n matrix M ), the rank–nullity theorem asserts that if T has rank r , then n - r is the dimension of the null space of M , which represents the kernel of T . In some texts, a third fundamental subspace associated to T is considered alongside its image and kernel: the cokernel of T is the quotient space W / \operatorname{Im}(T) , and its dimension is m - r . This dimension formula (which might also be rendered \dim \operatorname{Im}(T) + \dim\operatorname{Coker}(T) = \dim(W) ) together with the rank–nullity theorem is sometimes called the fundamental theorem of linear algebra.^[6]

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 saying that each short exact sequence of vector spaces splits. Explicitly, given that$$0\; \backslash rightarrow\; U\; \backslash rightarrow\; V\; \backslash mathbin\; R\; \backslash rightarrow\; 0$$is a short exact sequence of vector spaces, then

U ⊕ R \cong V , hence$$\backslash dim(U)\; +\; \backslash dim(R)\; =\; \backslash dim(V)\; .$$Here R plays the role of \operatorname{Im} T and U is \operatorname{Ker}T , i.e.$$0\; \backslash rightarrow\; \backslash ker\; T\; \backslash mathbin\; V\; \backslash mathbin\; \backslash operatorname\; T\; \backslash rightarrow\; 0$$

In the finite-dimensional case, this formulation is susceptible to a generalization: if$$0\; \backslash rightarrow\; V\_1\; \backslash rightarrow\; V\_2\; \backslash rightarrow\; \backslash cdots\; V\_r\; \backslash rightarrow\; 0$$is an exact sequence of finite-dimensional vector spaces, then^[7] $$\backslash sum\_^r\; (-1)^i\backslash 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$$\backslash operatorname\; T\; =\; \backslash dim\; \backslash operatorname(T)\; -\; \backslash dim\; \backslash operatorname\; 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$$\backslash operatorname\; T\; =\; \backslash dim\; V\; -\; \backslash 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

• Book: Axler, Sheldon. Linear Algebra Done Right. Springer. 2015. 978-3-319-11079-0. 3rd. Undergraduate Texts in Mathematics. Sheldon Axler.
  • Book: Friedberg. Stephen H.. Linear Algebra. Insel. Arnold J.. Spence. Lawrence E.. Pearson Education. 2014. 978-0130084514. 4th.
• .
• Book: Katznelson. Yitzhak. A (Terse) Introduction to Linear Algebra. Katznelson. Yonatan R.. 2008. American Mathematical Society. 978-0-8218-4419-9. 2008. Yitzhak Katznelson.
• Book: Valenza, Robert J.. Linear Algebra: An Introduction to Abstract Mathematics. Springer. 1993. 3-540-94099-5. 3rd. Undergraduate Texts in Mathematics. 1951.

External links

• , MIT Linear Algebra Lecture on the Four Fundamental Subspaces, from MIT OpenCourseWare

Notes and References

1. p. 63, §3.22
2. p. 70, §2.1, Theorem 2.3
3. p. 52, §2.5.1
4. p. 71, §4.3
5. pp. 103-104, §2.4, Theorem 2.20
6. • Strang, Gilbert. Linear Algebra and Its Applications. 3rd ed. Orlando: Saunders, 1988.
7. Web site: Zaman. Ragib. Dimensions of vector spaces in an exact sequence. 27 October 2015. Mathematics Stack Exchange. DimVS.