Le cycle à quatre sommets

La matrice. Chaque sommet est relié à ses deux voisins sur le cycle : $$A=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right).$$

Le carré. Le coefficient $(1,1)$ vaut $0+1+0+1=2=\mathrm{deg}(1)$ ; le coefficient $(1,2)$ vaut $0\times 1+1\times 0+0\times 1+1\times 0=0$ ; le coefficient $(1,3)$ vaut $0+1+0+1=2$. En poursuivant : $$A^2=\left(\begin{array}{cccc}2& 0& 2& 0\\ 0& 2& 0& 2\\ 2& 0& 2& 0\\ 0& 2& 0& 2\end{array}\right).$$

Le cube. $A^3=A^{2}A$. Première ligne : $(2,0,2,0)$ contre les colonnes de $A$ donne $0$, $2+2=4$, $0$, $2+2=4$. Par symétrie du cycle, $$A^3=\left(\begin{array}{cccc}0& 4& 0& 4\\ 4& 0& 4& 0\\ 0& 4& 0& 4\\ 4& 0& 4& 0\end{array}\right).$$

Les réponses. $(A^3{)}_{11}=0$ : aucune chaîne de longueur $3$ de $1$ vers $1$. $(A^3{)}_{13}=0$ : aucune de $1$ vers $3$. $(A^3{)}_{12}=4$ : quatre de $1$ vers $2$, par exemple $1-2-1-2$, $1-4-1-2$, $1-2-3-2$, $1-4-3-2$.

Le motif. Répartissons les sommets en deux camps : $\{1,3\}$ et $\{2,4\}$. Chaque arête relie un camp à l'autre — aucune ne reste à l'intérieur d'un camp. Une chaîne change donc de camp à chaque pas : après un nombre impair de pas elle est dans l'autre camp, après un nombre pair dans celui du départ. Les zéros de $A^2$ et de $A^3$ ne sont donc pas un accident de calcul : ils sont la marque de cette alternance.