|
|
|
|
proof of Carathéodory's theorem
|
(Proof)
|
|
|
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_1x_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$
|
"proof of Carathéodory's theorem" is owned by kshum.
|
|
(view preamble | get metadata)
Cross-references: coefficient, indices, subset, real numbers, linearly dependent, integer, number, points, convex hull
This is version 1 of proof of Carathéodory's theorem, born on 2008-02-22.
Object id is 10306, canonical name is ProofOfCaratheodorysTheorem.
Accessed 1043 times total.
Classification:
| AMS MSC: | 52A20 (Convex and discrete geometry :: General convexity :: Convex sets in $n$ dimensions ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|