This puzzle requires some knowledge of Linear Algebra.

Suppose are m non-zero column vectors in with non-negative entries. Assume the span of the m vectors is of dimension . Assume . Consider the convex cone

Show that we can find vectors in with positive entries such that

Don't you want the vectors u_i to be non-negative too, Instead of positive?

Yes, non-negative. Sorry.

Rough sketch (intuition)

u₁,...,u_k have to be linearly independent. For instance, one solution could be the standard basis vectors (of k dimensions) that spans the same space as v₁,..,v_m.

We know that v₁,..,v_m are non-negative. So are the \theta_i. And the space spanned by them is k dimension. So, you can have k linearly independent vectors with non-negative entries that can span the same space.

My apologies that the statement of the puzzle doesn't hold. Here is a counter-example:

M=

[0 0 3/4 1/2

3/4 0 0 1/2

0 1/2 1/4 0

1/4 1/2 0 0 ]

It has rank 3 and all columns sum to 1. Hence all 4 points represented by the columns lie in an affine plane.

The intersection of the affine plane with the first hexant (set of positive vectors) is a quadrilateral with these 4 points. Hence you cannot find a triangle in the first hexant that contains these points. (or equivalently you cannot find 3 non-negative vectors whose span contains all 4 columns).