SYSTEMS OF LINEAR INEQUALITIES: THEOREMS OF THE ALTERNATIVE 67

Since I has a solution if and only if I has a solution, I has no solution if

and only if I has no solution. Now I has no solution if and only if the system

9A e 0

9B 0 x 0

- 1(0 , 1), (x, )2 9 0,

I: ,

L

9C 0 0

C 0 0

where 0 is the zero vector in RL, has no solution.

L

By Farkas™s lemma I has no solution if and only if the system II has a

solution, where

y

9AR 9BR 9CR CR y 0

: L, (y , y , , ) . 0.

II:

eR 0 0 0 1

But II having a solution is equivalent to the system

II: ARy ; BRy ; CR( 9 ) : 0, 1e, y 2 : 1,

having a solution y . 0, y . 0, . 0, . 0. If we let y : ( 9 ), we

see that if II has a solution as indicated, then

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

has a solution. In summary, we have shown that if I has no solution, then II

has a solution.

Now suppose that II has a solution (y , y , y ). Then 1e, y 2 9 0. Hence if

we set

y y y

y : , y : , y : ,

1e, y 2 1e, y 2 1e, y 2

then (y , y , y ) is a solution of II with 1e, y 2 : 1. Thus we may assume that

II has a solution (y , y , y ) with 1e, y 2 : 1.

be a vector whose dimension is that of y and whose ith component

Let

is equal to y , the ith component of y , if y . 0 and zero otherwise. Let

G G

be a vector whose dimension is that of y and whose ith component is equal

to "y " if y : 0 and zero otherwise. Then . 0, . 0, and y : ( 9 ).

G G

Hence if II has a solution, then so does II. Therefore, I has no solution.

Remark 5.1. Theorem 5.3 is valid if either B or C or both are zero. In fact, if

both B and C are zero, the lemma becomes Gordan™s theorem.

CONVEX SETS IN RL

68

T 5.4 [G¬ 1960]. L et A be an m ; n matrix and let c " 0 be a vector

in RK. T hen one and only one of the following systems has a solution:

Ax - c,

I:

II: ARy : 0, 1c, y2 : 91, y.0

Proof. The system Ax - c has a solution if and only if the system 9 0,

Ax - c has a solution. Thus the system I is equivalent to the system

x

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

L

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

L

only if the system II:

AR 0

yR : L , y . 0, y + RL,

9c 1

has no solution. But system II is the same as

1c, y2 : 91, ARy : 0, y . 0,

which is system (II).

C¬¬ 1. L et A be an m ; n matrix and let c " 0 in RK be such that, for

all x + RL, Ax 9 c 9 0. T hen there exists a vector y + RK such that y . 0, ARy : 0,

and 1c, y2 : 91.

To prove the corollary, we need only note that if Ax 9 c 9 0 for all x in RL,

then Ax - c has no solution in RL.

Exercise 5.1. Show that the set C of Lemma 5.1 is a convex cone.

Exercise 5.2. Let A be an m ; n matrix and b a vector in RL. Show that one

and only one of the following systems has a solution:

I: Ax . 0, x . 0, 1b, x2 9 0

II: ARy . b, y - 0.

Exercise 5.3. Let A be an m ; n matrix and let c " 0 be a vector in RK. Show

that one and only one of the following systems has a solution:

I: Ax : c, x + RL,

II: ARy : 0, 1c, y2 : 1.

AFFINE GEOMETRY 69

6. AFFINE GEOMETRY

Consider a plane II in R and a line in R. Let C be a subset of and let

S be a subset of . Although C and S are subsets of R, it is natural to consider

C as a two-dimensional object and S as a one-dimensional object. In this

section we shall make these ideas precise for subsets of RL.

Let V denote an r-dimensional vector subspace of RL. When we do not wish

P

to emphasize the dimension of the subspace, we shall write V. The reader will

recall from linear algebra that an (n 9 1)-dimensional subspace V of RL can

L\

be expressed as

L

V : x : a x : 0 : +x : 1a, x2 : 0,,

L\ GG

G

where a is a nonzero vector. Thus V is a hyperplane through the origin.

L\

Also, given a subspace V , there exist k linearly independent vectors

L\I

a , . . . , a such that

I

V : +x : 1a , x2 : 0, i : 1, . . . , k,.

L\I G

Thus V , a subspace of dimension n 9 k, is the intersection of k hyperplanes

L\I

through the origin.

De¬nition 6.1. A linear manifold M is a subset of RL of the form

M : V ; b : +x : x : v ; b, v + V ,,

where V is a subspace and b is a vector in RL.

Note that since b : 0 ; b and 0 + V, it follows that b + M.

Thus a linear manifold is a translate of a subspace. Since subspaces are

closed sets in RL, linear manifolds are closed sets. Note that RL is a linear

manifold, since RL : RL ; 0, and that a subspace V is a linear manifold, since

V : V ; 0. In Section 1 we saw that a hyperplane is the translate of a hyper-

plane through the origin and thus the translate of an (n 9 1)-dimensional

vector space. Therefore, hyperplanes are linear manifolds. In R the linear

manifolds are planes, lines, and points. (A point is the translate of the zero-

dimensional subspace consisting of the origin.)

Linear manifolds are also called ¬‚ats or af¬ne varieties or af¬ne sets.

L 6.1. L et M be a linear manifold, M : V ; b. T hen the subspace V is

unique.

CONVEX SETS IN RL

70

To prove the lemma, we suppose that M has another representation M :

V ; b and show that V : V. Since b + M, from M : V ; b, we have that

b : v ; b for some v + V . Hence b 9 b : 9v + V . Now let x + V. Then

x : m 9 b for some m + M. But m : y ; b for some y + V , and so

x : (y ; b) 9 b : y ; (b 9 b) + V .

Thus V 3 V . A similar argument shows that V 3 V.

If M : V ; b, then the vector b is not unique. In fact, M : V ; b for any

b + M. To see this, let b be any vector in M and let M : V ; b. Let m + M,

so m : v ; b for some v + V. Since b + M, we have b : v ; b for some v + V.

Hence m : (v 9 v) ; b, which is an element of M. Thus, M 3 M. A similar

argument shows that M 3 M.

On the other hand, if b is ¬xed and M : V ; b, then the representation of

an element x in M as x : v ; b is unique. For if x : v ; b, then v : x 9 b

and v : x 9 b.

If M is a linear manifold, then the unique subspace V such that M : V ; b

for some b is called the parallel subspace of M.

De¬nition 6.2. The dimension of a linear manifold M is de¬ned to be the

dimension of the parallel subspace V.

If M and M are two linear manifolds with the same parallel subspace, then

M and M are said to be parallel.

The next lemma characterizes linear manifolds as sets having the property

that if x and x belong to the set, then the entire line determined by these

points lies in the set.

L 6.2. A set M is a linear manifold if and only if, for every x , x in M and

real with ; : 1, the point x ; x belongs to M.

,

Proof. Let M be a linear manifold, M : V ; b. Let x and x be in M. Then

x : v ; b and x : v ; b, where v and v are in V. Hence for , with

; : 1,

x ; x : (v ; b) ; (v ; b) : ( v ; v ) ; b.

Since V is a subspace, v ; v + V, and so x ; x + M.

We now prove the reverse implication. Let M be a set such that if x and

x are in M and , are scalars such that ; : 1, then x ; x is

in M. Let x + M and let W : M 9 x . We shall show that W is a subspace,

and thus show that M is a linear manifold, since M : W ; x . Let y and y

AFFINE GEOMETRY 71

belong to W and let and be arbitrary scalars. Then

y ; y ; x : [ (y ; x ) ; (1 9 )x ] ; [ (y ; x ) ; (1 9 )x ] 9 x .

Since y ; x and y ; x belong to M, each of the expressions in square

brackets belongs to M. If we denote the expression in the ¬rst bracket by m

and the expression in the second bracket by m , we may write

y ; y ; x : 2+m ; m , 9 x : 2m 9 x ,

where m denotes the expression in curly braces. Since m and x are in M

and the sum of the coef¬cients on the extreme right is 1, we get that y ; y

; x + M. Thus, y ; y + W, and so W is a subspace.

C¬¬ 1. If M and M are linear manifolds, then so is M ; M Y

+x : x : m ; m , m + M , m + M ,.

C¬¬ 2. If +M , is a family of linear manifolds, then so is M.

7

? ? ?

We leave the proofs of these corollaries as exercises for the reader.

De¬nition 6.3. A point x is said to be an af¬ne combination of points x , . . . , x

I

if there exists a vector q : (q , . . . , q ) in RI such that

I

I

x : q x ; % ; q x and q : 1.

II G