Incremental algorithm for matrix eigenvalues 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
 A: 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.
A: 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.
