Notes on the Second Eigenvalue of the Google Matrix

Abstract

If $A$ is an $n\times n$ matrix whose $n$ eigenvalues are ordered in terms of decreasing modules, $|{\lambda }_1|\ge |{\lambda }_2|\ge ...|{\lambda }_n|$, it is often of interest to estimate $\frac{|{\lambda }_2|}{|{\lambda }_1|}$. If $A$ is a row stochastic matrix (so ${\lambda }_1=1$), one can use an old formula of R. L. Dobrushin to give a useful, explicit formula for $|{\lambda }_2|$. The purpose of this note is to disseminate these known results more widely and to show how they imply, as a very special case, some recent theorems of Haveliwala and Kamvar about the second eigenvalue of the Google matrix.

Email address for author is [email protected] (submission handled by colleague)