Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A bit unsure if my use/mention of proprietary software might be inappropriate or even frowned upon here. If this is the case, or if this kind of experimental question is not welcome, please let me know and I'll remove it quickly.

I was experimenting on the distribution of eigenvalues of random matrices via the following Mathematica code

dim = 301; decomplex = {z_Complex -> {Re[z], Im[z]}, A_Real -> {A, 0}}; b = Eigenvalues[ SparseArray[{i_, i_} -> 1, {dim, dim}] + Table[RandomReal[{-.9, 1.}], {i, 1, dim}, {j, 1, dim}]] /. decomplex; ListPlot[b, PlotStyle -> PointSize[0.015], AspectRatio -> Automatic]

This simply draws (or should draw) a picture of the complex eigenvalues of a 301 x 301 matrix, with entries uniformly distributed in the real interval [-0.9, 1]. If you try the code you will notice a disk of random eigenvalues, which is expected, plus a single positive eigenvalue at some distance of the disk. Decreasing the lower bound on the entries to -1 makes this phenomenon disappear, while increasing the lower bound makes it more evident.

Question: is this an artifact, a real phenomenon, or maybe even a well known and simple to explain phenomenon?

share|improve this question
3  
Would it be possible to link to a copy of the picture that this code generates? I don't think it's inappropriate for you to use Mathematica -- but I don't have Mathematica, so I can't run your code for myself. –  Michael Lugo Jul 3 '10 at 11:45
    
I like the style of your tentative asking but I think it is absolutely valid to use one of the market leaders in math software and ask questions about it here. –  vonjd Jul 3 '10 at 16:57
    
Sorry for not providing pictures -- was a bit afraid of breaking some rule I guess –  Piero D'Ancona Jul 3 '10 at 18:22

4 Answers 4

up vote 15 down vote accepted

The distribution of the bulk of the spectrum is an example of the circular law. For the model you selected (where each entry is uniformly chosen at random from an interval), the law was first proven by Bai (at least in the case where the entries are normalised to have mean zero), building upon previous work of Girko; the non-central case (non-zero mean) was recently established by Chafai.

The non-central case is a rank one perturbation of the central case (by the matrix whose entries are all equal to the mean) and should therefore cause one exceptional eigenvalue.
(In the central case it can be shown that the spectral radius is close to the radius of the disk, so there are basically no exceptional eigenvalues.) If the mean of each entry is $\mu$, then the rank one perturbation has an eigenvalue at $\mu n$, so one expects the exceptional eigenvalue to linger near this number. In your case, $\mu = 0.05$ and $n = 301$, so the exceptional eigenvalue should linger near $15.05$.

There is a paper of Silverstein which makes the above heuristics precise; see also the earlier work of Andrew.

There is quite a bit of recent literature on the circular law, see for instance this survey by Van Vu and myself, or my lecture notes on this topic.

share|improve this answer
    
So this is an actual phenomemon. It looks like there is a threshold: if the rank one perturbation is small, no exceptional eigenvalue; if the perturbation is large, alwas an e.e.; when the perturbation is close to the threshold, the phenomenon seems unstable (maybe just numerically so). I'd better read the papers, thank you for the pointers –  Piero D'Ancona Jul 3 '10 at 18:26
    
Piero, don't forget to accept this answer if you think this answers your question! –  Qiaochu Yuan Jul 3 '10 at 19:08

It looks like Joseph O'Rourke has beaten me, but I've generated a bit more data than he has:

Let $l$ be the lower bound so that the non-diagonal entries are uniformly distributed between $l$ and 1 and the diagonal entries are distributed between $l+1$ and 2. Note that Piero's original characterization of his code was inaccurate, but I just used his code to generate the figures below.

Here is a grid of eigenvalues of such $N$ by $N$ matrices with $l=-.9$ (plots are labeled by $N$)

-.9 plot

Here's the picture with $l=-.87$

-.87 plot

Here's the picture with $l=-.93$

-.93 plot

And here's a picture of the absolute value of the largest eigenvalue of the matrix as a function of $N$ (now the label is $l$)

plot of largest eigenvalues

Edit based on Helge's comment: Here's a picture of $\max_{1\leq j \leq N} \sum_{n=1}^{N} u_j^N(n)$ as a function of $N$ (the $u_j^N$ are normalized eigenvectors) with $l=-0.9$

plot of largest sum

And here's a picture of the further normalized version $\max_{1\leq j \leq N} \frac{1}{\sqrt{N}}\sum_{n=1}^{N} u_j^N(n)$

plot of largest sum normalized

share|improve this answer
1  
(These plots were made in response to Helge's fine answer) –  j.c. Jul 3 '10 at 13:56
1  
Do you mind also computing : $\max_{1\leq j \leq N} \sum_{n=1}^{N} u_j^N(n)$. Here $u_j^N$ denotes the $j$-th eigenvector of the $N \times N$ matrix. I would expect this to be $\frac{1}{2}$ based on my answer and your plots ... If this turns out to be true, one should ask oneself if this is known / proven? –  Helge Jul 3 '10 at 14:09
    
Have you ever seen the structure of zeros of polynomials related to rational solutions of the Painlev\'e differential equations? Their structure is much more regular (and plots are nicer :-) ) but nothing is proved. –  Wadim Zudilin Jul 3 '10 at 14:45
    
@jc: Thanks. @Wadim: There are plenty of tools and recent work for random matrices. Just look at the not so few papers by Erdoes, Schlein, Tau, Vu, Yau and others.... –  Helge Jul 3 '10 at 15:04
    
Actually, I think I asked for the wrong computation :-( The interesting thing would be the value for the matrix entries distributed in $[-1,1]$ and not $[\ell, 1]$ for some $\ell \in (-1,0)$. The reason for this is once one has an eigenvector with $\sum_{n=1}^{N} u(n)$ perturbation theory tells us that this gets amplified. –  Helge Jul 3 '10 at 15:30

Here is the output from Piero's posted code:

alt text

share|improve this answer

Why is your dimension 301? Does this phenomenon appear for dimension 300? Which seems like a more natural number to try this computation at.

Now as simple thought, about rescaling your matrix. If $A$ is matrix, whose entries are uniformly distributed in $[a,b]$ then $\lambda A$ is a matrix, whose entries are uniformly distributed in $[\lambda a , \lambda b]$. Define $$ B = \begin{pmatrix} 1 & \dots & 1 \\\ \vdots & \ddots & \vdots \\\ 1 & \dots & 1 \end{pmatrix}, $$ the matrix containing all ones. Then the entries of $A + \mu B$ have distribution $[a + \mu, b + \mu]$. Since, you know everything about $B$, that is it has the eigenvalue $$ v =\begin{pmatrix} 1 \\\ \vdots \\\ 1 \end{pmatrix} $$ to the eigenvalue $n$ (if $B$ is a $n\times n$ matrix). You see that you expect the eigenvalues $\lambda_j$ to the eigenvector $u_j$ of $A$ to be moved to $$ \lambda_j + \mu n \cdot \langle u_j, v\rangle $$ by first order perturbation theory. I think if $301$ is really a special choice, the conclusion is that in this case one of the eigenvectors of the random matrix is almost parallel to $v$.

share|improve this answer
    
That's interesting. And $301=7\cdot 43$ does not look a very special number, so it's more a generic one. –  Wadim Zudilin Jul 3 '10 at 12:33
    
I just noticed that the code actually computes eigenvalues for matrices with coefficients uniformly distributed in [-0.9,1] EXCEPT on the diagonal, which are distributed between [.1,2] –  j.c. Jul 3 '10 at 15:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.