<<

. 5
( 20 .)



>>

de¬ned by the condition
k
bfj = 0.
j=1

1. Prove that a ¬nite set F has a unique barycentre.

2. Further prove that the barycentre b is the point where the function
k
r(x, fj )2
M (x) =
j=1

takes its minimal value. In particular, if the set F is invariant under the
action of a group W of isometries, then W ¬xes the barycentre b.

Hint: Introduce orthonormal coordinates x1 , . . . , xn and show that the system of
equations
‚M (x)
= 0, i = 1, . . . , n,
‚xi
k
is equivalent to the equation j=1 xfj = 0, where x = (x1 , . . . , xk ).

1.4.3 If a and b are two points in ARn then the segment [a, b] can be charac-
terised as the set of all points x such that r(a, b) = r(a, x) + r(x, b).

1.4.4 Draw a diagram illustrating the construction of ± + β in the proof of
Theorem 1.4.2, and ¬ll in the details of the proof.

1.4.5 Prove that if t± is a translation through the vector ± and s is an orthog-
onal transformation then
st± s’1 = ts± .

1.4.6 Prove the following generalisation of Theorem 1.4.1: if a group W <
Isom ARn has a bounded orbit on ARn then W ¬xes a point.

Elations.

1.4.7 Prove that an elation of ARn preserves angles: if it sends points a, b, c
to the points a , b , c , correspondingly, then ∠abc = ∠a b c .

1.4.8 The group of all elations of ARn is isomorphic to Rn (On — R>0 ) where
R>0 is the group of positive real numbers with respect to multiplication.

1.4.9 Groups of symmetries. If ∆ ‚ ARn , the group of symmetries Sym ∆
of the set ∆ consists of all isometries of ARn which map ∆ onto ∆. Give
examples of polytopes ∆ in AR3 such that
20

1. Sym ∆ acts transitively on the set of vertices of ∆ but is intransitive on
the set of faces;

2. Sym ∆ acts transitively on the set of faces of ∆ but is intransitive on the
set of vertices;

3. Sym ∆ is transitive on the set of edges of ∆ but is intransitive on the set
of faces.


1.5 Simplicial cones
1.5.1 Convex sets
Recall that a subset X ⊆ ARn is convex if it contains, with any points
x, y ∈ X, the segment [x, y] (Figure 1.7).


¨¨rr
¨ r
¨ r
¨ r xr  
xr  
d  
d d
d d
dry
yr d
r ¨
rr ¨¨ d
d



convex set non-convex set

Figure 1.7: Convex and non-convex sets.

Obviously the intersection of a collection of convex sets is convex. Every
convex set is connected. A¬ne subspaces (in particular, hyperplanes) and
half spaces (open and closed) in ARn are convex. If a set X is convex then
so are its closure X and interior X —¦ . If Y ⊆ ARn is a subset, it convex
hull is de¬ned as the intersection of all convex sets containing it; it is the
smallest convex set containing Y .


1.5.2 Finitely generated cones
Cones. A cone in Rn is a subset “ closed under addition and positive
scalar multiplication, that is, ± + β ∈ “ and k± ∈ “ for any ±, β ∈ “ and
a scalar k > 0. Linear subspaces and half spaces of Rn are cones. Every
cone is convex, since it contains, with any two points ± and β, the segment

[±, β] = { (1 ’ t)± + tβ | 0 t 1 }.
A. & A. Borovik • Mirrors and Re¬‚ections • Version 01 • 25.02.00 21

A cone does not necessary contains the zero vector 0; this is the case, for
example, for the positive quadrant “ in R2 ,

x
∈ R2
“= x > 0, y > 0 .
y

However, we can always add to a cone the origin 0 of Rn : if “ is a cone then
so is “ ∪ { 0 }. It can be shown that if “ is a cone then so is its topological
closure “ and interior “—¦ . The intersection of a collection of cones is either
a cone or the empty set.
The cone “ spanned or generated by a set of vectors Π is the set of all
non-negative linear combinations of vectors from Π,

“ = { a1 ±1 + · · · + am ±m | m ∈ N, ±i ∈ Π, ai 0 }.

Notice that the zero vector 0 belongs to “. If the set Π is ¬nite then the
cone “ is called ¬nitely generated and the set Π is a system of generators
for “. A cone is polyhedral if it is the intersection of a ¬nite number of
closed half spaces.
The following important result can be found in most books on Linear
Programming. In this book we shall prove only a very restricted special
case, Proposition 1.5.6 below.

Theorem 1.5.1 A cone is ¬nitely generated if and only if it is polyhedral.


Extreme vectors and edges. We shall call a set of vectors Π positive
if, for some linear functional f : Rn ’’ R, f (ρ) > 0 for all ρ ∈ Π { 0 }.
This is equivalent to saying that the set Π { 0 } of non-zero vectors in Π
is contained in an open half space. The following property of positive sets
of vectors is fairly obvious.

Lemma 1.5.2 If ±1 , . . . , ±m are non-zero vectors in a positive set Π and

a1 ±1 + · · · + am ±m = 0, where all ai 0,

then ai = 0 for all i = 1, . . . , m.

Positive cones are usually called pointed cones (Figure 1.8).
Let “ be a cone in Rn . We shall say that a vector ∈ “ is extreme
or simple in “ if it cannot be represented as a positive linear combination
which involves vectors in “ non-collinear to , i.e. if it follows from =
c1 γ1 + · · · + cm γm where γi ∈ “ and ci > 0 that m = 1 and = c1 γ1 . Notice
that it immediately follows from the de¬nition that if is an extreme vector
22




$$$rr
$$ 
$ r
$ $ $
$ $$ $$ ¡
rr
s r$$$$   $$ $$$
d 
 
d $
¡ r$
 r r s r
de r
$u d ¡ rr
$¡ $
$$
$
$ de   $d ¡ ¡
!
$ rr $$ ¡$
X
$$ $ r
$ $
d¡ $
$W
$$ rr
$$$

e r $$
$$$ $
rr $
r$ $
$$ $$$
r
rr
$$$ r $$
r$
r $ $$
r$

a pointed ¬nitely generated cone a non-pointed ¬nitely generated cone


Figure 1.8: Pointed and non-pointed cones

“ β2
$$r
$$$ ±  rr β1 ± is a non-extreme vector in the
β3 $ $
$
r
drr$$$$  
d β4 T
s  
 cone “ generated by extreme
 r r
de r
$u (or simple) vectors β1 , β2 , β3 , β4
$ de  
$ r
$$$ r
$ d 
e r directed along the edges of “.
$$
r $$
r $
rr $$
$$
r $$
r$


Figure 1.9: Extreme and non-extreme vectors.

and Π a system of generators in “ then Π contains a vector k collinear to
.
Extreme vectors in a polyhedral cone “ ‚ R2 or R3 have the most
natural geometric interpretation: these are vectors directed along the edges
of “. We prefer to take this property for the de¬nition of an edge: if is
an extreme vector in a polyhedral cone “ then the cone “ © R is called an
edge of “, see Figure 1.9.

1.5.3 Simple systems of generators
A ¬nite system Π of generators in a cone “ is said to be simple if it consists
of simple vectors and no two distinct vectors in Π are collinear. It follows
from the de¬nition of an extreme vector that any two simple systems Π
and Π in “ contain equal number of vectors; moreover, every vector in Π
is collinear to some vector in Π , and vice versa.

Proposition 1.5.3 Let Π be ¬nite positive set of vectors and “ the cone
A. & A. Borovik • Mirrors and Re¬‚ections • Version 01 • 25.02.00 23

it generates. Assume also that Π contains no collinear vectors, that is,
± = kβ for distinct vectors ±, β ∈ Π and k ∈ R implies k = 0. Then Π
contains a (unique) simple system of generators.

In geometric terms this means that a ¬nitely generated pointed cone
has ¬nitely many edges and is generated by a system of vectors directed
along the edges, one vector from each edge.

Proof. We shall prove the following claim which makes the statement of
the lemma obvious.

A non-extreme vector can be removed from any generating set
for a pointed cone “. In more precise terms, if the vectors
±, β1 , . . . , βk of Π generate “ and ± is not an extreme vector
then the vectors β1 , . . . , βk still generate “.

Proof of the claim. Let

Π = { ±, β1 , . . . , βk , γ1 , . . . , γl },

where no γj is collinear with ±. Since ± is not an extreme vector,

k l
±= bi βi + cj γj , bi 0, cl 0.

<<

. 5
( 20 .)



>>