Matrices surprenantes et graphes de Moore

bs · May 2008

[Titre modifié un an plus tard; ancien titre: "Des matrices surprenantes." ]

Coucou,

A)

> C'est en faisant le problème ENS 1986 - Groupe A - 2ème épreuve, dans le livre de problèmes corrigé ENS - Ellipses que j'ai rencontré ces matrices;
Les auteurs Rosaz et Zeitoun parlent de "résultat final surprenant."

> Une matrice $M$ carrée à $n$ lignes, avec $n \geq 2$ vérifie la propriété (P) si les 5 conditions suivantes sont remplies:
1) $M=(m_{ij})$ est une matrice symétrique réelle.
2) La diagonale de $M$ est nulle.
3) Chaque ligne de $M$ comporte $d$ coefficients égaux à $1$ et $n-d$ nuls, avec $d \geq 2$
4) Si $m_{ij}=0$ et $i \neq j$ alors il existe un seul indice $k$ pour lequel on a la double égalité $m_{ik}=m_{jk}=1$
5) Si $m_{ij}=1$ alors il n'existe aucun indice $k$ pour lequel on a la double égalité $m_{ik}=m_{jk}=1$.

C)

> On démontre alors entre autre, que:
1) $n=d^2+1$
2) Il n'existe de telles matrices que pour $n=5, 10, 50, 3250$, correspondant à $d=2, 3, 7, 57$.
3) calcul du spectre...

D)--> Questions:
1) quelle est l'origine de ces matrices ?
2) Portent-elles un nom ?
3) Connaissez-vous un lien ou un livre qui parle de ces objets ?

Un gogol de mercis.

Amicalement.

john_john · May 2008

Bonjour,
est-ce en relation avec les graphes de Moore ?

Graphes de Moore

Cordialement j__j

bs · May 2008

Bonjour j_j,

Effectivement: (2,3,7,57), (10, 50, 3250), à ce niveau là, m'est avis que c'est plus qu'une coïncidence

J'espère que ces graphes figurent dans le cours d'alea, sinon j'emprunterai un livre de théorie des graphes en bibliothèque.

Je te renouvelle mon gogol de mercis

Si je ne comprends pas, certainement que je frapperai de nouveau à la porte.

Amicalement.

john_john · May 2008

De rien , BS !

Cordialement, j__j

bs · January 2010

Bonsoir,

Ces "matrices surprenantes" (il n'y en a que quatre qui possèdent la propriété (P) explicitée dans le premier message) sont réapparues dans l'énoncé CCP- PSI - 2006 - Epreuve 2, soit vingt ans après le sujet ENSET 1986. L'énoncé est sur le site UPS et dans Ellipses CCP-Tome 12.

Graphes de Moore: http://fr.wikipedia.org/wiki/Graphe_de_Moore

[Edit: je n'ai pas envie de jouer à a qui vous savez... certainement existe-t-il une liaison entre ces matrices surprenantes et les graphes de Moore de notre ami j___j que je ne saurais expliquer.]

Amicalement.

bs · January 2010

Bonjour,

[Je vais un peu, moi-aussi, jouer à Pablo]
[Les quatre dernières lignes et la PJ refusent de s'afficher, j'ouvre donc un nouveau message pour terminer, compris, il y avait un symbole pour cent dans un lien, donc résolu sans l'aide d'un GM

]

Merci Jean-Denis

En plus des délicieux moments passés à la lecture de ton livre, il est vrai que les fils ouverts par notre grand ami pappus nous y invitent régulièrement, tu m'as permis de comprendre l'origine obscure de ces deux énoncés ENSET 1986 et CCP 2006. Je n'aime pas, mais alors pas du tout, ignorer l'origine d'un énoncé même si je prends plaisir à résoudre le problème !

Ces quatre seules matrices qui vérifient les propriétés des deux énoncés sont exactement les matrices d'adjacence des graphes de Moore de diamètre 2, et donc vérifiant le théorème d'Hoffman–Singleton .

Wikipedia: "Le théorème d'Hoffman–Singleton stipule que tout graphe de Moore de maille 5 (et donc de diamètre 2) ne peut avoir qu'un degré 2, 3, 7 ou 57. Il s'agit du pentagone (degré 2 et 5 sommets), du graphe de Petersen (degré 3 et 10 sommets) et du graphe d'Hoffman-Singleton (degré 7 et 50 sommets). L'existence d'un graphe de Moore de maille 5 et de degré 57 n'est pas connue; un tel graphe aurait 3 250 sommets."

Ces deux problèmes démontrent donc le théorème d'Hoffman–Singleton sans le dire ! puis étudient quelques propriétés de ces matrices d'adjacence. Peut-être que les concepteurs de ces deux énoncés sont effectivement partis de ce théorème d'Hoffman–Singleton pour rédiger leur énoncé.

Correspondance:
-> l'ordre $n$ de la matrice carrée de l'énoncé correspond au nombre de sommets $n$ du graphe de Moore, et,
-> le nombre $\delta$ de coefficients égaux à $1$ sur chaque ligne de la matrice correspond au degré $d$ du graphe de Moore.

Les quatre cas:

1 ---> pentagone $(n=5, d=2)$ : ben, c'est le pentagone convexe "normal" : Pentagone_(figure)
[le pentagramme est également un graphe de Moore possédant 5 sommets mais de degré 4, et de diamètre 1]

2 --> graphe de Petersen $(n=10, d=3)$, clair sur le dessin: http://fr.wikipedia.org/wiki/Graphe_de_Petersen

3 -> graphe d'Hoffman-Singleton $(n=50, d=7)$, moins clair sur le schéma: http://fr.wikipedia.org/wiki/Graphe_d\'Hoffman-Singleton mais mieux ici: http://mathworld.wolfram.com/Hoffman-SingletonGraph.html

4 -> Wikiki: L'existence d'un graphe de Moore de maille 5, de degré 57 et de 3250 sommets n'est pas connue... avis aux amateurs.

En PJ, l'énoncé CCP 2006:

olib · January 2010

Merci BS et à ceux qui ont participé à ce fil, j'ai fait cette épreuve (ENS 86 ) il y a bien longtemps et je me suis toujours demandé ce qu'il y avait dessous.

Comme je suis beaucoup moins intéressé par l'algèbre que par l'analyse, je n'ai pas fait l'effort de me documenter. Mais c'est vrai que tu as dégotté un lièvre là...

Dans le genre étonnant, si qulqu'un peut me donner la source de ce problème, il y a ULM 84, première épreuve: http://concours-maths-cpge.fr/fichiers.php.
Ca parle entre autres de parties épanouies et de partie coincées...

P.S: Un sujet de topologie qui devrait plaire à CC à tout point de vue.:D

bs · January 2010

Bonsoir,

Olib, merci pour tes encouragements, sache que je suis également très content d'avoir ainsi réveillé de délicieux souvenirs de ta tendre jeunesse

C'est l'année dernière que j'avais fait le problème ENS 1986, puis commencé ce fil avec la réponse de notre ami Jean-Denis...qui est à l'origine du succès de cette enquête. Il y a quelques semaines, descente chez Gibert à Marseille avec razzia sur les Ellipses: Mines, Centrale, CCP,... avec découverte de ce nouvel énoncé CCP 2006 sur ces quatre bizarres matrices; là, cette fois, j'ai passé un peu plus de temps sur la théorie des graphes (que je n'ai jamais eu la chance d'étudier avec un professeur en chair et en os au tableau) pour enfin comprendre l'origine de ces matrices surprenantes.

Ici la preuve du théorème d'Hoffman-Singleton paru dans IBM Journal of Research and Development, vol. 5, no 4, 1960, p. 497–504 http://wikiwix.com/cache/url=http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf ; les auteurs utilisent effectivement les matrices d'adjacence pour démontrer l'existence des quatre seuls graphes de Moore de diamètre 2.

Vraiment magique ce forum.

[Je viens de lire ULM 84 au vocabulaire surprenant, merci à toi, ce sera pour une autre fois, direction dodo...]

Amicalement.