Let S be a nonempty subset of a linear space and let m dim cone S For every x cone S, there exist x1,x2, ,xn S and Icirc plusmn 1, Icirc plusmn 2, , Icirc plusmn n Such that x Icirc plusmn 1x1 Icirc plusmn 2x2 Icirc plusmn nxn (14) 1 If n m dim cone S, show that the elements x1 x2 , xn S are linear...

1 If dim cone dim lin the elements x 1 x 2 x are linearly depen ...

Let S be a nonempty subset of a linear space and let m dim cone S. For

Question:

Let S be a nonempty subset of a linear space and let m ˆ dim cone S. For every x ˆˆ cone S, there exist x1,x2,...,xn ˆˆ S and Î±1, Î±2, . . ., Î±n ˆˆ „œ + Such that
x = Î±1x1 + Î±2x2 + . . . + Î±nxn (14)
1. If n > m = dim cone S, show that the elements x1; x2; . . . , xn ˆˆ S are linearly dependent and therefore there exist numbers Î²1; Î²2; . . . , Î²n, not all zero, such that

2. Show that for any number t, x can be represented as

3. Let t = mini {Î±i/Î²i: Î²i > 0 }. Show that Î±i - tÎ²i = 0 for at least one t. For this particular t, (14) is a nonnegative representation of x using only n - 1 elements.
4. Conclude that every x ˆˆ cone S can be expressed as a nonnegative combination of at most dim S elements.