16
$\begingroup$

Plot the eigenvalues of many $n\times n$ real matrices in the complex plane, where the matrices are taken from a some distribution. For $n>7$, you can start to see a hole at the origin starting to form. From Girko's Circular Law I'd expect the distribution to tend toward a solid disc (with no hole in it). Below, the eigenvalue distributions of $10\times 10$ matrices taken from three distributions are seen, all with holes in them. The bigger $n$ is, the larger the hole is. The distributions are:

  1. All entries of all matrices are $\mathcal{N}(0,1)$
  2. All entries of all matrices are $\mathcal{U}(0,1)$
  3. The matrices are picked uniformly over the volume of a unit $n^2$-ball.

Is this real (and not a bug in my code)? If it is, what is this phenomenon called?

This seems to violate Girko's Circular Law, so what am I missing?

enter image description hereenter image description hereenter image description here

Edit: Here is my Matlab-code for generating these (without the scatterplot):

n = 10;
X = zeros(10^5,1);
Y = zeros(10^5,1);

for i = 1:10^5
    B = randn(n);
    C = eig(B);
    j = 1+4*(i-1);
    X(j:j+n-1) = real(C);
    Y(j:j+n-1) = imag(C);
end

Have I perhaps made some stupid mistake?

2nd edit: Here is a plot with the corrected code, as requested: enter image description here

$\endgroup$
14
  • $\begingroup$ Could it be an effect of finite precision in floating point numbers? You may test changing from double to single precision and see if the effect appears earlier (at lower values of $n$) to test this idea. $\endgroup$
    – dioid
    May 19, 2017 at 16:28
  • $\begingroup$ And as a quick sanity check, what is the quality of your random number generator? You're not using drand48() or something similar but some high quality random number generator, right? $\endgroup$
    – dioid
    May 19, 2017 at 16:31
  • $\begingroup$ How are you implementing this? Some quick testing in Mathematica doesn't reproduce any such hole. $\endgroup$ May 19, 2017 at 17:02
  • $\begingroup$ @dioid I'm using Matlab's standard functions for such distributions, i.e., randn(n), rand(n) and so on. I would think that that would be sufficient, but perhaps not? $\endgroup$ May 19, 2017 at 17:27
  • $\begingroup$ @Semiclassical I've included my code. $\endgroup$ May 19, 2017 at 17:33

3 Answers 3

19
$\begingroup$

As far as I can tell, the problem is in how you're aggregating the eigenvalues into X and Y. j is incrementing by $4$ when it ought to be incrementing by $n = 10$, which has the effect of wiping out the smallest $6$ eigenvalues of almost every matrix, hence the hole. There's an easier way to do the aggregating that doesn't involve a j at all:

N = 10^4;
n = 10;
X = [];
Y = [];

for i = 1:N
    A = randn(n);
    E = eig(A);
    X = [X; real(E)];
    Y = [Y; imag(E)];
end

scatter(X, Y);
$\endgroup$
4
  • $\begingroup$ That seems to be it! Changing the 4 in original code to n should also fix the issue. Original code preallocates X and Y which should be good from a performance perspective, but there is a mismatch between vector size and loop over i, it should just be to 10^4. Anyways, original code just keeps first 4 eigenvalues and by the algorithm matlab uses they tend to be the ones largest in magnitude which explains the hole around the origin. $\endgroup$
    – dioid
    May 19, 2017 at 18:40
  • $\begingroup$ D'oh, you're right! It was some old code that I reused, and I forgot to change the 4 when changing the dimension to 10. Thanks! $\endgroup$ May 19, 2017 at 19:06
  • 3
    $\begingroup$ Can we see a plot with the corrected code? $\endgroup$
    – brichins
    May 19, 2017 at 20:53
  • 2
    $\begingroup$ @brichins Certainly, see edit. $\endgroup$ May 19, 2017 at 22:40
8
$\begingroup$

Your plots instantly reminded me of something I'd seen before (click for a hi-res version):

Turns out that if your matrices have integer entries of bounded height, you do get holes, with the details depending on the distribution. What's more, there are all sorts of interesting and, to my knowledge, unsolved questions about this! More details here.

Given that real matrices can be approximated by rational ones, and bounded-height rationals can be multiplied by a sufficiently-large factor to give bounded-height integers, I wouldn't be surprised if there was some connection with the pattern you saw, even if it was only visible due to a bug.

$\endgroup$
3
7
$\begingroup$

Because you are overwriting some of the eigenvalues by using the offset of 4 rather than 10, you are preferentially overwriting the smaller eigenvalues. This is confirmed in this SO selected answer, which states, for the Matlab algorithm:

The eigenvalues TEND to be in descending order, but this is not assured at all. They tend to be in order because the largest tend to trickle out of the algorithm on top. Eig has no sort at the end to ensure that fact.

So while it isn't purposely sorted in descending order, the algorithm has this effect.

$\endgroup$

You must log in to answer this question.

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