Log In

Convex cone

Posted on: July 31st, 2013 by
4

This puzzle requires some knowledge of Linear Algebra.
Suppose v_1, v_2, \dots v_m are m non-zero column vectors in \mathbb{R}^n with non-negative entries. Assume the span of the m vectors is of dimension k. Assume k<\text{min}(m,n). Consider the convex cone
\mathcal{C}=\left\{\theta_1 v_1+ \theta_2 v_2 + \dots \theta_m v_m ~~:~~\theta_i \ge 0,~i=1,2,\dots m\right\}
Show that we can find k vectors u_1,u_2,\dots u_k in \mathbb{R}^n with positive entries such that
\mathcal{C}\subseteq \left\{\theta_1 u_1+ \theta_2 u_2 + \dots \theta_k v_k ~~:~~\theta_i \ge 0,~i=1,2,\dots k\right\}


4 Responses to Convex cone

  1. Sushant S had this to say about that:

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

  2. Shiny had this to say about that:

    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.

  3. admin had this to say about that:

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


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}