Les triangles se lisent sur $A^3$

Ce que compte le coefficient. Par le théorème des puissances, $(A^3{)}_{ii}$ est le nombre de chaînes de longueur $3$ de $i$ à $i$, c'est-à-dire de suites $i\to j\to k\to i$ avec $a_{ij}=a_{jk}=a_{ki}=1$.

Les trois sommets sont distincts. Le graphe est sans boucle, donc $a_{ii}=0$ : cela interdit $j=i$ et $k=i$, et interdit aussi $j=k$ puisque $a_{jj}=0$. Ainsi $\{i,j,k\}$ est un ensemble de trois sommets deux à deux adjacents : un triangle contenant $i$.

Le compte. Réciproquement, un triangle $\{i,j,k\}$ fournit exactement deux telles chaînes : $i\to j\to k\to i$ et $i\to k\to j\to i$, les deux sens de parcours. D'où $$(A^3{)}_{ii}=2\times \#\{\text{triangles contenant }i\}.$$

Vérification sur le graphe complet à quatre sommets. Chaque sommet y appartient à $3$ triangles, et le calcul donne $(A^3{)}_{ii}=6=2\times 3$. En ajoutant les $n$ coefficients diagonaux, chaque triangle est compté six fois — deux sens, trois sommets.

Le point à retenir. Un motif du graphe devient un coefficient de matrice : compter des configurations, c'est multiplier des matrices.