Page 409 - A Course in Linear Algebra with Applications

10.3: Basic Solutions and Extreme Points 393

Proof
Suppose that the linear programming problem is

maximize: z = C X

AX = B
subject to:
X>Q
and it has variables x\,..., x n. Here A may be assumed to be
an m x n matrix with rank m: as has been pointed out, this
is no restriction. Then A has m linearly independent columns
and, by relabeling the variables if necessary, we can assume
these are the last m columns, say A[,..., A' m. Let

X = (0 .. 0 x[ ... x'jr
.
be the corresponding basic solution. Assume that X is feasi-
ble, i.e., x'j > 0 for j — 1,2,... ,m. Our task is to prove that
X is an extreme point of S, the set of all feasible solutions.
Suppose X is not an extreme point of S; then

X = tU+(l- t)V,

where 0 < t < 1, U, V 6 S and X ^ U, V. Write

U = (Ui ... U n- m u[ ... u' m) T

and
T
.
V = (Vi .. V n-m v[ ... v' m) .
Equating the th entries of X and tU + (1 — t)V, we obtain
j
tuj + (1 — t)vj = 0 , 1 < j < n — m
tu'j + (1 - t)v'j =x' j, l<j<m

Since 0 < t < 1 and Uj,Vj > 0, the first equation shows that
Uj = 0 = Vj for j = 1,..., n — m.