Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

1.7 Excercises

1.7 Excercises

Excercise 1.7.1 Find the parameter t for the system

v 1 = ( 1,2 , 3 ) , v 2 = ( - 1,0 , 2 ) , v 3 = ( 2,1 , t )

to be linearly dependent. Prove that in case of t=1 the system is linearly independent and find the coordinates of

v = ( 1,8 , - 2 )

with respect to the basis

v 1 = ( 1,2 , 3 ) , v 2 = ( - 1,0 , 2 ) , v 3 = ( 2,1 , 1 ) .

Excercise 1.7.2 Find the inverse of the matrix

1 - 1 2 2 0 1 3 2 1 .

How the inverse matrix is related to the coordinate transformation?

Excercise 1.7.3 Find the parameters t and s for the system

v 1 = ( 1,2 , 3 ) , v 2 = ( - 1 , t , 2 ) , v 3 = ( 2,1 , s )

to be linearly dependent. What is the locus of points with coordinates t and s in the plane.

Excercise 1.7.4 Find the rank of the systems

v 1 = ( 2 , - 1,2 ) , v 2 = ( 1,2 , - 3 ) , v 3 = ( 3 , - 4,7 ) .

v 1 = ( - 2,3 , 4 ) , v 2 = ( 3 , - 4,5 ) , v 3 = ( 3,3 , - 3 ) .

v 1 = ( 1 , - 2,3 ) , v 2 = ( - 4,5 , 6 ) , v 3 = ( 7,8 , - 9 ) .

Excercise 1.7.5 Find the rank of the systems

v 1 = ( 1,0 , 0 , - 1 ) , v 2 = ( 2,1 , 1,0 ) , v 3 = ( 1,1 , 1,1 ) ,

v 4 = ( 1,2 , 3,4 ) , v 5 = ( 0,1 , 2,3 ) .

v 1 = ( 1,2 , 2 , - 1 ) , v 2 = ( 2,3 , 2,5 ) , v 3 = ( - 1,4 , 3 , - 1 ) ,

v 4 = ( 2,9 , 3,5 ) .

v 1 = ( - 3,1 , 5,3 , 2 ) , v 2 = ( 2,3 , 0,1 , 0 ) , v 3 = ( 1,2 , 3,2 , 1 ) ,

v 4 = ( 3 , - 5 , - 1 , - 3 , - 1 ) , v 5 = ( 3,0 , 1,0 , 0 ) .

Excercise 1.7.6 Find the inverse of the matrices

1 2 3 1 3 - 2 2 4 7

and solve the equation

1 2 3 1 3 - 2 2 4 7 X = 4 7 1 - 14 8 - 5 11 14 3 .

To calculate the distance between a point and a linear (or affine) subspace[2] H in the Euclidean space one typically needs the orthogonal complement to H. Especially systems consisting of pairwise orthogonal non-zero vectors play a distinguished role in Euclidean geometry (see Gram-Schmidt's process of orthogonalization). The following excercises refer to some special tools and process in the coordinate space of dimension three. Problems in higher dimensionalspaces will be also formulated.

Excercise 1.7.7 Calculate the vectorial product of the elements

v 1 = ( 2 , - 1,2 ) , v 2 = ( 1,2 , - 3 )

in the coordinate space of dimension three. Is the resulting vector perpendicular to the terms of the product? How to express its length in terms of lengths of the given vectors and the angle between them? What about the orientation of the system

v 1 , v 2 , v 3 = v 1 × v 2 ?

Excercise 1.7.8 Calculate the mixed product of the elements

v 1 = ( 2 , - 1,2 ) , v 2 = ( 1,2 , - 3 ) , v 3 = ( 3 , - 4,7 ) .

Excercise 1.7.9 Calculate the distance between the point

p = ( - 2 , - 4,3 )

and the plane

2 x - y + 3 z = 1 .

Excercise 1.7.10 Calculate the distance between the point

p = ( 5 , - 12 , - 4 )

and the line

x - 7 5 = y + 2 - 4 = z - 1 .

Excercise 1.7.11 Calculate the distance between the lines

x + 7 3 = y + 4 4 = z + 3 - 2

and

x - 21 6 = y + 5 - 4 = 2 - z .

Excercise 1.7.12 Calculate the distance between the point

p = ( 4,2 , - 5,1 )

and the affine subspace given by the system of equations

2 x 1 - 2 x 2 + x 3 + 2 x 4 = 9 ,

2 x 1 - 4 x 2 + 2 x 3 + 3 x 4 = 12 .

Excercise 1.7.13 Calculate the distance between the point

p = ( 4 , - 1,3 , 7 )

and the affine subspace given by the system of equations

3 x 1 + 2 x 2 + 2 x 4 = - 5 ,

3 x 1 + 4 x 2 + 3 x 3 + x 4 = 3 ,

x 1 - x 3 + x 4 = - 3 .

Excercise 1.7.14 Prove that the formal determinant of the matrix

e 1 e 2 e 3 e 4 3 2 0 2 3 4 3 1 1 0 - 1 1 ,

where the first row contains the members of the canonical basis 1.9 gives a vector perpendicular to every element of the system

v 1 = ( 3,2 , 0,2 ) , v 2 = ( 3,4 , 3,1 ) , v 3 = ( 1,0 , - 1,1 ) .

Excercise 1.7.15 Use the standard Gram-Schmidt process to transform the system

v 1 = ( 1 , - 2,2 ) , v 2 = ( - 1,0 , - 1 ) , v 3 = ( 5 , - 3 , - 7 )

into an orthogonal system of vectors. How to compute the coordinates of

v = ( 6 , - 1,4 )

with respect to a basis consisting of pairwise orthogonal unit vectors.

Excercise 1.7.16 Use the standard Gram-Schmidt process to transform the following systems into orthogonal ones in the generated linear subspaces.

v 1 = ( 0,1 , 0,1 ) , v 2 = ( - 2,3 , 0,1 ) , v 3 = ( 1,1 , 1,5 ) .

v 1 = ( 1,1 , 1,1 ) , v 2 = ( 3,3 , - 1 , - 1 ) , v 3 = ( - 2,0 , 6,8 ) .

Find the missing vectors to give orthogonal bases in the coordinate space of dimension four.

Although vector spaces of the same finite dimension are isomorphic sometimes they have lots of different features relative to the standard coordinate space of dimension n. To finish this section we formulate some excercises related to vector spaces of different objects to illustrate how the presented technics and methods work in strange situations.

Excercise 1.7.17 Prove that the set of square matrices of order n forms a Euclidean vector space with respect to the inner product

A , B = t r a c e A T B ,

where the operator T refers to the transpose of the matrix.

Excercise 1.7.18 Prove that the set of polynomials of order at most n forms a Euclidean vector space with respect to the inner product

P , Q = - 1 1 P ( x ) Q ( x ) d x .

Use the standard Gram-Schmidt process to transform the system of monomials

1 , x , x 2 , , x n

into an orthogonal system of polynomials; see Legendre polynomials.

Excercise 1.7.19 Prove that for every Euclidean vector space v and w are perpendicular to each other if and only if

v + w 2 = v 2 + w 2 .

(1.47)

Hint. Formula 1.47 is just the generalization of the classical Pythagorean theorem (and its converse).

Figure 15: Legendre polynomials up to order four.

Excercise 1.7.20 Prove that for every Euclidean vector space the elements v and w have the same length if and only if the sum of the given vectors is perpendicular to the difference vector.

Hint. The diameters of a rhombus are perpendicular to each other.

One of the most important relationships in Euclidean vector spaces is the so-called parallelogram-law

v + w 2 + v - w 2 2 = v 2 + w 2 .

It can be easily derived from the characteristic properties of the inner product: additivity and homogeneity in each of the variables, symmetry and positive definiteness. Actually it is a necessary and sufficient condition for the existence of an inner product corresponding to a given norm. Recall that the norm provides an adequate way to measure the length of vectors in the space. This means non-negativity and positive definiteness, absolute homogeneity and subadditivity (in an equivalent terminology: triangle inequality).

Excercise 1.7.21 Using the parallelogram law prove that the norm

z : = m a x { | v 1 | , | v 2 | , , | v n | }

does not come from any inner product. What about the so-called taxicab norm

v : = | v 1 | + | v 2 | + + | v n | ?

(1.48)

Using the associated distance function

d 1 ( p , q ) = | p 1 - q 1 | + | p 2 - q 2 |

(1.49)

in the coordinate plane sketch the "ellipse"

d 1 ( ( x , y ) , ( 1,0 ) ) + d 1 ( ( x , y ) , ( - 1,0 ) ) = 1

and find its perimeter.

Hint. The equation of the ellipse is

| x - 1 | + | y | + | x + 1 | + | y | = 4

with perimeter 12 (with respect to the associated distance function 1.49).

Excercise 1.7.22 Prove or disprove the following statements:

• The intersection of open/closed subsets is open/closed.

• The union of closed subsets is closed.

• The intersection of compact subsets is compact.

Excercise 1.7.23 Prove that for any subset A in a topological space the collection of sets of the form

V = U A ,

(1.50)

where U is open in the embedding space forms a topology for A.

Hint. The set A equipped with the so-called relative topology 1.50 is called a subspace of the embedding topological space.

Excercise 1.7.24 Let A be a subset all of whose convergent sequences tend to an element in A. Prove that A is closed. Prove the converse of the statement in case of subsets in the real coordinate space of dimension n.

The following excercise contains the topological characterization of the continuity of a mapping

f : E n E m

(1.51)

at the point p of its domain. For the sake of simplicity let q:=f(p) be the image of p under f.

Excercise 1.7.25 Prove that the mapping 1.51 is continuous at p if and only if for every open neighbourhood V around q there exists an open neighbourhood U around p such that f(U) is a subset in V.

Hint. Suppose that the topological characterization is true and let p(k) be a sequence tending to p. If r is an arbitrary positive real number and V is the open ball around f(p) with radius r then, by our assumption, there exists an open neighbourhood U around p such that f(U) is a subset in V. Since p is an interior point of U it follows that p(k) is in U provided that k is great enough. Therefore f(p(k)) is in V showing that f(p(k)) tends to f(p). To prove the converse of the statement let V be an open neighbourhood around q and suppose in contrary that for any integer k the open ball U(k) around p with radius (1/k) contains an element f(p(k)) which is not in V. To present the contradiction it is enough to consider the limit of f(p(k)) as k tends to the infinity.

Excercise 1.7.26 Prove that the mapping 1.51 is continuous if and only if for every open set in the coordinate space of dimension m the pre-image under the mapping f is an open set in the coordinate space of dimension n.

Excercise 1.7.27 How the pre-image/image of the union of subsets A and B is related to the union of pre-images/images of A and B.

Excercise 1.7.28 How the pre-image/image of the intersection of subsets A and B is related to the intersection of pre-images/images of A and B.

Definition The final topology (the strong topology with respect to f) of the coordinate space of dimension m is defined by the collection of subsets for which the pre-images under the mapping 1.51 are open in the usual sense. The initial topology (the weak topology with respect to f) of the coordinate space of dimension n is defined by the collectionof subsets for which the images under the mapping 1.51 are open in the usual sense.

Excercise 1.7.29 Prove that both the final and the initial topology satisfy conditions T1, T2 and T3.

Excercise 1.7.30 Prove or disprove the following statements:

• the image of an open set under a continuous mapping is open,

• the pre-image of a closed set under a continuous mapping is closed,

• theimage of a compact set under a continuous mapping is compact.

Excercise 1.7.31 Let A be a compact subset in the real coordinate space of dimension n. Prove that

• A is closed and bounded.

• Every sequence in A has a convergent subsequence.

• Every continuous function on A attains both its minimum and its maximum.

Excercise 1.7.32 How the closure/interior of the intersection of A and B isrelated to the intersection of the closures/interiors of A and B.

Excercise 1.7.33 How the closure/interior of the union of A and B is related to the union of the closures/interiors of A and B.

Excercise 1.7.34 Prove that both the interior and the closure of a convex set are convex.

Excercise 1.7.35 Find the convex hull of three not collinear points in the space.

Excercise 1.7.36 Find theconvex hulls of the following subsets in the plane:

y = x 2 , y = x 2   a n d   x 0 , y = 1 x   a n d   x 1 2 .

Hint. See epigraphs of functions; proposition 1.6.1.

Excercise 1.7.37 Find the convex hull of the set y=sin x in the plane.

Excercise 1.7.38 Find the convex hulls of the following subsets in the plane:

y = x 3 , y = x 5 , y = x 7 , . . .

Hint. In case of the cubic function prove that any point (x,y) in the plane can be written as

( x , y ) = 1 3 ( x 1 , x 1 3 ) + 2 3 ( x 2 , x 2 3 ) ,

i.e. as a trisection of a segment joining two points on the graph. (Use the fundamental theorem of algebra to prove that a real polynomial of order three always has a real root).

Excercise 1.7.39 Find the equation of the affine hull of the elements

p 1 = ( 1,2 , 3 ) , p 2 = ( - 1,0 , 2 ) , p 3 = ( 2,1 , 1 ) .

Hint. To find the equation of the affine hull choose the point p(1) as the "origin" and consider the linear subspace L spanned by the position vectors

p 2 - p 1 , p 3 - p 1

with respect to p(1). It can be easily checked that the orthogonal complement is generated by

v = ( p 2 - p 1 ) × ( p 3 - p 1 ) = ( 3 , - 5,4 )

and the equation of the affine hull is just

3 x - 5 y + 4 z = 3 ( 1 ) - 5 ( 2 ) + 4 ( 3 ) = 5 .

The right hand side is created in the only possible way to provide p(1) as the element of the affine hull.

Excercise 1.7.40 Find the equation of the affine hull of the elements

p 1 = ( 1 , - 1,2 , - 1 ) , p 2 = ( 2 , - 1,2 , 0 ) , p 3 = ( 1,0 , 2,0 ) , p 4 = ( 1,0 , 3,1 ) .

Excercise 1.7.41 Find the dimension of the affine hull of the elements

p 1 = ( 1,0 , 2,1 ) , p 2 = ( 2,1 , 2,3 ) , p 3 = ( 0,1 , - 2,1 ) , p 4 = ( - 1,0 , - 2 , - 1 ) .

Excercise 1.7.42 Find the dimension of the affine hull of the elements

p 1 = ( 1,2 , 3 ) , p 2 = ( 0,1 , - 1 ) , p 3 = ( 1,0 , 2 ) , p 4 = ( - 2,1 , 3 ) .

Excercise 1.7.43 Prove that if A and B are affine sets with a non-empty intersection then

d i m ( A B ) = d i m A + d i m B - d i m ( A B ) .

What about the dimension of the union of disjoint affine subsets?

Hint. The formula for the dimension of the union of intersecting affine subsets is just the same as the usual one for linear subspaces. But the condition of a non-empty intersection is important as the case of parallel lines in the coordinate space of dimension three shows. Here is the only big difference between affine and linear subspaces: two linear subspaces always meet in the origin of the space. The translation part varies the possible positions of an affine subspace relative to another one (see e.g. parallelism).

Excercise 1.7.44 Find the sets

A + B , ( A + B ) + C   a n d   A + ( B + C ) ,

where A, B and C are the segments joining the points

( 0,0 ) a n d ( 2,0 ) , ( 0,0 ) a n d ( 0,2 ) , ( 0,0 ) a n d ( 2,2 )

in the plane, respectively.

Figure 16: Addition of sets.

Figure 17: Addition of sets.

Excercise 1.7.45 Find the sum of the sets A and D, where A is the segment joining the points

( 0,0 ) a n d ( 2,0 )

and D is the unit disk centered at the origin, cf. the definition of parallel bodies 1.5.

Figure 18: Addition of sets.

Excercise 1.7.46 Find the sum of the sets A and B, where

A = c o n v { ( 1,2 ) , ( 3,2 ) , ( 3,4 ) , ( 1,4 ) }

and B is the closed unit disk given by the inequality

( x - 5 ) 2 + ( y - 1 ) 2 1 .

Figure 19: Addition of sets.

Figure 20: Addition of sets.

Excercise 1.7.47 Why distributivity-like property 1.25 is not true in general?

Excercise 1.7.48 Prove the subbaditivity

c o n v ( A + B ) c o n v A + c o n v B

(1.52)

and the homogenity

c o n v ( λ A ) = λ c o n v A

(1.53)

of the conv - operator.

Excercise 1.7.49 Why the cancellation laws are false in general?

Hint. Let C be the unit disk centered at the origin and consider its boundary B. Since B+C is the union of unit disks centered at the points of B we have that B+C=2C (the disk centered at the origin with radius 2). If A={ 0} then A+C is obviously a subset in 2C=B+Cbut 0 is not in B.

Excercise 1.7.50 Find the parallel body of a point, a segment and a polygonal chain in the plane, see figure 18.

Excercise 1.7.51 Prove that

P ( P ( A , λ ) , μ ) P ( A , λ + μ ) .

What about the converse of the statement?

Excercise 1.7.52 Prove that if A is a non-empty compact convex set then

P ( P ( A , λ ) , μ ) = P ( A , λ + μ ) .

Excercise 1.7.53 Express the Hausdorff distance between closed disks in the plane in terms of the radius and the distance between the centers.

Excercise 1.7.54 Let

A = [ - 1,2 ] × [ 2,3 ] , B = [ 1,2 ] × [ - 1 , - 1 ]

and C be the closed unit disk given by the inequality

( x + 1 ) 2 + ( y + 1 ) 2 1 .

Calculate the Hausdorff distances among the given subsets in the coordinate plane.

Excercise 1.7.55 Prove that any two of the segments forming the sides of a square in the plane have the same Hausdorff distance.

Excercise 1.7.56 Prove that the operator conv is Lipschitzian, i.e.

h ( c o n v A , c o n v B ) h ( A , B ) .

(1.54)

Hint. Since

A B + h ( A , B ) D

it follows from the subadditivity 1.52 and the homogenity 1.53 that

c o n v A c o n v B + h ( A , B ) c o n v D = c o n v B + h ( A , B ) D .

In a similar way

c o n v B c o n v A + h ( A , B ) c o n v D = c o n v A + h ( A , B ) D

proving equation 1.54.

Excercise 1.7.57 Prove that the collection of non-empty convex compact subsets is a closed set in the metric space of non-empty compact sets equipped with the Hausdorff metric, i.e. the limit of a convergent sequence of compact convex subsets is convex.

Hint. Use the Lipschitzian property 1.54 to prove that if A(k) tends to B then conv A(k) tends to conv B.

Excercise 1.7.58 Find examples to present the strict inequality

h ( c o n v A , c o n v B ) < h ( A , B )

(1.55)

Excercise 1.7.59 Prove that Hausdorff metrics related to different compact convex "unit" bodies containing the origin in their interiors are equivalent to each other.

Excercise 1.7.60 Prove that equality holds in 1.34 for any real number λ if and only if

g : = f - f ( 0 )

is a linear functional.

Excercise 1.7.61 Prove that the set of convex functions with a common domain forms a convex cone, i.e. it is closed under the addition of functions and the multiplication with non-negative scalars.

Excercise 1.7.62 Prove that the lower level sets defined by the inequality

f ( p ) c o n s t a n t

are convex in case of a convex function. Prove that the upper level sets defined by the inequality

f ( p ) c o n s t a n t

are convex in case of a concave function. What about the converse statements?

Hint. Consider revolution surfaces as graphs of functions to illustrate that convex (lower) level sets do not guarantee the convexity in the sense of 1.34 (functions with convex lower level sets are called quasi-convex).

Excercise 1.7.63 Find the convex functions in the following list:

f ( x ) = 2 x - 3 , f ( x ) = 2 ( x - 1 ) 2 + 6 , f ( x ) = x 3 , f ( x ) = t a n x , f ( x ) = e x .

How the convexity of invertible continuous functions with one variable and their inverses are related?

Hint. Using Bolzano's theorem prove that invertible continuous functions are strictly monotone. How the convexity of a strictly monotone increasing function and its inverse are related?

Excercise 1.7.64 Find the convex functions in the following list:

f ( x , y ) = e x 2 + y 2 , f ( x , y ) = 2 ( x - 1 ) 2 + 6 ( y + 3 ) 2 , f ( x , y ) = ( x - y ) 3 + y 2 - 4 ,

f ( x , y ) = x y + 1 ,   w h e r e   x > 0   a n d   y > 0 ,

f ( x , y ) = t a n ( x 2 + y 2 ) ,   w h e r e   x 2 + y 2 < π 2 .

Excercise 1.7.65 Find the parameters a and b for the function

f ( x ) = x 2 i f x 1 a x + b o   t h e   r w i s e  

to be convex on the entire real line.

Excercise 1.7.66 Let

g : [ 0,1 ] R   w i t h   i n i t i a l   v a l u e   g ( 0 ) = 0

be a convex function. Prove that

f ( t ) : = g ( t ) t

is non-decreasing.

Excercise 1.7.67 Prove that the subgradient vectors form a convex set.

Excercise 1.7.68 Find the subgradient vectors of the function

f ( x , y ) = x + y i f x 0   a n d   y 0 - 2 x + y i f x < 0   a n d   y 0 - 2 x - y i f x < 0   a n d   y > 0 x - y i f x 0   a n d   y > 0

at the origin.

Hint. If w is a subgradient vector at the origin then, by definition,

w 1 x + w 2 y x + y ( 0 x , 0 y )

in the first quadrant of the coordinate plane. Therefore

0 ( 1 - w 1 ) x + ( 1 - w 2 ) y

which means that (1 - w(1),1 - w(2)) must be also in the first quadrant. Therefore

w 1 1 , w 2 1 .

Using the same technic in the further quadrants of the plane we have that the subgradient vectors form the set

c o n v { ( 1,1 ) , ( - 2,1 ) , ( - 2 , - 1 ) , ( 1 , - 1 ) } .

Excercise 1.7.69 Prove that the minimizers of a convex function form a convex set.

Definition The function f is strictly convex if

f ( λ p + ( 1 - λ ) q ) < λ f ( p ) + ( 1 - λ ) f ( q )

for any different points p, q and real number 0<λ<1. In other words equality in 1.34 can be realized only in trivial ways: either p=q or λ=0 or 1.

Excercise 1.7.70 Prove that a strictly convex function has at most one minimizer.

In the theory of convex functions there are several methods to generate new convex functions from given ones (operations). The following examples are devoted to illustrate some of them.

Definition Let f(1), ..., f(m) be given real-valued functions on the same domain in the coordinate space of dimension n. By taking the pointwise maxima we define the max function as follows:

g ( p ) = m a x { f 1 ( p ) , , f m ( p ) } .

Especially,

( f h ) ( p ) = m a x { f ( p ) , h ( p ) } .

Excercise 1.7.71 Prove that the max-function of convex functions is convex.

Figure 21: The max-function.

Using the sum of (strict) epigraphs as convex sets in the coordinate space of dimension n+1 we can create a new (strict) epigraph together with a new function. It will be convex because the sum of convex sets is convex. This leads to the notion of infimal convolution of convex functions(see also conjugation).

Excercise 1.7.72 Find the analytic description of the infimal convolution of convex functions.

Hint. In case of real functions

( f * g ) ( x ) = i n f y f ( x - y ) + g ( y )

Excercise 1.7.73 Find the gradient vectors of the following functions

f ( x , y ) = x 3 l n y + 2 y 2 x + 5 ,

f ( x , y , z ) = z x z + y ,

f ( x , y ) : = x 2 + 2 y 2 - x - 2 y - 1 .

Excercise 1.7.74 Find the equation of the tangent lines to the following plane curves at the given points:

x 2 16 + y 2 12 = 1   a n d   p = ( 2 , - 3 ) ,

x 2 5 - y 2 4 = 1   a n d   p = ( 5 , - 4 ) .

Excercise 1.7.75 Find the equation of the tangent line to the following plane curve at the given point:

y 2 = 18 x   a n d   p = ( 2 , - 6 ) .