# Prove Sylvester rank inequality: $\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.

• Do you know the rank nullity theorem? – Bombyx mori 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. – TheRealFakeNews Jan 3 '13 at 1:00
• Hint: Sylvester's Rank Inequality. Regards – Amzoti Jan 3 '13 at 1:43
• Another Hint: Frobenius Inequality. Regards – Amzoti Jan 3 '13 at 6:17
• – Martin Sleziak May 28 '16 at 14:03

We claim $$\dim \ker\,A+\dim\ker B \geq \dim\ker AB$$.

Let $$\beta=\{\alpha_1,\dots,\alpha_r \}$$ be a basis for $$\ker B$$. It is not hard to see that $$\ker B\subseteq \ker AB$$ so we can extend $$\beta$$ to a 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.

We show that $$\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$$ is linear independent. We have $$\dim\ker A\geq n-r$$. Assume that $$\sum_{i=r+1}^n\gamma_iB(\alpha_i)=0$$. In other words we have $$B(\sum_{i=r+1}^n\gamma_i\alpha_i)=0$$ and as a result $$\sum_{i=r+1}^n\gamma_i\alpha_i$$ belongs to the kernel of $$B$$. On other hand we already know that $$\beta=\{\alpha_1,\dots,\alpha_r \}$$ is a basis for the kernel B. Next since the set $$\{\alpha_1,\dots,\alpha_r,\alpha_{r+1},\dots,\alpha_n \ \}$$ is an independent set, we infer that all $$\gamma_i$$ must be zero.

Now one can see that $$\dim\ker A+\dim\ker B \geqslant n-r+r =n \Longrightarrow\dim\ker A+\dim\ker B \geqslant \dim\ker AB$$

• Why $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent ? – user185640 Mar 9 '17 at 20:46
• If they are linearly dependent, then either $\alpha_{r+1} \ldots \alpha_{n}$ are LD or linear combinations of them is in $N(B)$. Both are not true. Hence they have to be LI – Nagabhushan S N Oct 14 '20 at 8:20

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.$

• I have a doubt in the last line of the proof. Ker(B) ⊆ker(AB) implies nullity(B) <= nullity(AB). So nullity(B)-nullity(AB) <=0 which means nullity(A)+nullity(B)-nullity(AB) <=nullity(A). But in your proof its the other-way. May I know how? – La Rias Nov 15 '15 at 6:42

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.

Because I can't comment (yet), I will answer @user185640's question in a comment to @Babak Miraftab's answer which is "Why $$\{B(\alpha_{r+1}),\ldots,B(\alpha_n)\}$$ is linear independent" in this post.

Now, suppose $$\sum_{i=r+1}^{n}c_i B(\alpha_i) = 0$$ for some $$i \in K$$ where $$K$$ is the scalar field.

This would imply: $$B \left(\sum_{i=r+1}^{n}c_i\alpha_i\right) = 0$$

Hence, it is immediate to see that $$\sum_{i=r+1}^{n}c_i\alpha_i \in \ker B$$. But in his proof we know $$\beta$$ is a basis for $$\ker B$$. So we can write $$\sum_{i=r+1}^{n}c_i\alpha_i$$ as $$\sum_{i=1}^{r}d_i\alpha_i$$ for some $$d_i \in K$$. In particular we can write it as the following:

$$\sum_{i=r+1}^{n}c_i\alpha_i = \sum_{i=1}^{r}d_i\alpha_i \implies \sum_{i = r+1}^{n}c_i\alpha_i - \sum_{i=1}^{r}d_i\alpha_i = 0$$

To see this even more clearer, we can expand the sum to see this:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} - d_1\alpha_1 - \ldots - d_r\alpha_r = 0$$

This may look unusual but it is not. We can further rewrite it as:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} + (-d_1)\alpha_1 + \ldots + (-d_r)\alpha_r = 0$$

Let $$e_i =-d_i$$ for $$i = 1,\ldots,n$$ to see things even more clearer. We can then rewrite the above as:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} + e_1\alpha_1 + \ldots + e_r\alpha_r = 0$$

Now since $$\{\alpha_1, \ldots, \alpha_n\}$$ is linearly independent (as it is a basis for $$\ker AB$$), we must have that

$$c_{r+1} = \ldots = c_n = e_1 = \ldots = e_r = 0$$

In particular, $$c_{r+1} = \ldots = c_n = 0$$

which directly implies that indeed $$B(\alpha_{r+1}),\ldots,B(\alpha_n)$$ are linearly independent and hence the set containing these vectors is a linearly independent set. Done.