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

r¨

r¨

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

$$$

d

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.