How to determine if a subset of rank-1 matrices can sum to a full-rank matrix?

[Pere Callahan]

HI,

I came across the following question, which I could only solve for one trivial special case. I'm hoping for help from your side on how to deal with the general case.

Assume we are in the situation that we have a decomposition of a full-rank d x d matrix, M, into a sum of N rank-1 matrices, N>d, in formulas,
[tex]
M = m_1+\ldots+m_N.
[/tex]

I'm interested in whether or not one can in general conclude that there exists a subset [itex]\{m_{k_1},\ldots,m_{k_d}\}[/itex] whose sum is a full-rank (that is rank d) matrix.

The special case I mentioned is the case d=1, in which case there is nothing to prove
What I tried is writing the rank 1 matrices [itex]m_n[/itex] as an outer product of vectors, that is [itex]m_n=b_n\otimes a_n[/itex]. Then the assumption that the sum of the [itex]m_n[/itex] have full rank certainly implies that the [itex]b_n[/itex] span all of [itex]\mathbb{R}^d[/itex], so in looking for a subset whose sum is rank d I started with choosing a basis from among the [itex]b_n[/itex]; i did not succeed, however, in showing that the sum of the corresponding [itex]m_n[/itex] is a full rank matrix.I would appreciate any tips from you,

Thanks,
Pere

 

[fantispug]

Yes, it is true. I'll outline the proof, and let you fill in the details.

For each column there exists a matrix in the decomposition with non-trivial elements in that column.

So if we choose the kth element of our subset as the one with non-zero entries in the kth column the sum of this subset must be full rank.