The
proof of
Radon's theorem is little more than an imaginative
exercise in
linear algebra, but (like the
theorem) it always seems to me to reveal some of the
structure of
Rd. In any case, make sure you read
what we're proving before reading the proof...
So suppose we're given d+2 points x0,...,xd+1∈Rd (the theorem is true for any n>=d+2 points, but obviously adding more points just makes it easier to prove). Then these points have some affine dependence, and WLOG (maybe after reordering the points) we may write
xd+1 = ∑i=0d cixi,
∑i=0d ci = 1.
Since their sum is
positive,
some of the c
i's must be positive, and WLOG (again, after reordering the points) we may say c
0,...,c
k > 0 >= c
k+1,...,c
d.
Rewrite the affine dependence all coefficients separated by their signs:
xd+1 + ∑i=k+1d (-ci)xi =
∑i=0k cixi.
The point here is that
all coefficients appearing are positive!
Now let S = ∑i=0k ci = 1 - ∑i=k+1d ci > 0. Write bi=ci/S for 0<=i<=k, bi=-ci/S for k<i<=d, and bd+1=1/S. Then all the bi's are positive, ∑i=0kbi = ∑i=k+1d+1bi = 1, and we have the equal convex combinations
∑i=0k bixi = ∑i=k+1d+1 bixi
Q.E.D.!