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