Why Does This Adjacency Matrix Theorem Work?

[physicsguy101]

I'm curious as to why the following theorem always works with a graph of vertices and the number of steps between the vertices when placed into an adjacency matrix.


If A is the adjacency matrix of a graph G (with vertices v1,…, vn), the (i, j)-entry of Ar represents the number of distinct r-walks from vertex vi to vertex vj in the graph.


If anyone can provide any insight or explanation, I would appreciate it.

The theorem makes sense to me, but I'm just unsure mathematically why exactly it works the way it does.

Thanks!

 

[HallsofIvy]

Your "Ar" is, of course, the power, $A^r$.

In an adjacency matrix, A, $a_{ij}$ is 1 if i is "adjacent to j- if there is a path from vertex i to vertex j- 0 otherwise. In $A^2$, $(a^2)_{ij}= \sum_k a_{ik}a_{kj}$.

Each term in that sum will be either 0 or 1 and 1 only if both $a_{ik}$ and $a_{kj}$ are 1. That is, only if there is a path from vertex i to k and a path from k to j- so there is a path going from i to k and then from k to j- a path from i to j of length 2. That sum, then, counts the number of length 2 paths from i to j.

Since $A^r= A^{r-1}A$ you can apply an inductive argument: $(a^{r})_{ij}= \sum_k (a^{r-1})_{ik}a_{kj}$ sums the number of paths of length r-1 from i to k and then from k to j.

 

[physicsguy101]

HallsofIvy, thank you very much. Your response pretty much summed up what I was looking for (sorry, no pun intended!).

I really appreciate it, and understand the concept much more clearly now. Thanks again.