# 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 $\mathcal{I}$ 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 $\mathcal{I}$ is not empty. Define

$$a=\underset{i\in I}{\mathrm{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 |