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

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

Downloading requires you to have access to the YouScribe library
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 finite dimensionalnormed linear spaces. Also in view of very recent developments, this field 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 field. Having chosen such an approach, we follow the modern trend that numericalcomputations are based on exact arithmetics.

Subjects

Informations

Published by
Published 01 January 2006
Reads 16
Language English
Document size 1 MB

Selected Problems
from
Minkowski Geometry
von der Fakultat fur Mathematik¨ ¨
der Technischen Universitat Chemnitz genehmigte¨
DISSERTATION
zur Erlangung des akademischen Grades
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 finite dimensional
normed linear spaces. Also in view of very recent developments, this field 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 field. 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 classified to belong to the following topics:
Discrete and Convex Geometry (MR 52), including the theory of polytopes, finite dimensional
Banach Space Theory (MR 46Bxx), and Foundations of (nonuclidean) Geometries (MR 51 and
MR 53).
Many specialists in the field of Discrete Geometry know the problem of classifying 2istance
sets. Wepresentsuchaclassification,whichcanbeconsideredasthemainresultofthedissertation.
Due to several talks of myself at international conferences, these experts are waiting with large
interest for this complete classification of 2istance sets. It occurs here for the first 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.
Konrad J. Swanepoel. I am also grateful for helpful discussions with Gennadiy Averkov.
Finally, I want to thank the “Studienstiftung des deutschen Volkes” for financial 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 Affine 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 Birkhoff 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 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.17 Polyhedra and polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.18 Tasks, systems, and algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Angular measures and bisectors 19
2.1 Some definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 definition with that of a ?isector . . . . . 25
2.4.6 The equivalence of Glogovskij’s definition 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 simplification 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 Coefficients of the linear functions . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.4 Polynomial coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 influence of parameters . . . . . . . . . . . . . . . . . . 60
5.3 Certificates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3.1 Certificates for nondmissibility . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.2 Certificates for upper bounds on the dimension of the solution set . . . . . 62
5.3.3 Certificates for lower bounds on the dimension of the solution set . . . . . . 63
5.3.4 Certificate for full solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Verification 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 Definitions and classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.1 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.2 Full 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.3 Maximal 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . 77
6.2.4 Affine 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2.5 Strong 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.6 Surprising results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.2 Completeness of the classification . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.3 Realizability of candidates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.4 Affine 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . . . 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 affine 2istance Configurat ions 89
6.3.9 Strong 2istance configurations . . . . . . . . . . . . . . . . . . . . . . . . 90
Bibliography 92
Index 94
Symbols 97
Theses 99
Lebenslauf (Curriculum Vitae) 100Introduction
WithinChapter1wecollectalotofdefinitionsandbasicresultswhicharewellknownandstandard.
For basic notions, such as real linear vector space, we give exact definitions 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 finite 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 certificates to decouple the algorithms which should find
a solution of a family of parametrized linear systems from a simpler procedure, which verifies that
this solution is correct.
Finally, Chapter 6 gives a complete classification 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 field of real numbers byR, the field 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 finite 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 define its concatenation g◦f : A→ C
by a7! g(f(a)). A sequence in A is a function f :N → A (called finite sequence) or a functionn
f :N→A (called infinite 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.
Definition 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 definite (ρ(x,y)≥ 0 with equality if and only if x =y) and
• ρ satisfies the triangle inequality (ρ(x,z)≥ρ(x,y)+ρ(y,z) for all x,y,z∈X).
˜Definition 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.
˜Definition 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.
˜ ˜Definition 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.
Definition 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 fits 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.
Definition 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 finite 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.

′ ′Definition 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 .
′ ′ ′Definition 1.8 An affine 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 defineV :=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 affine subspace ofV.
Note that X ⊂V is an affine subspace ofV if and only if λx+(1−λ)y∈X for all x,y∈X, λ∈R.
Definition 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
Definition 1.10 For a system (x ) of vectors x (i∈ I =∅) of a real linear vector spaceV thei i∈I i
affine hull, aff{x :i∈I}, of (x ) or of the set {x :i∈I}, is the smallest affine subspace ofVi i i∈I i
containing all vectors x , i∈I. More precisely, we havei ( )X X
′ ′ ′aff{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 affine subspace ofV after fixing some 0 ∈ aff{x :i∈I} asi
origin, as described in Definition 1.8.
Definition 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
finite dimensional real linear vector space. For any set U ∈V we denote its (affine) dimension by
dimU := dimaffU. NotethatthisquantityisindependentonthechoiceoftheoriginofaffU,since
affU is implicitly considered as affine subspace ofV for which we already defined the dimension.
Definition 1.12 We call a set S ⊂V affinely independent, if for all x ∈ S we have that x ∈/
aff(S\{x}). Otherwise S is called affinely dependent.
The finite subset S⊂V is affinely independent if and only if dimaffS =|S|−1.
It is a fundamental result that each finite 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 finite 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 )issomefixedbasisofR 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 identified) 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 define 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 defined 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 affine hull
H := affA 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 Affine 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.