nLab rank-nullity theorem

Idea

In linear algebra, what is known as the rank-nullity theorem (e.g. 3.22 of Axler 2015, who calls it the fundamental theorem of linear maps) is the statement that for any linear map $f \colon V \to W$ out of a finite-dimensional vector space, the sum of

• the rank $rk(f) \coloneqq dim\big(im(f)\big)$, i.e. the dimension of the image;

with

• the nullity $nl(f) \coloneqq dim\big( ker(f) \big)$, i.e. the dimension of the kernel

equals

• the dimension $d_V \coloneqq dim(V)$ of the domain space $V$:

(1)$$d_V \;=\; rk(f) + nl(f) \,.$$

This rank-nullity theorem is the decategorification (under the dimension functor $dim \colon FinDimVect \to \mathbb{Z}$) of the stronger statement that $V$ itself is the direct sum of its kernel and image vector spaces:

$$V \;\simeq\; im(f) \oplus ker(f) \,.$$

This may be understood as an instance of the splitting lemma for vector spaces, or more precisely of the statement (here) that every short exact sequence of vector spaces, such as

$$0 \to ker(f) \longrightarrow V \longrightarrow im(f) \to 0$$

is a split exact sequence, hence of the form

$$0 \to ker(f) \longrightarrow ker(f) \oplus im(f) \longrightarrow im(f) \to 0 \,.$$

Partial generalization to modules

While the rank-nullity theorem (1) does not fully generalize from vector spaces over fields to modules over rings, some aspects do carry over. For instance:

Proposition

Let $M$ be a finitely generated module over a unital commutative ring, and $N \subset M$ a submodule. Then surjective module homomorphisms $f \colon N \twoheadrightarrow M$ are already isomorphisms.

This was claimed in Orzech 1971, though with a gap in the proof (cf. Grinberg 2014). A full proof was given by Grinberg 2016. For the special case $N = M$ see also SP 05G8.

Proof

The following proof essentially reproduces a proof by Thomas Browning using the Cayley-Hamilton theorem.

Let $(m_i \in M)_{i = 1}^k$ be the assumed finite tuple of generators of the module $M$, so that

$$M = \langle m_1,\ldots,m_k\rangle \mathrlap{\,.}$$

By the assumption that $f$ is surjective, there must be preimages $(n_i \in N)_{i =1}^k$, hence with

$$m_i = f(n_i) \mathrlap{\,.}$$

Moreover, by the assumption that $N$ is a submodule of $M$, these preimages must be linear combinations of the generators,

$$n_i = \textstyle{\sum_j} a_{i j} m_j$$

with coefficient matrix

$$A = (a_{i j}) \mathrlap{\,,}$$

so that

$$\vec{n}=A\vec{m} \mathrlap{\,.}$$

Now, by Cayley-Hamilton theorem, the matrix $A$ satisfies its own characteristic polynomial equation:

$$A^k + c_{k-1} A^{k-1} + \cdots + c_2 A^2 + c_1 A + c_0 I \;=\; 0 \mathrlap{\,.}$$

Applying this equation to $\vec{m}$ gives

$$A^k\vec{m} + c_{k-1} A^{k-1}\vec{m} + \cdots + c_2 A^2 \vec{m} + c_1 A\vec{m} + c_0\vec{m} \;=\; 0 \mathrlap{\,.}$$

Now consider the step of first substituting $A\vec{m}=\vec{n}$

$$A^{k-1}\vec{n} + c_{k-1} A^{k-2}\vec{n} + \cdots + c_2A\vec{n} + c_1\vec{n} + c_0\vec{m} \;=\; 0 \mathrlap{\,.}$$

and then applying $f$ component-wise, to obtain:

$$A^{k-1}\vec{m} + c_{k-1}A^{k-2}\vec{m} + \cdots + c_2A\vec{m} + c_1\vec{m} + f(c_0\vec{m}) \;=\; 0 \mathrlap{\,.}$$

Observe that this has had the effect of reducing the order of the powers of $A$. So, applying the same kind of step again, by first substituting $A\vec{m}=\vec{n}$

$$A^{k-2}\vec{n} + c_{k-1}A^{k-3}\vec{n} + \cdots + c_2\vec{n} + c_1\vec{m} + f(c_0\vec{m}) \;=\; 0$$

and then applying $f$ component-wise, reduces the order by another unit, to yield:

$$A^{k-2}\vec{m} + c_{k-1}A^{k-3}\vec{m} + \cdots + c_2\vec{m} + f\big( c_1\vec{m} + f(c_0\vec{m}) \big) \;=\; 0 \mathrlap{\,.}$$

Hence by iteration of this step we eventually deduce an identity of the form

$$\vec{m} + f\Big( c_{k-1}\vec{m} + f\big( c_{k-2}\vec{m} + f(\cdots) \big) \Big) \;=\; 0 \mathrlap{\,.}$$

But since the $\vec m = (m_i)$ are generators, this same identity thus holds for arbitrary $x \in M$, by forming linear combinations:

$$x + f\Big( c_{k-1}x + f\big( c_{k-2}x + f(\cdots) \big) \Big) \;=\; 0 \mathrlap{\,.}$$

Evaluating this for any element $x \in \ker(f)$ in the kernel of $f$ clearly causes the nested terms to vanish iteratively and hence implies $x = 0$, whence the kernel is trivial. This means that the surjective map $f$ is also injective and therefore a module isomorphism, as claimed.

The following special case is important in practice and may still be proven essentially by recourse to the ordinary rank-nullity theorem:

Example

A surjective linear map of the form $\mathbb{Z}^n \longrightarrow \mathbb{Z}^n$ is already an isomorphism.

Proof

The linear map is represented by a square matrix with integer coefficients, and it being surjective means that this matrix has full rank. But under the canonical inclusion $\mathbb{Z} \subset \mathbb{R}$ we may regard this also as a real matrix. As such it still has full rank, and hence vanishing kernel by the rank-nullity theorem (1), hence is injective.

References

Ordinary

Textbook accounts:

• Sheldon Axler, 3.22 in: Linear Algebra Done Right, Springer (2015) [doi:10.1007/978-3-319-11080-6]

A formal proof of the rank-nullity theorem in the Isabelle proof assistant:

• Archive of Formal Proof, Rank-Nullity Theorem in Linear Algebra

See also:

• Wikipedia, Rank-nullity theorem

Partial generalization to modules

• Morris Orzech: Onto Endomorphisms are Isomorphisms, The American Mathematical Monthly 78 4 (1971) 357-362 [doi:10.2307/2316897, jstor:2316897]

• Darij Grinberg: Is Orzech’s generalization of the surjective-endomorphism-is-injective theorem correct? (2014) [MO:q/1065786]

• Darij Grinberg: A constructive proof of Orzech’s theorem (2016) [pdf, pdf]

• The Stacks Project: Tag 05G8