13
$\begingroup$

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

$\endgroup$
6
  • $\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

4
+300
$\begingroup$

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

$\endgroup$
4
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.