Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

12. fejezet - Rådström's embedding theorem

12. fejezet - Rådström's embedding theorem

12.1 Rådström's embedding theorem

Let C* be the collection of non-empty bounded and closed (i.e. compact) convex sets in the coordinate space of dimension n equipped with the Hausdorff distance. In section 1.5 we proved that it is a metric space and the elements of C* form a cancellative semigroup with respect to the addition of sets. Moreover scalar multiplication have several properties like the ordinary scalar multiplication of vectors but not without any restriction (see section 1.4). Rådström's embedding theorem eliminates these additional requirements to provide an infinitely dimensional normed linear space environment for convex sets. The method can be used in general to present any cancellative semigroup as a subset of a group in the usual sense.

Definition Consider the set of ordered pairs (A, B) of elements in C*. We say that (A,B) and (C,D) are related if

A + D = B + C

(12.1)

Lemma 12.1.1 Relation 12.1 is an equivalence relation.

Proof Reflexivity and symmetry are clear by the definition. Suppose that (A,B) is related to (C,D) and (C,D) is related to (E,F). Then, by definition,

A + D = B + C   a n d   C + F = E + D .

Adding these equations we have that

A + F + D + C = E + B + D + C

which means by the cancellation law 1.4.3 that

A + F = E + B

proving that (A,B) is related to (E,F) and the transitivity holds for 12.1 as was to be proved. ▮

The equivalence class represented by the ordered pair (A,B) will be denoted as [A,B].

Definition Let us define the addition

[ A , B ] + [ C , D ] = [ A + C , B + D ]

(12.2)

between the equivalence classes.

Excercise 12.1.2 Prove that the addition 12.2 is independent of the choice of the representation of equivalence classes. Find the zero element with respect to the operation 12.2 and prove that the set of the equivalence classes equipped with 12.2 is an Abelian group.

Definition Let the scalar multiplication be defined as

λ [ A , B ] = [ λ A , λ B ] i f λ 0 ( - λ ) [ B , A ] i f λ < 0

(12.3)

Excercise 12.1.3 Prove that the scalar multiplication 12.3 is independent of the choice of the representation of equivalence classes.

Lemma 12.1.4 The salar multiplication 12.3 satisfies the following properties:

λ [ A , B ] + [ C , D ] = λ [ A , B ] + λ [ C , D ] ,

(12.4)

( λ 1 + λ 2 ) [ A , B ] = λ 1 [ A , B ] + λ 2 [ A , B ] ,

(12.5)

( λ 1 λ 2 ) [ A , B ] = λ 1 λ 2 [ A , B ]

(12.6)

and

1 [ A , B ] = [ A , B ] .

(12.7)

Proof Suppose first of all that the scalar multiplier is non-negative in property 12.4. Then the left hand side can be written as

[ λ ( A + C ) , λ ( B + C ) ]

and the right hand side is

[ λ A + λ C , λ B + λ D ] .

They are obviously equal to each other by property 1.24. The case of negative multipliers is similar. Property 12.5 comes from 1.25 in case of scalars with the same sign. The only non-trivial case when we have scalars with different signs. From now on we suppose that

λ 1 > 0   a n d   λ 2 < 0 .

(12.8)

Let the sum of the scalars be non-negative, i.e.

λ 1 + λ 2 0 .

Then the left hand side of 12.5

( λ 1 + λ 2 ) [ A , B ] = [ ( λ 1 + λ 2 ) A , ( λ 1 + λ 2 ) B ] .

The right hand side

λ 1 [ A , B ] + λ 2 [ A , B ] = [ λ 1 A , λ 1 B ] + [ ( - λ 2 ) B , ( - λ 2 ) A ] =

[ λ 1 A + ( - λ 2 ) B , λ 1 B + ( - λ 2 ) A ] .

To prove that they are the same we should check that

X + W = Z + Y ,

where

X = ( λ 1 + λ 2 ) A , Y = ( λ 1 + λ 2 ) B ,

Z = λ 1 A + ( - λ 2 ) B , W = λ 1 B + ( - λ 2 ) A .

Since the scalars

( λ 1 + λ 2 )   a n d   ( - λ 2 )

have the same sign we can write that

X + W = ( ( λ 1 + λ 2 ) + ( - λ 2 ) ) A + λ 1 B = λ 1 A + λ 1 B = λ 1 ( A + B )

and

Z + Y = λ 1 A + ( ( λ 1 + λ 2 ) + ( - λ 2 ) ) B = λ 1 A + λ 1 B = λ 1 ( A + B )

as was to be proved. The discussion of the further possible cases is similar. To prove the associativity-like property 12.6 consider again the case of scalars with different signs under the convention 12.8. The left hand side is

( - λ 1 λ 2 ) [ B , A ] = [ ( - λ 1 λ 2 ) B , ( - λ 1 λ 2 ) A ] .

The right hand side is

λ 1 [ ( - λ 2 ) B , ( - λ 2 ) A ] = [ λ 1 ( - λ 2 ) B , λ 1 ( - λ 2 ) A ] .

They are obviously equal to each other by property 1.26. Consider the case of scalars with the same sign. Then the left hand side preserves the ordering of the set A and B. The right hand side also preserves this ordering by changing it two times in case of negative scalar multipliers. The last property 12.7 is trivial.

Corollary 12.1.5 The set of equivalence classes is a real vector space with respect to the addition 12.2 and the scalar multiplication 12.3.

In what follows we shall construct a norm on the vector space of the equivalence classes.

Definition Let the mapping H be defined as

H ( [ A , B ] , [ C , D ] ) : = h ( A + D , B + C ) .

(12.9)

Lemma 12.1.6 Definition 12.9 is independent of the representation of equivalence classes.

Proof We have that

H ( [ A ' , B ' ] , [ C ' , D ' ] ) = h ( A ' + D ' , B ' + C ' ) =

h ( A ' + D ' + ( A + B + C + D ) , B ' + C ' + ( A + B + C + D ) )

because the Hausdorff metric is translation invariant. Furthermore

h ( A ' + D ' + ( A + B + C + D ) , B ' + C ' + ( A + B + C + D ) ) =

h ( ( A ' + B ) + ( D ' + C ) + ( A + D ) , ( B ' + A ) + ( C ' + D ) + ( B + C ) ) =

h ( A + D , B + C ) )

provided that

A + B ' = A ' + B   a n d   C + D ' = C ' + D ,

i.e. [A,B] is related to [A',B'], and [C,D] is related to [C',D']. Therefore

H ( [ A ' , B ' ] , [ C ' , D ' ] ) = H ( [ A , B ] , [ C , D ] )

as was to be proved.

Lemma 12.1.7 H is a translation invariant metric on the vector space of equivalence classes and

H ( λ [ A , B ] , λ [ C , D ] ) = | λ | H ( [ A , B ] , [ C , D ] ) .

(12.10)

Proof The translation invariance follows from the corresponding theorem 1.5.5 for the Hausdorff distance:

H ( [ A , B ] + [ E , F ] , [ C , D ] + [ E , F ] ) = H ( [ A + E , B + F ] , [ C + E , D + F ] ) =

h ( A + D + E + F , C + B + E + F ) = h ( A + D , C + B ) = H ( [ A , B ] , [ C , D ] ) .

On the other hand if we have a non-negative scalar multiplier then

H ( λ [ A , B ] , λ [ C , D ] ) = H ( [ λ A , λ B ] , [ λ C , λ D ] ) = h ( λ A + λ D , λ B + λ C ) =

h ( λ ( A + D ) , λ ( B + C ) ) = λ h ( A + D , B + C ) = λ H ( [ A , B ] , [ C , D ] ) .

The case of a negative scalar multiplier is similar. Among the metric properties non-negativity and symmetry are trivial because of the corresponding properties of the Hausdorff metric. To check the positive definiteness suppose that

0 = H [ A , B ] , [ C , D ] ) = h ( A + D , B + C )

which means that

A + D = B + C

because of the positive definiteness of the Hausdorff metric. This means that (A,B) and (C,D) are related to each other, i.e. the equivalence classes represented by them coincide. Finally, the triangle inequality follows as

H ( [ A , B ] , [ E , F ] ) = h ( A + F , B + E ) = h ( A + F + ( C + D ) , B + E + ( C + D ) ) =

h ( ( A + D ) + ( C + F ) , ( B + C ) + ( D + E ) )

h ( ( A + D ) + ( C + F ) , ( B + C ) + ( C + F ) ) +

h ( ( B + C ) + ( C + F ) , ( B + C ) + ( D + E ) ) =

h ( A + D , B + C ) + h ( C + F , D + E ) = H ( [ A , B ] , [ C , D ] ) + H ( [ C , D ] , [ E , F ] )

because of the corresponding property of the Hausdorff metric.

Lemma 12.1.8 If δ is a translation invariant metric satisfying property 12.10 then

N ( v ) : = δ ( x , y ) i f v = y - x

(12.11)

is a norm on the vector space.

Proof Suppose that y - x=y' - x'; then y+x'=y'+x=w and the translation invariance of the metric implies that

δ ( x , y ) = δ ( x + ( x ' + y ' ) , y + ( x ' + y ' ) ) =

δ ( x ' + ( x + y ' ) , y ' + ( y + x ' ) ) = δ ( x ' + w , y ' + w ) = δ ( x ' , y ' ) .

Therefore the mapping N is well-defined. The properties of the norm can be derived from the corresponding properties of the distance and property 12.10 (cf. absolute homogenity). To prove the triangle inequality consider two elements v=y - x and w=y' - x'. We have that

N ( v + w ) = δ ( x + x ' , y + y ' ) δ ( x + x ' , y + x ' ) + δ ( y + x ' , y + y ' ) =

δ ( x , y ) + δ ( x ' , y ' ) = N ( v ) + N ( w )

as was to be proved.

Corollary 12.1.9 The set of equivalence classes equipped with the norm coming from H forms a normed vector space.

Theorem 12.1.10 The family of non-empty compact convex subsets in the coordinate space of dimension n can be isometrically embedded as a convex cone into a real normed vector space. Explicitly

μ : K μ ( K ) : = [ K , K + K ] ,

(12.12)

where the mapping 12.12 is additive and positively homogeneous in the sense that

μ ( λ K ) = λ μ ( K )

for any positive real number λ.

Proof First of all note that for any non-empty compact convex sets L and M

[ L , K + L ] = [ M , K + M ]

(12.13)

because of L+(K+M)=M+(K+L). Especially,

μ ( K ) = [ M , K + M ] .

Then we have

μ ( K ) + μ ( L ) = [ M , K + M ] + [ M , L + M ] = [ M + M , ( K + L ) + ( M + M ) ] =

= μ ( K + L )

because of 12.13. Using the invariance property 12.13 again

μ ( λ K ) = [ M , λ K + M ] = [ λ M , λ K + λ M ] =

[ λ M , λ ( K + M ) ] = λ [ M , K + M ] = λ μ ( K )

provided that the scalar multiplier is positive (or at least non-negative). In the next step we prove that μ is an isometric embedding.

H ( μ ( K ) , μ ( L ) ) = H ( [ M , K + M ] , [ M , L + M ] ) = h ( M + M + L , M + M + K ) =

h ( L , K ) = h ( K , L )

because of the translation invariance of the Hausdorff metric. ▮

Remark A similar statement can be formulated for any subfamily of non-empty compact convex sets provided that the subfamily is a cone: it is closed under the addition and the scalar multiplication by positive real numbers.

Excercise 12.1.11 Prove that the family of closed disks around the origin is closed under the addition and the scalar multiplication by positive real numbers.

For a more general survey of spaces of convex sets (together with the partial ordering induced by the inclusion of sets) we can refer to [17].