Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
This might be of help:… – 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

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer
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)$.

share|cite|improve this answer

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

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.