7
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Is the altered matrix intended to be symmetric? $\endgroup$
    – Chris Godsil
    Commented Apr 6, 2010 at 12:29
  • $\begingroup$ A quick answer from nonnegative matrix theory. If you change one arbitrary element from $0$ to $1$, the spectral radius grows, and ....decreases. $\endgroup$
    – Sunni
    Commented Apr 6, 2010 at 13:46
  • 2
    $\begingroup$ Small-dimensional cases show that some properties of the matrix can change dramatically. However, in the 2x2 case, you are changing 1/4 of the entries, and in the 3x3 case, 1/9 of the entries, and any example of a matrix which is badly behaved makes up a significant percentage of the space of all symmetric 0-1 matrices. Is it really plausible that there is nothing that can be said if you change 1 out of 10,000 entries of a 100x100 matrix? 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. $\endgroup$
    – Douglas Zare
    Commented Apr 6, 2010 at 14:03
  • $\begingroup$ Eigenvalues change continuously, but normalized eigenvectors don't, as you can see by continuously perturbing I. However, I would be surprised if there were not some correspondence most of the time. $\endgroup$
    – Douglas Zare
    Commented Apr 6, 2010 at 14:09
  • 1
    $\begingroup$ You are probably right. Larger matrices should behave better. But it doesn't only depend on the matrix. It also depends on the entry you want to change as the examples in the two answers show. It is very easy to construct similar examples with large matrices. So the problem is to decidee whether we are in the "98%" of the cases or in the 2%. How can the "good" matrices and/or good entries be determined? $\endgroup$
    – Tile
    Commented Apr 6, 2010 at 14:47

4 Answers 4

Reset to default
4
$\begingroup$

Terry Tao had a blog post on a related topic: http://terrytao.wordpress.com/2008/10/28/when-are-eigenvalues-stable/

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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:

  1. 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .