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$,

$$p={\alpha }_1{x}_1+{\alpha }_2{x}_2+\mathrm{\dots }+{\alpha }_n{x}_n$$

where ${\alpha }_1+\mathrm{\dots }+{\alpha }_n=1$ and $x_1,\mathrm{\dots },x_n\in P$. If $n\le d+1$, then it is already in the required form.

If $n>d+1$, the $n-1$ points $x_2-x_1$, $x_3-x_1,\mathrm{\dots },x_n-x_1$ are linearly dependent. Let ${\beta }_i$, $i=2,3,\mathrm{\dots },n$, be real numbers, which are not all zero, such that

$$\sum _{i=2}^n{\beta }_i(x_i-x_1)=0.$$

So, there are $n$ constants ${\gamma }_1,\mathrm{\dots }{\gamma }_n$, not all equal to zero, such that

$$\sum _{i=1}^n{\gamma }_i{x}_i=0,$$

and

$$\sum _{i=1}^n{\gamma }_i=0.$$

Let $ℐ$ be a subset of indices defined as

$$\{i\in \{1,2,\mathrm{\dots },n\}:{\gamma }_i>0\}.$$

Since ${\sum }_{i=1}^n{\gamma }_i=0$, the subset $ℐ$ is not empty. Define

$$a=\underset{i\in I}{\max }{\alpha }_i/{\gamma }_i.$$

Then we have

$$p=\sum _{i=1}^n({\alpha }_i-a{\gamma }_i)x_i,$$

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