Eigenvalue perturbation

In mathematics, an eigenvalue perturbation problem is that of finding the eigenvectors and eigenvalues of a system that is perturbed from one with known eigenvectors and eigenvalues. This is useful for studying how sensitive the original system's eigenvectors and eigenvalues are to changes in the system. This type of analysis was popularized by Lord Rayleigh, in his investigation of harmonic vibrations of a string perturbed by small inhomogeneities.[1]

The derivations in this article are essentially self-contained and can be found in many texts on numerical linear algebra[2] or numerical functional analysis.

Example

Suppose we have solutions to the generalized eigenvalue problem,

${\displaystyle \mathbf {K} _{0}\mathbf {x} _{0i}=\lambda _{0i}\mathbf {M} _{0}\mathbf {x} _{0i}.\qquad (0)}$

where ${\displaystyle \mathbf {K} _{0}}$ and ${\displaystyle \mathbf {M} _{0}}$ are matrices. That is, we know the eigenvalues λ_0i and eigenvectors x_0i for i = 1, ..., N. It is also required that the eigenvalues be distinct. Now suppose we want to change the matrices by a small amount. That is, we want to find the eigenvalues and eigenvectors of

${\displaystyle \mathbf {K} \mathbf {x} _{i}=\lambda _{i}\mathbf {M} \mathbf {x} _{i}\qquad (1)}$

where

${\displaystyle {\begin{aligned}\mathbf {K} &=\mathbf {K} _{0}+\delta \mathbf {K} \\\mathbf {M} &=\mathbf {M} _{0}+\delta \mathbf {M} \end{aligned}}}$

with the perturbations ${\displaystyle \delta \mathbf {K} }$ and ${\displaystyle \delta \mathbf {M} }$ much smaller than ${\displaystyle \mathbf {K} }$ and ${\displaystyle \mathbf {M} }$ respectively. Then we expect the new eigenvalues and eigenvectors to be similar to the original, plus small perturbations:

${\displaystyle {\begin{aligned}\lambda _{i}&=\lambda _{0i}+\delta \lambda _{i}\\\mathbf {x} _{i}&=\mathbf {x} _{0i}+\delta \mathbf {x} _{i}\end{aligned}}}$

Steps

We assume that the matrices are symmetric and positive definite, and assume we have scaled the eigenvectors such that

${\displaystyle \mathbf {x} _{0j}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}=\delta _{ij}\qquad (2)}$

where δ_ij is the Kronecker delta. Now we want to solve the equation

${\displaystyle \mathbf {K} \mathbf {x} _{i}=\lambda _{i}\mathbf {M} \mathbf {x} _{i}.}$

Substituting, we get

${\displaystyle (\mathbf {K} _{0}+\delta \mathbf {K} )(\mathbf {x} _{0i}+\delta \mathbf {x} _{i})=\left(\lambda _{0i}+\delta \lambda _{i}\right)\left(\mathbf {M} _{0}+\delta \mathbf {M} \right)\left(\mathbf {x} _{0i}+\delta \mathbf {x} _{i}\right),}$

which expands to

${\displaystyle {\begin{aligned}\mathbf {K} _{0}\mathbf {x} _{0i}&+\delta \mathbf {K} \mathbf {x} _{0i}+\mathbf {K} _{0}\delta \mathbf {x} _{i}+\delta \mathbf {K} \delta \mathbf {x} _{i}=\\[6pt]&=\lambda _{0i}\mathbf {M} _{0}\mathbf {x} _{0i}+\lambda _{0i}\mathbf {M} _{0}\delta \mathbf {x} _{i}+\lambda _{0i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}+\lambda _{0i}\delta \mathbf {M} \delta \mathbf {x} _{i}+\delta \lambda _{i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\delta \mathbf {x} _{i}+\delta \lambda _{i}\delta \mathbf {M} \delta \mathbf {x} _{i}.\end{aligned}}}$

Canceling from (0) (${\displaystyle \mathbf {K} _{0}\mathbf {x} _{0i}=\lambda _{0i}\mathbf {M} _{0}\mathbf {x} _{0i}}$) leaves

${\displaystyle {\begin{aligned}\delta \mathbf {K} \mathbf {x} _{0i}+\mathbf {K} _{0}\delta \mathbf {x} _{i}+\delta \mathbf {K} \delta \mathbf {x} _{i}=\lambda _{0i}\mathbf {M} _{0}\delta \mathbf {x} _{i}+\lambda _{0i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}+\lambda _{0i}\delta \mathbf {M} \delta \mathbf {x} _{i}+\delta \lambda _{i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\delta \mathbf {x} _{i}+\delta \lambda _{i}\delta \mathbf {M} \delta \mathbf {x} _{i}.\end{aligned}}}$

Removing the higher-order terms, this simplifies to

${\displaystyle \mathbf {K} _{0}\delta \mathbf {x} _{i}+\delta \mathbf {K} \mathbf {x} _{0i}=\lambda _{0i}\mathbf {M} _{0}\delta \mathbf {x} _{i}+\lambda _{0i}\delta \mathbf {M} \mathrm {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}.\qquad (3)}$

When the matrix is symmetric, the unperturbed eigenvectors are orthogonal and so we use them as a basis for the perturbed eigenvectors. That is, we want to construct

${\displaystyle \delta \mathbf {x} _{i}=\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {x} _{0j}\qquad (4)}$

where the ε_ij are small constants that are to be determined. Substituting (4) into (3) and rearranging gives

${\displaystyle {\begin{aligned}\mathbf {K} _{0}\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {x} _{0j}+\delta \mathbf {K} \mathbf {x} _{0i}&=\lambda _{0i}\mathbf {M} _{0}\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {x} _{0j}+\lambda _{0i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}&&(5)\\\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {K} _{0}\mathbf {x} _{0j}+\delta \mathbf {K} \mathbf {x} _{0i}&=\lambda _{0i}\mathbf {M} _{0}\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {x} _{0j}+\lambda _{0i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}&&{\text{Applying }}\mathbf {K} _{0}{\text{ to the sum}}\\\sum _{j=1}^{N}\varepsilon _{ij}\lambda _{0j}\mathbf {M} _{0}\mathbf {x} _{0j}+\delta \mathbf {K} \mathbf {x} _{0i}&=\lambda _{0i}\mathbf {M} _{0}\sum _{j=1}^{N}\varepsilon _{ij}\mathbf {x} _{0j}+\lambda _{0i}\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {M} _{0}\mathbf {x} _{0i}&&{\text{Using Eq. }}(1)\end{aligned}}}$

Because the eigenvectors are M₀-orthogonal when M₀ is positive definite, we can remove the summations by left-multiplying by ${\displaystyle \mathbf {x} _{0i}^{\top }}$:

${\displaystyle \mathbf {x} _{0i}^{\top }\varepsilon _{ii}\lambda _{0i}\mathbf {M} _{0}\mathbf {x} _{0i}+\mathbf {x} _{0i}^{\top }\delta \mathbf {K} \mathbf {x} _{0i}=\lambda _{0i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\varepsilon _{ii}\mathbf {x} _{0i}+\lambda _{0i}\mathbf {x} _{0i}^{\top }\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}.}$

By use of equation (1) again:

${\displaystyle \mathbf {x} _{0i}^{\top }\mathbf {K} _{0}\varepsilon _{ii}\mathbf {x} _{0i}+\mathbf {x} _{0i}^{\top }\delta \mathbf {K} \mathbf {x} _{0i}=\lambda _{0i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\varepsilon _{ii}\mathbf {x} _{0i}+\lambda _{0i}\mathbf {x} _{0i}^{\top }\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}.\qquad (6)}$

The two terms containing ε_ii are equal because left-multiplying (1) by ${\displaystyle \mathbf {x} _{0i}^{\top }}$ gives

${\displaystyle \mathbf {x} _{0i}^{\top }\mathbf {K} _{0}\mathbf {x} _{0i}=\lambda _{0i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}.}$

Canceling those terms in (6) leaves

${\displaystyle \mathbf {x} _{0i}^{\top }\delta \mathbf {K} \mathbf {x} _{0i}=\lambda _{0i}\mathbf {x} _{0i}^{\top }\delta \mathbf {M} \mathbf {x} _{0i}+\delta \lambda _{i}\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}.}$

Rearranging gives

${\displaystyle \delta \lambda _{i}={\frac {\mathbf {x} _{0i}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}}{\mathbf {x} _{0i}^{\top }\mathbf {M} _{0}\mathbf {x} _{0i}}}}$

But by (2), this denominator is equal to 1. Thus

${\displaystyle \delta \lambda _{i}=\mathbf {x} _{0i}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}.}$

Then, by left-multiplying equation (5) by ${\displaystyle \mathbf {x} _{0k}^{\top }}$:

${\displaystyle \varepsilon _{ik}={\frac {\mathbf {x} _{0k}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}}{\lambda _{0i}-\lambda _{0k}}},\qquad i\neq k.}$

Or by changing the name of the indices:

${\displaystyle \varepsilon _{ij}={\frac {\mathbf {x} _{0j}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}}{\lambda _{0i}-\lambda _{0j}}},\qquad i\neq j.}$

To find ε_ii, use the fact that:

${\displaystyle \mathbf {x} _{i}^{\top }\mathbf {M} \mathbf {x} _{i}=1}$

implies:

${\displaystyle \varepsilon _{ii}=-{\tfrac {1}{2}}\mathbf {x} _{0i}^{\top }\delta \mathbf {M} \mathbf {x} _{0i}.}$

Summary

${\displaystyle {\begin{aligned}\lambda _{i}&=\lambda _{0i}+\mathbf {x} _{0i}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}\\\mathbf {x} _{i}&=\mathbf {x} _{0i}\left(1-{\tfrac {1}{2}}\mathbf {x} _{0i}^{\top }\delta \mathbf {M} \mathbf {x} _{0i}\right)+\sum _{j=1 \atop j\neq i}^{N}{\frac {\mathbf {x} _{0j}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}}{\lambda _{0i}-\lambda _{0j}}}\mathbf {x} _{0j}\end{aligned}}}$

for infinitesimal ${\displaystyle \delta \mathbf {K} }$ and ${\displaystyle \delta \mathbf {M} }$ (the high order terms in (3) being negligible)

Results

This means it is possible to efficiently do a sensitivity analysis on λ_i as a function of changes in the entries of the matrices. (Recall that the matrices are symmetric and so changing K_kℓ will also change K_ℓk, hence the (2 − δ_kℓ) term.)

${\displaystyle {\begin{aligned}{\frac {\partial \lambda _{i}}{\partial \mathbf {K} _{(k\ell )}}}&={\frac {\partial }{\partial \mathbf {K} _{(k\ell )}}}\left(\lambda _{0i}+\mathbf {x} _{0i}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}\right)=x_{0i(k)}x_{0i(\ell )}\left(2-\delta _{k\ell }\right)\\{\frac {\partial \lambda _{i}}{\partial \mathbf {M} _{(k\ell )}}}&={\frac {\partial }{\partial \mathbf {M} _{(k\ell )}}}\left(\lambda _{0i}+\mathbf {x} _{0i}^{\top }\left(\delta \mathbf {K} -\lambda _{0i}\delta \mathbf {M} \right)\mathbf {x} _{0i}\right)=\lambda _{i}x_{0i(k)}x_{0i(\ell )}\left(2-\delta _{k\ell }\right).\end{aligned}}}$

Similarly

${\displaystyle {\begin{aligned}{\frac {\partial \mathbf {x} _{i}}{\partial \mathbf {K} _{(k\ell )}}}&=\sum _{j=1 \atop j\neq i}^{N}{\frac {x_{0j(k)}x_{0i(\ell )}\left(2-\delta _{k\ell }\right)}{\lambda _{0i}-\lambda _{0j}}}\mathbf {x} _{0j}\\{\frac {\partial \mathbf {x} _{i}}{\partial \mathbf {M} _{(k\ell )}}}&=-\mathbf {x} _{0i}{\frac {x_{0i(k)}x_{0i(\ell )}}{2}}(2-\delta _{k\ell })-\sum _{j=1 \atop j\neq i}^{N}{\frac {\lambda _{0i}x_{0j(k)}x_{0i(\ell )}}{\lambda _{0i}-\lambda _{0j}}}\mathbf {x} _{0j}\left(2-\delta _{k\ell }\right).\end{aligned}}}$

Existence of eigenvectors

Note that in the above example we assumed that both the unperturbed and the perturbed systems involved symmetric matrices, which guaranteed the existence of ${\displaystyle N}$ linearly independent eigenvectors. An eigenvalue problem involving non-symmetric matrices is not guaranteed to have ${\displaystyle N}$ linearly independent eigenvectors, though a sufficient condition is that ${\displaystyle \mathbf {K} }$ and ${\displaystyle \mathbf {M} }$ be simultaneously diagonalizable.

See also

• Perturbation theory (quantum mechanics)
• Bauer–Fike theorem

References

1. Rayleigh, J. W. S. (1894). Theory of Sound. I (2nd ed.). London: Macmillan. pp. 115–118. ISBN 1-152-06023-6.
2. Trefethen, Lloyd N. (1997). Numerical Linear Algebra. SIAM (Philadelphia, PA). p. 258. ISBN 0-89871-361-7.

Further reading

Books

• Ren-Cang Li (2014). "Matrix Perturbation Theory". In Hogben, Leslie (ed.). Handbook of linear algebra (Second ed.). ISBN 978-1466507289.
• Rellich, F., & Berkowitz, J. (1969). Perturbation theory of eigenvalue problems. CRC Press.
• Bhatia, R. (1987). Perturbation bounds for matrix eigenvalues. SIAM.

Journal papers

• Simon, B. (1982). Large orders and summability of eigenvalue perturbation theory: a mathematical overview. International Journal of Quantum Chemistry, 21(1), 3-25.
• Crandall, M. G., & Rabinowitz, P. H. (1973). Bifurcation, perturbation of simple eigenvalues, and linearized stability. Archive for Rational Mechanics and Analysis, 52(2), 161-180.
• Stewart, G. W. (1973). Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM review, 15(4), 727-764.
• Löwdin, P. O. (1962). Studies in perturbation theory. IV. Solution of eigenvalue problem by projection operator formalism. Journal of Mathematical Physics, 3(5), 969-982.