86 2 Algebra
It follows that forv, w∈K,v =w,δ(f (v), f (w)) < δ(v, w).
Now,Kis closed and but is not bounded in the Hilbert norm; some points are infinitely
far apart. But even ifKis not bounded in the Hilbert metric,f(K)is (prove it!). If
we denote byK 0 the closure off(K)in the Hilbert norm, then this space is closed and
bounded.
The functionφ:K 0 ×K 0 →[ 0 ,∞),φ(v,w)=δ(f (v),f (w))δ(v,w) attains its maximumc.
Sinceφis strictly less than 1,c<1. This proves thatfis contractive onK 0 ; its fixed
point is the unique eigenvector ofAwith positive coordinates.
We are done with the first half of the proof. Now let us show that the eigenvalue of
this positive vector is larger than the absolute value of any other eigenvalue. Letr(A)be
the largest of the absolute values of the eigenvalues ofAand letλbe an eigenvalue with
|λ|=r(A). In general, for a vectorvwe denote by|v|the vector whose coordinates are
the absolute values of the coordinates ofv. Also, for two vectorsv, wwe writev≥w
if each coordinate ofvis greater than the corresponding coordinate ofw.Ifvis an
eigenvector ofAcorresponding to the eigenvalueλ, then|Av|=|λ|·|v|. The triangle
inequality impliesA|v|≥|Av|=r(A)|v|. It follows that the set
K 1 ={v|‖v‖= 1 ,v≥ 0 ,Av≥r(A)v},is nonempty. BecauseAhas positive entries,A(Av−r(A)v)≥0 forv ∈K 0 .So
A(Av)≥r(A)(Av), forv∈K 1 , proving thatf(K 1 )∈K. AgainK 1 is closed and
f(K 1 )is bounded, so we can reason as above to prove thatfrestricted toK 1 has a fixed
point, and becauseK 1 ⊂K, this is the fixed point that we detected before. Thusr(A)is
the unique positive eigenvalue.
There cannot exist another eigenvalueλwith|λ|=r(A), for otherwise, for a small
>0 the matrixA−Inwould still have positive entries, but its positive eigenvalue
r(A)−would be smaller than the absolute value of the eigenvalueλ−, contradicting
what we just proved. This concludes the proof of the theorem.
Nowhere in the book are more appropriate the words of Sir Arthur Eddington: “Proof
is an idol before which the mathematician tortures himself.’’
The conclusion of the theorem still holds in the more general setting of irreducible
matrices with nonnegative entries (irreduciblemeans that there is no reordering of the
rows and columns that makes it block upper triangular). This more general form of the
Perron–Frobenius Theorem is currently used by the Internet browser Google to sort the
entries of a search. The idea is the following: Write the adjacency matrix of the Internet
with a link highlighted if it is related to the subject. Then multiply each nonzero entry
by a larger or smaller number that takes into account how important the subject is in that
page. The Perron–Frobenius vector of this new matrix assigns a positive weight to each
site on the Internet. The Internet browser then lists the sites in decreasing order of their
weights.
We now challenge you with some problems.