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.
Réponses
-
Bonjour,
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. -
Le problème est que tu confonds $\Z/2\Z$ avec $\{0;1\}$ (comme sous-ensemble de $\R$). Calculer l'espérance d'une v.a à valeurs dans $\Z/2\Z$ n'a pas vraiment de sens (que signifie ton $p^n$ dans $\Z/2\Z$ par exemple ?)
-
Ah oui, j'ai fait un peu n'importe quoi avec $\Z/2\Z$ : je voulais relier ma proba à une espérance pour avoir la linéarité et l'espérance du produit de va indépendantes, mais effectivement $p^n$ dans $\Z/2\Z$ est bien stupide.
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. -
Pour pouvoir tester un éventuel résultat, j'ai énuméré toutes les matrices possibles de taille $n$ dans le cas où mes va suivent une loi de Bernoulli de paramètre $\frac12$. J'ai donc $2^{n^2}$ matrices possibles et j'ai : $1, 6, 174, 22560$ matrices inversibles (avec $n = 1,2,3,4$).
-
Bonjour,
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$ ? -
Je n'avais plus pensé à ce résultat qui évitera à mon ordi de chauffer à énumérer toutes les matrices à coefficients dans $\{0,1\}$.
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. -
Eh oui, est-ce que \[M=\left(\begin{array}{rrr}
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1
\end{array}\right),\]dont le déterminant vaut $2$, est inversible ? -
C'est dur, comme tous les problemes d'Alban_. N'est-il pas rigolo de decouvrir que si $n=2$ alors la probabilite d'avoir une matrice inversible est maximale pour $p=\sqrt{2}/2$ et est seulement 1/2?
-
C'est marrant, je n'ai pas l'impression de poser des questions compliquées : à chaque fois qu'on me donne la réponse, je me dis que j'aurais dû y penser.
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 -
Si tu sais, pour tout $k \in \{0,\ldots,n^2\}$, combien il y a de matrices inversibles avec $k$ fois le nombre $1$ et $n^2 - k$ fois le nombre $0$, tu serais sorti d'affaire : si $n_k$ est ce nombre, alors la probabilité est $\sum^{n^2}_{k=0} p^k(1-p)^{n^2 - k} n_k$.
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... -
Et moi qui pensait qu'une fois de plus, j'aurais dû réfléchir plus longtemps avant de poser ma question...
Du coup, je vais me motiver pour écrire un script qui me fait les calculs en petite dimensions -
En taille 3, j'arrive à une proba d'être inversible de $18p^9-54p^8+54p^7-6p^6-18p^5+6p^3$ (je mettrai le code qui me donne ça, mais j'essaie d'abord de le rendre moins vilain).
En faisant une étude de fonctions rapidement, j'arrive à un max égale à approximativement $0.407229075$, atteint en $p = 0.6336209375$. -
Joli, ton polynôme, aussi égal à $6p^3(1-p)^2(1+2p-3p^3+3p^4).$ Pour $n=2$ c’était $2p^2(1-p)(1+p).$ Déjà de quoi conjecturer.
edit: des 2 changes en 3 grace a marco: merci. -
En taille 4, j'ai $-24*p^4*(36*p^9-132*p^8+204*p^7-172*p^6+76*p^5-12*p^3+3*p+1)*(p-1)^3$
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. -
P: es-tu sûr de ta factorisation ? Comment arrives-tu au terme $18p^9$ en développant ta factorisation ? En effet, les termes de plus haut degré de la forme factorisée sont $6p^3$, $p^2$, $2p^4$, donc ça fait $12 p^9$.
-
Merci marco, j'ai corrige. Il semble que la probabilite $P_n(p)$ pour que la matrice soit inversible est toujours de la forme $P_n(p)=n!p^n(1-p)^{n-1}Q_n(p)$ avec $Q_n$ polynome de degre $(n-1))^2$ tel que $Q_n(0)=1$ et $Q_n(1)=n.$ Et peut etre $Q_n$ croissant sur $[0,1].$
-
Voici le script (en Python) qui a permis de faire les calculs. Si certains ont des idées d'amélioration (ou de correction évidemment !) je suis preneur.
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.def proba_matrice_inversible(n): dico = {} for x in product([0, 1], repeat = n**2): A = [list(x[k*n:(k + 1)*n]) for k in range(n)] if abs(np.linalg.det(A)) > 10**(-3): i = sum(A[k].count(1) for k in range(n)) j = n**2 - i dico[(i, j)] = dico.get((i, j), 0) + 1 formule = '' for key, value in dico.items(): formule += str(value) + '*' + 'p^%s*(1-p)^%s' %(key[0], key[1]) + ' + ' return(formule[:-2])
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... -
Peut-être tu peux remplir la matrice progressivement. Commencer par la première colonne. Puis la deuxième, et tester si elle n'est pas colinéaire à la première. Puis la troisième, et tester si elle n'est pas engendré par la famille constituée de la première et de la deuxième, etc... En effet, si les deux premières colonnes sont liées, ce n'est pas la peine de continuer (de même si les trois premières sont liées, etc...). Cela ira peut-être plus vite pour $n=5$ ou $n=6$. Pour $n=4$, ce n'est pas sûr car le programme sera plus compliqué.
-
Pour savoir si les premières colonnes sont liés, tu peux utiliser le pivot de Gauss. Et garder en mémoire calcul du pivot des $k-1$ premières colonnes, pour calculer le pivot des $k$ premières.
-
Voici le nombre de matrices inversibles $6 \times 6$ en fonction du nombre de $1$:
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 -
Concernant la première colonne, on peut supposer que les $k$ premières coordonnées sont $1$, et les suivantes $0$ et multiplier le nombre de matrices obtenues par $C^k_n$.
-
Bonjour Alban_,
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!$. -
Bonjour Marco, je n'ai pas eu le temps de réfléchir à ta suggestion de remplir la matrice progressivement et d'utiliser le pivot de Gauss, ça m'intéresse de voir comment tu as mis en oeuvre cela.
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. -
Si $M=(X_{ij})_{1\leq i,j\leq n}$ avec les $X_{ij}$ indépendants et Bernoulli de moyenne $p$, on peut conjecturer que $$f(p)=\Pr(\det M\neq 0)= n!\,p^n(1-p)^{n-1}Q_n(p),$$ où $Q_n$ est un polynôme de degré $(n-1)^2$ tel que $Q_n(0)=1,\ Q_n(1)=n,$ car vrai pour $n\leq 6.$ Pour justifier $ f(p)\sim_{p\to 0}n!\,p^n$ on appelle $P_n$ le groupe des matrices de permutations. Alors
$$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. -
@Alban_: en effet, pour $n=6$, si il y a moins de six $1$, il y a forcément une colonne de zéros, donc la matrice sera non inversible.
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. -
@P: je n'ai pas compris pourquoi $f(p)$ est inférieur à la proba de la réunion des $A_{\sigma}$ ? J'imagine que tu utilises la formule qui donne le déterminant à l'aide des permutations, mais je ne vois pas pourquoi si on est dans l'un au moins des $A_{\sigma}$, alors la matrice est inversible ? On pourrait être dans deux $A_{\sigma}$ exactement, une fois pour une permutation paire et une fois pour une permutation impaire et le déterminant serait nul.
@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. -
$\det M\neq 0$ entraîne qu'il existe au moins un $\sigma$ tel que $\prod_i^nX_{i,\sigma(i)}\neq 0$ et donc $f(p)\leq \sum_{\sigma}\Pr(A_{\sigma}).$
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}.$$ -
Merci de l'explication, je prenais les choses à l'envers
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 23
+18 Invités