Sylvester rank inequality

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

-
This might be of help: math.stackexchange.com/questions/978/… – Git Gud Feb 9 '13 at 19:54
@GitGud Not really, I knew that but doesn't solves anything. Thanks anyway. – Ben Ward Feb 9 '13 at 20:04
– Martin Sleziak May 28 at 14:02

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

-

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

-

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.

-
Nice concise proof ! – LeGrandDODOM Feb 20 '15 at 8:58
@Vim No, that's not what I did in the proof (and that equality is false anyway). You see, if $A=P\tilde{A}Q$ where $P,Q$ are invertible and $\tilde{A}=I_r\oplus0$, the inequality in question is equivalent to $r(\tilde{A}) + r(QB) \le r(\tilde{A}QB) + n$. Let $\tilde{B}=QB$, we can rewrite the inequality as $r(\tilde{A})+r(\tilde{B})\le r(\tilde{A}\tilde{B})+n$. – user1551 Sep 7 '15 at 11:38
@user1551 I am still a bit confused, what is $I$ in your answer? I don't think it means the identity matrix. – Vim Sep 7 '15 at 12:43
@Vim It is the identity matrix. – user1551 Sep 7 '15 at 14:31
@user1551 alright.. I thought the sylvester's inequality the OP posted was the general $m\times s\times s \times n$ case. – Vim Sep 7 '15 at 14:42

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

-

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

-
I have reformatted your answer slightly, please check whether it is OK. Also, please allow me to be pedant. You shouldn't denote a base as a set, for instance because the order is important. Mind you, it is perfectly clear what you mean. – Andreas Caranti Feb 9 '13 at 20:02
@Andreas Caranti: W,V are finite vector space then exist $r\in \mathbb N$ s.t $a_1,a_2,\ldots,a_r$ be base for $\ker (S)$ – Maisam Hedyelloo Feb 9 '13 at 20:16
That's ok, my point was that denoting it as a set $\{ a_1,a_2,\ldots,a_r \}$ is improper, for instance because if you change the order you get a different base, while in a set there's no order of elements. – Andreas Caranti Feb 9 '13 at 20:54

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.

-
This assumes that either $\operatorname{rank} A + \operatorname{rank} B \leq \operatorname{rank} AB + n$ or $\operatorname{rank} A + \operatorname{rank} B > \operatorname{rank} AB + n$. It could be the case that there is no relationship between $\operatorname{rank} A + \operatorname{rank} B$ and $\operatorname{rank} AB + n$. – Michael Albanese Sep 7 '14 at 4:32
I submit the following. The maximum rank of A,B is an integer n. – John Knox Sep 12 '14 at 22:53
See above per @MichaelAlbanese – John Knox Sep 15 '14 at 22:40