# Eigenvalues of $A+\alpha uu^T$

Let $A = diag \left (\lambda_1, ..., \lambda_n \right ) \in \mathbb{R}^{n \times n}$, with $\lambda_1 < \lambda_2 < ... < \lambda_n$.
Let $u = \left (u_1, ..., u_n \right ) ^T \in \mathbb{R}^n$, with $u_i \neq 0 \ \ \forall i$.
How can be shown that:

1. For any $\alpha \in \mathbb{R}, \alpha \neq 0, \lambda_i$ is not an eigenvalue of $A+\alpha uu^T$.
2. The eigenvalues of $A+\alpha uu^T$ are the roots of the equation $f(\tau)=0$, where:
$\displaystyle f(\tau)=1+\alpha \sum_{i=1}^n{\frac {u_i^2}{\lambda_i-\tau}}$.
-

Suppose that $(A-\lambda_j I+\alpha\,uu^T)x=0$. We can write this as $(A-\lambda_j)x=-\alpha\,uu^Tx$. If we look at the $j^{\rm th}$ coordinate, the left-hand side is $0$, and the right-hand side is $$-\alpha(u^Tx) u_j,$$ so (using that all coordinates of $u$ are nonzero) $u^Tx=0$. But then the right-hand side is $0$ in all its coordinates. For any $k\ne j$, the corresponding coordinate on the left-hand side is $(\lambda_k-\lambda_j)x_k$, so $x_k=0$.

We have thus shown that $x=0$, i.e. the kernel of $(A-\lambda_j I+\alpha\,uu^T)$ is the trivial subspace, which says that $\lambda_j$ is not an eigenvalue of $A+\alpha uu^T$.

For part 2), one only needs to notice that $$\det(A-\tau\,I+\alpha\,uu^T)=(\lambda_1-\tau)\cdots(\lambda_n-\tau)\,\left(1+\alpha\,\sum_{j=1}^n\frac{u_j^2}{\lambda_j-\tau}\right)$$ and that by part 1) the factors $\lambda_j-\tau$ are all nonzero. Indeed, this equality follows from the fact that if $B$ is $n\times n$ invertible and $x,y\in\mathbb R^n$, then $$\det(B+xy^T)=(1+y^TB^{-1}x)\,\det B$$ (taking of course $B=A$, $x=y=\alpha^{1/2}\,u$).

-
Great job. Thanks so much Martin. –  user79230 May 6 '13 at 3:58
My pleasure. I had to search for the determinant identity at the end, which I didn't know about. Interesting. –  Martin Argerami May 6 '13 at 4:05

try using definition for prob a. try to find characteristic polynomial for b

-
Just a recommendation that it might be helpful to provide more details on this response to make what you are saying clearer. As currently written, it is very difficult to understand. Regards –  Amzoti May 5 '13 at 21:48

Hint: Let $$g(\tau):=\prod_i(\lambda_i-\tau)\,\cdot f(\tau)=\prod_i(\lambda_i-\tau)+\alpha\,\sum_i\,\left(u_i^2\cdot\prod_{j\ne i}(\lambda_j-\tau) \right)\,,$$ which is a polynomial of $\tau$ (of degree $n$). By (a big amount of) hypothesis, we have that $g(\lambda_i)\ne 0$, and if we prove that the roots of $g$ are exactly the eigenvalues of $A+\alpha\,uu^T$, we're ready. I would not be much surprised if $g$ were just its characteristic polynomial.

-