Proving Matrix X rank Decomposition

[rhuelu]

How can you prove that matrix X with rank n can be written as the sum of matrices Y and Z where Y has rank n-1 and Z has rank of 1. Thanks!

 

[maze]

It may be helpful to think of matrix products as sums of rank-1 matrices. For example, consider matrices A and B and their product AB. If the columns of A are a1, a2, ..., and the rows of B are b1*, b2*, ..., then the product is

AB = \left[\begin{array} & a_1 \vline a_2 \vline ... \vline a_n\end{array}\right]\left[\begin{array} & b_1^* & \hline & b_2^* & \hline & \vdots & \hline & b_n^*\end{array}\right] = \sum_{i=1}^n a_i b_i^*

Where a_i b_i^* are all rank-1 matrices.

Now if you have a matrix M, all you have to do is find any decomposition of it (M = AB), and you can write it as the sum of rank-1 matrices. M = MI works just fine (can you see what this is this in summation form?), or you could use any other factorization you like. The SVD is particularly enlightening in this regard.