Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why Does This Adjacency Matrix Theorem Work?

  1. Oct 24, 2011 #1
    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.

  2. jcsd
  3. Oct 24, 2011 #2


    User Avatar
    Science Advisor

    Your "Ar" is, of course, the power, [itex]A^r[/itex].

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

    Each term in that sum will be either 0 or 1 and 1 only if both [itex]a_{ik}[/itex] and [itex]a_{kj}[/itex] 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 [itex]A^r= A^{r-1}A[/itex] you can apply an inductive argument: [itex](a^{r})_{ij}= \sum_k (a^{r-1})_{ik}a_{kj}[/itex] sums the number of paths of length r-1 from i to k and then from k to j.
  4. Oct 24, 2011 #3
    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.
    Last edited: Oct 24, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook