Exercices Alternatifs

Les matrices au secours des réseaux

\begin{matrix}c \\ ◯ \end{matrix}2001 Frédéric Le Roux (copyleft LDL : Licence pour Documents Libres).

Sources et figures: matrices et reseaux aeriens/.
Version imprimable: matrices et reseaux aeriens.pdf

Algèbre linéaire. DEUG deuxième année. Angle pédagogique : À quoi ça sert.

Objectifs et commentaires. Le but de ce problème est de faire découvrir les graphes (qui font partie des objets mathématiques les plus simples), et de montrer comment l’algèbre linéaire intervient de manière essentielle dans leur étude (ce qui peut paraître surprenant au premier abord). Le problème choisi, une histoire abracadabrante de réseau aérien, est évidemment à prendre sur le mode ludique plus que comme un exemple d’application concrète... Au passage, on visite les polynômes de matrices, la trigonalisation, et un brin d’arithmétique. Ce problème a été donné en devoir à la maison. Les étudiants l’ont trouvé difficile : notamment, la question portant sur le lien entre le graphe et les matrices (propriété QFTM) a été très peu abordée ; peutêtre faudrait-il la rédiger autrement. Mais on a eu l’impression que le problème les avait motivés, et qu’ils avaient assez bien compris la démarche globale (ce qui est malheureusement plutôt rare...).

Références. Ce problème est adapté de la page Web http://www.cut-the-knot.org, rubrique No 4 “arithmetic and algebra”, puis rubrique 125 “When the counting gets tough, the tough counts on mathematics : an airline problem”. Il semble provenir de l’étude de certains “groupes de permutations” ; on obtient notamment l’existence du graphe à 50 sommets à partir d’un certain groupe de matrices dont les coefficients appartiennent à un corps ne contenant qu’un nombre fini d’éléments...

I. Introduction

On considère le problème suivant : Etant données n villes, on veut mettre en place un réseau aérien entre ces villes satis-

faisant les conditions suivantes :

(1) Le nombre de vols directs issus d’une ville donnée est le même pour toutes les villes du réseau ;

(2) Un voyageur qui voudra aller d’une ville donnée à une autre en faisant au plus une escale aura exactement une possibilité d’un tel voyage.

Pour quelles valeurs de n peut-on concevoir un tel réseau ?

– Pour n = 2, il y a une solution simple : un vol direct entre les deux villes.

– Pour n = 3 ou 4 il n’existe pas de réseau satisfaisant ces conditions.

– Pour n = 5 une solution est donnée par le graphe suivant :

[figure: V_{1}; V_{5}; V_{2}; V_{4}; V_{3}]

Ici le nombre de vols issus d’une ville donnée est égal à 2 quelle que soit la ville du réseau, donc la première condition est bien vérifiée ; et entre deux villes il y a soit un vol direct, soit un vol avec une escale, mais pas les deux, et la deuxième condition est également satisfaite.

– Il n’y a pas non plus de solution pour n = 6, 7, 8, ou 9. Par contre il y a une solution pour n = 10, réalisée par le graphe suivant :

[figure: V_{6}; V_{10}; V_{1}; V_{7}; V_{5}; V_{2}; V_{4}; V_{3}; V_{9}; V_{8}]

On peut ici aussi vérifier que les deux conditions sont remplies, bien que ce soit un peu plus long (on admettra ceci dans la suite).

La modélisation mathématique du réseau aérien est un objet appelé graphe : un graphe est constitué d’un ensemble de sommets S = {V_{1}, ⋯, V_{n}} et d’un ensemble d’arêtes entre certains des sommets (de manière précise, une arête est un sousensemble de S à deux éléments, ces deux éléments sont appelés extrémités de l’arête). Par exemple, le premier graphe a pour sommets {V_{1}, V_{2}, V_{3}, V_{4}, V_{5}} et pour arêtes {{V_{1}, V_{2}}, {V_{2}, V_{3}}, {V_{3}, V_{4}}, {V_{4}, V_{5}}, {V_{5}, V_{1}}}.

On doit aussi définir ce qu’est un chemin : c’est une suite finie de sommets du graphe dans laquelle deux sommets successifs sont reliés par une arête dans le graphe : par exemple, toujours dans le premier graphe, (V_{1}) , (V_{1}, V_{2}) , (V_{3}, V_{2}, V_{1}, V_{2}, V_{3}, V_{4}) sont trois chemins de longueur respective 1, 2 et 6 (la longueur du chemin est le nombre d’arêtes parcourues, autrement dit le nombre d’éléments de la suite moins 1).

Voici la stratégie proposée : dans toute la suite du problème, on suppose qu’on a un entier n et un graphe G à n sommets vérifiant les hypothèses suivantes (formalisation des hypothèses (1) et (2) du problème de l’introduction) : (H1) il existe un entier k tel que pour tout sommet V_{i} du graphe, le nombre d’arêtes dont V_{i} est une extrémité est égal à k. (H2) pour tout couple de sommets distincts V_{i} et V_{j} du graphe, il existe un et un seul chemin allant de V_{i} à V_{j} qui soit de longueur 1 ou 2. Nous allons chercher à exploiter les deux hypothèses pour montrer que n ne peut prendre que quelques valeurs (par exemple, on va montrer que n ne peut pas être égal à 3, 4, 6, 7, 8, ou 9, comme on l’a affirmé dans l’introduction).

II. Liens avec les matrices

Soit A la matrice d’incidence du graphe, qui indique les liaisons entre les villes : A est la matrice carrée, de taille n, dans laquelle on a mis un 1 à la case i, j si il y a une arête entre V_{i} et V_{j}, et un 0 sinon.

Montrer que la matrice A est symétrique (c’est-à-dire égale à sa transposée).

Question 1. Compter le nombre de chemins

Le but de cette question est de comprendre et de montrer la propriété suivante^{1} :

Propriété QFTM (Qui Fait Tout Marcher) L’entrée i, j de la matrice A^{d} est égale au nombre de chemins de longueur d entre V_{i} et V_{j}.

a. Un exemple pour comprendre Ecrire la matrice d’incidence M du graphe à 5 sommets dessiné dans l’introduction. Calculer M^{2} ; quels sont les 2 chemins de longueur 2 de V_{1} à V_{1} ? Calculer M^{3} et tester également la propriété QFTM sur quelque cases de M^{3} (quels sont les 3 chemins de V_{1} à V_{2} ? etc...).

b. Preuve Montrer la propriété QFTM par récurrence sur d (on pourra commencer par traiter le cas d = 2, mais ça n’est pas obligatoire).

III. Application à notre problème.

Question 1.

Comment se traduit la propriété (H1) sur la matrice A? On appelle (P1) cette propriété matricielle.

Question 2.

Montrer que la propriété (H2) entraîne l’égalité matricielle :

A^{2} + A − (k − 1)I = J (P 2)

où I est la matrice identité et J la matrice ne contenant que des 1.

1C’est une propriété générale des graphes, c’est-à-dire qu’elle n’utilise pas les hypothèses (H1) et (H2).

IV. Où l’on utilise la valeur propre la plus simple

Question 1. Un lien entre les valeurs propres de A et celle de J

Soit λ une valeur propre de A; montrer que λ^{2} + λ − (k − 1) est une valeur propre de J.

Question 2. Utilisation

Trouver une valeur propre et un vecteur propre^{2} de A en utilisant la propriété (P1). En déduire la relation :

n = k^{2} + 1.

Résoudre le problème pour n ≤ 16, c’est-à-dire dire pour chacun des entiers de 1 à 16 s’il existe ou non un réseau aérien vérifiant les deux conditions.

Donner aussi quelques valeurs de n pour lesquelles on ne peut pas conclure pour l’instant. Combien reste-t-il d’entiers pour lesquels on ne peut pas encore conclure ?

V. Où les autres valeurs propres ont aussi leur mot à dire

Question 1. Valeurs propres de J...

Trouver les valeurs propres de J et leurs multiplicités (remarque : on peut le faire sans calcul !).

Question 2. ...et de A

Montrer que A possède au plus 3 valeurs propres distinctes : k mise à part, on notera les deux autres λ_{+} et λ_{−}, et m_{+} et m_{−} leur multiplicité respective.

Question 3. Multiplicité de k

Montrer que le sous-espace propre Ker(A − kI) est de dimension 1. Peut-on en déduire la multiplicité de k? Montrer que k est de multiplicité 1 en admettant (provisoirement) le lemme suivant :

Lemme 1 La multiplicité de λ comme valeur propre de M est égale à la multiplicité de P (λ) comme valeur propre de P (M), où M est une matrice de M_{n}(ℂ) et P un polynôme, par exemple le polynôme X^{2} + X − (k − 1).

Question 4. Relations

Trouver deux relations reliant m_{+}, m_{−} et k (indications : utiliser la question précédente, et la trace). Montrer notamment que (m_{+} − m_{−})\sqrt{4k − 3} = k^{2} − 2k.

VI. On y est presque !

Question 1. Le cas simple

On suppose que m_{+} = m_{−}. Trouver les valeurs possibles de k, puis de n.

2Pour les profs : faut-il leut donner le vecteur propre ? ? ?

On suppose dans la suite que m_{+} ≠ m_{−}.

Question 2. Où l’on voit que 4k − 3 est un carré parfait.

Un carré parfait est un entier de la forme p^{2}, où p est un autre entier. En utilisant le lemme suivant :

Lemme 2 Soit b un entier ; si b n’est pas un carré parfait, alors \sqrt{b} ∉ ℚ.

montrer que 4k − 3 est un carré parfait (propriété *). En déduire que n ne peut pas être égal à 17.

Question 3. Astuce et arithmétique

Soit p tel que p^{2} = 4k − 3. Montrer que 4k − 3 divise 4^{4} × (k^{2} − 2k)^{2}. Trouver un polynôme Q tel que Q(4k) = 4^{4} × (k^{2} − 2k)^{2}. En déduire que p^{2} = 4k − 3 divise Q(3). Autrement dit :

4k − 3 divise 225 (propriété **) .

Montrer rapidement qu’il n’y a qu’un nombre fini d’entiers n répondant au problème initial.

Trouver tous les k vérifiant les propriétés (*) et (**).

Question 4. Conclusion

On admet que n = 3250 est impossible^{3}, mais que par contre il existe un graphe vérifiant (H1) et (H2) avec 50 sommets. Résoudre totalement le problème.

VII. Les lemmes

Question 1.

Montrer le lemme 1 : on peut commencer par le cas d’une matrice triangulaire T, et chercher le lien entre les éléments de la diagonale de T et ceux de P (T). Pour le cas général, utiliser le fait que M est trigonalisable.

Question 2.

Montrer le lemme 2 en vous inspirant de la preuve de l’irrationnalité de \sqrt{2}.

VIII. Question subsidiaire

Proposer une méthode pour s’assurer du fait que le graphe à 10 sommets dessiné en introduction a les propriétés voulues.

3La preuve se trouve dans l’article de M. Aschbacher, The non-existence of rank three permutation groups of degree 3250 and subdegree 57, J. Algebra 19 (1971), 538-540.