# Rank-one update of eigenvalues

Let $$\lambda_1,\dots,\lambda_n$$ be the eigenvalues of the square and symmetric $$n\times n$$ real matrix $$A$$. Consider a rank-one perturbation $$B=A+uu^T$$, where $$u$$ is a real $$n$$-vector.

Is there an analytical expression for the eigenvalues of $$B$$, exploiting the known eigenvalues of $$A$$? I'm thinking something similar to the Sherman-Woodbury formula for the update of the inverse could work, but I have not succeeded.

I found some related results: https://en.wikipedia.org/wiki/Bunch%E2%80%93Nielsen%E2%80%93Sorensen_formula, and also https://doi.org/10.1137%2FS089547989223924X. But both seem to require that $$u$$ is an eigenvector of $$A$$. Here I am considering a more general statement, where $$u$$ need not be an eigenvector of $$A$$>

• If $\lambda_1,\ldots,\lambda_n$ are the eigenvalues of $A$, then I think you can say without loss of generality that the eigenvalues of $B$ are $\lambda_1,\lambda_2,\ldots,\lambda_{n-1}$ and $\lambda_n+u^\top u$. – StubbornAtom Dec 26 '18 at 15:01
• This is not true. Suppose $A = \lambda_1 uu^T + \lambda_2 vv^T$ with $\lambda_1 > \lambda_2$. Then then $B = A + uu^T = (\lambda_1 + 1) uu^T + \lambda_2 vv^T$ – tch Dec 26 '18 at 16:48

This isn't a complete answer, but maybe can be a starting point.

A symmetric matrix has eigen-decomposition $$A = U\Lambda U^T = \sum_i \lambda_i u_iu_i^T$$.

Essentially we can view this as the stretching of a sphere along the directions $$u_i$$. To compute $$Ax$$ we can compute the projection of $$x$$ is on each of the $$u_i$$, scale these projections by $$\lambda_i$$, and add them back together.

Now, when we compute $$Bx = Ax + uu^Tx$$ we additionally compute the projection of $$x$$ onto $$u$$ and add this in with the previous projections. If $$u$$ is in the direction of one of the $$u_i$$ that means that direction alone will be scaled by an additional amount. More precisely, if $$u = c u_i$$ for some $$j$$, then $$uu^T = c^2 u_iu_i^T$$ so $$B = A+uu^T = (\lambda_j + c^2)u_iu_i^T + \sum_{i\neq j} \lambda_i u_i u_i^T$$ That is, the eigen value in the direction $$u_i$$ changes by $$c^2$$.

Now let's consider what happens if $$u$$ is in the span of $$u_i$$ and $$u_j$$. First, note that the action of $$A$$ on everything outside of this span is the same as that of $$B$$. So none of the eigenvalues in the directions other than $$u_i$$ or $$u_j$$ will change. More generally, only the eigenvectors who are not orthogonal to $$u$$ will change.

Consider $$u = c_1u_1 + c_2u_2$$. Then $$uu^T = c_1^2 u_1u_1^T + c_2^2u_2u_2^T + c_1c_2 u_1u_2^T + c_1c_2u_2u_1^T$$. So now we see that while the update does contribute to the directions $$u_1$$ and $$u_2$$, it also "skews" the original image.

If we viewed the image in this plane as an ellipse, we now get a new ellipse. I'm guessing there is a way to write down the new axes of this ellipse which is the 2d version of your question.

Unfortunately, I'm not exactly sure how to do this.