3
$\begingroup$

I try to solve the following problem:
Given a stream of symmetric matrices $A_0, A_1, ...,A_n$ such that $A_i$ is different from $A_{i-1}$ only in one place, I want to compute the eigenvalues of $A_i$.
Since the matrices are very large, computing the eigenvalues from scratch isn't efficient (and since the matrices are different only in one place, that's also not very smart..), and I try to find how to calculate the eigenvalues of $A_i$ using the eigenvalues of $A_{i-1}$.

Any help will be welcomed,

Thanks

$\endgroup$
3
  • $\begingroup$ Perhaps you could try finding a zero of the determinant using Newton's method - this presumes they are distinct, of course. $\endgroup$
    – copper.hat
    Apr 23 '15 at 16:14
  • $\begingroup$ So if the matrices are symmetric and change only in one place, that means you change only the diagonal? $\endgroup$
    – cfh
    Apr 23 '15 at 16:32
  • $\begingroup$ ieeexplore.ieee.org/document/1529967 Only computes the eigenvector corresponding to the dominant eigenvalue though. $\endgroup$
    – Yfiua
    Jul 31 '18 at 14:20
0
$\begingroup$

The problem of finding eigenvalues of a matrix (especially for large non-sparse matrices) is highly unstable; for symmetric matrices the problem is a bit better, but even there the situation is far from ideal.

You have continuous dependence of eigenvalues on the coefficients of the matrix. Unfortunately, in general case the estimations on this dependence are impractical (to put it mildly). You'll need some additional hypothesis on the specter of the matrix (cf. specter dichotomy problems) and on the changes of the matrix on each step.

One of options would be to use some sort of iterative algorithm for finding the eigenvalues of the new matrix, put initial approximation as eigenvalues of the previous matrix, and hope that the eigenvalues didn't escape too far.

$\endgroup$
2
  • 2
    $\begingroup$ Isn't it true that each eigenvalue cannot change more than the change in a single entry of a matrix? I think this follows from Weyl's inequality. If so, it seems like a usable bound given that something about the changes in the single matrix entries is known. $\endgroup$
    – cfh
    Apr 23 '15 at 16:37
  • $\begingroup$ @cfh You are right, and your remark is important: if the initial matrix is symmetric and the perturbation is symmetric, then we have nice estimations on the specter of perturbed matrix in terms of specter of the initial matrix and the spectre of the perturbation matrix. However, this is a)only an estimation; b) here we are lucky, because the specter of the perturbation is easy to find (in general case we are not that lucky). The problem of finding exact eigenvalues still holds. $\endgroup$ Apr 23 '15 at 16:46
0
$\begingroup$

Building on another answer, it's not just the eigenvalues that change when you change one entry -- you also change the eigenvectors. And the way they change when you change a single entry will depend on the eigenvalues and the eigenvectors. You could start with the old eigenvalue and eigenvector pair and optimize to find the modified eigenvector and eigenvalue pair in the next matrix, hoping that they didn't change too much so your optimization will quickly converge. But that seems almost guaranteed to require that you are changing your single matrix entry by a small amount compared to the eigenvalues.

$\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.