The Product $AB$ can be Written as a Sum of Rank $1$

Question

Let $A$ be an $m \times n$ matrix and $B$ be a $n \times \ell$ matrix. Prove that $AB$ can be written as a sum of $n$ matrices of rank one.

I am having trouble seeing how this is true. Here is the best solution I could come up with. Let $A_p \in M_{m \times n}$ have its $p$-th column equal to $A$' $p$-th column, with zeros elsewhere, and let $B_q$ be matrix whose $j$-th column is $B$'s $j$-th column, with zeros elsewhere. Clearly then $A = \sum A_p$ and $B = \sum B_q$. Then

$$AB = \sum_{p,q=1}^n A_p B_q$$

$$= \sum_{p=1}^n A_p B_p + \sum_{p \neq q}^n A_p B_q$$

I claim that $A_p B_q = 0$ if $p \neq q$. To see this, consider the $(i,j)$-th entry of $A_pB_q$:

$$(A_pB_q)_{ij} = \sum_{k=1}^n (A_p)_{ik}(B_q)_{kj}$$

$$= (A_p)_{ip}(B_q)_{pj} + (A_p)_{iq}(B_q)_{qj} + \sum_{k \neq p,q}^n (A_p)_{ik}(B_q)_{kj}$$

Now, if neither $k=p$ nor $k=q$, then $(A_p)_{ik}=(B_q)_{kj}=0$, which means the sum on the LHS vanishes. When $k=p$, $(B_q)_{pj}=0$ since $B_q$ has zeros across every row, except possibly the $q$-th row; and a similar conclusion is drawn when $k=q$. Thus $(A_pB_q)_{ij}=0$.

---

As I was typing this up, I made a crucial mistake: I thought that the $p$-th column of $A_pB_P$ was equal to $AB$ and had zeros elsewhere. I tried this on specific $3 \times 3$ $A$ and $B$ and found that every entry of $A_1B_1$ was nonzero; I did find that the $1$-st and $3$-rd column of my example were multiples of each other. So, it may be possible to fix this proof, but I cannot see it.

In any case, these matrices $A_pB_p$ are clearly not necessarily rank $1$ matrices. What I find disconcerting is that both link1 and and link2 give roughly the same answer (cf problem 18 on page 75 and 170, respectively), except they conclude that matrices in the sum are of rank at most $1$, which is the conclusion I am coming to draw. So, is this an error in the book.

Answer 1

$A = \sum_{p=1}^n A_p$ so $AB = \sum_{p=1}^n A_p B$, and $A_p B$ has rank $\le 1$ (hint: what do you know about the rank of a product of two matrices, in terms of the ranks of the two matrices?)

Answer 2

For $n=1$ the claim is false when $AB = 0$. For any other $n>1$, the claim may be salvaged as follows: if the constituent terms in the sum are all identically zero, then we can replace any pair with $\pm C$ where $C$ is a rank-one matrix of the appropriate size. Thus WLOG we can assume at least one term $C$ is is non-zero, in which case we may replace it with $k$ copies of $C/k$ where $k$ is chosen to make the number of rank-1 terms exactly equal to $n$ (and drop the all the rank-0 summands).

But more likely, the author of the question just intended to use "of rank one" to mean "of rank $\le 1$", which is a very common usage that unfortunately is confusing here.