Why Does This Adjacency Matrix Theorem Work?

  • #1
physicsguy101
19
0
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!
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
43,021
970
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.
 
  • #3
physicsguy101
19
0
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:

Suggested for: Why Does This Adjacency Matrix Theorem Work?

Replies
4
Views
358
  • Last Post
Replies
3
Views
486
  • Last Post
Replies
3
Views
238
  • Last Post
Replies
3
Views
519
  • Last Post
Replies
1
Views
370
Replies
9
Views
764
Replies
2
Views
895
Replies
0
Views
518
Replies
36
Views
3K
Top