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

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.