Sylvester rank inequality: $\operatorname{rank} A + \operatorname{rank}B \leq \operatorname{rank} AB + n$ 
If $A$ and $B$ are two matrices of the same order $n$, then
  $$ \operatorname{rank} A + \operatorname{rank}B \leq \operatorname{rank} AB + n. $$

I don't know how to start proving this inequality. I would be very pleased if someone helps me. Thanks!
Edit I.  Rank of $A$ is the same of the equivalent matrix $A' =\begin{pmatrix}I_r & 0 \\ 0 & 0\end{pmatrix}$. Analogously for $B$, ranks of $A$ and $B$ are $r,s\leq n$. Hence, since $\operatorname{rank}AB = \min\{r,s\}$, then $r+s\leq \min\{r,s\} + n$. (This is not correct since $\operatorname{rank} AB \leq \min\{r,s\}$.
Edit II. A discussion on the rank of a product of $H_f(A)$ and $H_c(B)$ would correct this, but I don't know how to formalize that $\operatorname{rank}H_f(A) +\operatorname{rank}H_c(B) - n \leq \operatorname{rank}[H_f(A)H_c(B)]$.
 A: Let $T:V\to W,\ S:W\to V$ be linear transformations which correspond to $A,B$. Equivalently we want prove that $r(T)+r(S)\leq r(TS)+n$ also  similarly show that $$\dim \ker(T) + \dim \ker(S) \gt \dim \ker(TS).$$ I know that $\ker (S) \subset \ker (TS)$. Let {$a_1,a_2,\ldots,a_r$} be a base for $\ker (S)$; expand this base for $\ker(ST)$  to  {$a_1,a_2,\ldots,a_r,a_{r+1},a_{r+2},\ldots,a_s$} and then show that {$S(a_{r+1}), S(a_{r+2}),\ldots,S(a_s)$} are a set of independent elements s.t. $S(a_i)\in \ker (T) \, \forall i:r+1,\ldots,s$ and indicate $\ker (T) \ge s-r,$ so $\dim \ker T+ \dim \ker S\ge s-r+r=\dim \ker TS$. $$ 1.\dim  \ker T+ \dim \ker S\ge \dim \ker TS$$ $$2.\dim \ker T+r(T)=n$$ $$3.\dim \ker S T+r(S)=n$$ $$4.\dim \ker TS+r(TS)=n.$$ By 1, 2, 3, 4 easily conclude $r(T)+r(S)\leq r(TS)+n$.
A: Subtract $2n$ from both sides and then multiply by $-1$; this gives the equivalent inequality $\def\rk{\operatorname{rank}}(n-\rk A)+(n-\rk B)\geq n-\rk(AB)$. In other words (by the rank-nullity theorem) we must show that the sums of the dimensions of the kernels of $A$ and of $B$ gives at least the dimension of the kernel of $AB$. Intuititively vectors that get killed by $AB$ either get killed by $B$ or (later) by $A$, and the dimension of $\ker(AB)$ therefore cannot exceed $\dim\ker A+\dim\ker B$. Here is how to make that precise.
One has $\ker B\subseteq \ker(AB)$, so if one restricts (the linear map with matrix) $B$ to $\ker(AB)$, giving a map $\tilde B:\ker(AB)\to K^n$, one sees that $\ker(\tilde B)=\ker(B)$ (both inclusions are obvious). Since the image of $\tilde B$ is contained in $\ker A$ by the definition of $\ker(AB)$, one has $\rk\tilde B\leq\dim\ker A$. Now rank-nullity applied to $\tilde B$ gives $$\dim\ker(AB)=\dim\ker\tilde B+\rk\tilde B\leq\dim\ker B+\dim\ker A,$$ as desired.
A: Denote by $r(A)$ the rank of $A$ and by $n(A)$ the nullity of $A$, i.e. the dimension of the nullspace of $A$. The rank plus nullity theorem says that
$r(A)+n(A)=n$ and $r(B)+n(B)=n$ and so $2n= r(A)+r(B)+n(A)+n(B)$.
Let $N(A)$ be the nullspace of $A$ and $R(B)$ the range-space of $B$.
Then $r(AB)=n - n(B)- \dim(N(A) \cap R(B))$ (try proving this, hint: what is the nullspace of $AB$?). This gives $n = r(AB) +n(B)+ n(N(A) \cap R(B))$ and so $n + r(AB) = r(A)+r(B) +n(A) - n(N(A) \cap R(B)) \ge 
r(A)+r(B)$.
A: As left or right multiplications by invertible matrices (and in particular, elementary matrices) don't change the rank of a matrix, we may assume WLOG that $A=\pmatrix{I_r&0\\ 0&0}$. Therefore,
\begin{align*}
\operatorname{rank}(A)+\operatorname{rank}(B)
&=\operatorname{rank}(A)+\operatorname{rank}(AB+(I-A)B)\\
&\le\operatorname{rank}(A)+\operatorname{rank}(AB)+\operatorname{rank}((I-A)B)\\
&\le r+\operatorname{rank}(AB)+(n-r)\\
&=\operatorname{rank}(AB)+n.
\end{align*}
The last but one line is due to the fact that the first $r$ rows of $(I-A)B$ are zero.
A: $$n+r(AB)=r(M)=r \begin{pmatrix}
      I_n   &   0 \\
      0     &   AB
    \end{pmatrix}$$
Using generalized elementary transformation to $M$:
$$M=\begin{pmatrix}
      I_n   &   0 \\
      0     &   AB
    \end{pmatrix}
\to \begin{pmatrix}
      I_n   &   0 \\
      A     &   AB
    \end{pmatrix}
\to \begin{pmatrix}
      I_n   &   -B \\
      A     &   0
    \end{pmatrix}
\to \begin{pmatrix}
      B     &   I_n \\
      0     &   A
    \end{pmatrix},$$
hence
$$n+r(AB)=r(M)=
r\begin{pmatrix}
      B     &   I_n \\
      0     &   A
 \end{pmatrix}\geq r(A)+r(B):$$
This solution is from here.
A: In response to Mr. Albanese's correct critique. I submit the following. The rank of A,B is in the set of integers [0,n]. Assume we know the relatively straigtfoward proofs that rank(AB)<= min(rank(A),rank(B)), -> rank(AB) = n if rank(A) and rank(B) have rank n. There are three rank possibilities. Let the rank of A = p, the rank of B = q with p,q integers. Then (p or q < n) or (p and q < n) or (p=q=n). The first two cases imply (rank(A) + rank(B) < rank(AB) + n) or (p+q < min(p,q) + n) as p+q < 2n and (rank(A) + rank(B)  > rank(AB) + n) is a contradiction. This is a contrapositive proof of the strict inequality in the Sylvester theorem (rank(A) + rank(B) < rank(AB) + n).  For the equality case p=q=n. Then (rank(A) + rank(B)  = rank(AB)) + n) or n + n = n + n which is true because rank(A) and rank(B) have full rank, n, implies rank(AB)=n.  
