Matrice aléatoire inversible

Ismaric · January 2018

Bonjour à tous

Je me pose la question suivante : existe-t-il une formule reliant n entier naturel non nul et la probabilité qu'une matrice 2x2 à coefficients entiers choisis aléatoirement, de manière indépendante, en suivant une loi une loi uniforme sur 1,n, soit inversible?

Il est assez facile de voir que pour n=1 la proba vaut 0, que pour n=2 elle vaut 0.625 (=10/16) .

J'ai essayé de voir informatiquement ce que cela donne pour n entre 1 et 9. Comme on peut s'y attendre la forme du nuage donne une asymptote horizontale (y=1) et on semble avoir une forme puissance (du genre p=1-n^a), mais la régression linéaire de ln(1-p) en fonction de n ne donne pas quelque chose de satisfaisant).

Si quelqu'un a une formule (connue ou à tester), merci d'avance

Dom · January 2018

N'y a-t-il pas une coquille : "inversible" en "non inversible" ? Ou bien ailleurs, certainement...

Je regarde le cas n=1, c'est plutôt 1, la probabilité d'avoir une matrice inversible.
(Edit : c'est pourtant bien écrit "matrice 2x2", j'ai lu trop vite).
Je regarde le cas n=2, je trouve bien 10/16, la probabilité d'avoir une matrice inversible.

Bon, j'imagine (je veux croire) que quelqu'un va trouver la formule...

Ismaric · January 2018

Avec n=1, une seule matrice possible, (avec des 1 partout) qui est non inversible. donc on a bien p=0

Ismaric · January 2018

Je sais bien que cela revient à calculer $P(X_1X_4\neq X_2X_3)$ avec pour tout $i$, $X_i$ suivant la loi uniforme sur $1,n$, les variables étant mutuellement indépendantes.
Je voulais juste savoir si quelqu'un avait déjà le résultat (pas trop envie, le temps de faire le calcul et besoin assez vite de la formule!)

Dom · January 2018

Ha oui d'accord, j'ai mal lu.
Je pensais que la taille de la matrice était aussi cet entier $n$.
Sorry 8-)

Poirot · January 2018

Peut-être qu'en écrivant $$\mathbb P(X_1X_4 = X_2X_3) = \mathbb P\Big(\frac{X_1}{X_2} = \frac{X_3}{X_4}\Big) = \sum_{q \in \mathcal F_{\leq n}} \mathbb P\Big(\frac{X_1}{X_2}=q\Big)\mathbb P\Big(\frac{X_3}{X_4}=q\Big)$$ on peut s'en sortir ? $\mathcal F_{\leq n}$ désigne les quotients de Farey d'ordre jusqu'à $n$, c'est-à-dire les fractions d'entiers entre $1$ et $n$.

Ismaric · January 2018

Bien, j'ai finalement pris le temps de réfléchir.
Pour des raisons d'équiprobabilité et passage au contraire (c'est plus facile à calculer), il reste donc à calculer $N_n=\mathrm{Card}\big(\{(a,b,c,d)\in 1,n \mid ad=bc\}\big)$, pour tout $n\geq 1$.

On a clairement $N_1=1$ (et on retrouve $p_n=1-\dfrac {N_1}{1^4}=0$)
Et pour $n\geq 2$, par séparation en deux parties disjointes :
$N_n=\mathrm{Card}\big(\{(a,b,c,d)\in 1,n-1 \mid ad=bc\}\big)+\mathrm{Card}\big(\{(a,b,c,d)\in 1,n \mid ad=bc\mbox{ et }(a=n\mbox{ ou }b=n\mbox{ ou }c=n\mbox{ ou }d=n)\} \big)$

pour le premier morceau, facile on retrouve $N_{n-1}
pour le deuxième morceau, c'est vraiment plus complexe.
1. On peut quand même faire dans un cas : si $n$ est premier. Pour des raisons de divisibilité (quand $a=n$, $n$ divise forcement $bc$ et donc $b=n$ ou $c=n$ et symétriquement), il reste 5 formes possibles pour les quadruplets $(n,n,x,x)$, $(n,x,n,x)$, $(x,x,n,n)$, $(x,n,x,n)$ avec $x\neq n$ et $(n,n,n,n)$ ce qui donne $4(n-1)+1=4n-3$ possibilités
2. pour $n$ non premier, les quadruplets listés au a) comptent encore, mais il y en a d'autres (ceux avec une seule fois $n$, où interviennent les diviseurs stricts de $n$; et là je ne m'y mettrai pas ce soir)

En conclusion : si $n$ est premier $N_n=N_{n-1}+4n-3$ et si $n$ n'est pas premier $N_n=N_{n-1}+4n-3 + \cdots$

Remarque : on trouve alors :
pour $n=2$ $N_2=N_1+4\times 2-3=6$ et donc $p_2=1-\dfrac 6 {16}=\dfrac {10} {16}$
pour $n=3$ $N_3=N_2+4\times 3-3=15$ et donc $p_3=1-\dfrac {15}{81}=\dfrac {22}{27}$
pour $n=4$ ...

Et donc, il me semble bien qu'il n'y aura pas de formule directe entre la proba envisagée et la valeur de $n$

P. · January 2018

Soit $A,B,C,D$ independantes et de meme loi definie par $\Pr(A=k)=1/n$ avec $k=1,\ldots,n.$ Tu demandes $\Pr(AB-CD=0).$ .Je ne crois pas que ce soit faisable de facon exacte pour un $n$ quelconque. $$\mathbb{E}(z^A)=f(z)= \frac{z(1-z^n)}{n(1-z)}, g(z)=\mathbb{E}(z^{AB})=\mathbb{E}(f(z^B)), \Pr(AB-CD=0)=\frac{1}{2\pi}\int_0^{2\pi}\mathbb{E}(e^{it(AB-CD)})dt=\frac{1}{2\pi}\int_0^{2\pi}|g(e^{it})|^2dt.$$ La difficulte est de calculer $$g(z)=\frac{1}{n^2}\sum_{k=1}^n\frac{z^k(1-z^{nk})}{1-z^k}$$.Un des rares cas ou on est capable de calculer la loi de $X=AB-CD$ est celui de $A\sim N(0,1)$, ou $X$ est alors de densite $e^{-|x|/4}/8.$

Matrice aléatoire inversible

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 17