Introduction to Computational Linear Algebra

Algorithms for the Eigenvalue Problem 145

In matrix form (5.52) becomes:

G = δT

d

+ (1 − δ)E, (5.53)

where E is the n × n matrix which elements are all p =

1

n

.

For 0 < δ < 1 the matrix G is a Markov chain type matrix. Using

the Perron-Frobenius theory for Markov chains type matrices its spectrum

Λ(G) ⊂ {z ∈ C ||z| ≤ 1} and furthermore there is only one maximal eigen-

value λ = 1 with algebraic and geometric multiplicity equal to 1 and a corre-

sponding eigenvector s which has non-negative elements s

i

.

Use of Power Method to Compute the PageRank Vector

On the basis of (5.51), the vector of page scores s of W

n

satisfies:

s = Gs = δT

d

s + (1 − δ)Es (5.54)

These ...