Marche sur un graphe : $M^k$ compte les chemins

Ce qu'on a le droit d'utiliser. La définition du produit $(AB{)}_{i,j}={\sum }_l{a}_{i,l}{b}_{l,j}$, la formule du binôme pour deux matrices qui commutent, et la relation $J^2=3J$ (chaque coefficient de $J^2$ est une somme de trois $1$). La stratégie du a) est une récurrence sur $k$, où la formule du produit est le dénombrement.

a) Le produit recolle les chemins. Par récurrence sur $k$. Pour $k=1$ : $m_{i,j}$ vaut $1$ s'il y a une arête de $i$ à $j$, $0$ sinon — c'est le nombre de chemins de longueur $1$. Hérédité : supposons que $(M^k{)}_{i,l}$ compte les chemins de longueur $k$ de $i$ à $l$, pour tous $i,l$. Un chemin de longueur $k+1$ de $i$ à $j$ se décompose de façon unique en un chemin de longueur $k$ de $i$ à un sommet intermédiaire $l$ (son avant-dernier sommet), suivi d'une arête de $l$ à $j$. Pour $l$ fixé, il y a $(M^k{)}_{i,l}$ choix du premier morceau et $m_{l,j}$ choix du second ($1$ ou $0$). En sommant sur $l$ : $$\#\{\text{chemins de longueur }k+1\text{ de }i\text{ aˋ }j\}=\sum _{l=1}^3(M^k{)}_{i,l}{m}_{l,j}=(M^{k}M{)}_{i,j}=(M^{k+1}{)}_{i,j}.$$ Ce qui achève la récurrence. La formule du produit n'est pas une convention : c'est le dénombrement des chemins composés.

b) Les premières puissances. Comme $J$ et $I_3$ commutent, on développe : $M^2=(J-I_3{)}^2=J^2-2J+I_3=3J-2J+I_3=J+I_3$, et $M^3=M^{2}M=(J+I_3)(J-I_3)=J^2-I_3=3J-I_3$. Donc $$M^2=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right),M^3=\left(\begin{array}{ccc}2& 3& 3\\ 3& 2& 3\\ 3& 3& 2\end{array}\right).$$ Lecture. $(M^2{)}_{1,1}=2$ : deux façons de quitter $1$ et d'y revenir en deux pas, par $2$ ou par $3$. $(M^2{)}_{1,2}=1$ : un seul chemin de longueur $2$ de $1$ à $2$, à savoir $1\to 3\to 2$. $(M^3{)}_{1,1}=2$ : les deux tours du triangle, $1\to 2\to 3\to 1$ et $1\to 3\to 2\to 1$. $(M^3{)}_{1,2}=3$ : les chemins $1\to 2\to 1\to 2$, $1\to 2\to 3\to 2$ et $1\to 3\to 1\to 2$.

c) La forme close. Montrons par récurrence que $M^k$ est de la forme ${\alpha }_{k}J+{\beta }_k{I}_3$. C'est vrai pour $k=1$ avec ${\alpha }_1=1$, ${\beta }_1=-1$. Si $M^k={\alpha }_{k}J+{\beta }_k{I}_3$, alors $$M^{k+1}=({\alpha }_{k}J+{\beta }_k{I}_3)(J-I_3)={\alpha }_k{J}^2-{\alpha }_{k}J+{\beta }_{k}J-{\beta }_k{I}_3=(3{\alpha }_k-{\alpha }_k+{\beta }_k)J-{\beta }_k{I}_3=(2{\alpha }_k+{\beta }_k)J-{\beta }_k{I}_3.$$ Donc ${\alpha }_{k+1}=2{\alpha }_k+{\beta }_k$ et ${\beta }_{k+1}=-{\beta }_k$. De ${\beta }_1=-1$ on tire ${\beta }_k=(-1{)}^k$, puis ${\alpha }_{k+1}=2{\alpha }_k+(-1{)}^k$. Vérifions la formule ${\alpha }_k=\frac{2^k-(-1{)}^k}{3}$ par récurrence : pour $k=1$, $\frac{2+1}{3}=1$ ; et si elle vaut au rang $k$, $${\alpha }_{k+1}=\frac{2^{k+1}-2(-1{)}^k}{3}+(-1{)}^k=\frac{2^{k+1}-2(-1{)}^k+3(-1{)}^k}{3}=\frac{2^{k+1}+(-1{)}^k}{3}=\frac{2^{k+1}-(-1{)}^{k+1}}{3}.$$ Donc $M^k=\frac{2^k-(-1{)}^k}{3}J+(-1{)}^k{I}_3$ pour tout $k\ge 1.$ On retrouve $M^2=J+I_3$ (${\alpha }_2=1$) et $M^3=3J-I_3$ (${\alpha }_3=3$).

d) Circuits et contrôle. Le nombre de circuits de longueur $k$ au départ d'un sommet est le coefficient diagonal $(M^k{)}_{i,i}={\alpha }_k+{\beta }_k=\frac{2^k-(-1{)}^k}{3}+(-1{)}^k=\frac{2^k+2(-1{)}^k}{3}$ : $2$ pour $k=2$, $2$ pour $k=3$, $6$ pour $k=4$ (on vérifie : $(M^4{)}_{1,1}=(M^2{M}^2{)}_{1,1}=2\cdot 2+1\cdot 1+1\cdot 1=6$). La somme d'une ligne de $M^k$ vaut $3{\alpha }_k+{\beta }_k=2^k-(-1{)}^k+(-1{)}^k=2^k$. Pourquoi : la somme de la ligne $i$ compte tous les chemins de longueur $k$ partant de $i$, toutes arrivées confondues ; or à chaque pas on a exactement deux choix (les deux autres sommets), donc $2^k$ chemins. Le calcul matriciel et le dénombrement se confirment l'un l'autre.

Le point délicat. « Chemin » signifie ici suite d'arêtes consécutives, avec répétitions de sommets permises : l'aller-retour $1\to 2\to 1$ est compté, et c'est pour cela que $(M^2{)}_{1,1}=2$ et non $0$. Compter les chemins sans répétition ne se fait pas par un produit matriciel — c'est un problème d'une tout autre difficulté.

Ce que l'exercice installe. Le produit matriciel est l'opération de composition des chemins, et c'est la raison pour laquelle les réseaux, les moteurs de recherche et les chaînes de Markov se calculent en algèbre linéaire. Le chapitre 13 nommera la chose : $M$ est la matrice d'une application linéaire, et $M^k$ celle de sa composée $k$ fois. Et la méthode « $M^k={\alpha }_{k}J+{\beta }_{k}I$ » — chercher les puissances dans un espace de matrices stable par produit, engendré par deux matrices qui commutent — est celle de l'exercice 7.