Le carré de la matrice d'une chaîne

La matrice. Chaque sommet n'est relié qu'à ses voisins immédiats dans la chaîne : $$A=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right).$$

Le carré. Le coefficient $(i,j)$ de $A^2$ est la ligne $i$ de $A$ multipliée par la colonne $j$ de $A$. Par exemple, ligne $2$ contre colonne $2$ : $(1,0,1,0)\cdot (1,0,1,0)=1+0+1+0=2$. En poursuivant, $$A^2=\left(\begin{array}{cccc}1& 0& 1& 0\\ 0& 2& 0& 1\\ 1& 0& 2& 0\\ 0& 1& 0& 1\end{array}\right).$$

La diagonale. Elle vaut $(1,2,2,1)$. Or les degrés sont $\mathrm{deg}(1)=1$, $\mathrm{deg}(2)=2$, $\mathrm{deg}(3)=2$, $\mathrm{deg}(4)=1$ : ils coïncident.

Pourquoi. Une chaîne de longueur $2$ d'un sommet vers lui-même consiste à emprunter une arête puis à revenir par la même : il y en a donc autant que d'arêtes issues de ce sommet, soit $\mathrm{deg}(i)$. Le calcul le confirme : $(A^2{)}_{ii}={\sum }_k{a}_{ik}{a}_{ki}={\sum }_k{a}_{ik}^2={\sum }_k{a}_{ik}=\mathrm{deg}(i)$, puisque $a_{ik}$ vaut $0$ ou $1$ et que la matrice est symétrique.

Une lecture hors diagonale. $(A^2{)}_{13}=1$ : il y a une chaîne de longueur $2$ de $1$ à $3$, à savoir $1-2-3$. Et $(A^2{)}_{14}=0$ : aller de $1$ à $4$ demande au moins trois arêtes.