<< Предыдущая стр. 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
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.
 << Предыдущая стр. 5(из 20 стр.)ОГЛАВЛЕНИЕ Следующая >>