interpreting the power of adjacency matrix Given a directed graph $G$, and let $A$ be $G$'s adjacency matrix, whose $(i,j)$-entry is 1 when there is an edge from $i$ to $j$. Is there any interpretative meaning of the $(i,j)$-entry of the matrix $(A^5\cdot{(A^T)}^5)$ and the matrix $({(A^T)}^8\cdot{A}^8)$, respectively ?

The intuition comes easily if you stop thinking of the matrix elements as _switches_ for the edges. Instead, **think of $(A)_{ij}$ as the number of distinct walks of length $1$ from $i$ to $j$**. Try! ;)

Note this also allows you to account naturally for looping, directed, undirected and multiple edges if you don't restrict to a symmetric matrix with null diagonal and elements in $\\{0,1\\}$.

What happens if you take a power of the adjacency matrix? Multiplying the matrices you are essentially concatenating walks, so...

> $(A^k)_{ij}$ is the number of distinct walks of length $k$ from $i$ to $j$.

Transposing the matrix simply flips the edges. So..

> $((A^T)^kA^l)_{ij}$ is the number of distinct walks of length $k+l$ starting from $i$, doing $k$ steps against the direction of the edges and $l$ steps following them finally arriving at $j$. The meaning of $(A^k(A^T)^l)_{ij}$ is similar.