It's best to read about Caratheodory's theorem, to know we're trying to prove.

Caratheodory's theorem on convex sets is essentially equivalent to Radon's theorem; we'll use that theorem in our proof.

Suppose x = ∑k=1mxkxk is a convex combination of m>d+1 points. We need to show that x is a convex combination of m-1 of these points (this is the equivalent formulation given).

By Radon's theorem (and since m>d+1 is large enough!), we can divide our m points into 2 nonempty sets of points (WLOG x1,...,xl and xl+1,...,xm) whose convex hulls share a point:

i=1laixi = ∑i=l+1mbixi
ai >= 0, bj >= 0, ∑ai = ∑bj = 1
Furthermore, one of the b's, WLOG bm, satisfies ∀k:ck/bk >= cm/bm (every finite set has a minimum!).

Isolating xm, we have:

xm = (∑i=1laixi - ∑i=l+1m-1bixi) / bm
Substituting for x, we may write x as a linear combination of the points x1,...,xm-1 (this in itself is no surprise; it's true for any linear combination of >d points in Rd! The point is we'll show it's a convex combination...):
x = ∑i=1l(ci+aicm/bm)xi + ∑i=l+1m-1(ci-bicm/bm)xi
Checking, we find the sum of the coefficients is 1 (this is not surprising), so it's an affine combination.

It remains to prove that all coefficients are nonnegative. Those involving ai are just sums of positive numbers, so there's no problem. And for each l+1<=i<m, we have ci>=bicm/bm) due to how we arranged the coefficients.

So x is a convex combination of m-1 points. We may continued to eliminate points from the convex combination until only d+1 are left; at that point, Radon's theorem could fail, so no further reduction is possible.

Log in or registerto write something here or to contact authors.