7
$\begingroup$

If $A$ is a $m \times n$ matrix and $B$ a $n \times k$ matrix, prove that

$$\text{rank}(AB)\ge\text{rank}(A)+\text{rank}(B)-n.$$

Also show when equality occurs.

$\endgroup$
  • 2
    $\begingroup$ Title is inaccurate? $\endgroup$ – Calvin Lin Jan 3 '13 at 0:02
  • 1
    $\begingroup$ Please edit the title to reflect the question. $\endgroup$ – Potato Jan 3 '13 at 0:06
  • 1
    $\begingroup$ Do you know the rank nullity theorem? $\endgroup$ – Bombyx mori Jan 3 '13 at 0:15
  • $\begingroup$ Have you tried working out an example? Try a few by hand and see if you can generalize it. Or you can try showing it by contradiction; though I always feel direct proofs are much more clear. $\endgroup$ – AlanH Jan 3 '13 at 1:00
  • 1
    $\begingroup$ Hint: Sylvester's Rank Inequality. Regards $\endgroup$ – Amzoti Jan 3 '13 at 1:43
2
$\begingroup$

Recall Linear Transformations Isomorphic to Matrix Space.

Using Rank–nullity theorem, $\operatorname{rank}(A)+\operatorname{nullity}(A)=n,\operatorname{rank}(B)+\operatorname{nullity}(B)=k$ and $\operatorname{rank}(AB)+\operatorname{nullity}(AB)=k.$

So, $\operatorname{rank}(A)+\operatorname{rank}(B)+\operatorname{nullity}(A)+\operatorname{nullity}(B)=n+\operatorname{rank}(AB)+\operatorname{nullity}(AB)$

$\implies \operatorname{rank}(AB)-\operatorname{rank}(A)-\operatorname{rank}(B)+n=\operatorname{nullity}(A)+\operatorname{nullity}(B)-\operatorname{nullity}(AB)$

$\geq \operatorname{nullity}(A)$[Since $Bv_2=0$ for $v_2\in Mat_{k\times 1}(F)\implies ABv_2=0$] $\geq 0.$

$\endgroup$
  • 2
    $\begingroup$ I have a doubt in the last line of the proof. Ker(B) ⊆ker(AB) implies nullity(B) <= nullity(AB). So nullity(B)-nullity(AB) <=0 which means nullity(A)+nullity(B)-nullity(AB) <=nullity(A). But in your proof its the other-way. May I know how? $\endgroup$ – La Rias Nov 15 '15 at 6:42
2
$\begingroup$

As noted in the other answer, it suffices to show $\dim\ \operatorname{Ker}(A)+\dim\ \operatorname{Ker}(B) \geq \dim\ \operatorname{Ker}(AB)$. This is equivalent to showing that $\dim\ \operatorname{Ker}(AB)/\operatorname{Ker}(B) \leq \dim\ \operatorname{Ker}(A)$. To do this, use the first isomorphism theorem for vector spaces on the linear map $\operatorname{Ker}(AB) \rightarrow \operatorname{Ker}(A)$ defined by $x \mapsto Bx$. This shows that $\operatorname{Ker}(AB)/\operatorname{Ker}(B)$ is isomorphic to a subspace of $\operatorname{Ker}(A)$, which proves the inequality.

$\endgroup$
1
$\begingroup$

We claim $\dim \ker\,A+\dim\ker B \geq \dim\ker AB$.

Let $\beta=\{\alpha_1,\dots,\alpha_r \}$ be basis for $\ker B$. It is not hard to see that $\ker B\subseteq \ker AB$ so we can extend $\beta $ to basis for $\ker AB$. Suppose $\{\alpha_1,\dots,\alpha_r,\alpha_{r+1},\dots,\alpha_n \ \}$ be basis for $\ker AB$. So $B(\alpha_{i})\neq 0$ for $i \in \{r<i<n+1\}$. It is easily seen that $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent. We have $\dim\ker A\geq n-r$.

$$\dim\ker A+\dim\ker B \geqslant n-r+r =n \Longrightarrow\dim\ker A+\dim\ker B \geqslant \dim\ker AB$$

$\endgroup$
  • 1
    $\begingroup$ Why $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent ? $\endgroup$ – user185640 Mar 9 '17 at 20:46
0
$\begingroup$

Because I can't comment (yet), I will answer @user185640's question in a comment to @Babak Miraftab's answer which is "Why $\{B(\alpha_{r+1}),\ldots,B(\alpha_n)\}$ is linear independent" in this post.

Now, suppose $\sum_{i=r+1}^{n}c_i B(\alpha_i) = 0$ for some $i \in K$ where $K$ is the scalar field.

This would imply: $$B \left(\sum_{i=r+1}^{n}c_i\alpha_i\right) = 0$$

Hence, it is immediate to see that $\sum_{i=r+1}^{n}c_i\alpha_i \in \ker B$. But in his proof we know $\beta$ is a basis for $\ker B$. So we can write $\sum_{i=r+1}^{n}c_i\alpha_i$ as $\sum_{i=1}^{r}d_i\alpha_i$ for some $d_i \in K$. In particular we can write it as the following:

$$\sum_{i=r+1}^{n}c_i\alpha_i = \sum_{i=1}^{r}d_i\alpha_i \implies \sum_{i = r+1}^{n}c_i\alpha_i - \sum_{i=1}^{r}d_i\alpha_i = 0$$

To see this even more clearer, we can expand the sum to see this:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} - d_1\alpha_1 - \ldots - d_r\alpha_r = 0$$

This may look unusual but it is not. We can further rewrite it as:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} + (-d_1)\alpha_1 + \ldots + (-d_r)\alpha_r = 0$$

Let $e_i =-d_i$ for $i = 1,\ldots,n$ to see things even more clearer. We can then rewrite the above as:

$$c_{r+1} \alpha_{r+1} + \ldots + c_{n} \alpha_{n} + e_1\alpha_1 + \ldots + e_r\alpha_r = 0$$

Now since $\{\alpha_1, \ldots, \alpha_n\}$ is linearly independent (as it is a basis for $\ker AB$), we must have that

$$c_{r+1} = \ldots = c_n = e_1 = \ldots = e_r = 0$$

In particular, $$c_{r+1} = \ldots = c_n = 0$$

which directly implies that indeed $B(\alpha_{r+1}),\ldots,B(\alpha_n)$ are linearly independent and hence the set containing these vectors is a linearly independent set. Done.

$\endgroup$

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.