It's a well known fact that for any matrix $A \in \Bbb R^{m \times n}$ which is the sum of $k$ matrices $A_1,\dots,A_k\in \Bbb R^{m \times n}$ of rank $1$, it holds that $\operatorname{rank}(A) \le k$.
My question is, does it hold that for any matrix $A \in \Bbb R^{m \times n}$ of rank $k$ there exist a set of matrices $A_1, \dots ,A_k \in \Bbb R^{m \times n}$ of rank $1$ such that $A = A_1 + \cdots + A_k$? It may seem as a direct consequence of the aforementioned proposition, but it doesn't seem that obvious, at least for me. Can someone guide me to a typical proof of it?
Best Answer
Let $A = U \Sigma V^T$ be the SVD of $A$, where $U$ and $V$ are orthogonal and $\Sigma = \operatorname{diag}(\sigma_1, \dots, \sigma_{\min\{m,n\}})$. We usually take $\sigma_1 \ge \sigma_2 \ge \dots$, so $\sigma_i = 0$ for $i > k$. Define
$$\Sigma_i := \operatorname{diag}(0, \dots, 0, \sigma_i, 0, \dots, 0),$$
i.e., it has $\sigma_i$ at $i$-th position and zeroes everywhere else. Obviously, $\Sigma = \sum_i \Sigma_i$ and $\Sigma_i \ne 0$ if and only if $i \in \{1,\dots,k\}$, so
$$A = U \Sigma V^T = U \left( \sum_i \Sigma_i \right) V^T = \sum_{i=1}^k U \Sigma_i V^T$$
is a desired sum.