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


Also show when equality occurs.

  • 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$ – TheRealFakeNews Jan 3 '13 at 1:00
  • 1
    $\begingroup$ Hint: Sylvester's Rank Inequality. Regards $\endgroup$ – Amzoti Jan 3 '13 at 1:43
  • $\begingroup$ Another Hint: Frobenius Inequality. Regards $\endgroup$ – Amzoti Jan 3 '13 at 6:17
  • $\begingroup$ See also: math.stackexchange.com/questions/298836/… $\endgroup$ – Martin Sleziak May 28 '16 at 14:03

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

Let $\beta=\{\alpha_1,\dots,\alpha_r \}$ be a basis for $\ker B$. It is not hard to see that $\ker B\subseteq \ker AB$ so we can extend $\beta $ to a 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\}$.

We show that $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent. We have $\dim\ker A\geq n-r$. Assume that $\sum_{i=r+1}^n\gamma_iB(\alpha_i)=0$. In other words we have $B(\sum_{i=r+1}^n\gamma_i\alpha_i)=0$ and as a result $\sum_{i=r+1}^n\gamma_i\alpha_i$ belongs to the kernel of $B$. On other hand we already know that $\beta=\{\alpha_1,\dots,\alpha_r \}$ is a basis for the kernel B. Next since the set $\{\alpha_1,\dots,\alpha_r,\alpha_{r+1},\dots,\alpha_n \ \}$ is an independent set, we infer that all $\gamma_i$ must be zero.

Now one can see that $$\dim\ker A+\dim\ker B \geqslant n-r+r =n \Longrightarrow\dim\ker A+\dim\ker B \geqslant \dim\ker AB$$

  • 2
    $\begingroup$ Why $\{B(\alpha_{r+1}),\dots,B(\alpha_{n})\}$ is linear independent ? $\endgroup$ – user185640 Mar 9 '17 at 20:46
  • $\begingroup$ If they are linearly dependent, then either $\alpha_{r+1} \ldots \alpha_{n}$ are LD or linear combinations of them is in $N(B)$. Both are not true. Hence they have to be LI $\endgroup$ – Nagabhushan S N Oct 14 '20 at 8:20

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

  • 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

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.


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.


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.