# Eigenvalues of the Google Matrix

Let $c \in \mathbb{C}$ and $x, v \in \mathbb{C}^n$ satisfy $v^*x= 1$ (where the start means conjugate transpose). Given that a square ($n\times n$) matrix $A$ with complex entries has eigenvalues $\lambda_1, \lambda_2...\lambda_n$ with associated eigenvectors $x_1 = x, x_2...x_n$, is there a way to find the eigenvalues of the "Google" matrix $cA + (1-c)\lambda_1 xv^*?$.

I can find that $\lambda_1$ is an eigenvalue by direct computation (just multiply by the vector $x$). It seems that $c\lambda_2, c\lambda_3..c\lambda_n$ are the other eigenvalues, but that is just a hypothesis.

I am thinking that it somehow relates to a theorem of Brauer (link: An Article)

Let $B = c A + (1-c) \lambda_1 x v^*$, $C = cA - \mu I$ and $u = (1-c) \lambda_1 x$.. Then $B - \mu I = C + u v^*$. Now $C x = c A x - \mu x = (c \lambda_1 - \mu) x$ so if $\mu \ne c \lambda_1$, $C^{-1} x = (c \lambda_1 - \mu)^{-1} x$ and $$v^* C^{-1} u = (c \lambda_1 - \mu)^{-1} v^* u = (c \lambda_1 - \mu)^{-1} (1-c) \lambda_1 = -1 + \dfrac{\lambda_1 - \mu}{c \lambda_1 - \mu}$$ The eigenvalues of $C$ are $c \lambda_i - \mu$. By the Sherman-Morrison formula, if $C$ is invertible (i.e. $\mu$ is not $c \lambda_i$ for any $i$) and $1 + v^* C^{-1} u \ne 0$, i.e. $\mu \ne \lambda_1$, then $B - \mu I$ is invertible and
$$(B - \mu I)^{-1} = (C + u v^*)^{-1} = C^{-1} - \dfrac{C^{-1} u v^* C^{-1}}{1 + v^* C^{-1} u} = C^{-1} - \dfrac{c \lambda_1 - \mu}{\lambda_1 - \mu} C^{-1} u v^* C^{-1}$$
In particular the only possible eigenvalues of $B$ (the values $\mu$ for which $B - \mu I$ is not invertible) are $\lambda_1$ (which you already know is an eigenvalue) and $c \lambda_i$, $i=1 \ldots n$.
Now $\text{Tr}(xv^*) = \text{Tr}(v^*x) = 1$ so $\text{Tr}(B) = c \text{Tr}(A) + (1-c) \lambda_1 = \lambda_1 + \sum_{i=2}^n c \lambda_i$. Since the trace is the sum of the eigenvalues, the one of $c \lambda_i$, $i=1\ldots n$ that is not an eigenvalue of $B$ is $c \lambda_1$. So the eigenvalues are $\lambda_1, c \lambda_2, \ldots, c \lambda_n$.