If $A$ is the adjacency matrix of a graph, why does the $(i,j)$ entry of $A^n$ give the number of $n$-step walks from $i$th vertex to $j$th vertex? Let $A$ be the adjacency matrix of some directed graph with $m$ vertices labeled as $v_1, v_2, \ldots, v_m$. So here $A_{ij} = 1$ if there is an edge from $v_i$ to $v_j$, and $A_{ij} = 0$ otherwise. By induction it is not too hard to show that $(A^n)_{ij}$ is the number of $n$-step walks from $v_i$ to $v_j$.
Why is this the case? Is there some geometric explanation, or some explanation using linear algebra? The definition of matrix multiplication comes from composition of linear maps, and it seems surprising to me to see this connection between linear maps and graphs.
 A: Another way to think of the adjacency matrix is that it can be used to "count" all of the neighbors of a particular vertex by adding along a row. Now this may seem less than useful, but if you think of that as right multiplication by $[1,1,1,\dots,1]^T$ instead, then you might be able to see how to extend this. If you assign objects to each of the vertices, then the adjacency matrix allows a vertex to combine all of the objects of its neighbors, in some particular way those objects want to be combined.
Repeatedly applying the adjacency matrix will then combine neighbors of neighbors of neighbors of etc. For example, by placing ones initially on all the vertices, you combine them by adding to get the total number of paths into a vertex (with length the number of times you apply the matrix). The statement that $A^n_{ij}$ is the number of ways to get from $i$ to $j$ is thus an extension of this idea. That is, by placing the proper initial objects on the vertices, you can keep track of not just how many paths come into a vertex but in fact where they came from.
