<< Предыдущая стр. 6(из 20 стр.)ОГЛАВЛЕНИЕ Следующая >>
i=1 j=1

Also, since the vectors О±, ОІ1 , . . . , ОІk generate the cone О“,
k
Оіj = dj О± + fji ОІi , dj 0, fji 0.
i=1

Substituting Оіi from the latter equations into the former, we have, after a
simple rearrangement,
l k l
1в€’ cj dj О±= bi + cj fji ОІi .
j=1 i=1 j=1

The vector О± and the vector on the right hand side of this equation both
lie in the same open half space; therefore, in view of Lemma 1.5.2,
l
1в€’ cj dj > 0
j=1
24

and
k l
1
О±= bi + cj fji ОІi
1в€’ j cj dj i=1 j=1

expresses О± as a nonnegative linear combination of ОІi вЂ™s. Since the vectors
О±, ОІ1 , . . . , ОІk generate О“, the vectors ОІ1 , . . . , ОІk also generate О“.
The following simple lemma has even simpler geometric interpretation:
the plane passing through two edges of a cone cuts in it the cone spanned
by these two edges, see Figure 1.10.

ОІ
О“ \$\$r
\$\$\$ В  rr
В
\$ \$
rr О± В \$\$\$
В В
В
d r\$\$ В
В  The intersection of a cone О“ with the
d В  В ВЈ В
В
uВ  ВЈ
deeВ ВЈ В
В
В
В  plane spanned by two simple vectors
В
eВ ВЈ О± and ОІ is the coned generated by О±
ВЈe
and ОІ.
ВЈe
ВЈe
ВЈВ
ВЈВ
ВЈ
В

Figure 1.10: For the proof of Lemma 1.5.4

Lemma 1.5.4 Let О± and ОІ be two distinct extreme vectors in a п¬Ѓnitely
generated cone О“. Let P be the plane (2-dimensional vector subspace)
spanned by О± and ОІ. Then О“0 = О“ в€© P is the cone in P spanned by О± and
ОІ.

Proof. Assume the contrary; let Оі в€€ О“0 be a vector which does not
belong to the cone spanned by О± and ОІ. Since О± and ОІ form a basis in the
vector space P ,
Оі = a О± + b ОІ,
and by our assumption one of the coeп¬ѓcients a or b is negative. We can
assume without loss of generality that b < 0.
Let О±, ОІ, Оі1 , . . . , Оіm be the simple system in О“. Since Оі в€€ О“,

Оі = aО± + bОІ + c1 Оі1 + В· В· В· + cm Оіm ,

where all the coeп¬ѓcients a, b, c1 , . . . , cm are non-negative. Comparing the
two expressions for Оі, we have

(a в€’ a )О± + (b в€’ b )ОІ + c1 Оі1 + В· В· В· + cm Оіm = 0.
A. & A. Borovik вЂў Mirrors and Reп¬‚ections вЂў Version 01 вЂў 25.02.00 25

Notice that b в€’ b > 0; if a в€’ a 0 then we get a contradiction with the
assumption that the cone О“ is pointed. Therefore a в€’ a < 0 and
1
О±= ((b в€’ b )ОІ + c1 Оі1 + В· В· В· + cm Оіm )
a в€’a
expresses О± as a non-negative linear combination of the rest of the simple
system. This contradiction proves the lemma.

1.5.4 Duality
If О“ is a cone, the dual cone О“в€— is the set

О“в€— = { П‡ в€€ Rn | (П‡, Оі) 0 for all Оі в€€ О“ }.

It immediately follows from this deп¬Ѓnition that the set О“в€— is closed with
respect to addition and multiplication by positive scalars, so the name
вЂ˜coneвЂ™ for it is justiп¬Ѓed. Also, the dual cone О“в€— , being the interesection of
closed half-spaces (П‡, Оі) 0, is closed in topological sense.
The following theorem plays an extremely important role in several
branches of Mathematics: Linear Progamming, Functional Analysis, Con-
vex Geometry. We shall not use or prove it in its full generality, proving
instead a simpler partial case.

Theorem 1.5.5 (The Duality Theorem for Polyhedral Cones) If О“ is a
polyhedral cone, then so is О“в€— . Moreover, (О“в€— )в€— = О“.

Recall that polyhedral cones are closed by deп¬Ѓnition.

1.5.5 Duality for simplicial cones
Simplicial cones. A п¬Ѓnitely generated cone О“ вЉ‚ Rn is called simplicial
if it is spanned by n linearly independent vectors ПЃ1 , . . . , ПЃn . Denote О  =
{ ПЃ1 , . . . , ПЃn }.
We shall prove the Duality Theorem 1.5.5 in the special case of simpli-
cial cones, and obtain, in the course of the proof, very detailed information
First of all, notice that if the cone О“ is generated by a п¬Ѓnite set О  =
{ ПЃ1 , . . . , ПЃn } then the inequalities

(П‡, Оі) 0 for all Оі в€€ О“

are equivalent to
(П‡, ПЃi ) 0, i = 1, . . . , n.
26

Hence the dual cone О“в€— is the intersection of the closed subspaces given by
the inequalities
(П‡, ПЃi ) 0, i = 1, . . . , n.
We know from Linear Algebra that the conditions
в€’1 if i = j
(ПЃв€— , ПЃj ) =
i
0 if i = j
uniquely determine n linearly independent vectors ПЃв€— , . . . , ПЃв€— (see Exer-
1 n
cises 1.5.2 and 1.5.3). We shall say that the basis О  = { ПЃв€— , . . . , ПЃв€— } is
в€—
1 n
dual to the basis ПЃ1 , . . . , ПЃn . If we write a vector П‡ в€€ R in the basis О в€— ,
5 n

П‡ = y1 ПЃв€— + В· В· В· + yn ПЃв€— ,
в€— в€—
1 n

then (П‡, ПЃi ) = в€’yi and П‡ в€€ О“в€— if and only if yi
в€—
0 for all i, which
means that П‡ в€€ О“в€— . So we proved the following partial case of the Duality
Theorem, illustrated by Figure 1.11.

b О“
ВЁВ€В€В€ a
cВЁ
g ВЎ The simplicial cones О“ and
g ВЎ
О“в€— are dual to each other:
g ВЎ
g ВЎ
gВЎ
oa вЉҐ b oc , ob вЉҐ c oa , oc вЉҐ a ob ,
o gВЎ
ВЂВЂВЂ
 e
 ВЂВЂ
 e ВЂВЂ oa вЉҐ boc, ob вЉҐ coa, oc вЉҐ aob.
 ВЂc
 ВЂ
e
aВ€
В€В€ ВЁ
В€В€В€ ВЁ
e ВЁ
В€В€
В€В€ e ВЁВЁ
В€В€ВЁ e
О“в€—
b

Figure 1.11: Dual simplicial cones.

Proposition 1.5.6 If О“ is the simplicial cone spanned by a basis О  of Rn
then the dual cone О“в€— is also simplicial and spanned by the dual basis О в€— .
Applying this property to О“в€— we see that О“ = (О“в€— )в€— is the dual cone to О“в€—
and coincides with the intersection of the closed half spaces
(П‡, ПЃв€— ) 0, i = 1, . . . , n.
i
5
We move a little bit away from the traditional terminology, since the dual basis is
usually deп¬Ѓned by the conditions
1 if i = j
(ПЃв€— , ПЃj ) = .
i 0 if i = j
A. & A. Borovik вЂў Mirrors and Reп¬‚ections вЂў Version 01 вЂў 25.02.00 27

1.5.6 Faces of a simplicial cone
Denote by Hi the hyperplane (П‡, ПЃв€— ) = 0. Notice that the cone О“ lies in
i
one closed half space determined by Hi . The intersection О“k = О“ в€© Hk
consists of all vectors of the form П‡ = y1 ПЃ1 + В· В· В· + yn ПЃn with non-negative
coordinates yi , i = 1, . . . , n, and zero k-th coordinate, yk = 0. Therefore
О“k is the simplicial cone in the n в€’ 1-dimensional vector space (П‡, ПЃв€— ) = 0
k
spanned by the vectors ПЃi , i = k. The cones О“k are called facets or (n в€’ 1)-
dimensional faces of О“.
More generally, if we denote I = { 1, . . . , n } and take a subset J вЉ‚ I of
cardinality m, then the (n в€’ m)-dimensional face О“J of О“ can be deп¬Ѓned
in two equivalent ways:
вЂў О“J is the cone spanned by the vectors ПЃi , i в€€ I J.
вЂў О“J = О“ в€© Hj .
jв€€J

It follows from their deп¬Ѓnition that edges are 1-dimensional faces.
If we deп¬Ѓne the faces О“в€— in an analogous way then we have the formula
J

О“в€— = { П‡ в€€ О“в€— | (П‡, Оі) = 0 for all Оі в€€ О“IrJ }.
J

Abusing terminology, we shall say that the face О“в€— of О“в€— is dual to the face
J
О“IrJ of О“. This deп¬Ѓnes a one-to-one correspondence between the faces of
the simplicial cone О“ and its dual О“в€— .
In particular, the edges of О“ are dual to facets of О“в€— , and the facets of
О“ are dual to edges of О“в€— .
We shall use also the Duality Theorem for cones О“ spanned by m < n
linearly independent vectors in Rn . The description of О“в€— in this case is an
easy generalisation of Proposition 1.5.6; see Exercise 1.5.4.

Exercises
1.5.1 Let X be an arbitrary positive set of vectors in Rn . Prove that the set

X в€— = { О± в€€ Rn | (О±, Оі) 0}

is a cone. Show next that X в€— contains a non-zero vector and that X is contained
in the cone (X в€— )в€— .

1.5.2 Dual basis. Let 1 , . . . , n be an orthonormal basis and ПЃ1 , . . . , ПЃn a
basis in Rn . Form the matrix R = (rij ) by the rule rij = (ПЃi , j ), so that ПЃi =
n
j=1 rij j . Notice that R is a non-degenerate matrix. Let ПЃ = y1 1 + В· В· В· + yn n .
For each value of i, express the system of simultaneous equations

в€’1 if i = j
(ПЃ, ПЃj ) =
0 if i = j
28

in matrix form and prove that it has a unique solution. This will prove the
existence of the basis dual to ПЃ1 , . . . , ПЃn .
1.5.3 A formula for the dual basis. In notation of Exercise 1.5.2, prove
that the dual basis { ПЃв€— } can be determined from the formula
i

r11 . . . r1,jв€’1 r1,j+1 . . . r1,n
1
r21 . . . r2,jв€’1 r2,j+1 . . . r2,n
2
. . . . .
. . . . .
1 . . . . .
 << Предыдущая стр. 6(из 20 стр.)ОГЛАВЛЕНИЕ Следующая >>