Path Counting with Matrix Power

Adjacency matrix power counts walks of exact length between vertices.

Try this in Python

adj = [[0, 1], [1, 0]]

def mul(a, b):
    return [[sum(a[i][k] * b[k][j] for k in range(2)) for j in range(2)] for i in range(2)]

print(mul(mul(adj, adj), adj))

Key takeaways

• Walks allow revisiting nodes—paths do not; different structure.
• Modulo walks use same power with mod mul.
• Exponentiate sparse graphs with doubling on adjacency lists specialized.