Canonical forms for certain rank one perturbations and an application to the Google PageRanking problem
Roger A. Horn, Stefano Serra‐Capizzano · 2006
Let A be a given n-by-n complex matrix with eigenvalues λ, λ2, . . . , λn. Suppose there are nonzero vectors x, y ∈ Cn such that Ax = 3Dλx, y∗A = 3Dλy∗, and y∗x = 3D1. Let v ∈ Cn be such that = v∗x = 3D1, let c ∈ C, and assume that λ 6= cλj for each j = 3D2, . . . , n. Define A(c) := 3DcA + (1 − c)λxv∗. The eigenvalues of A(c) are λ, cλ2, . . . , cλn. Every left eigenvector of A(c) corresponding to λ is a scalar multiple of y − z(c), in which the vector z(c) is an explicit rational function of c. If a standard form such as the Jordan canonical form or the Schur triangular form is known for A, we show how to obtain the corresponding standard form of A(c). The web hyperlink matrix G(c) used by Google for computing the PageRank is a special case in which A is real, nonnegative, and row stochastic (taking into consideration the dangling nodes), c ∈ (0, 1), x is the vector of all ones, and v is a positive probability vector. The PageRank vector (the normalized dominant left eigenvector of G(c)) is therefore an explicit rational function of c. Extrapolation procedures on the complex field may give a practical and efficient way to compute the PageRank vector when c is close to 1.