PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] 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)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 MSC52A20 (Convex and discrete geometry :: General convexity :: Convex sets in $n$ dimensions )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
Flaw in logic by desimba on 2008-08-23 00:39:48

There appears to be an error in the proof. There is nothing which guarantees that at the last step (αi – aγi) are all non-negative. In fact I tried to make this algorithm work by choosing some random numbers. The user can verify the problem himself by trying x1, x2, x3, x4 as (1,1), (2,2), (3,4) and (4,3) with the point x = (5/2, 5/2)
= 1/4 (1,1) + 1/4 (2,2) + 1/4 (3,4) + 1/4 (4,3). Here one choice of β2, β3 and β4 which solves the equation are -5, 1 and 1. Now with these values of β2, β3 and β4, we get γ1, γ2, γ3 and γ4 as 3, -5,1 and 1 respectively. Finally with these values of γ1, γ2, γ3 and γ4, we get a = 1/4 and (α1 – aγ1) turns out to be -1/2 which is a problem. In general nothing prevents these coefficients from being negative.

A solution to this problem would be to define a as the min positive number which is the ratio of αi/γi. With that change made, the rest of the proof can stay the same as before and I believe it should work out.
[ reply | up ]

Interact
post | correct | update request | add example | add (any)