A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example,

$$\begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$

for the graph

Diagonal Elements

The diagonal elements are 0 for graphs without loops.

$A[u,v]$ is the length-1 path between node $u$ and $v$. If $A[u,v]=0$, there is no path. If $A[u,v]=1$, we have a length-1 path.

For $A^2[u,v]$, we have

$$A^2_{uv} = \sum_k A_{uk}A_{kv}.$$

This is the length-2 path. If node $u$ or node $v$ has no neighbors, $A^2_{uv}=0$. If there is an edge $(u, \tilde u)$ and $(\tilde u, v)$, we get one path, and $A_{u\tilde u}A_{\tilde uv}=1$.

When we sum over all the possible values of index $k$, i.e., $\sum_k A_{uk}A_{kv}$, we get the total number of length-2 path between $u$ and $v$.

This idea is extrapolated to the $i$th power of the adjacency matrix.

Published: by ;

Lei Ma (2021). 'Graph Adjacency Matrix', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-adjacency-matrix/.