2. Carath´ eodory’s Theorem 11
with fewer terms. Let us consider a system of linear homogeneous equations in m
real variables γ1,... , γm:
γ1y1 + . . . + γmym = 0 and γ1 + . . . + γm = 0.
The first vector equation reads as d real linear equations
γ1η1j + . . . + γmηmj = 0 : j = 1, . . . , d
in the coordinates ηij of yi: yi = (ηi1, . . . , ηid). Altogether, we have d + 1 linear
homogeneous equations in m variables γ1,... , γm. Since m d + 1, there must
be a non-trivial solution γ1,... , γm. Since γ1 + . . . + γm = 0, some γi are strictly
positive and some are strictly negative. Let
τ = min αi/γi : γi 0} = αi0 /γi0 .
αi = αi − τγi for i = 1, . . . , m. Then
αi ≥ 0 for all i = 1, . . . , m and αi0 = 0.
α1 + . . . +
αm = (α1 + . . . + αm) − τ(γ1 + . . . + γm) = 1
α1y1 + . . . +
αmym = α1y1 + . . . + αmym − τ(γ1y1 + . . . + γmym) = x.
Therefore, we represented x as a convex combination
of m − 1 points y1,... , yi0 , . . . , ym (yi0 omitted).
So, if x is a convex combination of m d + 1 points, it can be written as a
convex combination of fewer points. Iterating this procedure, we get x as a convex
combination of d + 1 (or fewer) points from S.
Show by an example that the constant d + 1 in Carath´ eodory’s Theorem
cannot be improved to d.
2∗ (I. B´ ar´ any). Let S1,... , Sd+1 be subsets of Rd. Prove that if u ∈ conv(Si))
for each Si, then there exist points vi ∈ Si such that u ∈ conv
v1,... , vd+1 .
Hint: Choose points vi ∈ Si in such a way that the distance from u to
conv(v1, . . . , vd+1) is the smallest possible. Prove that if u / ∈ conv
v1,... , vd+1
the distance could have been decreased further. This result is known as the “Col-
ored Carath´ eodory Theorem”; see [Bar82].
Let S ⊂
be a set and let u be a point in the interior of conv(S). Prove
that one can choose 2d points v1,... , v2d ∈ S such that u lies in the interior of
v1,... , v2d
4. Suppose that S ⊂ Rd is a set such that every two points in S can be
connected by a continuous path in S or a union of at most d such sets. Prove that
every point u ∈ conv(S) is a convex combination of some d points of S.
Here is a useful corollary relating convexity and topology.