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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Aug 13, 2020 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
    Commented Aug 13, 2020 at 12:55
  • $\begingroup$ The fraction of eigenvalues that are strictly real decreases as $1/\sqrt{n}$ $\endgroup$
    – thedude
    Commented Aug 13, 2020 at 12:58

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ $1-2^{- \frac{n(n-1)}{4}}$ fits nice to what I got with MC. Thanks. $\endgroup$
    – prosti
    Commented Aug 13, 2020 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$
    – user21349
    Commented Aug 13, 2020 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
    Commented Aug 13, 2020 at 21:15

You must log in to answer this question.

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