6
$\begingroup$

I find this is the best site to post this question, even though I considered cs.

It is a Monte Carlo experiment over the set of 10.000 n×n matrices. If a single matrix eigenvalue is complex then python numpy package will return all the eigenvalues as numpy.complex128 type, else it will return all eigenvalues as numpy.float64 type.

Here is the algorithm:

# Monte carlo experiment in numpy

import numpy as np
from numpy import linalg as LA

e=10000 # examples
# n - matrix rank
for n in range(1,10):
    cc=0 # complex counter
    for i in range (e):
        m=np.random.randn(n,n)#  m=np.random.random((n,n))        
        w, _ = LA.eig(m)        
        if (type(w[0]).__name__ == "complex128"):        
            cc+=1    
    print(f'matrix:{n}x{n}, total cases: {e}, complex cases: {cc}, ratio: {cc/e}')

The output of this algorithm is as follows:

matrix:1x1, total cases: 10000, complex cases: 0, ratio: 0.0
matrix:2x2, total cases: 10000, complex cases: 2851, ratio: 0.2851
matrix:3x3, total cases: 10000, complex cases: 6481, ratio: 0.6481
matrix:4x4, total cases: 10000, complex cases: 8782, ratio: 0.8782
matrix:5x5, total cases: 10000, complex cases: 9674, ratio: 0.9674
matrix:6x6, total cases: 10000, complex cases: 9944, ratio: 0.9944
matrix:7x7, total cases: 10000, complex cases: 9998, ratio: 0.9998
matrix:8x8, total cases: 10000, complex cases: 9999, ratio: 0.9999
matrix:9x9, total cases: 10000, complex cases: 10000, ratio: 1.0

It is very easy to understand the 1x1 case, since we take values from floating point numbers (set $\mathbb Q$) the eigenvalue will be the number itself (also in $\mathbb Q$).

For the case 2x2 and later, we may get complex eigenvalues ($\mathbb Z$).

I am counting the complex cases (where at least one eigenvalue is complex) and providing the ratio.

I would like to get some thoughts about this ratio possible the formula how to calculate one analytically.


My thought is that the ratio is not dependent on floating point arithmetic. I used the normal distribution $\sim \mathcal N(0,1)$, but one may test also the uniform distribution I commented.

$\endgroup$
  • $\begingroup$ To get a first guess of the functional dependence of the ration with respect to $n$: I would try first if f.i. this may be a logistic function. You can estimate the parameters of this function with programs as R or the python module pandas. $\endgroup$ – Dieter Kadelka Aug 13 at 12:32
  • 2
    $\begingroup$ You may be interested in the paper "How Many Eigenvalues of a Random Matrix are Real?" by Alan Edelman, Eric Kostlan and Michael Shub $\endgroup$ – thedude Aug 13 at 12:55
  • $\begingroup$ The fraction of eigenvalues that are strictly real decreases as $1/\sqrt{n}$ $\endgroup$ – thedude Aug 13 at 12:58
10
$\begingroup$

The probability that a $n\times n$ real matrix (with elements that are independent random variables with standard normal distributions) has only real eigenvalues is given by $$ 2^{-n(n-1)/4}$$

Reference: A. Edelman, The Probability that a Random Real Gaussian Matrix has $k$ Real Eigenvalues, Related Distributions, and the Circular Law. Journal of Multivariate Analysis 60, 203-232 (1997).

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ $1-2^{- \frac{n(n-1)}{4}}$ fits nice to what I got with MC. Thanks. $\endgroup$ – prosti Aug 13 at 15:00
  • $\begingroup$ Is there any simple heuristic that would explain why it's asymptotically an exponential in $n^c$, with $c=2$? If the probabilities were independent for the $n$ eigenvalues, we'd expect $c=1$. If every matrix element had some probability of perturbing each eigenvalue off the real line, then maybe we'd imagine $c=3$. Maybe it's like random collisions between one eigenvalue and another, where being too close causes a repulsion that forces them off the real line? That would seem to make sense of the $c=2$. $\endgroup$ – Ben Crowell Aug 13 at 18:51
  • 1
    $\begingroup$ @Ben Crowell There are $n^2$ independent random variables involved, namely the entries of the matrix... for this reason, the rate $n^2$ is typical of large deviations for the empirical measure of eigenvalues of random matrices. $\endgroup$ – ofer zeitouni Aug 13 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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