Étape 1
Calculons d'abord la matrice $M^2$ en effectuant le produit matriciel $M \times M$ : $$M^2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix}$$
Étape 2
Calculons ensuite la matrice $M^3 = M^2 \times M$ : $$M^3 = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 2 & 2 \\ 2 & 0 & 0 \\ 2 & 0 & 0 \end{pmatrix} = 2M$$
Étape 3
On en déduit les puissances successives de la matrice $M$ : pour les puissances impaires, on a $M^5 = 2M^3 = 4M$ et $M^7 = 4M^3 = 8M$. Pour les puissances paires, on obtient $M^4 = M^3 \times M = 2M^2$, puis $M^6 = 2M^4 = 4M^2$ et $M^8 = 2M^6 = 8M^2$.
Étape 4
Le nombre de chemins de longueur $n$ reliant le sommet $1$ à lui-même est donné par le coefficient situé sur la première ligne et la première colonne de la matrice $M^n$, noté $(M^n)_{1,1}$.
Étape 5
Pour tout entier impair $n$, la matrice $M^n$ est proportionnelle à $M$, dont le premier coefficient diagonal est nul, donc $(M^n)_{1,1} = 0$.
Étape 6
Pour les entiers pairs : pour $n = 2$, $(M^2)_{1,1} = 2$ ; pour $n = 4$, $(M^4)_{1,1} = 2 \times 2 = 4$ ; pour $n = 6$, $(M^6)_{1,1} = 4 \times 2 = 8$ ; pour $n = 8$, $(M^8)_{1,1} = 8 \times 2 = 16$.
Étape 7
La plus petite longueur $n \ge 1$ permettant d'obtenir au moins $16$ chemins reliant le sommet $1$ à lui-même est donc $8$.
Méthode clé
Utiliser le produit matriciel pour établir une relation de récurrence sur les puissances de la matrice d'adjacence, puis identifier le coefficient $(i,j)$ de $M^n$ comme le nombre de chemins de longueur $n$ entre les sommets $i$ et $j$.
Piège à éviter
Confondre les puissances paires et impaires de la matrice, ou oublier que le nombre de chemins reliant le sommet 1 à lui-même correspond au coefficient situé sur la première ligne et la première colonne.
