Carathéodory's theorem (convex hull)

Proof

Note: We will only use the fact that ${\displaystyle \mathbb{R}}$ is an ordered field, so the theorem and proof works even when ${\displaystyle \mathbb{R}}$ is replaced by any field ${\displaystyle \mathbb{F}}$, together with a total order.

We first formally state Carathéodory's theorem:

Carathéodory's theorem—If ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{e}(S)\subset {\mathbb{R}}^d}$, then ${\displaystyle x}$ is the nonnegative sum of at most ${\displaystyle d}$ points of ${\displaystyle S}$.

If ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)\subset {\mathbb{R}}^d}$, then ${\displaystyle x}$ is the convex sum of at most ${\displaystyle d+1}$ points of ${\displaystyle S}$.

The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because ${\displaystyle \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)}$ is the set of finite convex combination of elements of ${\displaystyle S}$ (see the convex hull page for details).

Lemma—If ${\displaystyle q_1,...,q_N\in {\mathbb{R}}^d}$ then ${\displaystyle \mathrm{\forall }x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{e}(\{q_1,...,q_N\})}$, there exist ${\displaystyle w_1,...,w_N\ge 0}$ such that ${\displaystyle x=\sum _n{w}_n{q}_n}$, and at most ${\displaystyle d}$ of them are nonzero.

With the lemma, Carathéodory's theorem is a simple extension:

Proof of Carathéodory's theorem

For the first part: take any ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{e}(S)}$, represent ${\displaystyle x=\sum _{n=1}^N{w}_n{q}_n}$ for some ${\displaystyle q_1,...,q_N\in S}$ and ${\displaystyle w_n\ge 0}$, then ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{e}(\{q_1,...,q_N\})}$, and we use the lemma.

The second part reduces to the first part by "lifting up one dimension", a common trick used to reduce affine geometry to linear algebra, and reduce convex bodies to convex cones.

Explicitly, let ${\displaystyle S\subset {\mathbb{R}}^d}$, then identify ${\displaystyle {\mathbb{R}}^d}$ with the subset ${\displaystyle \{w\in {\mathbb{R}}^{d+1}:w_{d+1}=1\}}$. This induces an embedding of ${\displaystyle S}$ into ${\displaystyle S\times \{1\}\subset {\mathbb{R}}^{d+1}}$.

Any ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)}$ has a representation ${\displaystyle x=\sum _{n=1}^N{w}_n{q}_n}$, with ${\displaystyle \sum _{n=1}^N{w}_n=1}$ and ${\displaystyle w_n\ge 0}$; x has a "lifted" representation ${\displaystyle (x,1)=\sum _{n=1}^N{w}_n(q_n,1)}$, and so, by the first part, it has a representation ${\displaystyle (x,1)=\sum _{n=1}^N{w}_n^{\prime }(q_n,1)}$ with ${\displaystyle w_n^{\prime }\ge 0}$, where at most ${\displaystyle d+1}$ of ${\displaystyle w_n^{\prime }}$ are nonzero. That is, ${\displaystyle x=\sum _{n=1}^N{w}_n^{\prime }{q}_n}$ and ${\displaystyle 1=\sum _{n=1}^N{w}_n^{\prime }}$, which completes the proof.

Proof of lemma

This is trivial when ${\displaystyle N\le d}$. If we can prove it for all ${\displaystyle N=d+1}$, then by induction we have proved it for all ${\displaystyle N\ge d+1}$. Thus it remains to prove it for ${\displaystyle N=d+1}$. This we prove by induction on ${\displaystyle d}$.

Base case: ${\displaystyle d=1,N=2}$, trivial.

Induction case. Represent ${\displaystyle x=\sum _{n=1}^{d+1}{w}_n{q}_n}$. If some ${\displaystyle w_n=0}$, then the proof is finished. So assume all ${\displaystyle w_n>0}$

If ${\displaystyle \{q_1,...,q_d\}}$ is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in ${\displaystyle \sum _{n=1}^d\frac{w_n}{w_1+\cdots +w_d}{q}_n}$, and thus eliminate it in ${\displaystyle x=\sum _{n=1}^{d+1}{w}_n{q}_n}$ as well.

Else, there exists ${\displaystyle (u_1,...,u_d)\in {\mathbb{R}}^d}$, such that ${\displaystyle \sum _{n=1}^d{u}_n{q}_n=q_{d+1}}$. Then we can interpolate a full interval of representations:

$${\displaystyle x=\sum _{n=1}^d(w_n+\theta w_{d+1}{u}_n)q_n+(1-\theta )w_{d+1}{q}_{d+1};\theta \in [0,1]}$$

If ${\displaystyle w_n+w_{d+1}{u}_n\ge 0}$ for all ${\displaystyle n=1,...,d}$, then set ${\displaystyle \theta =1}$. Otherwise, let ${\displaystyle \theta }$ be the smallest ${\displaystyle \theta }$ such that one of ${\displaystyle w_n+\theta w_{d+1}{u}_n=0}$. Then we obtain a representation of ${\displaystyle x}$ as a linear combination with non-negative coefficients, with at most ${\displaystyle d}$ nonzero terms.

Alternative proofs use Helly's theorem or the Perron–Frobenius theorem.

Variants

Carathéodory's number

For any nonempty ${\displaystyle P\subset {\mathbb{R}}^d}$, define its Carathéodory's number to be the smallest integer ${\displaystyle r}$, such that for any ${\displaystyle x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(P)}$, there exists a representation of ${\displaystyle x}$ as a convex sum of up to ${\displaystyle r}$ elements in ${\displaystyle P}$.

Carathéodory's theorem simply states that any nonempty subset of ${\displaystyle {\mathbb{R}}^d}$ has Carathéodory's number ${\displaystyle \le d+1}$. This upper bound is not necessarily reached. For example, the unit sphere in ${\displaystyle {\mathbb{R}}^d}$ has Carathéodory's number equal to 2, since any point inside the sphere is the convex sum of two points on the sphere.

With additional assumptions on ${\displaystyle P\subset {\mathbb{R}}^d}$, upper bounds strictly lower than ${\displaystyle d+1}$ can be obtained.

Dimensionless variant

Caratheodory's theorem type results where the diameter replaces the dependency on the dimension are well known. An explicit statement of a no-dimensional Caratheodory's theorem was provided by Barman. It is probable that this theorem was stated much earlier, as it is an easy consequence of the analysis of the Perceptron algorithm of Novikoff. Specifically, for every positive integer ${\displaystyle r}$ and every point within the convex hull of a finite point set ${\displaystyle P}$, there exists an ${\displaystyle r}$-point subset ${\displaystyle R}$ such that the given point is within distance ${\displaystyle \mathrm{diam}P/\sqrt{2r}}$ of the convex hull of ${\displaystyle R}$.

Colorful Carathéodory theorem

Let X₁, ..., X_d+1 be sets in R^d and let x be a point contained in the intersection of the convex hulls of all these d+1 sets.

Then there is a set T = {x₁, ..., x_d+1}, where x₁ ∈ X₁, ..., x_d+1 ∈ X_d+1, such that the convex hull of T contains the point x.

By viewing the sets X₁, ..., X_d+1 as different colors, the set T is made by points of all colors, hence the "colorful" in the theorem's name. The set T is also called a rainbow simplex, since it is a d-dimensional simplex in which each corner has a different color.

This theorem has a variant in which the convex hull is replaced by the conical hull. Let X₁, ..., X_d be sets in R^d and let x be a point contained in the intersection of the conical hulls of all these d sets. Then there is a set T = {x₁, ..., x_d}, where x₁ ∈ X₁, ..., x_d ∈ X_d, such that the conical hull of T contains the point x.

Mustafa and Ray extended this colorful theorem from points to convex bodies.

The computational problem of finding the colorful set lies in the intersection of the complexity classes PPAD and PLS.