@techreport{ilprints597,
          number = {2003-36},
           month = {June},
          author = {Sepandar Kamvar and Taher Haveliwala},
           title = {The Condition Number of the PageRank Problem},
            type = {Technical Report},
       publisher = {Stanford InfoLab},
     institution = {Stanford InfoLab},
            year = {2003},
        keywords = {pagerank},
             url = {http://ilpubs.stanford.edu:8090/597/},
        abstract = {We determine analytically the condition number of the PageRank problem. Specifically, we prove the following statement: "Let $P$ be an $n \times n$ row-stochastic matrix whose diagonal elements $P_{ii}=0$.  Let $c$ be a real number such that $0 \leq c < 1$.  Let $E$ be the $n \times n$  rank-one row-stochastic matrix $E=\vec{e}\vec{v}^T$, where $\vec{e}$ is the n-vector  whose elements are all $e_i=1$,  and $\vec{v}$ is an n-vector that represents a probability  distribution.  Define the matrix $A=[cP + (1-c)E]^T$. The problem $A\vec{x}=\vec{x}$ has condition number $\kappa=(1+c)/(1-c)$."  This statement has implications for the accuracy to which PageRank can be  computed, currently and as the web scales.  Furthermore, it provides a simple proof that, for values of $c$ that are used by Google, small changes in  the link structure of the web do not cause large changes in the PageRanks of  pages of the web.}
}