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.

Advertisements
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!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s