# 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}+\ldots+\alpha_{n}x_{n}$

where $\alpha_{1}+\ldots+\alpha_{n}=1$ and $x_{1},\ldots,x_{n}\in P$. If $n\leq 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},\ldots,x_{n}-x_{1}$ are linearly dependent. Let $\beta_{i}$, $i=2,3,\ldots,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},\ldots\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 $\mathcal{I}$ be a subset of indices defined as

 $\{i\in\{1,2,\ldots,n\}:\,\gamma_{i}>0\}.$

Since $\sum_{i=1}^{n}\gamma_{i}=0$, the subset $\mathcal{I}$ is not empty. Define

 $a=\max_{i\in I}\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 ProofOfCaratheodorysTheorem 2013-03-22 17:50:08 2013-03-22 17:50:08 kshum (5987) kshum (5987) 4 kshum (5987) Proof msc 52A20