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

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.