102 Pages
English

# Selected problems from minkowski geometry [Elektronische Ressource] / vorgelegt von Nico Düvelmeyer

Learn all about the services we offer

Description

Selected ProblemsfromMinkowski Geometryvon der Fakultat fur Mathematik¨ ¨der Technischen Universitat Chemnitz genehmigte¨DISSERTATIONzur Erlangung des akademischen GradesDoctor rerum naturalium(Dr. rer. nat.)¨TECHNISCHE UNIVERSITAT CHEMNITZFakultat fur Mathematik¨ ¨vorgelegt von Dipl.-Math. Nico Duvelmeyer¨geb. am 30. Mai 1979 in Greiz eingereicht am 8. Juni 2006gefo¨rdert durch ein Stipendium der Studienstiftung des deutschen Volkes (4/2003 bis 3/2005)Gutachter: Prof. Dr. H. Martini (Betreuer, TU Chemnitz)Prof. Dr. K. J. Swanepoel (UNISA, Pretoria, South Africa)Prof. Dr. E. Hertel (Friedrichchiller-Universit a¨t Jena)Tag der Verteidigung: 9. November 2006Verfug¨ bar im MONARCH der TU Chemnitz: http://archiv.tu-chemnitz.de/pub/2006/0196PrefaceThe results of this dissertation refer to the geometry of Minkowski spaces, i.e., of ﬁnite dimensionalnormed linear spaces. Also in view of very recent developments, this ﬁeld can be located at theintersectionofFinslerGeometry,BanachSpaceTheory,andConvexGeometry,butitisalsocloselyrelated to Distance Geometry and Abstract Convexity. Moreover, the main part of the obtainedresults belongs to the Discrete Geometry of normed planes, where the use of numerical methodsis new in this ﬁeld. Having chosen such an approach, we follow the modern trend that numericalcomputations are based on exact arithmetics.

Subjects

##### Mathematics

Informations

Selected Problems
from
Minkowski Geometry
von der Fakultat fur Mathematik¨ ¨
der Technischen Universitat Chemnitz genehmigte¨
DISSERTATION
Doctor rerum naturalium
(Dr. rer. nat.)
¨TECHNISCHE UNIVERSITAT CHEMNITZ
Fakultat fur Mathematik¨ ¨
vorgelegt von Dipl.-Math. Nico Duvelmeyer¨
geb. am 30. Mai 1979 in Greiz eingereicht am 8. Juni 2006
gefo¨rdert durch ein Stipendium der Studienstiftung des deutschen Volkes (4/2003 bis 3/2005)
Gutachter: Prof. Dr. H. Martini (Betreuer, TU Chemnitz)
Prof. Dr. K. J. Swanepoel (UNISA, Pretoria, South Africa)
Prof. Dr. E. Hertel (Friedrichchiller-Universit a¨t Jena)
Tag der Verteidigung: 9. November 2006
Verfug¨ bar im MONARCH der TU Chemnitz: http://archiv.tu-chemnitz.de/pub/2006/0196Preface
The results of this dissertation refer to the geometry of Minkowski spaces, i.e., of ﬁnite dimensional
normed linear spaces. Also in view of very recent developments, this ﬁeld can be located at the
intersectionofFinslerGeometry,BanachSpaceTheory,andConvexGeometry,butitisalsoclosely
related to Distance Geometry and Abstract Convexity. Moreover, the main part of the obtained
results belongs to the Discrete Geometry of normed planes, where the use of numerical methods
is new in this ﬁeld. Having chosen such an approach, we follow the modern trend that numerical
computations are based on exact arithmetics. Within these computations semi-algebraic subsets
of the real numbers occur frequently as basic mathematical objects.
More precisely, the results obtained here can be classiﬁed to belong to the following topics:
Discrete and Convex Geometry (MR 52), including the theory of polytopes, ﬁnite dimensional
Banach Space Theory (MR 46Bxx), and Foundations of (nonuclidean) Geometries (MR 51 and
MR 53).
Many specialists in the ﬁeld of Discrete Geometry know the problem of classifying 2istance
sets. Wepresentsuchaclassiﬁcation,whichcanbeconsideredasthemainresultofthedissertation.
Due to several talks of myself at international conferences, these experts are waiting with large
interest for this complete classiﬁcation of 2istance sets. It occurs here for the ﬁrst time in printed
form. Otherpartsofthedissertationrefertocharacterizationsofinnerproductspacesbygeometric
properties of the space and related subjects.
Acknowledgement
My work was guided by valuable questions and hints of Prof. Dr. Horst Martini and Prof. Dr.
Finally, I want to thank the “Studienstiftung des deutschen Volkes” for ﬁnancial support.
1Contents
Introduction 5
1 Prerequisites 6
1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Metric spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Topological notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Algebraic notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.2 The Euclidean metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.3 Topological notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.4 Aﬃne geometric notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.5 Linear geometric notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Algebraic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Linear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 Minkowski geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8.1 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9 Birkhoﬀ orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.10 The functional β . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.11 Parametrization of the unit circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.12 Tangent vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.13 Radon curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.14 Equiframed bodies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.15 Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.16 Classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.17 Polyhedra and polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.18 Tasks, systems, and algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Angular measures and bisectors 19
2.1 Some deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Properties of angular bisectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2CONTENTS 3
2.4.1 Proofs concerning the properties of Busemann and Glogovskij angular bisector 22
2.4.2 Parametrization of the unit circle . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.3 The equivalence of Busemann and Glogovskij angular bisectors . . . . . . . 24
2.4.4 Extensions of systems of angular bisectors for straight angles . . . . . . . . 24
2.4.5 The equivalence of Busemann’s deﬁnition with that of a ?isector . . . . . 25
2.4.6 The equivalence of Glogovskij’s deﬁnition with that of a ?isectors . . . . 28
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Convex bodies with equiframed 2-dimensional sections 30
3.1 The statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Indirect approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Planar considerations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Local 3imensional extensions of the planar properties . . . . . . . . . . . . . . . 32
3.5 Global 3imensional properties of ∂B . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.6 Interpretation of the contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7 Application to the results for angular measures . . . . . . . . . . . . . . . . . . . . 36
4 Embedding metric spaces into a Minkowski space 37
4.1 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Transformation of the embedding task . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.1 Embedding into a suitable Minkowski space . . . . . . . . . . . . . . . . . . 38
4.2.2 Embedding into a given polytopal Minkowski space . . . . . . . . . . . . . . 42
4.3 Simplifying the analytical systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1 General simpliﬁcation principles . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Simplifying the general embedding system . . . . . . . . . . . . . . . . . . . 45
4.3.3 Using subsystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4 Algorithmical solvability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Reducing the number of systems which need to be checked for admissibility . . . . 47
4.6 One application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Solving parametrized linear systems 56
5.1 Systems to solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.1.1 Homogeneous and inhomogeneous systems . . . . . . . . . . . . . . . . . . . 56
5.1.2 Removing strict inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.3 Coeﬃcients of the linear functions . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.4 Polynomial coeﬃcients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.5 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2 Solution of a linear system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.1 Admissibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.2 Solution vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.3 Solution set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58CONTENTS 4
5.2.4 Special cases for the inﬂuence of parameters . . . . . . . . . . . . . . . . . . 60
5.3 Certiﬁcates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3.1 Certiﬁcates for nondmissibility . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.2 Certiﬁcates for upper bounds on the dimension of the solution set . . . . . 62
5.3.3 Certiﬁcates for lower bounds on the dimension of the solution set . . . . . . 63
5.3.4 Certiﬁcate for full solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Veriﬁcation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.2 Full search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.4.3 Instantiation and generalizing . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.5 Further notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6 2-distance sets in Minkowski planes 71
6.1 Deﬁnitions and classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.1 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.2 Full 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.3 Maximal 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . 77
6.2.4 Aﬃne 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2.5 Strong 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.6 Surprising results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Veriﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.2 Completeness of the classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.3 Realizability of candidates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.4 Aﬃne 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.5 Nonlinear restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3.6 The exception which is not polyhedral . . . . . . . . . . . . . . . . . . . . . 87
6.3.7 Reducing the symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.8 Construction of polynomial representatives of aﬃne 2istance Conﬁgurat ions 89
6.3.9 Strong 2istance conﬁgurations . . . . . . . . . . . . . . . . . . . . . . . . 90
Bibliography 92
Index 94
Symbols 97
Theses 99
Lebenslauf (Curriculum Vitae) 100Introduction
WithinChapter1wecollectalotofdeﬁnitionsandbasicresultswhicharewellknownandstandard.
For basic notions, such as real linear vector space, we give exact deﬁnitions as far as appropriate.
We will not state all their well known properties, although later on these might be used.
In the following Chapter 2 we consider some possibilities to generalize the well known concepts
of measuring angles and bisecting angles of the Euclidean plane to Minkowski planes. Then we
focus on all Minkowski planes with the property that two such possibilities yield exactly the same
angular bisector for every angle. This yields characterizations of inner product spaces, of Radon
planes and of equiframed planes. These results and parts of this chapter are contained in my
papers [14, 15].
Then we consider higher dimensional Minkowski spaces with the same property. Using well
known results from convex geometry, the twoimensional result generalizes easily to higher di-
mensions in case of Euclidean and Radon planes. A new similar result for equiframed planes is
obtained in Chapter 3, which is also published in [13].
In Chapter 4 we introduce the theory of embedding a given ﬁnite metric space into a suitable
Minkowski space of given dimension d, or into a given Minkowski space with polytopal unit ball.
The results of this chapter are needed in Chapter 6 for d = 2. But also not depending on this, the
theory developed here has many applications in view of practical embedding problems.
Chapter 5 is another preparatory part for Chapter 6, also to use the results from Chapter 4.
Here we introduce terminology and algorithms for solving families of linear systems of equations
and inequalities. We emphasize the use of certiﬁcates to decouple the algorithms which should ﬁnd
a solution of a family of parametrized linear systems from a simpler procedure, which veriﬁes that
this solution is correct.
Finally, Chapter 6 gives a complete classiﬁcation of 2istance sets in Minkows ki planes.
The appendix contains the bibliography, an index, another index of symbols with the corre
sponding terms and introducing page numbers, and the theses.
5Chapter 1
Prerequisites
1.1 Basics
We denote the ﬁeld of real numbers byR, the ﬁeld of rational numbers byQ, the ring of integers
0byZ, the set of positive integers byN and the set of non-negative integers byN . We use the
standard symbols for the set operations union A∪B, intersection A∩B and complement A of the
sets A and B. A is a subset of B, A⊂ B and B ⊃ A, if every element of A is also an element of
˙B, thus A⊂ A holds true. A( B means that A⊂ B and A = B. The notation A∪B of disjoint
union is an expression for the union set A∪B and also expresses the relation A∩B = ∅. This
symbol is also used for more than two sets. We use the abbreviationN :={1,2,...,n} for n∈N.n
Furthermore, we denote the closed interval {x ∈R : a ≤ x ≤ b} by [a,b] (a,b ∈R), the open
interval{x∈R :a<x<b} by (a,b) (a∈R∪{−∞}, b∈R∪{∞}) and the half open intervals by
[a,b) ={x∈R : a≤ x < b} and (a,b] ={x∈R : a < x≤ b}. The set of positive real numbers
+ ≥0is denoted byR := (0,∞), the set of nonegative real numbers is denoted by R := [0,∞).
By f : A → B we denote a function (or map) which maps exactly one b ∈ B to each a ∈ A,
Aalso denoted by f(a) = b or f : a7! b. The set of all such functions is denoted by B . For some
subsetX ⊂A we denote byf(X) :={f(x) :x∈X} the image (set) ofX underf, and forY ⊂B
−1we denote by f (Y) :={a∈ A : f(a)∈ Y } the inverse image of Y under f. The function f is
called bijective (f is a bijection), if for each b∈ B there is exactly one a∈ A with f(a) = b, i.e.,? ?
−1? ?if f ({b}) = 1 for all b ∈ B. We denote the cardinality of X by |X|. This is for ﬁnite sets X
the number of elements in X, otherwise some symbolic value∞ which is greater than any natural
number. For two functions f : A→ B and g : B → C we deﬁne its concatenation g◦f : A→ C
by a7! g(f(a)). A sequence in A is a function f :N → A (called ﬁnite sequence) or a functionn
f :N→A (called inﬁnite sequence). For the sequence f :N →A we also write (f ,f ,...,f ) orn 1 2 n
N nn((f ) ). In this sense we identify A with A . Analogously for f :N→A we write (f ,f ,...)i i∈N 1 2n
and ((f ) ). In some circumstances, if the meaning is clear from the context, we use a mixedi i∈N
l lnotation, (i,J,k) for example with i,k∈A, J ∈A , which is formally in A×A ×A, to denote the
l+2corresponding sequence (i,J ,...,J ,k) in A .1 l
We denote the power set of X by P(X) := {Y : Y ⊂ X} and the n-power set of X by? ?
X 2:= {Y ∈ P(X) : |Y| = n}. P :=N \{(i,i) : i ∈N } is the set of all pairs of distinctn nn
integers from 1 to n. We denote the sign of a real number λ by sign(λ) and the absolute value of
λ by|λ|.
1.2 Metric spaces
From a certain classical point of view, geometry is the science of measuring distances. Therefore
the metric space is a very basic and general geometric object.
Deﬁnition 1.1 A pair (X,ρ) consisting of a set X and a function ρ : X ×X →R is called a
metric space with distance function (metric) ρ if and only if
6
6CHAPTER 1. PREREQUISITES 7
• ρ is symmetric (ρ(x,y) =ρ(y,x) for all x,y∈X),
• ρ is positive deﬁnite (ρ(x,y)≥ 0 with equality if and only if x =y) and
• ρ satisﬁes the triangle inequality (ρ(x,z)≥ρ(x,y)+ρ(y,z) for all x,y,z∈X).
˜Deﬁnition 1.2 An embedding f of the metric space (X,ρ) into the metric space (X,ρ˜) is a map
˜f :X →X satisfying ρ˜(f(x),f(y)) =ρ(x,y) for all x,y∈X.
˜Deﬁnition 1.3 We call a function φ :X →X an isometry between the two metric spaces (X,ρ)
˜ ˜and (X,ρ˜) if it is an bijective embedding of (X,ρ) into (X,ρ˜). If there is any isometry between
˜(X,ρ) and (X,ρ˜), then these two metric spaces are called isometric.
˜ ˜Deﬁnition 1.4 A subspace of a metric space (X,ρ) is any metric space (X,ρ| ) whereX ⊂X˜ ˜X×X
and ρ| denotes the restriction of the function ρ to arguments consisting of two elements from˜ ˜X×X
˜X.
By U (z) := {x ∈ X : ρ(x,z) ≤ ε} we denote a (closed) ε-neighborhood of z ∈ X belonging toε
some metric space (X,ρ) for the real number ε> 0 .
1.3 Topological notation
• A set A⊂X is called open (in (X,ρ)) if for each a∈A there is some ε> 0 with U (a)⊂A.ε
• A set A⊂X is called closed (in (X,ρ)) if its complement X\A is open in (X,ρ).
• The interior of A, intA, is the largest open set contained in A⊂ X, intA ={a∈ A :∃ε >
0 :U (a)⊂A}.ε
• The (topological) closure clA of a set A⊂X is the set clA :=X\int(X\A).
• The boundary ∂A of A⊂X is the set ∂A := clA\intA.
1.4 Vector spaces
The linear vector space is a model of some simple algebraic structure, well suited as background
space for doing geometry.
Deﬁnition 1.5 A real linear vector space (V,?,+) is a setV together with two binary operations
?:R×V→V, (λ,x)7! λx = λ?x (scalar multiple) and + :V×V→V, (x,y)7! x+y (addition)
satisfying the following axioms:
• x+y = y+x for all x,y∈V
• (x+y)+z = x+(y+z) for all x,y,z∈V
• there is one origin, 0∈V,
• x+0 = x for all x∈V
• for each x∈V there is one vector−x := y∈V with x+y = 0
(i.e., (V,+) forms an Abelian group)
• 1x = x for all x∈V
• λ(?x) = (λ )x for all x∈V and λ,?∈R
• (λ+?)x =λx+?x for all x∈V and λ,?∈R
• λ(x+y) =λx+λy for all x,y∈V and λ∈RCHAPTER 1. PREREQUISITES 8
(i.e., the scalar multiple ﬁts together with the addition operation). The elements ofV are called
vector or point ofV, and we denote them by lowercase Euler Fraktur letters.
Note that we identifyV with (V,?,+) whenever it is appropriate.
Deﬁnition 1.6 A system (x ) of vectors x (i ∈ I) of a real linear vector spaceV is calledi i∈I i
′linearly independent, if there is no corresponding ﬁnite system (α ) ′,∅ =I ⊂I, of real nonzeroi i∈IP
′numbers 0 = α ∈R (for i ∈ I ) with α x = 0. Otherwise this system is called linearlyi ′ i ii∈I
dependent.

′ ′Deﬁnition 1.7 A linear subspace (V,?j ,+| ) of a linear real vector space (V,?,+) is a subsetV V
′V ⊂V which is itself a real linear vector space with the same, restricted, binary operations, i.e.,
′ ′ ′if it holds∀λ∈R,x,y∈V that λx∈V and x+y∈V .
′ ′ ′Deﬁnition 1.8 An aﬃne subspace (V,?,+ ) of a real linear vector space (V,?,+) is any real
˜linear vector space which is a translate of a linear subspaceV ofV. More precisely, for any linear
′ ′ ′ ′ ′˜ ˜subspaceV ofV and a∈V we deﬁneV :=V+a, 0 := a (new origin), λ?x := 0 +λ?(x−0 ) and
′ ′ ′ ′ ′ ′ ′x+ y := 0 +((x−0 )+(y−0 )) = x+y−0, and then we call (V,?,+ ) an aﬃne subspace ofV.
Note that X ⊂V is an aﬃne subspace ofV if and only if λx+(1−λ)y∈X for all x,y∈X, λ∈R.
Deﬁnition 1.9 For a system (x ) of vectors x (i ∈ I = ∅) of a real linear vector spaceV thei i∈I i
linear subspace spanned by (x ) , lin{x :i∈I}, also called the linear hull of (x ) or of the seti i∈I i i i∈I
{x : i ∈ I}, is the smallest linear subspace ofV containing all vectors x , i ∈ I. More precisely,i i
we have ( )X
′ ′ ′lin{x :i∈I} = α x :I ⊂I,|I |<∞,α ∈R∀i∈I .i i i i
′i∈I
Deﬁnition 1.10 For a system (x ) of vectors x (i∈ I =∅) of a real linear vector spaceV thei i∈I i
aﬃne hull, aﬀ{x :i∈I}, of (x ) or of the set {x :i∈I}, is the smallest aﬃne subspace ofVi i i∈I i
containing all vectors x , i∈I. More precisely, we havei ( )X X
′ ′ ′aﬀ{x :i∈I} = α x :I ⊂I,|I |<∞,α ∈R∀i∈I , α = 1 .i i i i i
′ ′i∈I i∈I
′Note that this set can be regarded as aﬃne subspace ofV after ﬁxing some 0 ∈ aﬀ{x :i∈I} asi
origin, as described in Deﬁnition 1.8.
Deﬁnition 1.11 A system (x ) of vectors x (i ∈ I) of a real linear vector spaceV forms ai i∈I i
basis ofV, if it is linearly independent and linearly spansV = lin{x : i ∈ I}. In this case wei
call the cardinality |I| of I the dimension ofV, dimV, and if dimV < ∞, thenV is called a
ﬁnite dimensional real linear vector space. For any set U ∈V we denote its (aﬃne) dimension by
dimU := dimaﬀU. NotethatthisquantityisindependentonthechoiceoftheoriginofaﬀU,since
aﬀU is implicitly considered as aﬃne subspace ofV for which we already deﬁned the dimension.
Deﬁnition 1.12 We call a set S ⊂V aﬃnely independent, if for all x ∈ S we have that x ∈/
aﬀ(S\{x}). Otherwise S is called aﬃnely dependent.
The ﬁnite subset S⊂V is aﬃnely independent if and only if dimaﬀS =|S|−1.
It is a fundamental result that each ﬁnite dimensional real linear vector spaceV is isomorphic
d dtoR , where d = dimV. This means that there is a bijection φ :R →V satisfying φ(λx) =λφ(x)
d dfor all λ∈R and x∈R and φ(x+y) = φ(x)+φ(y) for all x,y∈R , always using the operations
of the corresponding vector space. Thus we know all ﬁnite dimensional real linear vector spaces if
d dwe know all the spacesR , d = 0,1,....R is the set of all d-tuples (x ,...,x ) of d real numbers1 d
x , 1≤i≤d.i
dAddition and the scalar multiple inR is simply done for each component via λ(x ,...,x ) =1 d
(λx ,...,λx ) and (x ,...,x )+(y ,...,y ) = (x +y ,...,x +y ). We also use the notation of1 d 1 d 1 d 1 1 d d
6666CHAPTER 1. PREREQUISITES 9
columnectors,  
α1 .x = . :=α b +??+?α b ,  1 1 d d.
αd
dwhereB := (b ,b ,...,b )issomeﬁxedbasisofR andα ,...,α arecalledthecoordinates of xin1 2 d 1 d
the basis B. For the standard basis (e = (1,0,...,0),e = (0,1,0,...,0),...,e = (0,...,0,1)),1 2 d
thecoordinatesα ofxcoincidewiththecomponentsx ofx = (x ,...,x ). Wedenotethetransposedi i 1 d
t tof a matrix M or vector x by M or x (that is, interchanging rows and columns of M or x). We
denote by M the i-th row of M and by M the j-th column of M.i,∗ ∗,j
dFor some vector x ∈ X (X =R or X =Z[X ,...,X ] for example), or sequence x or d-1 k
tuple x (which are all identiﬁed) and each i ∈N we denote by x the i-th component of x asd i
long as we did not introduce another notation. Sometimes we will explicitly use the exception
d+1x = (x ,...,x )∈X .0 d
1.4.1 Algebraic notations
d dFor subsets A,B ofR , vectors x∈R and scalars λ∈R we use the common algebraic notations
A+B := {a+ b : a ∈ A, b ∈ B} (Minkowski sum), λA := {λa : a ∈ A} and its special cases
−A := (−1)A, A−B :=A+(−B), A+x :=A+{x}, A−x :=A+{−x} and so on. Multiplication
nof vectors by a scalar can be generalized to sets: if A⊂R, X ⊂R , then A?X := AX :={ax :
na∈A,x∈X}, with the special case Ax :=A{x} for x∈R .
1.4.2 The Euclidean metric
dThe most natural way to deﬁne a metric inR is to use the Pythagorean theorem, which givesp
2 2the Euclidean metric ̺ (x,y) :=kx−yk via the Euclidean norm k(x ,...,x )k := x +??+?x .e 1 d 12 2 d
d dWe denote the Euclidean d-dimensional space byE := (R ,̺ ).e
1.4.3 Topological notions
dWe consider all topological notions ofR (open and closed sets, interior, closure and boundary) as
dusually deﬁned in the metric spaceE . It is well known that all dimensional normed spaces (see
dbelow) induce the same topology inR .
d• The relative boundary relbdA of A⊂R is the boundary of A with respect to the aﬃne hull
H := aﬀA of A, i.e., in the metric space (H,̺ (?,?)| ) we have relbd dA :=∂ A.e H E (H,̺ (?,?)| )e H
d• A set A⊂R is called bounded, if there is some c∈R with ̺ (0,x)<c for all x∈A.e
d• A set A⊂R is called compact, if it is closed and bounded.
1.4.4 Aﬃne geometric notions
The straight segment joining x and y is denoted by xy :={λx+(1−λ)y : λ∈ [0,1]}, the straight
line through x and y byhx,yi :={(1−λ)x+λy :λ∈R}, and the ray with starting point x passing
through yby[x,yi ={(1−λ)x+λy :λ≥ 0}. SmallGreeklettersdenoterealnumbersorfunctions.
dA subset A ⊂ R is called convex, if for all a,b ∈ A also the segment ab belongs to A.
d dThe convex hull, convA, of some subset A ∈R is the smallest convex set inR containing A,
convA ={α a +??+?α a :α ,...,α ≥ 0, a ,...,a ∈A, α +??+?α = 1}.1 1 k k 1 k 1 k 1 k
dWe call each compact, convex subset ofR with interior points a convex body.
d dWe say that two sets A,B ⊂ R are homothetic if there is some λ > 0 and x ∈ R with
B =λA+x.