Les puissances de la matrice comptent les chemins

Démonstration par récurrence sur la longueur $k$ :

• Initialisation ($k=1$) : $(M^1)[i][j]=M[i][j]$, qui vaut bien 1 si l'arc $i\to j$ existe (un chemin de longueur 1) et 0 sinon.
• Hérédité : Supposons la propriété vraie pour la longueur $k$. Par définition du produit matriciel : $$(M^{k+1})[i][j]=\sum _{\ell \in S}(M^k)[i][\ell ]\times M[\ell ][j]$$ Chaque terme $(M^k)[i][\ell ]\times M[\ell ][j]$ comptabilise le nombre de chemins de longueur $k$ allant de $i$ à $\ell$, prolongés par l'arc final $\ell \to j$ si celui-ci existe (soit le nombre de chemins de longueur $k+1$ reliant $i$ à $j$ d'avant-dernier sommet $\ell$). La sommation sur l'ensemble des sommets intermédiaires $\ell$ possibles fournit la totalité des chemins de longueur $k+1$, validant l'hypothèse au rang $k+1$.