<<

. 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
about their structure.
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

g ¡ The simplicial cones “ and
g ¡
“— are dual to each other:
g ¡
g ¡

oa ⊥ b oc , ob ⊥ c oa , oc ⊥ a ob ,
o g¡
€€€
 e
 €€
 e €€ oa ⊥ boc, ob ⊥ coa, oc ⊥ aob.
 €c
 €
e

ˆˆ ¨
ˆˆˆ ¨
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 .)



>>