2
$\begingroup$

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?

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

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.

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.