3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I remember my teacher showed these inequalities using relationship between matrices and linear operators. $\endgroup$ – pointer Jun 9 '14 at 17:43
  • 1
    $\begingroup$ I'm sorry. This is actual link: math.stackexchange.com/questions/298836/… $\endgroup$ – pointer Jun 12 '14 at 8:23
5
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! Be careful, it should be $\text{rk}(B) - \text{dim} \; (\text{ker}(A) \cap \text{col}(B)) \geq \text{rk}(B) + \text{rk}(A) - n.$ $\endgroup$ – user100106 Jun 12 '14 at 18:01
  • $\begingroup$ oops! It seems I was a bit sleepy by the end of the proof. Thanks for pointing that out! $\endgroup$ – etothepitimesi Jun 12 '14 at 18:06
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I've totally mixed up things, your answer was pretty useful in clearing it up, thanks very much. And, yes, I've meant rk, not rg. $\endgroup$ – user100106 Jun 12 '14 at 18:03

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.