Matrice aléatoire inversible
Bonjour,
je considère une matrice $M$ carrée de taille $n$ dont les coefficients sont des variables aléatoires $X_{i,j}$ mutuellement indépendantes et qui suivent une loi de Bernoulli de paramètre $p$. Je veux calculer la probabilité que la matrice $M$ soit inversible.
Pour cela, je considère que la matrice est à valeurs dans $\Z/2\Z$ et je veux calculer la probabilité de l'événement $(\det M = 1)$. Comme $\det(M)$ est une va à valeurs dans $\Z/2\Z$, elle suit une loi de Bernoulli, donc $p\big(\det(M)=1\big)=E\big(\det(M)\big)$.
Pour calculer l'espérance de $\det(M)$, j'utilise l'écriture du déterminant sous la forme
$$\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)\prod_{i=1}^{n} X_{\sigma(i),i}.
$$ Par linéarité de l'espérance puis indépendance des $X_{i,j}$, j'obtiens que l'espérance vaut :
$$E\big(\det(M)\big)=\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)\prod_{i=1}^{n} E(X_{\sigma(i),i}) =\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)p^n =0.
$$ Donc ma matrice est presque sûrement non inversible selon mon calcul. Mais j'ai voulu vérifier la cohérence de mon résultat en tirant des matrices au hasard et je n'arrive pas du tout à ce résultat. J'ai tendance à ne pas trop faire confiance à mon calcul de proba mais je ne vois pas l'erreur de raisonnement que je fais.
je considère une matrice $M$ carrée de taille $n$ dont les coefficients sont des variables aléatoires $X_{i,j}$ mutuellement indépendantes et qui suivent une loi de Bernoulli de paramètre $p$. Je veux calculer la probabilité que la matrice $M$ soit inversible.
Pour cela, je considère que la matrice est à valeurs dans $\Z/2\Z$ et je veux calculer la probabilité de l'événement $(\det M = 1)$. Comme $\det(M)$ est une va à valeurs dans $\Z/2\Z$, elle suit une loi de Bernoulli, donc $p\big(\det(M)=1\big)=E\big(\det(M)\big)$.
Pour calculer l'espérance de $\det(M)$, j'utilise l'écriture du déterminant sous la forme
$$\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)\prod_{i=1}^{n} X_{\sigma(i),i}.
$$ Par linéarité de l'espérance puis indépendance des $X_{i,j}$, j'obtiens que l'espérance vaut :
$$E\big(\det(M)\big)=\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)\prod_{i=1}^{n} E(X_{\sigma(i),i}) =\sum_{\sigma\in\mathfrak S_n} \varepsilon(\sigma)p^n =0.
$$ Donc ma matrice est presque sûrement non inversible selon mon calcul. Mais j'ai voulu vérifier la cohérence de mon résultat en tirant des matrices au hasard et je n'arrive pas du tout à ce résultat. J'ai tendance à ne pas trop faire confiance à mon calcul de proba mais je ne vois pas l'erreur de raisonnement que je fais.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
L'espérance de son déterminant dans $\R$ est clairement nulle. (intervertir deux colonnes multiplie le déterminant par -1 sans changer sa loi, donc c'est une variable aléatoire symétrique par rapport à 0)
En revanche, pour son déterminant modulo 2, je ne suis pas familier de la notion d'espérance d'une variable modulo 2.
Si je suis rigoureux en voulant suivre la même idée, je pose $X$ la va qui vaut $1$ si ma matrice est inversible et $0$ sinon, de sorte que je cherche $p(X = 1) = E(X)$, mais je suis coincé car je n'arrive pas à exprimer mon $X$ avec le déterminant de $M$ (en tout cas, pas directement).
J'ai du mal à me convaincre de l'argument de marsup sur la symétrie. La va $\det(M)$ est à valeurs dans $\Z$ et il faudrait montrer que $\big(\det(M)=k\big)$ et $\big(\det(M)=-k\big)$ ont la même proba. Si j'ai une matrice $M$ dont le déterminant est $k$, la matrice $M$ avec les colonnes 1 et 2 échangées aura bien une proba de $-k$. Et dans mes tirages possibles de matrices, s'il y a la matrice $M$, alors il y a ma matrice $M$ modifiée, mais je n'arrive pas à formaliser ça.
Compter le nombre d'éléments de $GL_n(\mathbb Z/2\mathbb Z)$ est un grand classique :
$2^n-1$ choix possibles pour le premier vecteur, $2^n-2$ pour le second, ..., $2^n-2^k$ pour le $k+1$-ème, ....
Au total $(2^n-1)(2^{n-1}-1)\cdots(2^2-1) 2^{n(n-1)/2}$.
Après, il faut savoir ce que tu veux ...
Matrice à coefficients $0,1$ inversible sur $\mathbb Z$ ? sur $\mathbb R$ ? sur $\mathbb Z/2\mathbb Z$ ?
J'ai eu l'air de changer d'énoncé en cours de route. Pour fixer le tout, je voudrais calculer la probabilité que ma matrice soit inversible dans $\R$. J'étais juste (mal) passé par $\Z/2\Z$ car je pensais que ça me permettait de calculer ma proba.
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1
\end{array}\right),\]dont le déterminant vaut $2$, est inversible ?
J'avais fait le calcul de la proba en taille 2 en distinguant des cas selon la valeur de la première colonne de la matrice (j'arrive à une proba de $2p^2-2p^4$). Je dois dire que je ne m'étais pas intéressé au max, bien que ce soit intéressant comme question. Mais évidemment, cette méthode ne se généralise pas bien aux plus grandes dimensions ; ça doit être faisable en taille 3, mais je n'ai pas eu le courage de m'y atteler.
Dans mon problème, la matrice de Math Coss est inversible et je reste dans R pour la suite (:D
Mais bon, c'est vrai que c'est compliqué, comme problème...
EDIT : Oulala je viens de trouver un papier (cliquer ici) où des matrices $\{\pm 1\}$ sont considérées et Tao a travaillé dessus...
Du coup, je vais me motiver pour écrire un script qui me fait les calculs en petite dimensions
En faisant une étude de fonctions rapidement, j'arrive à un max égale à approximativement $0.407229075$, atteint en $p = 0.6336209375$.
edit: des 2 changes en 3 grace a marco: merci.
En taille 5 :$120*p^5*(1-30*p^4-24*p^6-30*p^3+344*p^5+96460*p^12-4595*p^7+19955*p^8-49880*p^9+86136*p^10-107276*p^11-61220*p^13+26100*p^14-6750*p^15+810*p^16+4*p)*(p-1)^4$.
Et après, il y a trop de matrices pour résoudre ça par force brute.
Je parcours toutes les matrices de taille n fixée à coefficients 0 ou 1. Si une matrice est inversible (comme mon déterminant est entier même si Python me renvoie un flottant, est-ce que je ne pourrais pas d'ailleurs tester l'égalité à 0 du déterminant plutôt que le bricolage habituel dû aux flottants ?), alors je compte le nombre i de 1, j'en déduis le nombre j de 0 et j'ajoute 1 à la valeur d'un dico pour la clé (i,j). Puis, j'écris la formule de sorte à ce qu'elle soit lisible pour Maple afin de développer/factoriser facilement.
C'est instantané ou presque jusqu'à n=4. Pour n=5, ça se compte en minutes. Je n'ai pas testé pour n=6 vu qu'il faut étudier $2^{36}$ matrices...
0->0
1->0
2->0
3->0
4->0
5->0
6->720
7->21600
8->302400
9->2606400
10->15357600
11->65378880
12->210823200
13->541576800
14->1123513200
15->1973999520
16->2910435840
17->3768249600
18->4167144000
19->4129660800
20->3526986240
21->2690475840
22->1782572400
23->1054663200
24->528537600
25->230610240
26->82550880
27->24638400
28->5529600
29->885600
30->87120
31->4320
32->0
33->0
34->0
35->0
36->0
J'ai écrit un programme qui fait le calcul pour $n=6$ en $18$ secondes. Je peux te le transmettre sur le forum, si ça t'intéresse. Le programme utilise le fait que, si on associe à chaque colonne $c_i$ le nombre entier dont la colonne est l'écriture en binaire, pour calculer les matrices inversibles, on peut supposer $c_1<c_1 <\dots <c_n$ et multiplier le nombre de matrices obtenues par $n!$.
Ton résultat sur le nombre de matrices inversibles en fonction du nombre de 1 est amusant : s'il y a moins de 6 fois 1, alors la matrice n'est pas inversible. Par contre, je m'attendais à une symétrie dans le nombre de matrices inversibles en fonction du nombre de 1 et en fait pas du tout.
$$f(p)\geq \Pr (M\in P_n)=n!\,p^n(1-p)^{n^2-n}.$$ Ensuite si $\sigma$ est une permutation la probabilité de l’événement $A_{\sigma}=\{\prod_{i=1}^nX_{i,\sigma(i)}=1\}$ est $p^n$ et donc
$$f(p)\leq \Pr(\cup _{\sigma}A_{\sigma})\leq \sum_{\sigma} \Pr(A_{\sigma})=n!\,p^n$$ et donc $$(1-p)^{n^2-n}<\frac{f(p)}{n!p^n}<1$$ donne l’équivalence annoncée.
Ce n'est pas symétrique. Par exemple, pour $n=2$, il y a $2$ matrices avec deux $1$ et $4$ matrices avec trois $1$, et sinon aucune matrice inversible avec zéro, un ou quatre $1$.
J'ai essayé d'écrire le programme en Python, mais je n'y suis pas arrivé, donc il est en Java.
@marco : pas de souci pour dire que s'il y a trop peu de 1, alors la matrice aura une colonne nulle. C'est juste que naïvement, je m'attendais à une sorte de symétrie. Je ne connais pas Java, mais je vais voir si j'arrive à réécrire en Python ton idée.
Dans le genre soit $M_{i_0,\sigma}$ la matrice telle que $X_{j,\sigma(j)}=0$ si $j\neq i_0$ et telle que $X_{i,j}=1$ dans les $n^2-n+1$ autres cas. Exemple $M_{1, \mathrm{identite}}$ a des 1 partout sauf des zéros sur $(2,2),(3,3),\ldots (n,n).$ Et $\det(M_{i_0,\sigma})=\pm 1.$ Soit $B_{i_0,\sigma}=\{M=M_{i_0,\sigma}\}$ Ces $n! n$ événements sont disjoints et de même probabilité $(1-p)^{n-1}p^{n^2-n+1}$ et donc
$$
f(p)\geq \Pr(\cup_{i_0,\sigma}\{M=M_{i_0,\sigma}\})=n!\times n (1-p)^{n-1}p^{n^2-n+1}
$$ ce qui est une bonne étape pour montrer que $$f(p)\sim _{p\to 1}n!\times n (1-p)^{n-1}.$$