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

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.

i=1