POTW Is the Rank of AB Related to the Ranks of A and B?

[Euge]

Let $F$ be a field. If $A \in M_{n\times k}(F)$ and $B\in M_{k\times n}(F)$, show that $$\operatorname{rank}(A) + \operatorname{rank}(B) - k \le \operatorname{rank}(AB) \le \min\{\operatorname{rank}(A), \operatorname{rank}(B)\}$$

 

[julian]

Spoiler

First some preliminaries. The column space of a matrix $M$, denoted $\mathcal{C} (M)$, is the span of the columns of $M$ and the row space of a matrix $M$, denoted $\mathcal{R} (M)$, is the span of the rows of $M$. The column rank of a matrix $M$ is the dimension of the column space of $M$, while the row rank of $M$ is the dimension of the row space of $M$. It can be shown that the column rank is equal to the row rank, which is denoted $\text{rank} (M)$. Note $\mathcal{C} (M)$ is the $\text{range} (M)$.

For $M \in M_{k \times n} (F)$ we have by the rank-nullity theorem:

\begin{align*}
\dim \ker (M) + \dim \text{range} (M) = n .
\end{align*}

But $\dim \text{range} (M) = \dim \mathcal{C} (M) = \text{rank} (M)$. Therefore,

\begin{align*}
\dim \ker (M) + \text{rank} (M) = n \qquad (*)
\end{align*}

We have the inequality

\begin{align*}
\dim \ker (AB) \leq \dim \ker (A) + \dim \ker (B) \qquad (**)
\end{align*}

as

\begin{align*}
\dim \ker (AB) =\dim [\ker (A) \cap \text{range} (B)] + \dim \ker (B) .
\end{align*}

Using $(*)$ in $(**)$,

\begin{align*}
[n - \text{rank} (AB)] \leq [k - \text{rank} (A)] + [n - \text{rank} (B)]
\end{align*}

or

\begin{align*}
\text{rank} (A) + \text{rank} (B) - k \leq \text{rank} (AB)
\end{align*}

Next, the columns of $AB$ are linear combinations of columns of $A$ and are hence in its span so $\text{rank} (AB)$ is less than or equal to $\text{rank} (A)$. The rows of $AB$ are linear combinations of rows of $B$ and are hence in its span so $\text{rank} (AB)$ is less than or equal to $\text{rank} (B)$. Therefore,

\begin{align*}
\text{rank} (AB) \leq \min \{ \text{rank} (A) , \text{rank} (B) \} .
\end{align*}

 

[julian]

Supplementary

Spoiler

We elaborate on the proof of:

\begin{align*}
\dim \ker (AB) \leq \dim \ker (A) + \dim \ker (B) .
\end{align*}First, we have by the rank-nullity theorem:

\begin{align*}
\dim \ker (AB) = n - \dim \text{range} (AB) \qquad (*)
\end{align*}

Now, consider the linear transformation $A_{| \text{range} (B)} : \text{range} (B) \rightarrow F^n$ defined by $A_{| \text{range} (B)} x = A x$ for all $x \in \text{range} (B) \subseteq F^k$. Note $\text{range} (A_{| \text{range} (B)}) = \text{range} (AB)$. By the rank-nullity theorem applied to $A_{| \text{range} (B)}$:

\begin{align*}
\dim \text{range} (AB) = \dim \text{range} (A_{| \text{range} (B)}) = \dim \text{range} (B) - \dim \ker (A_{| \text{range} (B)})
\end{align*}

Note, by the rank-nullity theorem, $\dim \text{range} (B) = n - \dim \ker (B)$, therefore by the previous result

\begin{align*}
\dim \text{range} (AB) = n - \dim \ker (B) - \dim \ker (A_{| \text{range} (B)}) \quad (**)
\end{align*}

Using $(**)$ in $(*)$ we have

\begin{align*}
\dim \ker (AB) = \dim \ker (A_{| \text{range} (B)}) + \dim \ker (B)
\end{align*}

As $\ker (A_{| \text{range} (B)}) = \ker (A) \cap \text{range} (B)$,

\begin{align*}
\dim \ker (AB) = \dim [\ker (A) \cap \text{range} (B)] + \dim \ker (B) .
\end{align*}

Finally, as $\ker (A) \cap \text{range} (B) \subseteq \ker (A)$, we have $\dim [\ker (A) \cap \text{range} (B)] \leq \dim \ker (A)$, and thus

\begin{align*}
\dim \ker (AB) \leq \dim \ker (A) + \dim \ker (B) .
\end{align*}