<<

. 16
( 59 .)



>>


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

<<

. 16
( 59 .)



>>