Let S be a nonempty subset of a linear space, and let m = dim S = dim aff S. Suppose that x belongs to conv S so that there exist x1, x2, . . . , xn ˆˆ S and a1, a2, . . . , an ˆˆ R+ with a1,......, a2+...........+ an = 1 such that
x = a1x1 + a2x2 +..............+ anxn … 10†
1. If n > dim S + 1, show that the elements x1, x2, . . . , xn ˆˆ S are affinely dependent, and therefore there exist numbers b1, b2, . . . , bn, not all zero, such that

And
β1 + β2 +...............+ βn = 0
2. Show that for any number t, x can be represented as

3. Let t = mini{ai/βi: βi > 0}. Show that ai - tβi > 0 for every t and ai - tβi = 0 for at least one t. For this particular t, (12) is a convex representation of x using only n - 1 elements.
4. Conclude that every x ˆˆ conv S can be expressed as a convex combination of at most dim S + 1 elements.

(12)