Expressing a rank-$k$ matrix as a sum of $k$ rank-$1$ matrices

Question

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

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?

Answer 1

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.

Answer 2

Let $F_1,\cdots, F_m$ denote the rows of the matrix. Assume $\mathrm{rank}( A)=k$ and that $F_1,\cdots, F_k$ are linearly independent. Then, for $i=k+1,\cdots, m$ you there exists real numbers such that $$F_i=\alpha_{i1}F_1+\cdots +\alpha_{ik}F_k.$$ Now, let $A_j$ ($j=1,\cdots, k$) the matrix whose transpose is given by

$$\left(0,\cdots,0,F_j,\cdots, 0, \alpha_{k+1,j}F_j,\alpha_{k+2,j}F_j,\cdots ,\alpha_{m,j}F_j \right)$$

Then, we have

$$A=A_1+\cdots+A_k.$$

Answer 3

Think of $A$ as a linear operator from $\mathbb{R}^n$ to $\mathbb{R}^m$.

Let $V \subset \mathbb{R}^m$ the image of $A$. It has dimension $k$. Let $$\pi_V \colon \mathbb{R}^m \to \mathbb{R}^m$$ the projection with image $V$. Then $$A = \pi_V \circ A$$

Decompose $V$ into a direct sum of $1$-dimensional subspaces $$V = V_1 \oplus \ldots \oplus V_k$$ We have $$\pi_V = \sum_{i=1}^k \pi_{V_i}$$ a decomposition of $\pi_V$ as a sum of projectors of rank $1$. This give the decomposition $$A = \sum_{i=1}^k \pi_{V_i} \circ A $$