Probability of having complex eigenvalue? Let $A$ be a real $n \times n$ matrix with coefficients randomly chosen from Uniform Distribution [-1,1]. What's the probability that A has a complex eigenvalue with non-zero imaginary part?
If you'd like to know the motivation, I've been doing QR factorization and I notice that the algorithm seems to fail at times, producing blocks along the main diagonal but zero elsewhere. While I'm sure the fault lies with my code, it got me interested in the question. Props to you if you can generalize from Uniform distribution to any probability distribution.
 A: Let $p_n$ be the required probability. The case $n=2$ is not difficult when $a,b,c,d$ follow $U[-1,1]$. The probability that the roots are real  is 
$p_2=\dfrac{1}{32}\int\int\int\int_{[-1,1]^4} signum((a-e)^2+4bc)+1\;\; da\; db\; dc\; de\approx 0.6805$. Yet, we will see that $p_n$ decreases very quickly when $n$ increases.
This question is about the number $N$ of real roots of a real polynomial $\sum_{i=1}^na_ix^i$. Let $E_n(N)$ be the expected number of real roots of such a polynomial. In the following reference (dated 1994)
http://www-math.mit.edu/~edelman/publications/how_many_zeros.pdf
it is proved that i) if the $(a_i)$ follow $N(0,1)$, then $E_n(N)\sim \dfrac{2}{\pi}\log(n)$ 
In fact it is a result from Kac and the same estimation of $E_n(N)$ works when the $(a_i)$ follow $U[-1,1]$ (Kac) or follow $U\{-1,1\}$ (Erdos). Note that the proof concerning the law $U[-1,1]$ is much more difficult than the one concerning $N(0,1)$.
ii) if the $(a_i)$ follow $N(0,\binom{n}{i})$, then $E_n(N)\sim \sqrt{n}$. 
Note that when we consider $A\in M_n(\mathbb{R})$, where the $(a_{ij})$ follow $N(0,1)$, the polynomial $\det(A-xI)$ fulfills rather the condition ii) than the condition i). Anyway, $E_n(N)=o(n)$.
Now let $V_n(N)$ be the variance of $N$ ; Maslova proved, in the case i), the following estimate of the variance of $N$: $V_n(N)\sim \dfrac{4}{\pi}(1-2/\pi)\log(n)$. Thus, in case i), $\log(p_n)$ behaves somewhat like $-n^{2}$. In case ii), and when we consider the characteristic polynomial of a random matrix, one has to find similar results.
EDIT. Assume that $A\in M_n(\mathbb{R})$, where the $(a_{ij})$ are iid and follow $N(0,1)$ and let $N$ be the number of real eigenvalues of $A$. Then the estimates of the mean and the variance are $E_n(N)\sim\sqrt{\dfrac{2n}{\pi}}$ and $V_n(N)\sim (2-\sqrt{2})\sqrt{\dfrac{2n}{\pi}}$ (due to Edelman,Kostlan, Forrester, Nagao, cf. Theorem 16 in [1]).
[1] Tao and Vu http://arxiv.org/abs/1206.1893 . A monumental 97 p. paper where you will find (among others) a generalization of the previous result.
Assume that $n$ is a great number; if one approximates the distribution of $N$ by a normal one, then some calculations seem to show that $p_n$, the probability that $A$ has only real roots, satisfies $\log(p_n)=-n^{\frac{3}{2}+o(1)}$.
Happy Rounded Pi Day to all.
