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

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.

• i cant understand how or why you fixed $(n - rank(A)) + (n - rank(B))\leq (n - rank(AB))$ as according to the rank-nullity theorem, this is exactly: $N(A) + N(B) = N(AB)$, i mean, that wouldn't be correct to use $\leq$ – Jneven Jul 17 '18 at 9:20
• @jneven: As the text says, the new inequality is equivalent to the old one. It still needs to be proved, which I then do. – Marc van Leeuwen Jul 17 '18 at 11:49
• Could you please explain a bit more detail on "restricts matrix to a map"? I searched on the web but only found "restricted to a subspace / domain". Does these have same meaning? Thanks. – Page David Mar 29 at 14:04
• @PageDavid: The restriction was meant to be to the subspace $\ker(AB)$. Since that subspace was already mentioned a few words later as the domain of the restricted map $\tilde B$, I had omitted it to avoid repetition. But you are right, the sentence is more readable when the subspace is explicitly mentioned, so I edited it. – Marc van Leeuwen Mar 29 at 14:25

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 ! – Gabriel Romon 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

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

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)$ – M.H 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