Why does Carathéodory's theorem for $C\subset\mathbb R^n$ hold for $k\le n+1$?

Question

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?

Answer 1

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$.

Answer 2

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.