Symétrie des puissances

Le graphe étant non orienté, $A$ est symétrique : ${}^{t}A=A$. Or la transposition renverse l'ordre d'un produit, donc

$${}^t(A^d)=({}^{t}A{)}^d=A^d.$$

(Le renversement est sans effet ici : tous les facteurs sont égaux.) Donc $A^d$ est symétrique.

Interprétation. $(A^d{)}_{ij}$ compte les chaînes de longueur $d$ de $i$ à $j$. La symétrie dit qu'il y en a autant de $i$ vers $j$ que de $j$ vers $i$ — ce qui est évident sur le graphe : il suffit de parcourir la chaîne à l'envers, et c'est licite précisément parce que les arêtes n'ont pas de sens. Sur un graphe orienté, $A$ n'est pas symétrique et cette correspondance tombe.