An exercise in linear algebra

Let $A$ and $B$ be a $m$ by $n$ and $n$ by $p$ matrix respectively. Show that

$\text{nullity}(AB)\leq \text{nullity}(A)+\text{nullity}(B)$.

Solution (By Zorn Leung).

For convenience, given any matrix $A$, denote $A$ (abuse of notation) to be the linear operator $x\mapsto Ax$. Plus let $N(A)$ and $R(A)$ be the null space and range space of operator $A$ respectively.

Consider the restriction of $B$ on $N(AB)$, denoted by $B|_{N(AB)}$.

Observe first $\dim{N(B|_{N(AB)})}\leq\dim{N(B)}$ since $N(B|_{N(AB)})$ is clearly a subspace of $N(B)$. Also, $R(B|_{N(AB)})$ is a subspace of $N(A)$. Indeed, if $y\in R(B|_{N(AB)})$, then $y=Bx$ for some $x\in N(AB)$. Hence $Ay=ABx=0$ implying $y\in N(A)$. Therefore $\dim{R(B|_{N(AB)})}\leq\dim{N(A)}$.

By dimension theorem,

$\dim{N(AB)}=\dim{N(B|_{N(AB)})}+\dim{R(B|_{N(AB)})}\leq\dim{N(B)}+\dim{N(A)}$, which is the conclusion.

Corollary. $A$, $B$ as above. Then $\text{rank}(AB)\geq\text{rank}(A)+\text{rank}(B)-n$.

Proof.

Dimension theorem implies

$\text{nullity}(AB)=p-\text{rank}(AB)$,

$\text{nullity}(A)=n-\text{rank}(A)$, and

$\text{nullity}(B)=p-\text{rank}(B)$.

Using the previous result,

$p-\text{rank}(AB)\leq n-\text{rank}(A)+p-\text{rank}(B)$. The result follows.

This entry was posted in Linear Algebra. Bookmark the permalink.

2 Responses to An exercise in linear algebra

1. KKK says:

Let me 馬後砲 again. I think this inequality can be understood as “a tower of kernel inclusions” (perhaps you have noticed from Zorn Leung’s proof already). In an extremely rough language, $N(AB)$ is just “summing” $N(A)$ and $N(B)$ (well… in general if $v\in N(A_n\cdots A_1)$, then $v$ must goes to $0$ after passing through $A_1$ up to some $A_{k}$, $k\leq n$, so eventually $A_{k-1}\cdots A_1 v\in N(A_k)$). OK, I know $N(A)+N(B)$ seems nonsense, so if you think for a second (which takes me some minutes actually), you should guess that (now I use the notations $A^{-1}(V):=\{x\in X: Ax\in V\}$ for $A: X\rightarrow Y$ and $V\subset Y$):
$(AB)^{-1}(0)=B^{-1}(A^{-1}(0))\supset B^{-1}(0)$
I think this is quite clear and everyone can prove it.
The next observation is “$B$” is injective (and hence “preserves dimension”) on the complement of $B^{-1}(0)$ in $B^{-1}A^{-1}(0)$). More precisely, (notation abused) $B: B^{-1}A^{-1}(0)/B^{-1}(0)\rightarrow A^{-1}(0)$ is 1-1 (and is well-defined). This is obvious: if $Bv=0$ for some $v\in B^{-1}A^{-1}(0)$, of course $v\in B^{-1}(0)$. [In so many words, it’s nothing but just Zorn’s proof rephrased. ] Therefore by the above, we conclude that
$n(AB)=\dim B^{-1}(0)+\dim(B^{-1}A^{-1}(0))-\dim B^{-1}(0)=n(B)+\dim(B^{-1}A^{-1}(0)/B^{-1}(0))\leq n(B)+n(A).$
The analysis also shows that the equality holds if and only if $R(B)\supset A^{-1}(0)$, the deficit of the inequality (i.e. RHS-LHS) is measured by $\dim(A^{-1}(0)/R(B)\cap A^{-1}(0))$.

The same analysis can be applied to the general case for finitely many $A_i$‘s, too. i.e. for $V_1\stackrel{A_1}\rightarrow V_2\stackrel{A_2}\rightarrow \cdots \stackrel{A_n}\rightarrow V_{n+1}$, we have the tower of kernel inclusion:
$A_1^{-1}\cdots A_{n-1}^{-1}A_n^{-1}(0)\supset A_1^{-1}\cdots A_{n-1}^{-1}(0)\supset\cdots\supset A_1^{-1}(0)$. So by the telescoping trick, we can get:
Zorn Leung’s Theorem, 2010
$\displaystyle n(A_n\cdots A_1)=\dim (A_1^{-1}\cdots A_{n-1}^{-1}A_n^{-1}(0)/A_1^{-1}\cdots A_{n-1}^{-1}(0))+\dim(A_1^{-1}\cdots A_{n-1}^{-1}(0)/A_1^{-1}\cdots A_{n-2}^{-1}(0))+\cdots +\dim (A_1^{-1} A_{2}^{-1}(0)/A_1^{-1}(0))+\dim A_1^{-1}(0)\leq \sum_{i=1}^n n(A_i).$ The equality holds if and only if $R(A_i)\supset A_{i+1}^{-1}(0)$ for $i=1, \cdots , n-1.$

2. KKK says:

Since the last comment has become a bit long, I start a new one here.
The Corollary of Zorn Leung’s theorem can be regarded as the “dual version” of it. The general setting is the same, for $V_1\stackrel{A_1}\rightarrow V_2\stackrel{A_2}\rightarrow \cdots \stackrel{A_n}\rightarrow V_{n+1}$ and $n_i:=\dim V_i$, we have the tower of range inclusion: $R(A_n)\supset R(A_nA_{n-1})\supset \cdots \supset R(A_n\cdots A_1)$, note that for example when $n=3$, by abuse of notations, $A_3: V_3/R(A_2)\rightarrow R(A_3)/R(A_3A_2)$ is well-defined and is surjective (and hence “rank decreasing”), so we have $\dim (R(A_3)/R(A_3A_2))\leq n_3-\dim R(A_2)$ and similary $\dim R(A_3 A_2)/R(A_3A_2 A_1)\leq n_2-\dim R(A_1)$.
By telescoping,
$\dim R(A_3)=\dim R(A_3)/R(A_3A_2)+\dim R(A_3 A_2)/R(A_3 A_2A_1)+\dim R(A_3 A_2 A_1)\leq n_3-rk(A_2)+n_2-rk(A_1)+rk(A_3A_2A_1).$
Rearranging, we get $rk (A_1)+rk(A_2)+rk(A_3)\leq n_2+n_3+rk (A_3A_2 A_1).$ In general, we have the following theorem:
Zorn Leung’s Theorem, 2010
$\displaystyle \sum_{i=1}^n rk (A_i)\leq \sum_{i=2}^n \dim V_i+rk(A_n\cdots A_1).$

Question: When does the equality hold?
Answer: Ask Zorn Leung, who is the tutor of linear algebra. $\Box$
Merry Christmas!!