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

αi = αi τγi for i = 1, . . . , m. Then

αi 0 for all i = 1, . . . , m and αi0 = 0.
Furthermore,

α1 + . . . +

αm = (α1 + . . . + αm) τ(γ1 + . . . + γm) = 1
and

α1y1 + . . . +

αmym = α1y1 + . . . + αmym τ(γ1y1 + . . . + γmym) = x.
Therefore, we represented x as a convex combination
x =
i=i0
αiyi∼
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.
PROBLEMS.
1◦.
Show by an example that the constant d + 1 in Carath´ eodory’s Theorem
cannot be improved to d.
2∗ (I. 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].
3∗.
Let S
Rd
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
conv
(
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.
Previous Page Next Page