要素数が素数の重みなし有向グラフ理論の隣接行列のべき乗

図1
図1のような、向きが決まっていて重みが平等な五角形のグラフがあるとします。


ある点が「反時計回りにだけ」隣に移動するための行列Aなので、Aは図1のように定義されます。

このAのべき乗は何を意味するのかといいますと
図2


図3
たとえば3乗だったら「3つの辺で成り立っているパーツはどこにいくつあるのか」
といった情報を教えてくれます。(図3)

図4

向きがない、すなわち矢印が両方の向きについた「無向グラフ」や、
「重みを考慮したグラフ」だともう少し複雑になるのですが


このようにモデルを非常に単純化することで、
モデルと行列の意味をリンクさせてシンプルに考えることができます。

図5

興味深いのは、5乗つまり1周すると5次の単位行列になって、元に戻ることです。
この組み合わせは、自分自身のところに戻る、たった1パターンしかないことがわかります。(図5)

また、この行列には部分的に単位行列やゼロ行列が含まれているため
適切に分割することで、要素数が大きな素数でも、
2次行列に帰着させて手計算で計算が行えるのがメリットです。