2

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$"

In every proof I found, it say that it holds for $k\leq n+1$ elements from C. Why does it hold for that?

glS
  • 6,818
user23709
  • 759
  • 1
    They are using induction, and that is the inductive hypothesis? – Pedro Jun 11 '13 at 11:06
  • 1
    @PeterTamaroff: the proof's not actually an induction http://en.wikipedia.org/wiki/Carath%C3%A9odory's_theorem_(convex_hull) – Tim Jun 11 '13 at 11:46
  • 1
    Your problem is not a problem about convexity but a problem about logic. The set of all convex combinations of $k\leq n+1$ points of $C$ is the same as the set of all convex combinations of $n+1$ points of $C$, the reason being that in a set of $n+1$ weights $\lambda_i\geq0$ summing up to $1$ up to $n$ of them may be zero. – Christian Blatter Nov 27 '13 at 19:16

2 Answers2

7

Since $x \in conv(S)$ then there are nonnegative numbers $\lambda_1,\lambda_2, ... \lambda_t$ and vectors $x_1,x_2,...,x_t \in S$ such that $\sum_j \lambda_j=1$ and $x=\sum_j\lambda_jx_j$.

Suppose $x_1,x_2,...,x_t $ are not affine independent. Then there are numbers $\mu_1 ... \mu_t$ not all zeros such that $\sum_{j=1}^t\mu_j x_j=0$ and $\sum_{j=1}^t\mu_j =0$.

Since the $\mu_j$s are not all zero and sum to zero, at least one of these numbers must be positive.

Let $\mu_1>0$. We now multiply the equation $\sum_{j=1}^t\mu_j x_j=0$ by a nonnegative number $\alpha$ and substract with $x=\sum_j\lambda_jx_j$. This gives:

$$ x=\sum_j(\lambda_j-\alpha\mu_j)x_j $$

Note that $x=\sum_j(\lambda_j-\alpha\mu_j) = \sum_j\lambda_j-\alpha\sum_j\mu_j=1$.

When $\alpha=0$ this is just the original representation of x.

Now gradually increase $\alpha $ from zero to $\alpha_0$ until one of the coefficients $\lambda_j-\alpha\mu_j$ becomes zero. This means that we have found a new reprenstation of $x$ as a convex combination of $t-1$ vectors from S.

Continue this reduction process until we have $x$ written as a convex combination of at most $n+1$ affinely independent points.

*I got this from my lecture notes, all credit goes to my professor.

dresden
  • 1,073
  • 2
  • 11
  • 19
  • I think "Note that $x$" should be replaced by "Note that". Further I understand that if the vectors are not affine independent then $\sum_{j=1}^t\mu_{j}x_{j}=0$ but how to prove that $\sum_{j=1}^t\mu_j=0$? I do not understand this part please help me. Thanks – Frank Moses Jun 22 '16 at 03:37
3

Let $\left.\mathop{conv}\right._k C$ be the set of points that may be expressed as convex combinations of at most $k$ points from $C$.

Then by definition $\mathop{conv} C = \bigcup_{k=1}^\infty \left.\mathop{conv}\right._k C$.

Carathéodory's theorem says that $\mathop{conv} C =\left.\mathop{conv}\right._{n+1} C$ and to show this we need to check that $\left.\mathop{conv}\right._k C \subset \left.\mathop{conv}\right._{n+1} C$ for every $k\in\mathbb N$.

So if $x\in\left.\mathop{conv}\right._k C$ for $k\leq n+1$ then $x$ can be expressed as a convex combination of at most $k$ points from $C$, and so trivially $x$ can be expressed as a convex combination of at most $n+1$ points from $C$.

So we just need to do the "hard" cases where $k> n+1$.

Tim
  • 5,564
  • I know to show the part for $k>n+1$ case, but I still don't understand why does it hold for $k\leq n+1$. Is there some theorem which says that? Or I can check it at the same way I do it for $k>n+1$? – user23709 Jun 11 '13 at 12:27
  • @user23709: No, it's just what "at most $n+1$" means. If $x$ can be expressed as a convex combination of at most $k$ points then $x$ can be expressed as a convex combination of $i$ points for some $i\leq k$. So, if $k\leq n+1$, $x$ can be expressed as a convex combination of $i$ points for some $i\leq k\leq n+1$ and $x$ can be expressed as a convex combination of at most $n+1$ points. – Tim Jun 11 '13 at 12:36
  • So, in the proof of Caratheodory's theorem, there's no need to show that it holds for $k\leq n+1$ elements, but just that it doesn't hold for more than $n+1$ elements? – user23709 Jun 11 '13 at 12:47
  • 1
    yes, there's nothing to prove for $k\leq n+1$. – Tim Jun 11 '13 at 13:12