Basis of the image of the product of two matrices

Question

We have $A \in \mathbb R ^{\mathrm {mxn} }$ and $B \in \mathbb R ^{\mathrm {nxp}}$ which are two matrices. It is said that $\{ b_1, b_2, ..., b_k\}$, where $k \leq q$, is a basis for $\mathrm{Im}(B)$ and that $\mathrm{Ker}(A)\cap \mathrm{Im}(B) = \{ \vec{0}\}$. We have to show that $\{ Ab_1, Ab_2, ..., Ab_k \}$ form a basis for $\mathrm{Im}(AB)$.

I've tried fiddling with the rank nullity theorem, leading me to this: $$\dim (\mathrm{Im}(AB)) = \dim (\mathrm{Im}(B)) - \dim(\mathrm{Ker}(A)\cap \mathrm{Im}(B)) $$ which makes sense since $\dim(\mathrm{Ker}(A)\cap \mathrm{Im}(B)) = 0 $ (since it only contains the null vector) and since we are asked to show that the basis for $\mathrm{Im}(AB)$ is $\{ Ab_1, Ab_2, ..., Ab_k \}$ (i.e a set with $k$ vectors). But, unfortunately I don't where to go from here. The only thing I've shown is that $\dim (\mathrm{Im}(AB)) = k$

Another approach I tried to have to solve this problem was the following: $$AB\vec{x} = \vec{0} \\ \Leftrightarrow A(B\vec{x}) = \vec{0} \\ \Rightarrow B\vec{x}\in \mathrm{Ker}(A) \\ \text{and}\ B\vec{x}\in \mathrm{Im}(B)$$ but again I don't know where to go from here.

Answer 1

If you want to show that $\{A b_i\}_{i=1}^k$ is a basis, show first that $\{A b_i\}_{i=1}^k$ spans Im$AB$, then show that $\{A b_i\}_{i=1}^k$ is a set of linearly independent vectors. To see that it spans: pick $x \in \mathrm{Im}AB$. That means there exists $z$ such that $x = ABz$. Since $Bz \in \mathrm{Im}B$ and $\{b_i\}_{i=1}^k$ is a basis, there exists real numbers $a_i$ such that $$ Bz = \sum_{i=1}^k a_i b_i \implies \sum_{i=1}^k a_i Ab_i = A\sum_{i=1}^k a_i b_i = ABz = x , $$ which proves that $\{Ab_i\}_{i=1}^k$ spans Im$AB$. It remains to prove that $\{Ab_i\}_{i=1}^k$ are independent. To see that this is true, assume that $$ 0 = \sum_{i=1}^k a_i Ab_i \implies 0 = A\sum_{i=1}^k a_i b_i \implies \sum_{i=1}^k a_i b_i \in \mathrm{Ker}A. $$ We see also $\sum_{i=1}^k a_i b_i \in \mathrm{Im}B$ because Im$B$ is a linear subspace and $\{b_i\}_{i=1}^k$ is a basis, hence $\sum_{i=1}^k a_i b_i \in \mathrm{Im}B$. So $\sum_{i=1}^k a_i b_i \in \mathrm{Ker} A \cap \mathrm{Im} B$. That means $\sum_{i=1}^k a_i b_i = 0$. But since $\{b_i\}_{i=1}^k$ is a basis, that means $\sum_{i=1}^k a_i b_i = 0$ only has the trivial solution $a_i = 0$ for all $i \in \{1,2,\dots,k\}$ , which proves that $\{Ab_i\}_{i=1}^k$ are linearly independent.

Answer 2

Notice that $\ \mathrm{Ker}(A)\cap\mathrm{Im}(B) = \{ \vec{0}\}$ tell you that the only vector being in both $\mathrm{Ker}(A)$ and $\mathrm{Im}(B)$ is the zero vector, so:

$$ B\vec{x}\in\mathrm{Im}(B) \quad (\text{trivially})$$ and $$ A(B\vec{x})=\vec{0} $$ means that $B\vec{x}\in\mathrm{ker}(A)$, so $$B\vec{x}\in\mathrm{Ker}(A)\cap\mathrm{Im}(B) = \{ \vec{0}\}.$$ So $$ A(B\vec{x})=\vec{0} \Longrightarrow B\vec{x}=\vec{0}$$

therefore the condition $\mathrm{Ker}(A)\cap\mathrm{Im}(B) = \{ \vec{0}\}$ means that the linear transformation $\vec{x}\longmapsto A\vec{x}$ is injective on $\mathrm{Im}(B)$ and so if $\{b_1,\ldots,b_k\}$ is a basis of $\mathrm{Im}(B)$, then $\{Ab_1,\ldots,Ab_k\}$ is also a basis for $\mathrm{Im}(AB)$.

Answer 3

This is a special instance of Sylvester's Rank Formula. I will prove the general case for you and you should be able to modify it for this special case by looking at the proof methodology. Note that $Im(AB) = Col(AB)$.

$ \\ $

I claim the following:

$$Rank(AB) = Rank(B) - dim\left(Nul(A) \cap Col(B)\right)$$

Proof : Let $\{b_1,b_2,\dots b_s \}$ be basis for $Nul(A) \cap Col(B)$. This is a subspace of $Col(B)$ so we can extend

this to a basis of $Col(B)$, say

$$ \{b_1,b_2,\dots b_s,w_1,w_2,\dots w_t\} \text{ where } s+t = n$$

I claim that $$\{Aw_1,Aw_2,\dots Aw_t\} \text{ is a basis for } Col(AB)$$

$ \\ $

We Must show that it is both linearly independent and it spans $Col(AB)$

To show linear independence, suppose $$\sum_{i = 1}^t c_i Aw_i = \vec{0} \text { for some } c_i \in \mathbb{R}$$

Then by linearity, $$\vec0 = \sum_{i = 1}^s c_i Aw_i = \sum_{i = 1}^t A(c_iw_i) = A \left(\sum_{i = 1}^t c_i w_i \right)$$

Therefore, $$\sum_{i = 1}^t c_iw_i \in Nul(A)$$.

We also have $w_i \in Col(B)$ since they are part of a basis for it. Thus,

$$\sum_{i = 1}^t c_iw_i \in Nul(A) \cap Col(B)$$ which means that we can write it as a linear combination of the basis elements for

$Nul(A) \cap Col(B)$ given above.

Thus, $$\sum_{i = 1}^t c_i w_i = \sum_{i = 1}^s d_ib_i \text{ for some }d_i \in \mathbb{R}$$

Subtracting the sum on the other side we have $$c_1w_1 +c_2w_2 + \cdots c_sw_t +(-d_1)b_1+(-d_2)b_2 + \cdots (-d_s)b_s = \vec{0}$$

$ \\ $

Thus we must have all $c_i,d_i = 0$ since $\{b_1,b_2,\ldots w_1,w_2,\ldots w_t\}$ is a basis for $Col(B)$ and hence

linearly independent.

$ \\ $

In particular $c_i = 0$ for all $i$.

$ \\ $

For spanning, let $\vec y = AB\vec x \in Col(AB)$, then $Bx \in Col(B)$ so we can write $$Bx = c_1b_1+c_2b_2 + \cdots d_1w_1+d_2w_2 + \cdots d_sw_t \text { for some }c_i,d_i$$

$ \\ $

Then using the fact that the $b_i \text{ are in } Nul(A)$, we can write

$$\vec{y} = AB\vec{x} = A(B\vec{x}) = A(c_1b_1+c_2b_2 + \cdots d_1w_1+d_2w_2 + \cdots d_sw_t)$$ $$ = c_1Ab_1+c_2Ab_2 +\cdots d_1Aw_1+d_2Aw_2 + \cdots d_sAw_t = 0 + d_1Aw_1 + d_2Aw_2 + \cdots d_sAw_t$$ $$ = \sum_i d_i Aw_i$$

$ \\ $

Thus the set is also spanning, and we're done. You should be able to use this reasoning to answer your question.