3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer! Thanks! $\endgroup$ – xabdax Aug 16 at 23:20

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.