Page 403 - A Course in Linear Algebra with Applications

10.2: The Geometry of Linear Programming 3 8 7

The extreme points of a convex set can be characterized
in terms of convex combinations.

Theorem 10.2.4
Let S be a convex subset o/R n and let X e S. Then X is an
extreme point of S if and only if it is not a convex combination
of other points of S.

Proof
Suppose X is not an extreme point of S; then

X = tY + (l-t)Z,

where 0 < t < 1 and Y, Z G S. Then X is certainly a convex
combination of points of S, namely Y and Z.
Conversely, suppose that X is a convex combination of
other points of S. We will show that X is not an extreme
m
point of S. By assumption it is possible to write X = ^ qXi
2 = 1
m
where Xi G S, Xi ^ X, 0 < c; < 1 and ]T Q = 1. Notice
m
that Cj ^ 1; for otherwise ^ Q = 0 and Cj = 0 for all
i=l, i^j
j
i T^ , so that X = Xj.
Just as in the proof of Theorem 10.2.3, we can write
m—1
X
X = (1 - C ) J2 (TZ^) i + Cm*™-
m
i=l X C m
Also
m — 1
1 — C 1 — r ~~

and 0 < yf*— < 1, since a < c\ + • • • + Cm-i = 1 — c m if
i < m. It follows that
ro— 1