# Prove that if matrix $A$ is an $m\times n$ and $B$ is $n\times p$, then $\operatorname{rank} AB$ is less than or equal to $\operatorname{rank} B$

Prove that if $A$ is an $m\times n$ matrix and $B$ is an $n\times p$ matrix, then $\operatorname{rank} AB$ is less than or equal to $\operatorname{rank} B$.

The hint is: prove that if the $k$th column of $B$ is not a pivot column, then the $k$th column of $AB$ is not a pivot column of $AB$.

I don't think I am allowed to use row space, column space or the Sylvester's inequality as we haven't learned them yet in the class.

I have been stuck here for ages, so hints or solutions are very appreciated.

-
You are not allowed to use the concepts of row space and column space? What is the definition of the rank of a matrix then? –  user1551 Mar 18 '13 at 16:22
Well I guess my teacher haven't named those spaces yet... will first appear 2 chapters later according to the book. Though I do get ur point there. –  Patrick Olsen Mar 18 '13 at 16:27
That's fine, but what exactly is your textbook definition of the rank of a matrix? Without knowing that, people cannot help. –  user1551 Mar 18 '13 at 16:30

The trick is to use block multiplication. If we write $B$ columnwise as $$B=\begin{pmatrix}\mathbf{b}_1 & \cdots & \mathbf{b}_p\end{pmatrix}$$ then we may express $AB$ in the same way as $$AB = \begin{pmatrix}A\mathbf{b}_1 & \cdots & A\mathbf{b}_p\end{pmatrix}$$ To this end, it follows that if column $i$ of $B$ is originally a linear combination of the other columns of $B$, then we also have column $i$ of $AB$ as a linear combination of the other columns of $AB$. This shows that the number of linearly dependent columns of $AB$ is at least the number of linearly dependent columns of $B$. In other words, the number of linearly independent columns of $AB$ is at most the number of linearly independent columns of $B$, i.e. $$\rm rank(B) \ge \rm rank(AB)$$ You'll probably need to air out the above argument a bit, but this is the general idea.