1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.

    Thanks!
     
  2. jcsd
  3. Oct 24, 2011 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Why Does This Adjacency Matrix Theorem Work?
  1. Why does this work? (Replies: 4)

Loading...