Rank–nullity theorem

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 n − r linearly independent solutions that span the null space of A. These proofs are also available in the book by Banerjee and Roy (2014)

First proof: Suppose { u 1 , … , u m } forms a basis of ker T. We can extend this to form a basis of V: { u 1 , … , u m , w 1 , … , 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 image of T (im T) is n.

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

v = a 1 u 1 + ⋯ + a m u m + b 1 w 1 + ⋯ + b n w n ⇒ T v = a 1 T u 1 + ⋯ + a m T u m + b 1 T w 1 + ⋯ + b n T w n ⇒ T v = b 1 T w 1 + ⋯ + b n T w n ∵ T u i = 0

Thus, { T w 1 , … , T w n } spans im T.

Now, we need only show that this list is not redundant; that is, that { T w 1 , … , T 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:

c 1 T w 1 + ⋯ + c n T w n = 0 ⇔ T ( c 1 w 1 + ⋯ + c n w n ) = 0 ∴ c 1 w 1 + ⋯ + c n w n ∈ ker T

Then, since u_i span ker T, there exists a set of scalars d_i such that:

c 1 w 1 + ⋯ + c n w n = d 1 u 1 + ⋯ + d m u m

But, since { u 1 , … , u m , w 1 , … , w n } form a basis of V, all c_i, d_i must be zero. Therefore, { T w 1 , … , T 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 n − r linearly independent solutions to the homogeneous system Ax = 0, and (ii) that every other solution is a linear combination of these n − r solutions. In other words, we will produce an n × (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 write A = [A₁:A₂], where A₁ is m × r with r linearly independent column vectors and A₂ is m × (n − r), each of whose n − r columns are linear combinations of the columns of A₁. This means that A₂ = A₁ B for some r × (n − r) matrix B (see rank factorization) and, hence, A = [A₁:A₁B]. Let X = ( − B I n − r ) , where I n − r is the (n − r) × (n − r) identity matrix. We note that X is an n × (n − r) matrix that satisfies

A X = [ A 1 : A 1 B ] ( − B I n − r ) = − A 1 B + A 1 B = O .

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

X u = 0 ⇒ ( − B I n − r ) u = 0 ⇒ ( − B u u ) = ( 0 0 ) ⇒ u = 0 .

Therefore, the column vectors of X constitute a set of n − r 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 u = ( u 1 u 2 ) be any vector such that Au = 0. Note that since the columns of A₁ are linearly independent, A₁x = 0 implies x = 0. Therefore,

A u = 0 ⇒ [ A 1 : A 1 B ] ( u 1 u 2 ) = 0 ⇒ A 1 ( u 1 + B u 2 ) = 0 ⇒ u 1 + B u 2 = 0 ⇒ u 1 = − B u 2 ⇒ u = ( u 1 u 2 ) = ( − B I n − r ) u 2 = X u 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 rk(A) + nul(A) = n. QED.

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 → ker ⁡ T   → I d   V   → T   im ⁡ T → 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

∑ 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 : V → W, 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.