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

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 . . . . .