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<j\leqslant n}\left(\lambda_i(P)-\lambda_j(P)\right) \end{aligned}\right. $$ 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$.

  • $\begingroup$ What do you mean by roots of $P$? The eigenvalues of the random matrix? Also, what is $\chi_M$? The characteristic polynomial of $M$? $\endgroup$
    – Math1000
    Dec 27, 2019 at 5:55
  • $\begingroup$ And why are you invoking Fubini's theorem where there is no evidence of interchanging the order of integration? $\endgroup$
    – Math1000
    Dec 27, 2019 at 6:04
  • $\begingroup$ 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$. $\endgroup$
    – Tuvasbien
    Dec 27, 2019 at 12:32
  • $\begingroup$ The answer here may answer your question, or point to an answer in the literature. math.stackexchange.com/questions/3352786/… $\endgroup$ Dec 29, 2019 at 13:35
  • $\begingroup$ @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? $\endgroup$ Dec 29, 2019 at 15:40

1 Answer 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).

  • $\begingroup$ 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 ? $\endgroup$
    – Tuvasbien
    Dec 29, 2019 at 23:46
  • $\begingroup$ +1 purely for humor. is it wrong that when you said "neighbor's visa card", I also assumed the neighbor was a guy $\endgroup$ Dec 30, 2019 at 16:20
  • $\begingroup$ @mathworker21 , you are right :) $\endgroup$
    – user91684
    Jan 3, 2020 at 11:27
  • $\begingroup$ Thanks for the bounty. $\endgroup$
    – user91684
    Jan 6, 2020 at 15:59

You must log in to answer this question.

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