17
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 11:45
  • $\begingroup$ 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. $\endgroup$
    – vonjd
    Jul 3, 2010 at 16:57
  • $\begingroup$ Sorry for not providing pictures -- was a bit afraid of breaking some rule I guess $\endgroup$ Jul 3, 2010 at 18:22

4 Answers 4

21
$\begingroup$

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.

$\endgroup$
0
12
$\begingroup$

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

Edit 2: In response to Helge's comment asking for a plot of $\max_{1\leq j \leq N} \sum_{n=1}^{N} u_j^N(n)$ when $l=-1$:

l=-1 plot of largest sum

$\endgroup$
5
  • 1
    $\begingroup$ (These plots were made in response to Helge's fine answer) $\endgroup$
    – j.c.
    Jul 3, 2010 at 13:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – Helge
    Jul 3, 2010 at 14:09
  • $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 14:45
  • $\begingroup$ @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.... $\endgroup$
    – Helge
    Jul 3, 2010 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – Helge
    Jul 3, 2010 at 15:30
6
$\begingroup$

Here is the output from Piero's posted code:

alt text

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That's interesting. And $301=7\cdot 43$ does not look a very special number, so it's more a generic one. $\endgroup$ Jul 3, 2010 at 12:33
  • $\begingroup$ 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] $\endgroup$
    – j.c.
    Jul 3, 2010 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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