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
(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 +
Checking, we find the sum of the coefficient
s 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.