Page 401 - A Course in Linear Algebra with Applications

10.2: The Geometry of Linear Programming 385

Theorem 10.2.3
n
Let S be a non-empty subset o/R . Then C(S) is the smallest
convex subset o/R n which contains S.

Proof
In the first place it is clear that 5 C C(S). We show next
that C(S) is a convex set. Let X,Y G C(S); then we can
m m
c
write X = Yl i^i a n d Y = Yl diXi, where Xi,..., X m G S,
i = l i = l
m m
0 < Cj, di < 1, and Y Ci = 1 = Y2 d%. Then for any t
i=i i=i
satisfying 0 < t < 1, we have

m m
iX + (1 - t)Y= Y^teiXi + ] ( 1 - t)diXi
5
i=l i = l
m
= ^2(ta + {l-t)di)Xi.
i = l

Now

m / m \ / m
^ ( t c i + ( l - t ) d i ) = t l ^ c i ] + ( l - t ) ]Tdj
i = l \ i = l / \ i = l
= t + (l-t)
= 1.

Consequently £X + (1 - t)F G C(S) and (7(5) is convex.
Next suppose T is any convex subset of R n containing
S. We must show that C(S) C T; for then C(S) will be the
smallest convex subset containing S.
m
Let X G C(S) and write X = £ CjXj, where X; G 5,
i = i
771
Cj > 0 and ]T Q = 1. We will show that X G T by induction
i = l