[Math] Finding number of distinct walks between two vertices in a graph using Matrix Multiplication

adjacency matrixdiscrete mathematicseigenvalues-eigenvectorsgraph theorytriangles

Say, we have a graph G represented by an adjacency matrix A.

Graph G

Adjacency Matrix A

A = 0 1 1 0
    1 0 1 1
    1 1 0 1
    0 1 1 0

It is said that A^n[i][j] equals the
number of distinct walks of length [![n][2]][2] which start at vertex i and end at vertex j

A^n = A*A*A...n times

Testing for n = 2

A^2 = 2 1 1 2
      1 3 2 1
      1 2 3 1
      2 1 1 2

This says that, the number of paths of length 2, between vertex 0 and 0 is 2, which is indeed correct. The paths are 0-1-0 and 0-2-0

Testing for n = 3

 A^3 =  2 5 5 2
        5 4 5 2
        5 5 4 5
        2 5 5 2

This says that, the number of paths of length 3, between vertex 0 and 1 is 5. Are these paths 0-0-2-1, 0-1-2-1, 0-1-3-1,0-2-0-1, 0-2-1-1 and `0-2-3-1'

I would like to know the idea behind this method, and how it's working.

Best Answer

Just check the matrix multiplication formula for an individual entry:

$${A^n}_{ij} = \sum_{k=1}^v (A^{n-1})_{ik}A_{kj} $$

This translates into something like number paths from $i$ to $j$ is the sum of paths $i$ to $k$ and $k$ to $j$.

Related Question