<<

. 18
( 59 .)



>>

H
Thus, the ; 1 vectors y 9 y in (5) are in the vector space spanned by the
G 
linearly independent vectors x 9 x , . . . , x 9 x . Hence the vectors y 9 y
  M  G 
in (5) are linearly dependent and the corresponding points y , y , . . . , y are
 M>
af¬nely dependent.
CONVEX SETS IN RL
76


C¬¬ 4. T he points x , x , . . . , x are an af¬ne basis for [A].
 M
Proof. In the proof of Lemma 6.5 we showed that A 3 [+x , x , . . . , x ,].
 M
Hence [A] 3 [+x , x , . . . , x ,]. Since the opposite inclusion clearly holds,
 P
we have [A] : [+x , x , . . . , x ,]. The corollary then follows from the
 M
uniqueness of the representation (3) of a point x in [+x x , . . . , x ,].
 M
Let x , x , . . . , x be af¬nely independent. We call co+x , x , . . . , x , the
 P  P
simplex spanned by x , x , . . . , x . The points x , x , . . . , x are called the vertices
 P  P
of the simplex.
We leave it as an exercise for the reader to show that any r ; 2 points
in the simplex are af¬nely dependent. Thus the dimension of the simplex
co+x , x , . . . , x , is r.
 P
C¬¬ 5. T he dimension of a convex set C is the maximum dimension of
simplexes in C.

This corollary is a restatement of Lemma 6.5 when C is a convex set.
Intuitively, in R one would expect that a convex set that is not contained
in a plane or in a line to have nonempty interior. In terms of our de¬nition of
dimension of a set, we would expect a three-dimensional convex set to have
nonempty interior. This is indeed the case, not only in R, but also in RL, as
the following theorem shows.

T 6.1. A convex set C in RL has dimension n if and only if C has nonvoid
interior.

Suppose C has nonempty interior. Let x be an interior point of C and let

e , . . . , e denote the standard basis vectors in RL. Then there exists an 9 0
 L
such that each of the n ; 1 points x , x ; e , . . . , x ; e lies in C. These
   L
points are af¬nely independent. Since in RL any n ; 2 points are af¬nely
dependent, it follows from (ii) of Lemma 6.5 that C has dimension n.
Now suppose that C has dimension n. Then [C] : RL, and by Corollary
4 of Lemma 6.5 there exist points x , x , . . . , x in C that form an af¬ne basis
 L
for [C] : RL. Thus each x in RL can be written uniquely as

L L
x:  x ,  : 1. (6)
GG G
G G
Since C is convex, all points x in RL with . 0, i : 0, 1, . . . , n, lie in C. In
G
particular,

1
x: (x ; x ; % ; x ),
* n;1   L

the centroid of the simplex co+x , x , . . . , x ,, is in C.
 L
AFFINE GEOMETRY 77


We can also write x uniquely as

L
x :  (x 9 x ),
GG 
G

as in (6). Since the vectors x 9 x , . . . , x 9 x are linearly
with the
G   L 
independent, they form a basis for RL, and the linear transformation T from RL
to RK de¬ned by

T (x) : ( , . . . , )
 L

is nonsingular and continuous. Let f be the mapping from RL to RL> de¬ned
by

L
f(x) : f  x : ( , , . . . , ),
GG  L
G

where the are as in (6). The mapping f can be viewed as a composite map
G
h ° T, where

L
h( , . . . , ) : ( , , . . . , ), :19  .
 L  L  G
G

Thus, f is continuous.
Since f is continuous and since

1 1 1
f(x ) : ,...,
, ,
n;1 n;1 n;1
*

there exists a 9 0 such that for x + B(x , ) all components of f (x) will be
G
*
strictly positive. Thus, all x + B(x , ) lie in C, and so x is an interior point
* *
of C.
By experimenting with a sheet of cardboard, if necessary, the reader should
¬nd it plausible that an arbitrary plane in R can be put into coincidence with
the plane x : 0 by means of an appropriate sequence of rotations followed by

a possible translation. The plane x : 0 consists of those points in R of the

form (x , x , 0) and thus is essentially R. Thus, in some sense a plane in R is

equivalent to R. Similarly, any line in R can be made to coincide with any
one of the coordinate axes by means of an appropriate sequence of rotations
followed by a possible translation.
We shall now show that any r-dimensional manifold M in RL is equivalent,
in a sense to be made precise, to RP.
CONVEX SETS IN RL
78


De¬nition 6.6. An af¬ne transformation T from RL to RK is a mapping of the
form T x : Sx ; a, where a is a ¬xed vector in RK and S is a linear transfor-
mation from RL to RK.

Since relative to appropriate bases in RL and RK a linear transformation S
from RL to RK is given by Sx : Ax, where A is an m ; n matrix, we have
T x : Ax ; a.

L 6.6. A mapping T from RL to RK is af¬ne if and only if for each + R and
each pair of points x and x in RL
 
T [(1 9 )x ; x ] : (1 9 )T x ; T x . (7)
   
It is a straightforward calculation to show that if T is af¬ne, then (7) holds.
Now suppose that (7) holds. Let a : T (0), and let Sx : T x 9 a. To show that
T is af¬ne, we must show that S is linear.
For any in R and x in RL,

S( x) : T [ x ; (1 9 )0] 9 a : T (x) ; (1 9 )T (0) 9 a
: [T (x) 9 a] : S(x).

For any x and x in RL we have
 
S(x ; x ) : S[2(x ; x )] : 2S( x ; x ) : 2T ( x ;  x ) 9 2a
     
 
: [T (x ) 9 a]; [T (x ) 9 a] : S(x ) ; S(x ).
   
Thus S is linear.
From (7) we see that under an af¬ne map lines are mapped onto lines. Thus
under an af¬ne map linear manifolds are mapped onto linear manifolds. By
taking 0 - - 1 in (7), we see that under an af¬ne map convex sets are
mapped onto convex sets.

T 6.2. L et x , x , . . . , x and y , y , . . . , y be two af¬nely independent sets
 P  P
in RL. T hen there exists a one-to-one af¬ne transformation T from RL onto itself
such that T x : y , i : 0, 1, . . . , r. If r : n, then T is unique.
G G
If r : n, obtain two af¬nely independent sets x , . . . , x , x , . . . , x and
 P P> L
y , . . . , y , y , . . . , y of n ; 1 points by adjoining appropriate points to the
 P P> L
original sets. The vectors x 9 x , . . . , x 9 x constitute a basis for RL, as do
  L 
the vectors y 9 y , . . . , y 9 y . Thus, there exists a unique one-to-one linear
  L 
transformation S of RL onto itself such that S(x 9 x ) : y 9 y , i : 1, . . . , n.
G  G 
Let T x : Sx ; a for a ¬xed a to be determined. Then for i : 0, 1, . . . , n,

T (x ) : S(x ) ; a : S(x 9 x ) ; S(x ) ; a : y 9 y ; S(x ) ; a.
G G G   G  
AFFINE GEOMETRY 79


Therefore, if we take a : y 9 S(x ), we will have T x : y , i : 0, 1, . . . , n.
  G G
C¬¬ 6. L et M and M be two linear manifolds of the same dimension.
 
T hen there exists a one-to-one af¬ne transformation T of RL onto itself such that
TM :M .
 
By Lemma 6.4, M has an af¬ne basis x , x , . . . , x and M has an af¬ne
  P 
basis y , y , . . . , y . By Theorem 6.2 there exists a one-to-one transformation T
 P
from RL onto itself such that T x : y , i : 1, . . . , n. The corollary now follows
G G
from the facts that each x in M is a unique af¬ne combination of x , x , . . . , x ,
  P
each y in M is a unique af¬ne combination of y , y , . . . , y , and T maps af¬ne
  P
combinations onto af¬ne combinations.

Remark 6.3. If M is a linear manifold of dimension r, then there exists a
one-to-one af¬ne transformation T of RL onto itself that maps M onto the
manifold

V * : +y : y : (y , . . . , y ), y :y : % : y : 0,.
P  L P> P> L
The manifold V * can be identi¬ed with RP by means of the one-to-one
P
mapping. from V * onto RP given by
P
: y : (y , . . . , y , 0, . . . , 0) ; (y , . . . , y ).
 P  P
Denote the restriction of T to M by T , and de¬ne a mapping from M to RP
+
by the formula

x + M : (x) : (T x).
+
Then is one-to-one onto, is continuous, and has a continuous inverse, \.
Note that and \ map convex sets onto convex sets and linear manifolds
onto linear manifolds of the same dimension.

Exercise 6.1. Let k be a positive integer, 1 - k - n 9 1. Show that for a given
subspace V of RL, there exist k linearly independent vectors a , . . . , a such
L\I  I
that

V : +x + RL, 1a , x2 : 0, i : 1, . . . , k,.
L\I G
Exercise 6.2. Show that a set of points x , . . . , x is af¬nely dependent if and
 I
only if one of the points is an af¬ne combination of the other points.

Exercise 6.3. In R consider the plane 2x ; y ; z : 5.
CONVEX SETS IN RL
80


(a) Find an af¬ne basis for this plane that does not include the point x :
(91, 92, 9).
(b) Express x : (91, 92, 9) in barycentric coordinates relative to your
basis.

Exercise 6.4. Let x , x , . . . , x be af¬nely independent. Show that any r ; 2
 P
in co+x , x , . . . , x , are af¬nely dependent.
points y , y , . . . , y , y
 P P>  P
Exercise 6.5. Show that an af¬ne map T maps af¬ne combinations of points
onto af¬ne combinations of points.

Exercise 6.6. In Theorem 6.2, why is T unique if r : n?


7. MORE ON SEPARATION AND SUPPORT

<<

. 18
( 59 .)



>>