33
$\begingroup$

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

$\endgroup$
33
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Jneven Jul 17 '18 at 9:20
  • $\begingroup$ @jneven: As the text says, the new inequality is equivalent to the old one. It still needs to be proved, which I then do. $\endgroup$ – Marc van Leeuwen Jul 17 '18 at 11:49
  • $\begingroup$ 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. $\endgroup$ – Page David Mar 29 at 14:04
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Mar 29 at 14:25
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice concise proof ! $\endgroup$ – Gabriel Romon Feb 20 '15 at 8:58
  • $\begingroup$ @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$. $\endgroup$ – user1551 Sep 7 '15 at 11:38
  • $\begingroup$ @user1551 I am still a bit confused, what is $I$ in your answer? I don't think it means the identity matrix. $\endgroup$ – Vim Sep 7 '15 at 12:43
  • $\begingroup$ @Vim It is the identity matrix. $\endgroup$ – user1551 Sep 7 '15 at 14:31
  • $\begingroup$ @user1551 alright.. I thought the sylvester's inequality the OP posted was the general $m\times s\times s \times n$ case. $\endgroup$ – Vim Sep 7 '15 at 14:42
10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andreas Caranti Feb 9 '13 at 20:02
  • $\begingroup$ @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)$ $\endgroup$ – M.H Feb 9 '13 at 20:16
  • $\begingroup$ 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. $\endgroup$ – Andreas Caranti Feb 9 '13 at 20:54
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Michael Albanese Sep 7 '14 at 4:32
  • $\begingroup$ I submit the following. The maximum rank of A,B is an integer n. $\endgroup$ – John Knox Sep 12 '14 at 22:53
  • $\begingroup$ See above per @MichaelAlbanese $\endgroup$ – John Knox Sep 15 '14 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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