# prove that $\text{rank}(AB)\ge\text{rank}(A)+\text{rank}(B)-n.$

If $A$ is a $m \times n$ matrix and $B$ a $n \times k$ matrix, prove that

$$\text{rank}(AB)\ge\text{rank}(A)+\text{rank}(B)-n.$$

Also show when equality occurs.

-
Title is inaccurate? –  Calvin Lin Jan 3 '13 at 0:02
Please edit the title to reflect the question. –  Potato Jan 3 '13 at 0:06
Do you know the rank nullity theorem? –  user32240 Jan 3 '13 at 0:15
Have you tried working out an example? Try a few by hand and see if you can generalize it. Or you can try showing it by contradiction; though I always feel direct proofs are much more clear. –  AlanH Jan 3 '13 at 1:00
Hint: Sylvester's Rank Inequality. Regards –  Amzoti Jan 3 '13 at 1:43
show 1 more comment

Using Rank–nullity theorem, $\operatorname{rank}(A)+\operatorname{nullity}(A)=n,\operatorname{rank}(B)+\operatorname{nullity}(B)=k$ and $\operatorname{rank}(AB)+\operatorname{nullity}(AB)=k.$

So, $\operatorname{rank}(A)+\operatorname{rank}(B)+\operatorname{nullity}(A)+\operatorname{nullity}(B)=n+\operatorname{rank}(AB)+\operatorname{nullity}(AB)$

$\implies \operatorname{rank}(AB)-\operatorname{rank}(A)-\operatorname{rank}(B)+n=\operatorname{nullity}(A)+\operatorname{nullity}(B)-\operatorname{nullity}(AB)$

$\geq \operatorname{nullity}(A)$[Since $Bv_2=0$ for $v_2\in Mat_{k\times 1}(F)\implies ABv_2=0$] $\geq 0.$

-

As noted in the other answer, it suffices to show $\dim\ \operatorname{Ker}(A)+\dim\ \operatorname{Ker}(B) \geq \dim\ \operatorname{Ker}(AB)$. This is equivalent to showing that $\dim\ \operatorname{Ker}(AB)/\operatorname{Ker}(B) \leq \dim\ \operatorname{Ker}(A)$. To do this, use the first isomorphism theorem for vector spaces on the linear map $\operatorname{Ker}(AB) \rightarrow \operatorname{Ker}(A)$ defined by $x \mapsto Bx$. This shows that $\operatorname{Ker}(AB)/\operatorname{Ker}(B)$ is isomorphic to a subspace of $\operatorname{Ker}(A)$, which proves the inequality.

-
We claim $\dim \ker\,A+\dim\ker B \geq \dim\ker AB$.
Let $\beta=\{\alpha_1,\dots,\alpha_r \}$ be basis for $\ker B$. It is not hard to see that $\ker B\subseteq \ker AB$ so we can extend $\beta$ to basis for $\ker AB$. Suppose $\{\alpha_1,\dots,\alpha_r,\alpha_{r+1},\dots,\alpha_n \ \}$ be basis for $\ker AB$. So $B(\alpha_{i})\neq 0$ for $i \in \{r<i<n+1\}$. It is easily seen that $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent. We have $\dim\ker A\geq n-r$.
$$\dim\ker A+\dim\ker B \geqslant n-r+r =n \Longrightarrow\dim\ker A+\dim\ker B \geqslant \dim\ker AB$$