Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

1.3 Affine and convex sets

1.3 Affine and convex sets

Definition The linear combination

λ 1 v 1 + + λ k v k

(1.17)

is affine if the sum of the coefficients is just one:

λ 1 + + λ n = 1 .

(1.18)

Convex combinations are affine combinations with non-negative coefficients.

The affine combination of vectors commutates with translations in the sense that the affine combination of the translated vectors is the translate (with the same vector) of the affine combination (with the same coefficients):

( λ 1 v 1 + + λ k v k ) + v = λ 1 ( v 1 + v ) + + λ k ( v k + v )

because of 1.18. In a similar way affine transformations preserve the affine combinations of the elements.

Definition The set l(p,q) consisting of the elements of the form

p + λ ( q - p ) ,   w h e r e   λ R

(1.19)

is the affine line joining the points p and q. The set s(p,q) consisting of the elements of the form

p + λ ( q - p ) ,   w h e r e   0 λ 1

(1.20)

is the segment joining the points p and q.

Remark Affine lines/segments are the set of all affine/convex combinations of two elements in the space.

Definition A subset in the space is called affine or convex if it contains all the affine lines or segments joining its points.

Remark It will be convenient to consider the empty-set and singletons, i.e. subsets containing at most one element as both affine and convex sets.

Proposition 1.3.1 A subset is affine if and only if it contains all of the affine combinations of its elements.

Proof The statement is trivial for subsets containing at most one element. Otherwise if a subset A contains all of the affine combinations of its elements then, especially, it contains the points of any affine line joining them. Conversely let A be an affine set. The proof is based on a simple induction by the number of the elements in the affine combination. The case of k=1 is trivial. If k=2 then we can use directly the definition of the affine set. Suppose that the statement is true for affine combinations containing at most k - 1 vectors and consider the affine combination

v : = λ 1 v 1 + + λ k v k

of the elements

v 1 , , v k A .

Because at least one of the coefficients must be different from 1 we can write, for example, that

v = ( 1 - λ k ) ( λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1 ) + λ k v k

where

w : = λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1

is in A because of the inductive hypothesis and

v = ( 1 - λ k ) w + λ k v k

is an expression for v as an affine combination of two elements from the affine set A. Therefore v is in A as was to be proved. ▮

Proposition 1.3.2 A subset is convex if and only if it contains all of the convex combinations of its elements.

Proof The statement is trivial for subsets containing at most one element. Otherwise if a subset K contains all of the convex combinations of its elements then, especially, it contains the points of any segment joining them. Conversely let K be a convex set. The proof is based on a simple induction by the number of the elements in the convex combination. The case of k=1 is trivial. If k=2 we can use directly the definition of the convex set. Suppose that the statement is true for convex combinations containing at most k - 1vectors and consider the convex combination

v : = λ 1 v 1 + + λ k v k

of the elements

v 1 , , v k K .

Because at least one of the coefficients must be different from 1 we can write, for example, that

v = ( 1 - λ k ) ( λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1 ) + λ k v k ,

where

w : = λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1

is in K because of the inductive hypothesis and

v = ( 1 - λ k ) w + λ k v k

is an expression for v as a convex combination of two elements from the convex set K. Therefore v is in K as was to be proved. ▮

Consider the collection of all linear combinations of the elements from H. It is called the linear hull (c.f. generated subspace) of the subset H. From the elements of the linear algebra it is well-known that the linear hull is a linear subspace.In what follows we present the corresponding results in case of the affine and convex hulls.

Definition The affine hull/affine envelope aff H is the collection of all affine combinations of the elements from H.

Theorem 1.3.3 The affine hull is an affine set.

Proof Let

p = λ 1 v 1 + + λ k v k   a n d   q = μ 1 w 1 + + μ l w l

be two elements from aff H. Any point z=(1 - λ)p+λq of the affine line joining p and q is the affine combination of the elements

v 1 , , v k , w 1 , , w l

in H because

z = ( 1 - λ ) λ 1 v 1 + + ( 1 - λ ) λ k v k + λ μ 1 w 1 + + λ μ l w l

and the sum of the new coefficients is just one:

( 1 - λ ) λ 1 + + ( 1 - λ ) λ k + λ μ 1 + + λ μ l = ( 1 - λ ) + λ = 1 .

Thereore z is in aff H as was to be proved. ▮

Definition The convex hull/convex envelope conv H is the collection of all convex combinations of the elements from H.

Theorem 1.3.4 The convex hull is a convex set.

Proof Let

p = λ 1 v 1 + + λ k v k   a n d   q = μ 1 w 1 + + μ l w l

be two elements from conv H. Any point z=(1 - λ)p+λq of the segment joining p and q is the convex combination of the elements

v 1 , , v k , w 1 , , w l

in H because

z = ( 1 - λ ) λ 1 v 1 + + ( 1 - λ ) λ k v k + λ μ 1 w 1 + + λ μ l w l

and the sum of the new (non-negative) coefficients is just one:

( 1 - λ ) λ 1 + + ( 1 - λ ) λ k + λ μ 1 + + λ μ l = ( 1 - λ ) + λ = 1 .

Thereore z is in conv H as was to be proved. ▮

Excercise 1.3.5 Prove that the intersection of affine/convex subsets is affine/convex.

Corollary 1.3.6 The affine hull aff H is just the intersection of affine sets containing H.

Corollary 1.3.7 The convex hull conv H is just the intersection of convex sets containing H.

Theorem 1.3.8 (Characterization of affine sets). Each non-empty affine set A can bewritten into the form A=p+L, where p is an arbitrary point in A and L is a uniquely determined linear subspace.

Proof Since A is non-empty choose a point p in A and let us define the translated set L= - p+A. The origin belongs to L because p is in A. We are going to prove that L is closed under the vector addition and the scalar multiplication which implies that it is a linear subspace. Let v(1), ..., v(k) be elements in L, i.e.

v 1 = - p + w 1 , , v k = - p + w k

for some elements w(1), ..., w(k) from A. Then

v = λ 1 v 1 + + λ k v k = - ( λ 1 + + λ k ) p + λ 1 w 1 + + λ k w k =

= - p + ( 1 - ( λ 1 + + λ k ) ) p + λ 1 w 1 + + λ k w k = - p + w

and v is in L because w is the affine combination of the elements p, w(1), ..., w(k) from the affine set A. To clarify that L is uniquely determined suppose that p+M=q+L for some points p, q and linear subspaces M, L. Translate with the additive inverse of p it follows that M=q - p+L. Since the origin must be an element of each linear subspace (especially M) we have that the difference vector of p and q is also in L. Here L is a linear subspace which is closed under the vector addition and thus

M = q - p + L = L

as was to be proved. ▮

According to the previous theorem non-empty affine sets are often called affine subspaces on the model of the linear subspaces.

Definition The dimension of a non-empty affine set is just the dimension of the associated linear subspace. In case of a subset H the dimension is defined as the dimension of its affin hull. The empty-set is of dimension - 1.