Earlier units counted the free variables of an echelon form and observed that the number of pivots plus the number of free variables equals the number of columns. The rank-nullity theorem says that this is a coordinate-free fact about every linear map on a finite-dimensional space: the dimension of the input space splits into what the map destroys (the kernel) and what it keeps (the range). We use bases and dimension (6.5), the extension of an independent list to a basis (6.8), column space and rank (6.6), and the kernel and range from the previous unit.
Statement
Definition 6.10.1
(Rank and nullity)
Let be a linear map with finite-dimensional. The nullity of is and the rank of is . For an matrix , the nullity of is and the rank is .
Theorem 6.10.2
(Rank-nullity theorem for linear maps)
If is finite-dimensional and is linear, then
Theorem 6.10.3
(Rank-nullity theorem for matrices)
For every matrix ,
The matrix form is the case of the theorem for linear maps, because , , and . It also has a direct proof from the reduced row echelon form, which we give first because it shows where the number comes from.
Proof from the reduced row echelon form
Proof
(One basis vector of the null space for each free column)
Let be the reduced row echelon form of ; it has the same solution set for as . Suppose has pivot columns, so , and free columns. Solving expresses each pivot variable as a linear combination of the free variables. Setting one free variable equal to and the others equal to produces solutions . They span , because every solution is the combination where is the value of the -th free variable. They are linearly independent, because in the combination the entry in the position of the -th free variable is exactly , so forces all . Hence .
Proof for linear maps
Proof
(Extend a kernel basis; the new vectors map to a basis of the range)
Let , and choose a basis of . Extend it to a basis of , so . It suffices to show that is a basis of .
They span the range. Let and write . Since ,
They are linearly independent. Suppose . Then , so and equals for some scalars . Then , and independence of the full basis of gives all and all .
Therefore and .
Proof X-ray
Which choice makes each half of the proof work
The proof has one design decision: the basis of is built from the kernel outward, kernel vectors first and then the extra vectors . Finite dimension of enters here, since it is what allows an independent list to be extended to a basis at all. Each half then uses that decision in a different way.
Spanning uses only that kills the : every input is a combination of the and the , and the contribute nothing to the image, so the images of the already generate the range. Independence is the non-obvious step. A vanishing combination says that lies in the kernel, which is spanned by the ; this converts a relation among images in back into a relation among basis vectors of . Independence of the whole basis of then kills every and every together. This is where the must be genuinely new: if one of them lay in , the combination would not need to vanish.
The argument closes by counting: the kernel vectors and the extra vectors make up all of the basis of , so , with the dimension of the range.
The theorem needs only to be finite-dimensional. The codomain may be any vector space, because the range is spanned by the images of a finite basis of and is therefore finite-dimensional.
Concept lensGeometric
The domain splits into a destroyed part and a kept part
Choose a complement of the kernel, so that . The proof shows that restricted to is a bijection onto : the kernel is flattened to the origin, and is carried faithfully onto the range. For the projection of onto the line , the kernel is the line spanned by , a complement is the line spanned by , and maps that complement onto itself. Thus : one dimension is destroyed and one is kept. A different complement, such as the -axis, gives the same count.
Consequences
Corollary 6.10.4
(Injectivity, surjectivity and dimension counts)
Let be linear with finite-dimensional.
- is injective if and only if .
- If , then is not injective. If , then is not surjective.
- If , then is injective if and only if it is surjective.
Proof
(Each part is a dimension count)
(1) is injective if and only if , that is ; apply the rank-nullity theorem. (2) We have , so . If , then , so . (3) Injective means , and a subspace of with dimension equals ; the converse is the same chain read backwards.
Part (3) uses finite dimension in an essential way, and it fails without it.
Counterexample mode
Injective versus surjective in infinite dimensions
Claim: a linear map from a vector space to itself is injective if and only if it is surjective. Let be the space of all real polynomials, which is infinite-dimensional. Differentiation satisfies , so and is not injective, yet every polynomial has an antiderivative: for instance , so is surjective. Multiplication goes the other way: forces , so is injective, but the constant polynomial is not of the form (the polynomial vanishes at while does not), so is not surjective. The repaired statement requires , where the dimension count above does apply.
Corollary 6.10.5
(Solution sets of consistent systems)
If is consistent for an matrix with rank , then its solution set is a translate of the null space, and it has "dimension" : it contains exactly one solution if and infinitely many otherwise.
Proof
(Differences of solutions lie in the null space)
If , then exactly when , that is, when . By the matrix form of the theorem, . The null space is exactly when . Otherwise it contains a nonzero vector , and then are infinitely many distinct solutions, .
Quick check
(A linear map is given. What is the smallest possible value of , and when is it attained?)
Bound above by the dimension of the codomain.
Solution · Answer
, so . The value is attained exactly when is surjective. In particular is never injective.
Worked examples
Worked example 6.10.6
(A matrix computation)
Let
Row reduction: subtract twice row 1 from row 2 and row 1 from row 3 to get rows , , ; add row 2 to row 3 to obtain a zero row, then subtract row 2 from row 1. The reduced form has rows and , so the pivot columns are and and . The free variables are and , with and . A basis of is
so the nullity is and . Check that : the rows give , , . Check that : the rows give , , .
Worked example 6.10.7
(A map between function spaces)
Let be differentiation, where denotes the real polynomials of degree at most . Then . The kernel is the set of constant polynomials, of dimension . The derivative of is , which covers every polynomial in , so has dimension . Indeed . By part (1) of the corollary, is not injective, but it is surjective.
Worked example 6.10.8
(Using the theorem to find a dimension)
Let be , a linear map on a space of dimension . Its kernel is the set of symmetric matrices, which has the basis
so the nullity is . By the theorem the range has dimension . Indeed for , and these matrices form the one-dimensional space spanned by . The theorem gave the dimension of the range without computing it.
Worked example 6.10.9
(Extreme cases and counting solutions)
For the zero map with , the kernel is all of and the range is , so the nullity is and the rank is ; for the identity map the nullity is and the rank is . Both satisfy the theorem. Now let , which has pivot columns (columns ), so and . For the consistent system with , a particular solution is , and the solution set is with : two free parameters, so infinitely many solutions. If instead , the null space would be and would be the only solution.
Common mistakes and subtle points
Common mistake
(Counting rows instead of columns)
In the matrix form of the theorem the number on the right is the number of columns (the dimension of the domain), not the number of rows. A matrix of rank has nullity , not .
Common mistake
(Taking basis vectors of the column space from the echelon form)
The rank is read from the echelon form, but a basis of must consist of the original pivot columns of . For the reduced form is , whose first column is ; but does not contain . The correct basis vector is the first column of .
Common mistake
(Assuming injective and surjective always go together)
They coincide only when . For with of size , the map can be injective (rank ) but never surjective, since . Also the kernel lives in the domain and the range in the codomain: their dimensions add up to , but the two subspaces sit in different spaces.
Exercises
Exercise 6.10.10
(Find the rank and nullity of .)
Foundation
Solution(2)
- 1
Row reduce
Subtract times row 1 from row 2 and times row 1 from row 3: the rows become , , . Subtracting twice row 2 from row 3 gives a zero row.
- 2
Count pivots and apply the theorem
There are two nonzero rows with pivots in columns and , so and by the matrix form of the theorem the nullity is . (A null vector is : , , .)
Exercise 6.10.11
(A linear map is surjective. Find . Can a linear map be surjective?)
Core
Solution(2)
- 1
Use surjectivity to get the rank
Surjective means , so the theorem gives .
- 2
Bound the rank of a map from
A linear map satisfies by the theorem, so and cannot be surjective.
Exercise 6.10.12
(A matrix has nullity . Find its rank. Is solvable for every ?)
Core
Solution(2)
- 1
Find the rank
Here , so .
- 2
Compare the column space with the codomain
The column space is a -dimensional subspace of , which is a proper subspace because . Therefore there exist vectors outside it, and for those has no solution. The system is not solvable for every .
Exercise 6.10.13
(Let be and be . Use the rank-nullity theorem to show .)
SynthesisProof
Solution(2)
- 1
Compare the null spaces
Key step
Let , so . Then , hence and .
Because: A vector killed by is also killed by .
- 2
Convert nullity into rank
∎Both and have columns, so the matrix form of the theorem gives