\Annee{2001}
\Titre{Les matrices au secours des r\'eseaux}
\Date{2001/10/01}
\Niveau{\DEUGii}
\Auteur{Fr\'ed\'eric \textsc{Le Roux}}
\Theme{\AlgLin}
\ThemesSecondaires{Graphes, R\'eduction des endomorphismes} 
\AnglePedagogique{\AQuoiCaSert} 
\AnglesSecondaires{\Ludique} 


\Objectif{Le but de ce probl\`eme est de faire d\'ecouvrir les graphes
(qui font partie des objets math\'ematiques les plus simples), et de
montrer comment l'alg\`ebre lin\'eaire intervient de mani\`ere
essentielle dans leur \'etude (ce qui peut para\^itre surprenant au
premier abord). Le probl\`eme choisi, une histoire abracadabrante de
r\'eseau a\'erien, est \'evidemment \`a prendre sur le mode ludique
plus que comme un exemple d'application concr\`ete...  Au passage, on
visite les polyn\^omes de matrices, la trigonalisation, et un brin
d'arithm\'etique.  Ce probl\`eme a \'et\'e donn\'e en devoir \`a la
maison. Les \'etudiants l'ont trouv\'e difficile~: notamment, la
question portant sur le lien entre le graphe et les matrices
(propri\'et\'e QFTM) a \'et\'e tr\`es peu abord\'ee~; peut-\^etre
faudrait-il la r\'ediger autrement. Mais on a eu l'impression que le
probl\`eme les avait motiv\'es, et qu'ils avaient assez bien compris
la d\'emarche globale (ce qui est malheureusement plut\^ot rare...).

\paragraph{R\'ef\'erences.}  Ce probl\`eme est adapt\'e de la
page Web
 \href{http\deuxpoints//www.cut-the-knot.org}{http\deuxpoints//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'\'etude de certains ``groupes de permutations'' ; on obtient
notamment l'existence du graphe \`a 50 sommets \`a partir d'un certain
groupe de matrices dont les coefficients appartiennent \`a un corps ne
contenant qu'un nombre fini d'\'el\'ements...}

\begin{exo}

\newtheorem{lemm}{Lemme}

\partie{Introduction} On consid\`ere le probl\`eme suivant~:

{\it Etant donn\'ees $n$ villes, on veut mettre en place un r\'eseau
a\'erien entre ces villes satisfaisant les conditions suivantes~:

(1) Le nombre de vols directs issus d'une ville donn\'ee est le m\^eme
    pour toutes les villes du r\'eseau ;

(2) Un voyageur qui voudra aller d'une ville donn\'ee \`a une autre en
    faisant au plus une escale aura exactement une possibilit\'e d'un
    tel voyage.

Pour quelles valeurs de $n$ peut-on concevoir un tel r\'eseau ?}


\begin{itemize}
\item Pour $n=2$, il y a une solution simple~: un vol direct entre les
deux villes.

\item Pour $n=3$ ou $4$ il n'existe pas de r\'eseau satisfaisant ces
conditions.

\item Pour $n=5$ une solution est donn\'ee par le graphe suivant~:

$$
\xymatrix{ & & V_1 \ar@{-}[rrd]& & \\ V_5 \ar@{-}[rru]& & & & V_2
\ar@{-}[ldd] \\ \\ & V_4 \ar@{-}[uul] & & V_3 \ar@{-}[ll]& }
$$

Ici le nombre de vols issus d'une ville donn\'ee est \'egal \`a $2$
quelle que soit la ville du r\'eseau, donc la premi\`ere condition est
bien v\'erifi\'ee ; et entre deux villes il y a soit un vol direct,
soit un vol avec une escale, mais pas les deux, et la deuxi\`eme
condition est \'egalement satisfaite.

\item 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\'ealis\'ee par le
graphe suivant~:
$$
\xymatrix{ & & & V_6 \ar@{-}'[d]\ar@{-}'[drrr]\\ V_{10}\ar@{-}'[dr]\ar@{-}'[urrr] &
& & V_1 \ar@{-}'[rddd]& & & V_7\ar@{-}'[dl]\ar@{-}'[ddddl] \\ & V_5 \ar@{-}'[rrrr]& &
& & V_2 \ar@{-}'[llldd] \\ \\ & & V_4 \ar@{-}'[ruuu] & & V_3 \ar@{-}'[llluu]& \\ &
V_9\ar@{-}'[ur]\ar@{-}'[luuuu] & & & & V_8\ar@{-}'[ul]\ar@{-}'[llll] }
$$
On peut ici aussi v\'erifier que les deux conditions sont remplies,
bien que ce soit un peu plus long (on admettra ceci dans la suite).
\end{itemize}


\paragraph{}
La mod\'elisation math\'ematique du r\'eseau a\'erien est un objet
appel\'e \emph{graphe}~: un graphe est constitu\'e d'un ensemble de
sommets ${\cal S}=\{V_1, \cdots , V_n \}$ et d'un ensemble d'ar\^etes
entre certains des sommets (de mani\`ere pr\'ecise, une ar\^ete est un
sous-ensemble de $\cal S$ \`a deux \'el\'ements, ces deux \'el\'ements
sont appel\'es \emph{extr\'emit\'es} de l'ar\^ete). Par exemple, le
premier graphe a pour sommets $\{V_1,V_2,V_3,V_4,V_5\}$ et pour
ar\^etes $\{ \{V_1,V_2\},
\{V_2,V_3\},\{V_3,V_4\},\{V_4,V_5\},\{V_5,V_1\} \}$.

On doit aussi d\'efinir ce qu'est un \emph{chemin}~: c'est une suite
finie de sommets du graphe dans laquelle deux sommets successifs sont
reli\'es par une ar\^ete 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
\emph{longueur} du chemin est le nombre d'ar\^etes parcourues,
autrement dit le nombre d'\'el\'ements de la suite moins 1).

\begin{center}
\noindent
\framebox{
\parbox{0.9\textwidth}{
Voici la strat\'egie propos\'ee~: dans toute la suite du
probl\`eme, on suppose qu'on a un entier $n$ et un graphe $\cal G$ \`a
$n$ sommets v\'erifiant les hypoth\`eses suivantes (formalisation des
hypoth\`eses (1) et (2) du probl\`eme de l'introduction)~:

(H1) il existe un entier $k$ tel que pour tout sommet $V_i$ du graphe,
le nombre d'ar\^etes dont $V_i$ est une extr\'emit\'e est \'egal \`a
$k$.


(H2) pour tout couple de sommets \emph{distincts} $V_i$ et $V_j$ du
graphe, il existe un et un seul chemin allant de $V_i$ \`a $V_j$ qui
soit de longueur $1$ ou $2$.


Nous allons chercher \`a exploiter les deux hypoth\`eses pour montrer
que $n$ ne peut prendre que quelques valeurs (par exemple, on va
montrer que $n$ ne peut pas \^etre \'egal \`a 3, 4, 6, 7, 8, ou 9,
comme on l'a affirm\'e dans l'introduction). 
}}
\end{center}





\partie{Liens avec les matrices}

Soit $A$ la \emph{matrice d'incidence} du graphe, qui indique les
liaisons entre les villes~: $A$ est la matrice carr\'ee, de taille
$n$, dans laquelle on a mis un 1 \`a la case $i,j$ si il y a une
ar\^ete entre $V_i$ et $V_j$, et un $0$ sinon.

Montrer que la matrice $A$ est sym\'etrique (c'est-\`a-dire \'egale
\`a sa transpos\'ee).


\qst{Compter le nombre de chemins}
Le but de cette question est de comprendre et de montrer la
propri\'et\'e suivante\footnote{C'est une propri\'et\'e g\'en\'erale
des graphes, c'est-\`a-dire qu'elle n'utilise pas les hypoth\`eses
(H1) et (H2).}~:
\begin{enonce1*}{Propri\'et\'e QFTM (Qui Fait Tout Marcher)}
L'entr\'ee $i,j$ de la matrice $A^{d}$ est \'egale au nombre
de chemins de longueur $d$ entre $V_i$ et $V_j$.
\end{enonce1*}




\sq[Un exemple pour comprendre]
Ecrire la matrice d'incidence $M$ du graphe \`a 5 sommets dessin\'e
dans l'introduction. Calculer $M^{2}$ ; quels sont les 2 chemins de
longueur 2 de $V_1$ \`a $V_1$ ? Calculer $M^{3}$ et tester \'egalement
la propri\'et\'e QFTM sur quelque cases de $M^{3}$ (quels sont les 3
chemins de $V_1$ \`a $V_2$ ? etc...).



\sq[Preuve]
 Montrer la propri\'et\'e QFTM par r\'ecurrence sur $d$ (on pourra
 commencer par traiter le cas $d=2$, mais \c{c}a n'est pas
 obligatoire).


\partie{Application \`a notre probl\`eme.}

\qst{} Comment se traduit la propri\'et\'e (H1) sur la matrice $A$ ? On
appelle (P1) cette propri\'et\'e matricielle.

\qst{} Montrer que la propri\'et\'e (H2) entra\^\i ne
l'\'egalit\'e matricielle~:
$$
A^{2}+A-(k-1)I=J \ \ \ \ \ \ \ \ \ \ \ (P2)
$$
o\`u $I$ est la matrice identit\'e et $J$ la matrice ne contenant que
des 1.





\partie{O\`u l'on utilise la valeur propre la plus simple}


\qst{Un lien entre les valeurs propres de $A$ et celle de $J$} Soit
$\lambda$ une valeur propre de $A$ ; montrer que
$\lambda^{2}+\lambda-(k-1)$ est une valeur propre de $J$.


\qst{Utilisation}

Trouver une valeur propre et un vecteur propre\footnote{Pour les profs
: faut-il leut donner le vecteur propre ???}  de $A$ en utilisant la
propri\'et\'e (P1).  En d\'eduire la relation~:
$$n=k^{2}+1.
$$


\emph{ R\'esoudre le probl\`eme pour $n \leq 16$, c'est-\`a-dire dire
pour chacun des entiers de 1 \`a 16 s'il existe ou non un r\'eseau
a\'erien v\'erifiant 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 ?




%%%%%%%%%%%%
\partie{O\`u les autres valeurs propres ont aussi leur mot \`a dire}

\qst{Valeurs propres de $J$...}
Trouver les valeurs propres de $J$ et leurs multiplicit\'es
 (remarque~:  on peut le faire sans calcul~!).

\qst{...et de $A$}
Montrer que $A$ poss\`ede au plus 3 valeurs propres distinctes~: $k$
mise \`a part, on notera les deux autres $\lambda_+$ et $\lambda_-$,
et $m_+$ et $m_-$ leur multiplicit\'e respective.



\qst{Multiplicit\'e de $k$} Montrer que le sous-espace propre
$\mathrm{Ker}(A-k I)$ est de dimension $1$. Peut-on en d\'eduire la
multiplicit\'e de $k$ ?  Montrer que $k$ est de multiplicit\'e $1$ en
admettant (provisoirement) le lemme suivant~:
\begin{enonce1}{Lemme}{}\label{lem:poly-matrice}
  La multiplicit\'e de $\lambda$ comme valeur propre de $M$ est
  \'egale \`a la multiplicit\'e de $P(\lambda)$ comme valeur propre de
  $P(M)$, o\`u $M$ est une matrice de ${\cal M}_n(\bbC)$ et $P$ un
  polyn\^ome, par exemple le polyn\^ome $X^{2}+X-(k-1)$.
\end{enonce1}


\qst{Relations}
Trouver deux relations reliant $m_+$, $m_-$ et $k$ (indications~:
utiliser la question pr\'ec\'edente, et la trace). Montrer notamment
que $(m_+-m_-)\sqrt{4k-3}=k^{2}-2k$.

%%%%%%%%%%%%%
\partie{On y est presque !}
\qst{Le cas simple} On suppose que $m_+=m_-$. Trouver les valeurs
possibles de $k$, puis de $n$.

\paragraph{}
\emph{On suppose dans la suite que $m_+ \neq m_-$.}

\qst{O\`u l'on voit que $4k-3$ est un carr\'e parfait.}  Un
\emph{carr\'e parfait} est un entier de la forme $p^{2}$, o\`u $p$ est
un autre entier. En utilisant le lemme suivant~:
\begin{enonce1}{Lemme}{}\label{lem:carre-parfait}
  Soit $b$ un entier ; si $b$ n'est pas un carr\'e parfait, alors
  $\sqrt b \not \in \bbQ$.
\end{enonce1}
montrer que $4k-3$ est un carr\'e parfait
(propri\'et\'e *). \emph{En d\'eduire que $n$ ne peut pas \^etre \'egal \`a
$17$.}



\qst{Astuce et arithm\'etique} Soit $p$ tel que $p^{2}=4k-3$.  Montrer
que $4k-3$ divise $4^{4}\times (k^{2}-2k)^{2}$. Trouver un polyn\^ome
$Q$ tel que $Q(4k)=4^{4}\times (k^{2}-2k)^{2}$. En d\'eduire que
$p^2=4k-3$ divise $Q(3)$. Autrement dit~:
$$
\mathbf{ 4k-3 \mbox{ \bf divise } 225 \mbox{ \bf (propri\'et\'e **)
 }}.
$$

Montrer rapidement qu'il n'y a qu'un nombre fini d'entiers $n$
r\'epondant au probl\`eme initial.

 Trouver tous les $k$ v\'erifiant les propri\'et\'es (*) et (**).




\qst{Conclusion} On admet que $n=3250$ est impossible\footnote{La
preuve se trouve dans l'article de M. Aschbacher, \emph{The
non-existence of rank three permutation groups of degree 3250 and
subdegree 57}, J. Algebra 19 ({\bf 1971}), 538-540.}, mais que par
contre il existe un graphe v\'erifiant (H1) et (H2) avec $50$
sommets. \emph{R\'esoudre totalement le probl\`eme}.



\partie{Les lemmes}
\qst{} Montrer le lemme~\ref{lem:poly-matrice}~: on peut commencer par le cas d'une
matrice triangulaire $T$, et chercher le lien entre les \'el\'ements
de la diagonale de  $T$ et ceux de $P(T)$. Pour le cas g\'en\'eral,
utiliser le fait que $M$ est trigonalisable. 


\qst{} Montrer le lemme~\ref{lem:carre-parfait} en vous inspirant de la preuve de
l'irrationnalit\'e de $\sqrt 2$. 


\partie{Question subsidiaire} Proposer une m\'ethode pour s'assurer du
fait que le graphe \`a $10$ sommets dessin\'e en introduction a les
propri\'et\'es voulues.





\end{exo}

