G

L 5.1. L et A be an m ; n matrix and let

C : +w : w : Ax, w + RK, x + RL, x . 0,.

T hen C is a closed convex cone.

Proof. A straightforward calculation veri¬es that C is a convex cone.

To show that C is closed, we ¬rst consider the case in which the columns of

A are linearly independent. Let w be a limit point of C, and let +w , be a

I

sequence of points in C converging to w . Then there exists a sequence of

points +x , in RL with x . 0 such that Ax ; w .

I I I

We show that +x , is bounded. If +x , were unbounded, there would exist a

I I

subsequence, again denoted by +x ,, such that #x # ; -. All points in the

I I

sequence +x /#x #, have norm 1, so there exists a subsequence and a point x

I I *

of norm 1 such that x /#x # ; x . From

I I *

#x #A(x /#x #) ; w , #x # ; -,

I I I I

we see that we must have A(x /#x #) ; 0. On the other hand, x /#x #; x

I I I I *

implies that A(x /#x #) ; Ax . Hence Ax : 0. Recall that #x # : 1, so that

I I * * *

x " 0. Therefore the relation Ax : 0 contradicts the linear independence of

* *

the columns of A.

Since +x , is bounded, +x , has a convergent subsequence, which we denote

I I

again by +x ,. Let x :lim x . Then x .0. Also, Ax ; Ax , so that Ax :w .

I I I

Thus w + C, and C is closed.

If the columns of A are not linearly independent, we ¬rst show that any

point z in C can be expressed as a nonnegative linear combination of p : n

linearly independent columns of A. Let A , j : 1, . . . , n, denote the jth column

H

of A. Then there exists an x . 0 such that

L

z: x A , x . 0.

HH H

H

Since the columns of A are linearly dependent, there exists a :( , . . . , ) "0

L

such that

A ; A ; % ; A : 0.

LL

+ R,

Therefore, for any

L

z : (x 9 )A : (x 9 )A ; x A .

H H H H H H HH

H IH$ IH

SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 63

Since " 0, the ¬rst sum on the right exists. If : 0, then x 9 .0

H H H

whenever . x / . In particular, since x . 0, we have x 9 . 0 whenever

HH H H H

. 0. If 9 0, then x / . 0 and x 9 . 0 if and only if - x / . If

H HH H H HH

there exist indices j such that 9 0, set

H

x

H: 90 .

: min

H

H

: 0 for all indices j for which " 0, set

If

H H

x

H: "0 .

: max

H

H

Then x 9 . 0 for all j : 1, . . . , n and x 9 : 0 for at least one value of

H H H H

j. We have now expressed z as a nonnegative linear combination of q : n

columns of A. We continue the process until we express z as a nonnegative

linear combination of p : n linearly independent columns of A.

Let denote a choice of p : n linearly independent columns of A and let

A( ) denote the corresponding m ; p matrix. There are a ¬nite number of such

choices. Let

C( ) : +w : w : A( )y, w + RK, y + RN, y . 0,.

We have shown that each set C( ) is closed and that

C 3 8 C( ).

N

We now show the opposite inclusion. Let w + C( ) for some . By relabeling

columns of A, we can assume without loss of generality that selects the ¬rst

p columns of A. Then there exists a y + RN, y . 0 such that

N N L

w : y A : y A ; (0)A , y . 0, j : 1, . . . , p.

HH HH H H

H H HN>

Let x : (y , . . . , y , 0, . . . , 0). Then w : Ax, and so w + C.

N

We have expressed C as the union of a ¬nite number of closed sets. Hence

C is closed and Lemma 5.1 is proved.

T 5.1 (F«™ L). L et A be an m ; n matrix and let b be a vector

in RL. T hen one and only one of the systems

Ax - 0, 1b, x2 9 0, x + RL,

I:

II: ARy : b, y . 0, y + RK,

has a solution.

CONVEX SETS IN RL

64

Figure 2.7.

The conclusion of the theorem is sometimes stated in the logically equival-

ent form: Either I has a solution or II has a solution but never both. It can

also be stated in the following form: System I has a solution if and only if

system II has no solution.

Figure 2.7 illustrates Farkas™s lemma when A is a 2 ; 2 matrix with rows

a and a . Any vector x in the cross-hatched region satis¬es Ax - 0. Thus, if b

does not lie in the acute angle determined by a and a , then I has a solution.

(Draw the hyperplane 1b, x2 : 0 for such a b.) If we write II in the equivalent

form yRA : bR, yR . 0, we see that for II to have a solution b must lie in the

angle determined by a , a . The vector b is given, so its position is ¬xed. It

either lies in the angle or does not. Thus, precisely one of the systems I and II

has a solution.

We now prove the theorem. The reader will get an appreciation of the

ef¬ciency and esthetic appeal of convexity arguments by looking up the

original proof [Farkas, 1901].

We ¬rst suppose that II has a solution y . We shall show that I has no

solution. If Ax 9 0 for all x in RL, then I has no solution. Suppose there exists

an x in RL such that Ax - 0. Then

1b, x 2 : bRx : (ARy )R x : yR Ax : 1y , Ax 2.

SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 65

Since y . 0 and Ax - 0, it follows that 1b, x 2 - 0. Hence I has no solution.

We now suppose that II has no solution. Let

C : +z : z : ARy, y + RK, y . 0, z + RL,.

The statement that II has no solution is equivalent to the statement that b , C.

By Lemma 5.1, C is closed and convex. Therefore, by Theorem 3.1 there exists

?

a hyperplane Hx that strongly separates b and C. Thus x " 0 and

1x , b2 9 9 1x , z2

for all z in C. Since 0 + C, we get that 9 0. Thus

1x , b2 9 0. (1)

For all z in C we have

1x , z2 : 1x , ARy2 : yRAx : ,

the last inequality now holding for all y in RK satisfying y . 0.

We claim that the last inequality implies that

Ax - 0. (2)

If (2) were false, there would exist at least one component of Ax , say the jth

denote this component. Let y : e :

component, that is positive. Let

H H H

(0, . . . , 0, 1, 0, . . . , 0), where 9 0. Then 1y , Ax 2 : : . Since 9 0, if

H H H

we take to be suf¬ciently large, we get a contradiction. Thus (2) is true. But

(1) and (2) say that x is a solution of I.

T 5.2 [G¤® 1873]. L et A be an m ; n matrix. T hen one and only

one of the following systems has a solution:

I: Ax : 0, x + RL,

II: ARy : 0, y + RK, y " 0, y . 0.

The reader should draw a ¬gure which illustrates this theorem when A is a

3 ; 2 matrix with rows a , a , a .

Proof. We shall show that the system I has a solution if and only if the

system

I: Ax - e, : 0,

has a solution, where e in the vector in RK all of whose entries equal 1. Let

CONVEX SETS IN RL

66

(x , ) be a solution of I. Then

Ax - e : 0,

so I has a solution. Now let x be a solution of I and let : Ax . If :

( , . . . , ), then : 0 for i : 1, . . . , m. Let : max+ , . . . , ,. Then (x , )

K G K

is a solution of I.

The system I has a solution if and only if the system

x

I: (A, 9e) - 0, 1(0 ,91), (x, )2 9 0,

L

where 0 is the zero vector in RL, has a solution. By Farkas™s lemma, either I

L

(and hence I) has a solution or

AR 0

y: y . 0, y + RK,

II: ,

9eR 91

has a solution but never both. System II can be written as

II: ARy : 0, 1e, y2 : 1, y . 0.

From 1e, y2 : 1 it follows that y " 0. Hence if II has a solution, so does

II: ARy : 0, y . 0, y " 0.

If II has a solution, then 1e, y2 " 0. If we set y : y/1e, y2, then II will have a

solution. Hence either I has a solution or II has a solution but never both.

T 5.3 [M«©® 1936]. L et A, B, C be given matrices with n columns

and let A " O. T hen one and only one of the following systems has a solution:

I: Ax 9 0, Bx . 0, Cx : 0, x + RL,

II: ARy ; BRy ; CRy : 0, y . 0, y " 0, y . 0.

Proof. Let e : (1, 1, 1, . . . , 1) be a vector all of whose entries equal 1 and

whose dimension is the row dimension of A. We assert that the system I has a

solution if and only if the system I has a solution, where

I: Ax . e, Bx . 0, Cx : 0, 9 0.

Here is a real scalar. It is clear that if I has a solution, then I has a solution.

If I has a solution x , let : ( , . . . , )R : Ax . Let : min+ , . . . , ,. Then

K K

9 0 and Ax . e, and so I has a solution.