Page 216 - Matrix Analysis & Applied Linear Algebra

4.5 More about Rank 211

Basis for an Intersection
If A is m × n and B is n × p, then a basis for N (A) ∩ R (B) can
be constructed by the following procedure.
Find a basis {x 1 , x 2 ,..., x r } for R (B).

Set X n×r = x 1 | x 2 |· · · | x r .
Find a basis {v 1 , v 2 ,..., v s } for N (AX).
B = {Xv 1 , Xv 2 ,..., Xv s } is a basis for N (A) ∩ R (B).

Proof. The strategy is to argue that B is a maximal linear independent sub-
set of N (A) ∩ R (B). Since each Xv j belongs to R (X)= R (B), and since

AXv j = 0, it’s clear that B⊂ N (A) ∩ R (B). Let V r×s = v 1 | v 2 |· · · | v s ,
and notice that V and X each have full column rank. Consequently, N (X)= 0
so, by (4.5.1),

rank (XV) = rank (V) − dim N (X) ∩ R (V)= rank (V)= s,
n×s
which insures that B is linearly independent. B is a maximal independent
subset of N (A) ∩ R (B) because (4.5.1) also guarantees that

s = dim N (AX) = dim N (X) + dim N (A) ∩ R (X) (see Exercise 4.5.10)
= dim N (A) ∩ R (B).

The utility of (4.5.1) is mitigated by the fact that although rank (A) and
rank (B) are frequently known or can be estimated, the term dim N (A)∩R (B)
can be costly to obtain. In such cases (4.5.1) still provides us with useful upper
and lower bounds for rank (AB) that depend only on rank (A) and rank (B).

Bounds on the Rank of a Product

If A is m × n and B is n × p, then
• rank (AB) ≤ min {rank (A), rank (B)} , (4.5.2)

• rank (A)+ rank (B) − n ≤ rank (AB). (4.5.3)