Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.