# Rank-1 update eigenvalues

If I had a diagonal matrix with rank-1 update $$D + uv^T$$ what can I say about its eigenvalues?

I know from Two matrices that are not similar have (almost) same eigenvalues that every eigenvalue of D with multiplicity m>1 will occur in $$D + uv^T$$ at least m-1 times. I am wondering what can be said about the remaining eigenvalues, and in particular, how do they scale with u and/or v.

For example in the following mathematica code:

    dim = 50;
SeedRandom[1]

Diag = DiagonalMatrix[Flatten[RandomInteger[{0, 10}, {1, dim}]]];

u = ConstantArray[{1}, dim];
v = List /@ RandomReal[{0, 100}, {dim}];
vT = Transpose[v];
uvT = Transpose[u.vT];

Eigenvalues[Diag]
Round[Eigenvalues[Diag + uvT], 0.01]

(*{10, 9, 9, 8, 8, 7, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3,
3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0}*)

(*{2340.33, 9.85, 9., 8.79, 8., 7.75, 6.98, 6., 6., 5.85, 5., 5., 5.,
5., 5., 4.68, 4., 4., 4., 4., 4., 3.59, 3., 3., 3., 3., 3., 3., 2.4,
2., 2., 2., 1.55, 1., 1., 1., 1., 1., 1., 1., 1., 1., 0.3, 0., 0.,
0., 0., 0., 0., 0.}*)


one can clearly see that the ev with multiplicity m>1 occurred in the perturbed case again at least m-1 times while every other eigenvalue lifted only slightly. If I now chose v to be of higher magnitude:

    v = List /@ RandomReal[{10^9, 10^10}, {dim}];


for some reason the eigenvalues change only insignificantly:

    (*{10, 9, 9, 8, 8, 7, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3,
3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0}*)

(*{2.60337*10^11, 9.86, 9., 8.79, 8., 7.76, 6.97, 6., 6., 5.84, 5., 5.,
5., 5., 5., 4.67, 4., 4., 4., 4., 4., 3.59, 3., 3., 3., 3., 3., 3.,
2.4, 2., 2., 2., 1.56, 1., 1., 1., 1., 1., 1., 1., 1., 1., 0.31, 0.,
0., 0., 0., 0., 0., 0.}*)


except for the first eigenvalue that blows up. Is there a mathematical argument for why most of the eigenvalues change only so slightly even when choosing v to be so large?

As it follows from my other answer in your link, the eigenvalues of $$D+uv^T$$ are the zeros of $$\det(\lambda I-D-uv^T)=p(\lambda)-\sum_{i=1}^nu_iv_ip_i(\lambda)$$ where $$p(\lambda)=\det(\lambda I-D)=\prod_{i=1}^n(\lambda-d_i),\qquad p_i(\lambda)=\frac{p(\lambda)}{\lambda-d_i}=\prod_{j\ne i}^n(\lambda-d_j).$$ After factoring out all the common factors in $$p(\lambda)$$ and $$p_i(\lambda)$$ (that correspond to the multiple eigenvalues of $$D$$), we are left with the polynomials with distinct numbers $$d_i$$. The polynomials $$p_i$$ for multiple eigenvalues are also the same (if $$d_i=d_j$$ then $$p_i=p_j$$), so we can collect them in one term. As a result, it is sufficient to study the eigenvalues of $$D+uv^T$$ where all $$d_i$$ are distinct. I already mentioned in my other answer that if all $$u_i\ne 0$$ then the pair $$(D,u)$$ is controllable, and it is possible to find $$v$$ such that $$D+uv^T$$ have any predefined set of eigenvalues. Why is it not the case in your example? Because you try only positive vectors $$v$$. Let's see, we have $$D=\begin{bmatrix}d_1 &&&\\&d_2&&\\&&\ddots&\\&&&d_{11}\end{bmatrix}= \begin{bmatrix}10 &&&\\&9&&\\&&\ddots&\\&&&0\end{bmatrix},\qquad u=\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix}$$ and $$v$$ is any positive vector. Then the eigenvalues are the zeros of $$\chi(\lambda)=p(\lambda)-\sum_{i=1}^{11}v_ip_i(\lambda).$$ If we set $$\lambda=d_i$$ we get \begin{align} \chi(d_1)&=-v_1p_1(10)&&<0,\\ \chi(d_2)&=-v_2p_2(9)&&>0,\\ \chi(d_3)&=-v_3p_3(8)&&<0,\qquad \text{etc.} \end{align} It means that the characteristic polynomial changes the sign between each pair of the eigenvalues. Therefore, it must have a zero there, thus, there is a perturbed eigenvalue between any pair of the original eigenvalues: $$10$$ and $$9$$, $$9$$ and $$8$$ etc, that you see in your example.