Prove that a matrix of rank r can be written as a sum of r rank-one matrices, but not as a sum of fewer than r rank-one matrices.

Step-by-step solution

1. 1

   Split the claim into two independent statements. "Exactly $r$ works" is an existence claim needing a construction; "fewer than $r$ fails" is an impossibility claim needing an inequality. The two halves use completely different tools, and neither implies the other.

2. 2

   Build a basis for the column space. Since $\operatorname{rank}(A)=r$, the column space of $A$ has dimension $r$, so $r$ linearly independent columns $u_1,\dots,u_r$ of $A$ span it. Every column $a_j$ of $A$ is then a combination

   $a_j=c_{1j}u_1+c_{2j}u_2+\cdots+c_{rj}u_r$

3. 3

   Package the combinations as a matrix product. Collecting the $u_i$ into an $m\times r$ matrix $U$ and the coefficients into an $r\times n$ matrix $C$ gives the rank factorisation

   $A=UC$

   This is the whole construction in compressed form - the rest is just reading it correctly.

4. 4

   Expand the product as outer products. Writing $v_i^{T}$ for the $i$-th row of $C$, block multiplication gives

   $A=UC=\sum_{i=1}^{r}u_i v_i^{T}$

   Each $u_iv_i^{T}$ has every column a scalar multiple of $u_i$, so its column space is spanned by the single vector $u_i$ and $\operatorname{rank}(u_iv_i^{T})=1$. That settles the first half.

5. 5

   Invoke subadditivity of rank for the second half. For any matrices, $\operatorname{rank}(B+C)\le\operatorname{rank}(B)+\operatorname{rank}(C)$, because the column space of $B+C$ is contained in the sum of the two column spaces. Iterating,

   $\operatorname{rank}(B_1+\cdots+B_k)\le\sum_{i=1}^{k}\operatorname{rank}(B_i)$

6. 6

   Derive the contradiction. Suppose $A=B_1+\cdots+B_k$ with each $\operatorname{rank}(B_i)=1$. Then

   $r=\operatorname{rank}(A)\le\underbrace{1+1+\cdots+1}_{k}=k$

   so $k\ge r$; no decomposition with $k<r$ can exist. Combined with the construction, the minimum number of rank-one summands is exactly $r$. $\blacksquare$