Notes on the Second Eigenvalue of the Google Matrix

If $A$ is an $n\times n$ matrix whose $n$ eigenvalues are ordered in terms of decreasing modules, $\mathrm{\mid }{\lambda }_1\mathrm{\mid }\ge \mathrm{\mid }{\lambda }_2\mathrm{\mid }\ge \mathrm{.}\mathrm{.}\mathrm{.}\mathrm{\mid }{\lambda }_n\mathrm{\mid }$, it is often of interest to estimate $\frac{\mathrm{\mid }{\lambda }_2\mathrm{\mid }}{\mathrm{\mid }{\lambda }_1\mathrm{\mid }}$. 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 $\mathrm{\mid }{\lambda }_2\mathrm{\mid }$. 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.