Matrices and rank inequality

Question

Let $A \in K^{m\times n}$ and $B \in K^{n \times r}$

Prove that min$\{rk(A),rk(B)\}\geq rk(AB)\geq rk(A)+rk(B)-n$

My attempt at a solution:

$(1)$ $AB=(AB_1|...|AB_j|...|AB_r)$ ($B_j$ is the j-th column of $B$), I don't know if the following statement is correct: the columns of $AB$ are a linear combination of the columns of $B$, then $rk(AB) \leq rk(B)$.

$(2)$In a similar way, $AB= \begin{bmatrix} —A_1B— \\ \vdots \\ —A_jB— \\ \vdots \\—A_mB— \end{bmatrix}$ ($A_j$ denotes the j-th row of $A$), so the rows of $AB$ are a linear combination of the rows of $A$, from here one deduces $rk(AB)\leq rk(A)$.

From $(1)$ and $(2)$ it follows $rk(AB)\leq min\{rk(A),rk(B)\}$.

This is what I've done so far. I am having doubts with, for example (1), this statement I've conjectured: the columns of $AB$ are a linear combination of the columns of $B$, then $rk(AB) \leq rk(B)$, but wouldn't this be the case iff $AB=(\alpha_1B_1|...|\alpha_jB_j|...|\alpha_rB_r)$ with $\alpha_1,...,\alpha_n \in K$ instead of $(AB_1|...|AB_j|...|AB_r)$ ? This is a major doubt I have, the same goes for (2).

I need help to show the inequality $rk(AB)\geq rk(A)+rk(B)-n$

Answer 1

Consider $A \in \mathbb{K^{m\times n}}$. I will use the following notation:

• column space of $A \equiv \text{col}(A) = \{ x \in \mathbb{K^m}: x=Ay, \text{ for some } y\in \mathbb{K^n} \}$;
• null space of $A \equiv \text{ker}(A) = \{ y \in \mathbb{K^n}: Ay=0\}$;
• rank of $A \equiv \text{rk}(A) = \text{dim} \; \text{col}(A)$.

Let's start by proving a very useful equality.

Theorem 1
If $A \in \mathbb{K^{m\times n}}$ and $B \in \mathbb{K^{n\times r}}$ then $$\text{rk}(AB)=\text{rk}(B) - \text{dim} \; ({ \text{ker}(A) \cap \text{col}(B)}).$$

Proof:

Take $S=\{x_1,...,x_s\}$ as a basis for $\text{ker}(A) \cap \text{col}(B)$ and note that $({ \text{ker}(A) \cap \text{col}(B)}) \subseteq \text{col}(B)$.

If $\text{dim} \; \text{col}(B) = s+t$, then we can find an extension set $S_e=\{ z_1,\ldots,z_t \}$ such that $U = \{ x_1, \ldots, x_s,z_1, \ldots, z_t\}$ is a basis for $\text{col}(B)$. Then, we just have to prove that $\text{dim}\;\text{col}(AB) = t$, which we can do by showing that $T=\{ Az_1, \ldots, Az_t \}$ is a basis for $\text{col}(AB)$.

In fact, we have that:

1. If $b \in \text{col}(AB)$ then $\exists y\in \mathbb{K^r}: b=ABy$. Now, $$By \in \text{col}(B) \Rightarrow By= \sum\limits_{i=1}^{s} {\xi_i x_i} + \sum\limits_{i=1}^{t} {\eta_i z_i}$$ so $$b=A \left( {\sum\limits_{i=1}^{s} {\xi_i x_i} + \sum\limits_{i=1}^{t} {\eta_i z_i}} \right) = \sum\limits_{i=1}^{s} {\xi_i \underbrace{Ax_i}_{={\bf{0}}}} + \sum\limits_{i=1}^{t} {\eta_i Az_i} = \sum\limits_{i=1}^{t} {\eta_i Az_i}.$$ Hence, $T$ spans $\text{col}(AB)$.
2. If ${\bf{0}} = \sum\limits_{i=1}^{t} {\alpha_i Az_i} = A \left( \sum\limits_{i=1}^{t} {\alpha_i z_i} \right)$, then $\sum\limits_{i=1}^{t} {\alpha_i z_i} \in \text{ker}(A) \cap \text{col}(B)$, so there are scalars $\beta_j$ such that $$\sum\limits_{i=1}^{t} {\alpha_i z_i} = \sum\limits_{j=1}^{s} {\beta_j z_j} \Leftrightarrow \sum\limits_{i=1}^{t} {\alpha_i z_i} - \sum\limits_{j=1}^{s} {\beta_j z_j} = {\bf{0}}.$$ Hence, recalling that $U$ is a basis for $\text{col}(B)$, therefore forming a linearly independent set, $\alpha_i=\beta_j=0$, so we conclude that $T$ is also a linearly independent set.

Thus $T$ is a basis for $\text{col}(AB)$, so $t= \text{dim} \; \text{col}(AB) = \text{rk}(AB)$, and we finally get $$\text{rk}(B) = \text{dim} \; \text{col}(B) = s + t = \text{dim} \; ({ \text{ker}(A) \cap \text{col}(B)}) + \text{rk}(AB).$$ Q.E.D.

i) Now, let's prove that $\text{rk}(AB) \leq \text{min} \{ \text{rk}(A),\text{rk}(B) \}$.

Resorting to Theorem 1, we have $$\tag{1} \text{rk}(AB)=\text{rk}(B) - \text{dim} \; ({ \text{ker}(A) \cap \text{col}(B)}) \leq \text{rk}(B).$$ Recalling that transposition does not alter rank, and again using Theorem 1, we get $$\tag{2} \text{rk}(AB)=\text{rk}(AB)^T = \text{rk}( B^T A^T) = \underbrace{\text{rk}(A^T)}_{=\text{rk}(A)} - \text{dim} \; ({ \text{ker}(B^T) \cap \text{col}(A^T)}) \leq \text{rk}(A).$$ From (1) and (2), we're able to conclude $$\text{rk}(AB) \leq \text{min} \{ \text{rk}(A),\text{rk}(B) \}.$$

ii) To prove $\text{rk}(A) + \text{rk}(B) - n \leq \text{rk}(AB)$, recall that if $X$ and $Y$ are vector spaces such that $X \subseteq Y$ then $\text{dim} \;X \leq \text{dim} \;Y$, and note that $\text{ker}(A) \cap \text{col}(B) \subseteq \text{ker}(A)$. We then have $$\text{dim} \; (\text{ker}(A) \cap \text{col}(B)) \leq \text{dim} \; \text{ker}(A) \mathop{=}^{\text{R-N}} n - \text{rk}(A)$$ where we have resorted to the Rank-Nullity Theorem (R-N) to get the last equality.

Plugging the last expression into Theorem 1, we arrive at $$\text{rk}(AB)=\text{rk}(B) - \text{dim} \; (\text{ker}(A) \cap \text{col}(B)) \geq \text{rk}(B) + \text{rk}(A) - n.$$

Answer 2

Use the dimension theorem on $A|_{\mathop{\rm Im}(B)}:\mathop{\rm Im}(B)\subseteq K^n\longrightarrow K^m$. Then $$\begin{align}\dim(\mathop{\rm Im}(B))&=\dim(\mathop{\rm Im}(A|_{\mathop{\rm Im}(B)}))+\dim(\mathop{\rm Ker}(A|_{\mathop{\rm Im}(B)}))\\&=\dim(\mathop{\rm Im}(AB))+\dim(\mathop{\rm Ker}(A)\cap\mathop{\rm Im}(B))\\&\leq\dim(\mathop{\rm Im}(AB))+\dim(\mathop{\rm Ker}(A)),\end{align}$$ and since $\dim(\mathop{\rm Ker}(A))=n-\dim(\mathop{\rm Im}(A))$, the claim follows.

Answer 3

$\DeclareMathOperator{\rg}{rg}$ $\DeclareMathOperator{\im}{im}$ (I assume $\rg$ denotes the rank, I haven't seen that notation before.)

Your arguments for the first part are almost correct. However, you seem to have "flipped" things. One way to see this is to check your dimensions: a linear combination of columns of $B$ would be a column vector with $n$ rows, but the columns of $AB$ have $m$ rows. Actually matrix multiplication $AB$ forms linear combinations of the columns of $A$, i.e. $$ A B_1 = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & \ddots & & \vdots \\ \vdots \\ a_{m1} & \cdots & & a_{mn} \end{bmatrix} \begin{bmatrix} b_{11} \\ b_{21} \\ \vdots \\ b_{n1} \end{bmatrix} = b_{11} \begin{bmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{bmatrix} + \cdots + b_{n1} \begin{bmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{bmatrix}. $$ This is very important to understand; you might want to verify this by multiplying a 3x3 matrix and checking it agrees with the above sum. In particular, observe that when you multiply matrices "by the formula", $b_{11}$ is always multiplied with the entries in the first column of $A$. More theoretically, the columns of A are the images of the basis vectors for K^n and we get the above formula by writing the vector in terms of this basis, i.e. as $$b_{11}(1,0,0,\ldots,0) + b_{21}(0,1,0,\ldots,0) + \cdots + b_{n1}(0,\ldots,0,1)$$ (the parenthesized terms are column vectors) and then linearity tells us that when we left-multiply by $A$, we get the expression above, where the basis vectors are replaced by the columns of $A$.

So in your problem, you should have written that each $AB_j$ is a linear combination of the column vectors of $A$. Now you may wonder, why does this mean $\rg(AB) \le \rg(A)$? Well (because rank = column rank) the rank of $AB$ is the dimension of the vector subspace spanned by the columns of $AB$. Since the columns of $AB$ lie in the subspace spanned by the columns of $A$, we know $$ \text{(subspace generated by columns of $AB$)} \subseteq (\text{subspace generated by columns of $A$}). $$ Taking the dimension of both sides gives the desired inequality (of column rank = rank).

After "unflipping" your other argument with the rows, you should be able to make a similar argument there.

Now for the second part of the problem, $\rg(AB) \ge \rg(A) + \rg(B) - n$, I am not aware of a "matrixy" way to show the inequality. However, if you know the rank-nullity theorem, then the problem is feasible. Here is a hint: think of (left multiplication by) $A$ as a linear map $\im B \to \im AB$. where $\im B$ denotes the image of $B$, i.e. the space spanned by the column vectors of $B$.