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$.


This is a hard question, but a very nice survey of results on this subject is this paper of Andre Ran He primarily talks about real matrices, but I am sure the results carry over mutates mutandis


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.