An adjacency matrix of a graph is a data structure that encodes the relationship between
the vertices and edges of the graph. For a graph with n vertices, the adjacency matrix has
n rows and n columns. The vertices must be put in an (arbitrary) order from 1 to n;
each row and column of the matrix then represents a distinct vertex.
If two vertices i and
j have an edge between them, the
i,j th entry of the matrix is 1.
If they don't, i,j th entry of the matrix is 0.
It is convenient to think of the adjacency
matrix as encoding not edges, but the neighbor relationship between two vertices.
Formally, the adjacency matrix G with vertices v ∈ V(G) and edges e ∈ E(G)
is given by:
$$a_{ij} = \begin{cases}
1 & \text{if } v_i v_j \in E(G) \\
0 & \text{if } v_i v_j \notin E(G) \\
\end{cases}$$
For the example graph G on the right, the adjacency matrix is:
$$ A_G = \left[ {\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 & 0
\end{array} } \right] $$
Now let's define a walk. A walk is an finite way of getting from one vertex to another
(or back to the same vertex). You are allowed to repeat edges and vertices. A walk
can even be no edges at all. The length of a walk is the number of edges traversed
during the walk, counting revisits.
An an example, there is a walk of length 4 from node B to node D.
Because the existence of a walk of length 1 between two vertices is the same as
the neighbor relationship between two vertices, the adjacency matrix also encodes
all the walks of length 1 in a graph. With this in mind, let us ask the following
question:
What does the adjecency matrix squared encode?
$$ A^2 = \left[ {\begin{array}{cccccc}
3 & 1 & 2 & 1 & 2 & 2 \\
1 & 3 & 2 & 2 & 1 & 2 \\
2 & 2 & 5 & 2 & 2 & 2 \\
1 & 2 & 2 & 3 & 2 & 1 \\
2 & 1 & 2 & 2 & 3 & 1 \\
2 & 2 & 2 & 1 & 1 & 0
\end{array} } \right] $$
Let's examine the entry $$A_{3,2} = A_{C,B} = 2$$
Matrix multiplication here is the product is obtained by multiplying term-by-term
the entries of the 3rd row and the 2nd column and summing those products. Its the dot product.
$$
\begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} \cdot
\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} =
\begin{pmatrix} 1 + 0 + 0 + 0 + 1 + 0 \end{pmatrix} = 2
$$
The left vector above represents the neighbors of C.
The right vector above represents the neighbors of B.
By taking the dot product, only entries where both are not zero are represented in the sum.
Therefore, this dot product represents the number of common neighbors between B
and C. Since two vertices have a common neighbor if
and only if a 2-walk exists between them,
this matrix entry is also the number of 2-walks between B
and C.
Now that we know that A2
encodes the number of 2-walks betwwen any two vertices in a graph, it is natural
to ask if A3
encodes 3-walks and if An encodes n-walks.
Theorem:
The i,j th entry of the kth power of the adjacency matrix of a graph G is the number of different
walks of length k in G between nodes i and j.
Our base case here is k=0, or the matrix of walks of length one. This is the adjacency matrix
by definition.
Now we need to prove that if our theorem is true for k, then it must always be true for k+1.
Let's split a k-length walk from i to j up into a walk of length one
from i to one of its neighbors l and a walk of length k-1
from l to j. Assuming our theorum is correct for k-1, this number
of k-walks from i to j would be:
$$
\sum_{\{v_i, v_l\} \in E} a_{lj}^{k-1} = \sum_{l=1}^n a_{il} a_{lj}^{k-1} = a_{ij}
$$
We are summing all the possible k-1-walks associated with each neighbor
across all neighbors to get all possible k-walks from the starting node.
This last summations give us matrix multiplication.
Intuitively, we can think of it as finding common nodes between the path of length one and
the k-1 path.
Therefore, k-1 being true
implies its successors k, k+1, etc. and the proof
by induction is complete.
The adjacency matrix and its squares of the graph to the right are as follows:
$$ A = \left[ {\begin{array}{cccccc} 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{array} } \right] A^2 = \left[ {\begin{array}{cccccc} 4 & 2 & 0 & 1 & 1 & 0 \\ 2 & 2 & 0 & 0 & 1 & 0 \\ 0 & 0 & 2 & 2 & 1 & 1 \\ 1 & 0 & 2 & 3 & 1 & 1 \\ 1 & 1 & 1 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{array} } \right] A^3 = \left[ {\begin{array}{cccccc} 2 & 1 & 6 & 7 & 5 & 4 \\ 1 & 0 & 4 & 5 & 2 & 2 \\ 6 & 4 & 0 & 1 & 2 & 0 \\ 7 & 5 & 1 & 2 & 4 & 1 \\ 5 & 2 & 2 & 4 & 2 & 1 \\ 4 & 2 & 0 & 1 & 1 & 0 \end{array} } \right] $$