# Diagonalizable random matrix

Let $$p_n$$ the probability that a random matrix $$M\in\mathcal{M}_n(\mathbb{R})$$ such that its entries $$(m_{i,j})_{1\leqslant i,j\leqslant n}$$ are independant and following an uniform distribution over $$[-1,1]$$, is diagonalizable. I was wondering how to calculate $$p_n$$ and maybe how to find its limit or an equivalent.

Diagonalization in $$\mathbb{C}$$ : I proved that $$p_n=1$$ for all $$n\in\mathbb{N}$$ if we talk about diagonalization in $$\mathbb{C}$$ :

Let \Phi_n : \left|\begin{aligned} &\ \ \ \ \ \ \ _ \ \ \ \ \mathbb{R}_{=n}[X] &\longrightarrow &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathbb{C} \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P &\longmapsto &\prod_{1\leqslant i where $$(\lambda_i(P))_{1\leqslant i\leqslant n}$$ are the roots of $$P$$ ordered in the lexicographical order. For any $$P\in\mathbb{R}_{=n}[X]$$, $$\Phi_n(P)$$ is, by a factor, the discriminant of $$P$$ and thus is a polynomial function of the coefficients of $$P$$. Moreover, $$\Phi_n(P)=0$$ if and only if $$P$$ has a multiple root so that $$p_n \geqslant \mathbb{P}(\Phi_n(\chi_M)\neq 0)=1-\mathbb{P}(\Phi_n(\chi_M)=0)$$ because $$M$$ is diagonalizable in $$\mathbb{C}$$ if $$\chi_M$$ has no multiple root.

Moreover, if we denote $$\lambda_n$$ the Lebesgue measure on $$\mathbb{R}^n$$, one can show that for any non-constant $$P\in\mathbb{R}[X_1,\ldots,X_n]$$, if $$\zeta(P) := \{ x\in\mathbb{R}^n\ |\ P(x)=0 \}$$ then $$\lambda_n(\zeta(P))=0$$. We show it by induction on $$n$$ : if $$n=1$$ then $$\zeta(P)$$ is finite so that $$\lambda_1(\zeta(P))=0$$. If $$n\geqslant 2$$, we write $$\zeta(P)=\bigcup_{t\in\mathbb{R}}\zeta(P(\cdot,t))$$ where $$P(\cdot,t):(x_1,\ldots,x_{n-1})\mapsto P(x_1,\ldots,x_{n-1},t)$$. By hypothesis $$\lambda_{n-1}(\zeta(P(\cdot,t)))=0$$ for all $$t\in\mathbb{R}$$, thus using Fubini's theorem we have $$\lambda_n(\zeta(P))=\int_{-\infty}^{+\infty}\lambda_{n-1}(\zeta(P(\cdot,t)))dt=0$$

Finally, since $$M\mapsto\Phi_n(\chi_M)$$ is a polynomial function of the coefficients of $$M$$ (because $$\Phi_n$$ and $$M\mapsto\chi_M$$ are), the measure of the set $$\{M\in\mathcal{M}_n(\mathbb{R})\ |\ \Phi_n(\chi_M)=0\}$$ is $$0$$ and $$\mathbb{P}(\Phi_n(\chi_M)=0)=0$$ and thus $$p_n=1$$.

Diagonalization in $$\mathbb{R}$$ : Because of what said above, for any $$M\in\mathcal{M}_n(\mathbb{R})$$, $$\chi_M$$ has no multiple root almost surely so that $$p_n=\mathbb{P}(\text{Sp}(M)\subset\mathbb{R})$$ I believe that $$\lim\limits_{n\rightarrow +\infty}p_n=0$$ but I don't know how to prove it, and even less how to find an equivalent of $$p_n$$.

EDIT : While searching for papers I found out about the circular law. Notice that the entries of $$M$$ has zero mean and, since $$A$$ is diagonalizable if and only if $$\lambda A$$ is diagonalizable for all $$\lambda\in\mathbb{R}$$, we can study the special case where the entries have a variance of $$1$$ (in our case we would study $$\sqrt{\frac{3}{2}}A$$). Let $$\mu_n$$ be the measure $$\mu_n=\frac{1}{n}\sum_{k=1}^n \delta_{n^{-1/2}\lambda_k(M_n)}$$ with $$M_n\in\mathcal{M}_n(\mathbb{R})$$ a random matrix, $$\lambda_k(M_n)$$ its random eigenvalues and $$\delta$$ the Dirac measure. What is interesting is that $$n\mu_n(\mathbb{R})$$ is the number of real eigenvalues (counted with multiplicity) of $$M_n$$ so that $$p_n=\mathbb{P}(\text{Sp}(M_n)\subset\mathbb{R})=\mathbb{P}(\mu_n(\mathbb{R})=1)$$ Since $$\mu_n(\mathbb{R})\leqslant 1$$ almost surely, we have using Markov's inequality $$p_n=\mathbb{P}(\mu_n(\mathbb{R})\geqslant 1)\leqslant\mathbb{E}(\mu_n(\mathbb{R}))$$ If we prove that $$\lim\limits_{n\rightarrow +\infty}\mu_n(\mathbb{R})=0$$ almost surely, we can use the dominated convergence theorem with the domination $$\mu_n(\mathbb{R})\leqslant 1$$ almost surely to prove that $$\lim\limits_{n\rightarrow +\infty}\mathbb{E}(\mu_n(\mathbb{R}))=0$$ and this would finally show that $$\lim\limits_{n\rightarrow +\infty}p_n=0$$.

The circular law states that the sequence of measures $$(\mu_n)_{n\in\mathbb{N}^*}$$ converges in distribution to the uniform measure on the unit disk almost surely. This means that for all smooth function $$f:\mathbb{C}\longrightarrow\mathbb{R}$$ that has a compact support, we have $$\lim\limits_{n\rightarrow +\infty}\int_{\mathbb{C}}f(z)d\mu_n(z)=\frac{1}{\pi}\int_{x^2+y^2\leqslant 1}f(x+iy)dxdy$$ Let $$\varepsilon>0$$, $$\beta>0$$ and $$f:\mathbb{C}\longrightarrow\mathbb{R}^+$$ a smooth function such that $$f(z)=1$$ for all $$z\in[-\beta,\beta]$$ and $$\frac{1}{\pi}\int_{x^2+y^2\leqslant 1}f(x+iy)dxdy<\frac{\varepsilon}{2}$$ (such a function exists, $$\varphi(x)=\mathbf{1}_{\{|x|\leqslant 1\}}+\left(1-e^{-\frac{x^2}{x^2-1}}\right)\mathbf{1}_{\{|x|>1\}}$$ is a smooth function such that $$\varphi(x)=1$$ for all $$x\in[-1,1]$$, we can use $$f(x+iy)=\varphi(x/\beta)\varphi(y/\eta)$$ with $$\eta>0$$ small enough). Thus $$\limsup\limits_{n\rightarrow +\infty}\mu_n([-\beta,\beta])\leqslant\lim\limits_{n\rightarrow +\infty}\int_{\mathbb{C}}f(z)d\mu_n(z)=\frac{1}{\pi}\int_{x^2+y^2\leqslant 1}f(x+iy)dxdy<\frac{\varepsilon}{2}$$ Furthermore \begin{aligned} \limsup\limits_{n\rightarrow +\infty}\mu_n(]-\infty,-\beta[\cup]\beta,+\infty[)&\leqslant\int_{-\infty}^{-\beta}\frac{t^2}{\beta^2}d\mu_n(t)+\int_{\beta}^{+\infty}\frac{t^2}{\beta^2}d\mu_n(t) \\ &\leqslant\frac{1}{\beta^2}\int_{\mathbb{C}}|z|^2 d\mu_n(z) \end{aligned} However $$\sum_{k=1}^n{\lambda_k(M_n)^2}=\text{tr}({}^t M_n M_n)=\sum_{1\leqslant i,j\leqslant n}m_{i,j}^2$$ so that $$\limsup\limits_{n\rightarrow+\infty}\int_{\mathbb{C}}|z|^2 d\mu_n(z)=\limsup\limits_{n\rightarrow +\infty}\frac{1}{n^2}\sum_{1\leqslant i,j\leqslant n}m_{i,j}^2\leqslant\mathbb{E}(m_{1,1}^2)=1$$ almsot surely according to the law of large numbers. Thus there exists $$C>0$$ such that $$\forall n\in\mathbb{N}^*,\int_{\mathbb{C}}|z|^2d\mu_n(z)\leqslant C$$ Finally $$\limsup\limits_{n\rightarrow +\infty}\mu_n(]-\infty,-\beta[\cup]\beta,+\infty[)\leqslant\frac{C}{\beta^2}$$ and if we set $$\beta=\sqrt{\frac{2C}{\varepsilon}}$$, we have $$\limsup\limits_{n\rightarrow +\infty}\mu_n(\mathbb{R})=\limsup\limits_{n\rightarrow+\infty}\mu_n([-\beta,\beta])+\limsup\limits_{n\rightarrow +\infty}\mu_n(]-\infty,-\beta[\cup]\beta,+\infty[)<\varepsilon$$ Letting $$\varepsilon\rightarrow 0$$ gives $$\limsup\limits_{n\rightarrow+\infty}\mu_n(\mathbb{R})=0$$ almost surely and thus $$\lim\limits_{n\rightarrow+\infty}p_n=0$$.

• What do you mean by roots of $P$? The eigenvalues of the random matrix? Also, what is $\chi_M$? The characteristic polynomial of $M$? Dec 27, 2019 at 5:55
• And why are you invoking Fubini's theorem where there is no evidence of interchanging the order of integration? Dec 27, 2019 at 6:04
• The roots of $P$ are the $x\in\mathbb{C}$ such that $P(x)=0$, $\chi_M$ is the characteristic polynomial of $M$ and thus the roots of $\chi_M$ are the eigenvalues of $M$. I can use Fubini's theorem without thinking about an evidence of interchanging, the function I am integrating is positive, the swapping is always true, even if the integral diverges to $+\infty$. Dec 27, 2019 at 12:32
• @Tuvasbien the characteristic polynomial takes the form $\lambda^n+f_{n-1}(m_{ij})\lambda^{n-1}+\dots+f_1(m_{ij})\lambda+f_0(m_{ij})$, where the $f_i$'s are just multilinear functions of the $m_{ij}$'s. So you just want to show that, with probability tending to $1$, this polynomial doesn't have only real roots. This should be doable, using just the fact that each $f_i$ is non-constant, right? Dec 29, 2019 at 15:40

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.

$$(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).

• Thank you, I edited my question. I found how to prove that $\lim\limits_{n\rightarrow +\infty}p_n=0$. However in my proof I use a strong theorem, thus finding an equivalent of $p_n$ seems quite hard. Do you have a proof for your (interesting) approximation ? Dec 29, 2019 at 23:46
• +1 purely for humor. is it wrong that when you said "neighbor's visa card", I also assumed the neighbor was a guy Dec 30, 2019 at 16:20
• @mathworker21 , you are right :)
– user91684
Jan 3, 2020 at 11:27
• Thanks for the bounty.
– user91684
Jan 6, 2020 at 15:59