C¬¬ 3. A set S is a linear manifold if and only if every af¬ne combination

of points in S is in S.

The proof is similar to that of Lemma 2.6.

De¬nition 6.4. A ¬nite set of points x , . . . , x is af¬nely dependent if there

I

; · · · ; : 0 and

exist real numbers , . . . , , not all zero such that

I I

x ; % ; x : 0. If the points x , . . . , x are not af¬nely dependent, then

II I

they are af¬nely independent.

L 6.3. A set of points x , x , . . . , x is af¬nely dependent if and only if the

I

vectors (x 9 x ), (x 9 x ), . . . , (x 9 x ) are linearly dependent.

I

Proof. Let x , . . . , x be af¬nely dependent. Then there exist real numbers

I

, . . . , not all zero such that

I

I

x ; x ; % ; x : 0, : 0. (1)

II G

G

CONVEX SETS IN RL

72

Hence

: 9( ; % ; ). (2)

I

Not all of ,..., are zero, for if they were, would also be zero,

I

contradicting the assumption that not all of , . . . , are zero. Substituting (2)

I

into the ¬rst relation in (1) gives

(x 9 x ) ; (x 9 x ) ; % ; (x 9 x ) : 0,

II

where , . . . , are not all zero. Thus the vectors (x 9 x ), . . . , (x 9 x ) are

I I

linearly dependent.

To prove the reverse implication, we reverse the argument.

Remark 6.1. Clearly, an equivalent statement of Lemma 6.3 is the follow-

ing. A set of points x , . . . , x is af¬nely independent if and only if the vectors

I

x 9 x , . . . , x 9 x are linearly independent.

I

L 6.4. L et M be a linear manifold. T hen the following statements are

equivalent:

(i) T he dimension of M equals r.

(ii) T here exist r ; 1 points x , x , . . . , x in M that are af¬nely independent

P

and any set of r ; 2 points in M is af¬nely dependent.

(iii) T here exist points x , x , . . . , x that are af¬nely independent and such

P

that each point x in M has a unique representation

P P

x: x , :1 (3)

GG G

G G

in terms of the x ™s.

G

Proof. We ¬rst show that (i) implies (ii). If (i) holds, then we may write

M : V ; x , where V is a subspace of dimension r and x is an arbitrary point

P P

in M. Let v , . . . , v be a basis for V and let

P P

x :v ;x , i : 1, . . . , r.

G G

Then the vectors x 9 x , i : 1, . . . , r, are linearly independent and the r ; 1

G

points x , x , . . . , x are af¬nely independent.

P

be any set of r ; 2 points in M. If we write M :

Let y , y , . . . , y , y

P P>

V ; y , then each of the vectors y 9 y , i : 1, . . . , r ; 1, is in V . Therefore the

P G P

r ; 1 vectors in this set are linearly dependent, and hence y , y , . . . , y , y

P P>

are af¬nely dependent.

AFFINE GEOMETRY 73

Next we show that (ii) implies (iii). Since M is a linear manifold and x + M,

we may write M : V ; x , where V is a subspace. We assert that V has

dimension r. To see this, let

v :x 9x , i : 1, . . . , r.

G G

Since the points x , x , . . . , x are af¬nely independent, the vectors v , . . . , v are

P P

be a set of r ; 1 distinct nonzero

linearly independent. Now let w , . . . , w

P>

vectors in V. Then there exist points y , . . . , y in M such that

P>

w :y 9x , i : 1, . . . , r ; 1.

G G

Since the w are distinct and none of the vectors w is zero, the r ; 2 points

G G

x y ,...,y are distinct. By hypothesis, they are af¬nely dependent. Hence

P>

are linearly dependent. Thus, V has dimension r, we

the vectors w , . . . , w

P>

may write V : V , and the vectors v , . . . , v are a basis for V .

P P P

For arbitrary x in M we have x : v ; x uniquely for some v in V . Hence

P

there exist unique real numbers , . . . , such that

P

P P P P

x : v ; x : (x 9 x ) ; x : 1 9 x ; x.

GG GG G GG

G G G G

We obtain the representation (3) by setting : (1 9 9 % 9 ).

P

To show that the representation is unique in terms of the x ™s, we suppose

G

that there were another representation

P P

x : x , : 1.

GG G

G G

Then

P P

0 : ( 9 )x , ( 9 ) : 0,

G G

GG G

G G

with not all of the coef¬cients ( 9 ) equal to zero. But then the points x ,

G G G

i : 0, . . . , r, would be af¬nely dependent, contrary to assumption.

We conclude the proof by showing that (iii) implies (i). Let x be an arbitrary

point in M. Then by virtue of (3)

P P P P

x: x : 19 x ; x : (x 9 x ) ; x . (4)

GG G GG GG

G G G G

Since x , x , . . . , x are af¬nely independent, the vectors

P

x 9x , x 9x , ...,x 9x

P

are linearly independent.

CONVEX SETS IN RL

74

Let V denote the r-dimensional vector space spanned by x 9x , . . . , x 9x .

P P

It follows from (4) that x + V ; x . Thus M 3 V ; x .

P P

To prove the opposite inclusion, we let W : M 9 x . We saw in the proof

of Lemma 6.2 that W is a subspace. Moreover, since x 9 x , . . . , x 9 x

P

belong to W, we have that V 3 W. Hence

P

V ;x 3W ;x :M

P

and so M : V ; x . This concludes the proof of Lemma 6.4.

P

Points x , x , . . . , x as in Lemma 6.4 are said to be an af¬ne basis for M.

P

The numbers , i : 0, 1, . . . , r, are called the barycentric coordinates of x

G

relative to the af¬ne basis x , x , . . . , x .

P

De¬nition 6.5. Let A be a subset of RL. The af¬ne hull of A, denoted by [A],

is de¬ned to be the intersection of all linear manifolds containing A. The

dimension of A is the dimension of [A].

Since A 3 RL, since RL is a linear manifold, and since the intersection of

linear manifolds is a linear manifold, it follows that, for any nonempty set A,

[A] is not empty. Thus the dimension of A is well de¬ned.

For any linear manifold M, the relations M 3 [M] and [M] 3 M hold,

so M : [M]. Thus, for a linear manifold M, the dimension of M as de¬ned

in De¬nition 6.2 coincides with that of De¬nition 6.5.

We shall often write dim A to refer to the dimension of A.

L 6.5. L et A be a subset of RL and let M(A) denote the set of all af¬ne

combinations of points in A. T hen

(i) [A] : M(A) and

(ii) if there exist ; 1 points x , x , . . . , x in A that are af¬nely independent

M

and if any set of ; 2 points in A is af¬nely dependent, then dim A : .

Remark 6.2. Statement (i) is the analog for af¬ne hulls of Theorem 2.1 for

convex hulls.

Proof. It is readily veri¬ed that if x and y are two points in M(A), then each

af¬ne combination of these points is in M(A). Hence, by Lemma 6.2, M(A) is

a linear manifold. Since M(A) 4 A, it follows from the de¬nition of [A] that

[A] 3 M(A). On the other hand, it follows from Corollary 3 to Lemma 6.2

that M(A) is contained in every linear manifold containing A. Thus [A] 4

M(A). Hence [A] : M(A).

We now establish (ii). Let x , x , . . . , x be ; 1 af¬nely independent points

M

in A and suppose that any set of ; 2 points is af¬nely dependent. Since the

points x , x , . . . , x are in [A], it follows from Lemma 6.4 that dim [A]. .

M

AFFINE GEOMETRY 75

On the other hand, for arbitrary x in A the vectors

x 9x , x 9x , . . . , x 9x , x9x

M

are linearly dependent, and the ¬rst vectors are linearly independent. Hence

for arbitrary x in A there exist unique scalars , . . . , such that

M

M

x 9 x : (x 9 x ).

GG

G

:19( ; ;%; ), we get, uniquely,

On setting

M

M M

x: x , : 1.

GG G

G G

Hence A is contained in the linear manifold [+x , x , . . . , x ,] and so

M

dim A < dim [+x , x , . . . , x ,].

M

To complete the proof of (ii), it suf¬ces to show that [+x , x , . . . , x ,] has

M

dimension . For then dim A - , and since we have already shown that

dim A . , statement (ii) will follow.

We now show that dim [+x , x , . . . , x ,] : . Since x , x , . . . , x are

M M

af¬nely independent to show that dim [+x , x , . . . , x ,] : , we must show

M

of ; 2 vectors in [+x , x , . . . , x ,] is af¬nely

that any set y , y , . . . , y , y

M M> M

dependent. From (i), we have that M(+x , . . . , x ,) : [+x , . . . , x ,]. Thus for

M M

i : 0, 1, . . . , ; 1 we have

M M

y: q x, q : 1.

G GH H GH

H H

Since q : 1 9 q 9 q 9 % 9 q , we have

G G G GM

M

y : q (x 9 x ) ; x , i : 0, 1, 2, . . . , ; 1.

G GH H

H

Hence,

M

y 9 y : (q 9 q )(x 9 x ), i : 1, . . . , ; 1. (5)

G GH H H