Advanced book on Mathematics Olympiad

2.3 Linear Algebra 85

Now, there is a rather general result that states that a contractive function on a complete
metric space has a unique fixed point, which we will prove in Section 3.1.3. Recall that
a metric space is a setXendowed with a functionδ: X×X →[ 0 ,∞)satisfying
(i)δ(x, y)=0 if and only ifx=y, (ii)δ(x, y)=δ(y, x)for allx, y∈X, (iii)δ(x, y)+
δ(y, z)≥δ(x, z)for allx, y, z∈X. A metric space is complete if every Cauchy sequence
converges to a limit inX. A functionf:X→Xis contractive if for anyx =y,

δ(f (x), f (y))≤cδ(x, y)

for some fixed constantc,0<c<1.
With this in mind, we want to find a distance on the setKthat makes the functionf
defined above contractive. This is the Hilbert metric defined by the formula

δ(v, w)=ln

(

max

i

{

vi

wi

}/

min

i

{

vi

wi

})

,

forv=(v 1 ,v 2 ,...,vn)andw=(w 1 ,w 2 ,...,wn)∈K. That this satisfies the triangle
inequalityδ(v, w)+δ(w, u)≥δ(v, w)is a consequence of the inequalities

max

i

{

vi

wi

}

·max

i

{

wi

ui

}

≥max

i

{

vi

wi

}

,

min

i

{

vi

wi

}

·min

i

{

wi

ui

}

≤min

i

{

vi

wi

}

.

Let us show thatfis contractive. Ifv=(v 1 ,v 2 ,...,vn)andw=(w 1 ,w 2 ,...,wn)
are inK,v =w, and ifαi>0,i= 1 , 2 ,...,n, then

min

i

{

vi

wi

}

<

α 1 v 1 +α 2 v 2 +···+αnvn

α 1 w 1 +α 2 w 2 +···+αnwn

<max

i

{

vi

wi

}

.

Indeed, to prove the first inequality, add the obvious inequalitieswjmini{wvii}≤vj,j=
1 , 2 ,...,n. Becausev =wand both vectors are on the unit sphere, at least one inequality
is strict. The second inequality follows fromwjmaxi{wvii}≥vj,j= 1 , 2 ,...,n, where
again at least one inequality is strict.
Using this fact, we obtain for allj,1≤j≤n,
aj 1 v 1 +···+ajnvn
aj 1 w 1 +···+ajnwn
maxi

{

vi

wi

} < 1 <

aj 1 v 1 +···+ajnvn

aj 1 w 1 +···+ajnwn

mini

{

vi

wi

}.

Therefore,

maxj

{a

j 1 v 1 +···+ajnvn

aj 1 w 1 +···+ajnwn

}

maxi

{

vi

wi

} <

mini

{a

j 1 v 1 +···+ajnvn

aj 1 w 1 +···+ajnwn

}

mini

{

vi

wi

}.