Proving Sylvester's Inequality

Question

I have been attempting to prove Sylvester's Inequality. $$rank(A)+rank(B)\leq n+rank(AB)$$

I have been referencing other proofs on this site, but all of them involve concepts and theorems that I am not familiar with, so I am still struggling.

So far, I have proven that $rank(AB) \le rank(A)$ and $rank(AB) \le rank(B)$. I also have rewritten the inequality as $ker(A)+ker(B) \ge ker(AB)$, but I can't seem to get past this point. Any help would be appreciated.

Answer 1

You can avoid using "advanced" theorems if you do the following steps:

Let $A$ be $m\times n$ matrix and $B$ be $n\times k$ matrix.

1. Prove that $$ \operatorname{rank}\begin{bmatrix}I_n & 0\\0 & AB\end{bmatrix}=n+\operatorname{rank}(AB). $$
2. Prove that $$ \operatorname{rank}\begin{bmatrix}I_n & 0\\0 & AB\end{bmatrix}=\operatorname{rank}\begin{bmatrix}I_n & B\\A & 0\end{bmatrix} $$ using e.g. $$ \begin{bmatrix}I_n & B\\A & 0\end{bmatrix}=\begin{bmatrix}I_n & 0\\A & I_m\end{bmatrix}\begin{bmatrix}I_n & 0\\0 & AB\end{bmatrix}\begin{bmatrix}I_n & B\\0 & -I_k\end{bmatrix}. $$
3. Prove that $$ \operatorname{rank}\begin{bmatrix}I_n & B\\A & 0\end{bmatrix}\ge \operatorname{rank}(A)+\operatorname{rank}(B). $$

The last step can be done easily if you prove that the columns of the block matrix corresponding to the linear independent columns of $A$ and that of $B$ are linear independent altogether. All you need here is the definition of linear independent vectors.