If I have a diagonal matrix with rank-$1$ update $$D + u v^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 eigenvalue 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?
Best Answer
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.