38
$\begingroup$

How to prove $\text{Rank}(AB)\leq \min(\text{Rank}(A), \text{Rank}(B))$?

$\endgroup$
2
  • 17
    $\begingroup$ The rank of a matrix $A$ which maps $V$ to $W$ is the same as the dimension of the image of $V$, which will be some subspace $U$. $AB$ is the composite of two linear maps. Try tracking the image and its dimension through subspaces as you do one after the other. $\endgroup$ Jul 2, 2011 at 7:14
  • 3
    $\begingroup$ math.stackexchange.com/questions/978/… $\endgroup$
    – user92843
    Jul 2, 2011 at 12:08

5 Answers 5

38
$\begingroup$

Hint: Show that rows of $AB$ are linear combinations of rows of $B$. Transpose this hint.

$\endgroup$
3
  • $\begingroup$ I know how to prove this but I just hate when someone is clearly asking for help and the answer is, "hint:" $\endgroup$
    – Maxim
    Mar 6, 2023 at 0:37
  • $\begingroup$ I understand @Maxim. As you can tell from the vote tallies, the site culture was very different in 2011. The average level of studies of the participants (and the questions) was also a bit higher. This has probably been upvoted as a pithy one-liner rather than pedagogical merits (which still are IMO ok). You are not the only one feeling this way. There is also a "secret" tally of unregistered votes from passers by, who were not eligible to downvote. This answer has raked in a number of such votes. Anyway, if posted today, the question would be closed rather speedily. $\endgroup$ Mar 6, 2023 at 5:16
  • $\begingroup$ (cont'd) Because this is first and foremost a Q & A site, not a help site. And the question does not show any research whatsoever. $\endgroup$ Mar 6, 2023 at 5:18
36
$\begingroup$

I used a way to prove this, which I thought may not be the most concise way but it feels very intuitive to me. The matrix $AB$ is actually a matrix that consist the linear combination of $A$ with $B$ the multipliers. So it looks like... $$\boldsymbol{AB}=\begin{bmatrix} & & & \\ a_1 & a_2 & ... & a_n\\ & & & \end{bmatrix} \begin{bmatrix} & & & \\ b_1 & b_2 & ... & b_n\\ & & & \end{bmatrix} = \begin{bmatrix} & & & \\ \boldsymbol{A}b_1 & \boldsymbol{A}b_2 & ... & \boldsymbol{A}b_n\\ & & & \end{bmatrix}$$ Suppose if $B$ is singular, then when $B$, being the multipliers of $A$, will naturally obtain another singular matrix of $AB$. Similarly, if $B$ is non-singular, then $AB$ will be non-singular. Therefore, the $rank(AB) \leq rank(B)$.

Then now if $A$ is singular, then clearly, no matter what $B$ is, the $rank(AB)\leq rank(A)$. The $rank(AB)$ is immediately capped by the rank of $A$ unless the the rank of $B$ is even smaller.

Put these two ideas together, the rank of $AB$ must have been capped the rank of $A$ or $B$, which ever is smaller. Therefore, $rank(AB) \leq min(rank(A), rank(B))$.

Hope this helps you!

$\endgroup$
1
  • $\begingroup$ In your first part how do you say that Similarly, if $B$ is non-singular, then $AB$ will be non-singular. I dont think you can jump to this conclusion at once. $\endgroup$
    – Upstart
    Jan 15, 2022 at 15:32
25
$\begingroup$

Since we have $\text{Col }AB \subseteq \text{Col }A$ and $\text{Row }AB \subseteq \text{Row }B$, therefore $\text{Rank }AB \leq \text{Rank }A$ and $\text{Rank }AB \leq \text{Rank }B$, then the result follows.

$\endgroup$
2
12
$\begingroup$

You know that a linear transformation cannot increase the dimension of its domain; i.e. If $T: V\rightarrow W$ is a linear transformation, $$\dim(T(V))\le \dim(V).$$

$\endgroup$
7
$\begingroup$

Surely vectors that are in the kernel of $B$ are also in the kernel of $AB$. Vectors that are in the kernel of $A^T$ are also in the kernel of $(AB)^T=B^TA^T$ therefore with the fact that Rank($A$)=Rank($A^T$) and the knowledge that the rank gives you the size of the kernel of a matrix you are done.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .