Page 411 - A Course in Linear Algebra with Applications

10.3: Basic Solutions and Extreme Points 395

Assume that diA[ -\ h d sA' s = 0 where not all the dj
are 0. Let e be any positive number. Then

In a similar fashion we have

a

Now define

£/ = (0 .. 0 xi + edi ... x' s + ed s ) T
.
.
1/ = (0 .. 0 x[ - ed x ... x' s- eds) T
Then AU = B = AV.
Next choose e so that

x',
0 < e < -rj- j = l,2,...,s,
Mil

if dj ^ 0. This choice of e ensures that x' ± edj > 0 for
2
j = 1, ,..., s. Hence U > 0 and V > 0, so that U and V are
feasible solutions. However, X = \U + \V, which means that
X = U or V since X is an extreme point. But both of these
are impossible because e > 0. It follows that A[,..., A' a are
linearly independent and X is a basic feasible solution.

We are now able to show that there are only finitely many
extreme points in the set of feasible solutions.