1
$\begingroup$

Let $M$ be a symmetric $n \times n$ matrix, let $v \in \mathbb{R}^n$. Then $M - vv^T$ is said to be a rank-1 modification of $M$ since $\text{rank}(vv^T) = 1$

Suppose I have a diagonal matrix: $$M = \text{diag}(v)$$ $v \in \mathbb{R}^n, \alpha \geq v_i \geq 0, \alpha \geq 0$

Clearly, $v_i$ are the eigenvalues of $M$.

What happens to the eigenvalues after a rank-1 modification? Is it possible to know the precise values of the eigenvalues in this case? Or is it possible to bound it?

$$M - vv^T = \text{diag}(v) - vv^T?$$

Is this a well known result? Any reference would help!

For example:

Let $z = \begin{bmatrix} 0.3 \\ 0.4 \end{bmatrix}$ Then $zz^T = \begin{bmatrix} 0.09 & 0.12 \\ 0.12 & 0.16 \end{bmatrix}$

So $\text{diag}(z) - zz^T = \begin{bmatrix} 0.21 & -0.12 \\ -0.12 & 0.24 \end{bmatrix}$

$\text{eigs}(\text{diag}(z) - zz^T) = \{ 0.3459, 0.1041\}$

Seems this answer might help? Maybe not Determinant of rank-one perturbations of (invertible) matrices

$\endgroup$
2
$\begingroup$

If you want to numerically calculate the new eigenvalues efficiently, that is the subject of section 5 of the following paper:

Golub, Gene H.
"Some modified matrix eigenvalue problems."
Siam Review 15.2 (1973): 318-334.

http://www.stat.uchicago.edu/~lekheng/courses/309f10/modified.pdf

In terms of general theoretical bounds, the Weyl inequalities imply that the perturbation of any given eigenvalue is at most $||v||$. I don't know if it is possible to say anything stronger than this without additional assumptions. Probably it would be useful if one could assume something about the degree of alignment or nonalignment of $v$ with respect to the coordinate axes.


As a (long) aside, if you don't really need the eigenvalues, but just need to apply the inverse of an updated system, you can do so efficiently with the Sherman-Morrison formula: $$(M + vv^T)^{-1} = M^{-1} - \frac{M^{-1}vv^TM^{-1}}{1 + v^T M^{-1} v}.$$

This is actually more powerful than it seems, due to the power of rational function approximations. A lot of times the reason people want compute an eigenvalue decomposition is because they need to apply functions of a matrix to a vector. For example, in computational statistics you may want to compute $(M+vv^T)^{1/2}x$, or in dynamical systems you may want to compute $\exp \left(M + vv^T\right) x$, or more generally you may want to compute $$f(M + vv^T)x$$ for some function $f$ (in all these cases $x$ is a vector). However, if you can efficiently apply the inverse of the shifted system: $$(M + \sigma I + vv^T)^{-1}x,$$ which you can using the Sherman-Morrison formula mentioned above, then you can efficiently apply general functions of the matrix using rational approximations or other techniques. If the scalar function $f(x)$ has rational approximation: $$f(z) \approx \frac{c_1}{z + \sigma_1} + \frac{c_2}{z + \sigma_2} + \dots + \frac{c_r}{z + \sigma_r},$$ then you can approximate the matrix function by: $$f(A)x \approx c_1(A + \sigma_1 I)^{-1}x + \dots + c_r(A + \sigma_r I)^{-1} x.$$ Generally one will need only a very small number of terms (e.g., $\# \text{ terms} = O(\log(\kappa))$, where $\kappa$ is the condition number of $M$) to get a very good approximation. See, for example, the following papers:

$\endgroup$

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.