How does eigenvalues and eigenvectors change if the original matrix changes slightly? Hi,
We have a square symmetric matrix M with all the elements 0 or 1, and the eigenvalues and vectors of M are computed.
Now if we change one arbitrary element of M (from 0 to 1 or 1 to 0), what will happen to eigenvalues (and eigenvectors)? Does there exist a clear relation or not?
Thank you for your help
Hoda
 A: Terry Tao had a blog post on a related topic:  http://terrytao.wordpress.com/2008/10/28/when-are-eigenvalues-stable/
A: Let's look at an example. If $M=\pmatrix{0&1\cr1&0\cr}$ then its eigenstuff is (1, 1) belonging to 1, and (1, -1) belonging to -1. Now if you make the "slight" change to $\pmatrix{0&1\cr0&0\cr}$, you get a repeated eigenvalue 0 with a one-dimensional eigenspace generated by (1, 0). So it seems that changing one entry can change everything about the eigendata. My guess is that there is, in general, no clear relation. 
A: As Matthew Daws pointed out with his link above, Terry Tao answers your specific question.  However, you might be interested in the larger framework of random matrix theory, which is includes the study of eigenvalue distributions of large random matrices.  This subject makes precise Douglas Zare's comment:I would guess that there will be some properties of the eigenvalues which hold for at least 98% of the alterations of a large matrices.
By putting special probability distributions on the space of $N \times N$ matrices, one can do everything explicitly using orthogonal polynomials, Riemann-Hilbert theory, and a whole slew of other exact tools.  For example, the Gaussian Unitary Ensemble (GUE) is the class of complex $N \times N$ matrices with i.i.d. Gaussian entries constrained so that the matrix is Hermitian.  Here, the distribution of largest eigenvalue follows the Tracy-Widom law, the cumulative distribution of eigenvalues is Wigner's semicircle law, and one can calculate explicitly pretty much any other quantity of interest.
Just as the central limit theorem holds for a much wider class of i.i.d. random variables than just Gaussians, much current work in the analysis of random matrix theory is to show that these properties are universal, and don't rely on the specific Gaussian structure.
A: Hello,
I cannot see a clear relation. Let's look at some easy but very instructive classes of matrices. Let $A$ denote the matrix with the properties you specified:


*

*Let $A$ be an upper triangular matrix. All eigenvalues are 1 or 0. If we change an entry on the diagonal the algebraic multiplicity of the eigenvalues changes by one (one goes up and one goes down). But if we change any other entry the multiplicity of the eigenvalues do not change at all.


2.Let $$A=\left(
\begin{array}{rrr}
1 & 1 & 0 \\\ 
1 & 1 & 0 \\\
0 & 0 & 1 
\end{array}
\right)$$
The you get three distinct eigenvalues, two of them not even real. But when you change one of the entries (1,2) or (2,1) then you get an upper/lower triangluar matrix having only 1 as eigenvalue.
It is certainly true that the eigenvalues depend continously on the entries of the matrix. The problem is that a change of 0<->1 is really big. I am quite sure that there is no clear answer if you don't impose further restrictions on A.
