<<

. 17
( 59 .)



>>

G
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 

<<

. 17
( 59 .)



>>