# Expressing a matrix of rank $k$ as the sum of $k$ matrices of rank 1.

It's a well known fact that for any matrix $A \in R^{m \times n}$ which is the sum of $k$ matrices $A_1,...,A_k\in 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 R^{m \times n}$ of rank $k$ there exist a set of matrices $A_1,...,A_k \in R^{m \times n}$ of rank $1$ such that $A = A_1 + ... + 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?

• Set $A_1:=A$ and let the rest be the null matrix. – Git Gud Sep 30 '14 at 15:22
• @GitGud Thanks, but is there a more "complicated" way? – Kapoios Sep 30 '14 at 15:28

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.

• All the answers have satisfied me, but I choose yours as the easiest to conceive. :) – Kapoios Oct 1 '14 at 9:47

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

• Can you explain me what is a file of a matrix? I didn't ever encounter this concept in a coursebook. – Kapoios Jan 28 '15 at 23:45
• @Kapoios I have used the word "file" incorrectly. I wanted to write "row". Thank you for noticing this mistake. – mfl Feb 1 '15 at 3:02
• You're welcome! Now your answer makes perfect sense. – Kapoios Feb 1 '15 at 13:14

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