Diagonalizable random matrix

Solution 1:

Your question can be broken down into two points.

i) For a fixed $n$, $\chi_M$ has distinct roots with probability $1$.

It's a consequence of the Zariski's theory. $\{M;discrim(\chi_M)=0\}$ is a Zariski closed set. Its supplementary $Z$ is a Zariski open set; $Z$ is dense if there is $M$ s.t. $\chi_M$ has distinct roots, that is obviously true. That implies that (for your choice of probability) $prob(M\in Z)=1$.

ii) When $n$ tends to $\infty$, $p_n=prob(spectrum(M)\subset\mathbb{R})$ tends to $0$.

Ethan gave you the famous paper of Do,Nguyen and Van vu (the latter has published a lot with Terrific Tao); in particular, this paper works (perhaps for you) for uniform distribution (this proof is more difficult than that concerning the normal law). Roughly speaking (up to the constants), the random variable $X$="number of real roots of $\chi_M$", has $m=\log(n)$ as mean value and $s=\sqrt{\log(n)}$ as standard deviation. If we approach the probability law of $X$ by the normal law, then $p_n$ behaves like

$(1)$ $p_n\approx I_n=\int_{n-0.5}^{\infty}\dfrac{1}{s\sqrt{2\pi}}\exp(-1/2(\dfrac{x-m}{s})^2)dx$, that is, $p_n$ behaves like

$(2)$ $p_n\approx \dfrac{\sqrt{\log(n)}}{n\sqrt{2\pi}}\exp(\dfrac{-(n-\log(n))^2}{2\log(n)})$.

Conclusion: $p_n$ converges towards $0$ at a gallop.

EDIT. Answer to the OP.

$(2)$ is deduced from $(1)$ as follows; putting $y=\dfrac{x-m}{s}$,

$I_n=\dfrac{1}{\sqrt{2\pi}}\int_{\dfrac{n-\log(n)}{\sqrt{\log(n)}}}^{\infty}\exp(-\dfrac{y^2}{2})dy$. On the other hand,

$\int_{u}^{\infty}\exp(-\dfrac{y^2}{2})dy\sim\dfrac{\exp(-u^2/2)}{u}$, when $u\rightarrow\infty$.

$\textbf{Remark}$. The advantage of having an equivalent of $p_n$ is purely theoretical. Indeed, when $n\geq 22$ (for example), to know if $p_n\approx 10^{-45}$ or $10^{-47}$ has no practical interest: in fact, $M_n$ is "never" diagonalizable over $\mathbb{R}$. European cryptography legislation required that cryptographic systems offered to banks (for example) have a probability $<2^{-80}\approx 10^{-24}$ of being broken by probabilistic (or other) methods. In other words, if $n=30$, you are no more likely to have your matrix $M_n$ diagonalizable than to hack your neighbor's visa card (unless you are going out with his wife).