proof of Carathéodory’s theorem

The convex hull of P consists precisely of the points that can be written as convex combination of finitely many number points in P. Suppose that p is a convex combination of n points in P, for some integer n,


where α1++αn=1 and x1,,xnP. If nd+1, then it is already in the required form.

If n>d+1, the n-1 points x2-x1, x3-x1,,xn-x1 are linearly dependent. Let βi, i=2,3,,n, be real numbers, which are not all zero, such that


So, there are n constants γ1,γn, not all equal to zero, such that




Let be a subset of indices defined as


Since i=1nγi=0, the subset is not empty. Define


Then we have


which is a convex combination with at least one zero coefficient. Therefore, we can assume that p can be written as a convex combination of n-1 points in P, whenever n>d+1.

After repeating the above process several times, we can express p as a convex combination of at most d+1 points in P.

Title proof of Carathéodory’s theorem
Canonical name ProofOfCaratheodorysTheorem
Date of creation 2013-03-22 17:50:08
Last modified on 2013-03-22 17:50:08
Owner kshum (5987)
Last modified by kshum (5987)
Numerical id 4
Author kshum (5987)
Entry type Proof
Classification msc 52A20