Suppose you have a non-directed graph, represented through its adjacency matrix. How would you discover how many paths of length 
link any two nodes?
For example, in the graph aside there is one path of length 2 that links nodes A and B (A-D-B). How can this be discovered from its adjacency matrix?
It turns out there is a beautiful mathematical way of obtaining this information! Although this is not the way it is used in practice, it is still very nice. In fact, Breadth First Search is used to find paths of any length given a starting node.
PROP. 
holds the number of paths of length from node 
to node 
.
Let’s see how this proposition works. Consider the adjacency matrix of the graph above:
![\[(A)_{ij} \ \ \begin{matrix} \textbf{-} & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} \\ \textbf{A} & 0 & 1 & 1 & 1 & 0 \\ \textbf{B} & 1 & 0 & 0 & 1 & 1 \\ \textbf{C} & 1 & 0 & 0 & 1 & 0 \\ \textbf{D} & 1 & 1 & 1 & 0 & 1 \\ \textbf{E} & 0 & 1 & 0 & 1 & 0 \\ \end{matrix}\]](https://quickmathintuitions.org/wp-content/ql-cache/quicklatex.com-75ae955c5217bca47cf3425ce2b29e15_l3.png "Rendered by QuickLaTeX.com")
With 
we should find paths of length 2. So we first need to square the adjacency matrix:
![\[(A^2)_{ij} \ \ \begin{matrix} \textbf{-} & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} \\ \textbf{A} & 3 & 1 & 1 & 2 & 2 \\ \textbf{B} & 1 & 3 & 2 & 2 & 1 \\ \textbf{C} & 1 & 2 & 2 & 1 & 1 \\ \textbf{D} & 2 & 2 & 1 & 4 & 1 \\ \textbf{E} & 2 & 1 & 1 & 1 & 2 \\ \end{matrix}\]](https://quickmathintuitions.org/wp-content/ql-cache/quicklatex.com-2f3f46e51f6ad295233fa377eb65c25e_l3.png "Rendered by QuickLaTeX.com")
Back to our original question: how to discover that there is only one path of length 2 between nodes A and B? Just look at the value 
, which is 1 as expected! Another example: 
, because there are 3 paths that link B with itself: B-A-B, B-D-B and B-E-B.
This will work with any pair of nodes, of course, as well as with any power to get paths of any length.
Why does it work?
Now to the intuition on why this method works. Let’s focus on 
for the sake of simplicity, and let’s look, again, at paths linking A to B. , which is what we look at, comes from the dot product of the first row with the second column of 
:
![\[(A^2)_{12} = \sum_{j=1}^N A_{1j} A_{j2} = (0, 1, 1, 1, 0) \cdot (1, 0, 0, 1, 1)\]](https://quickmathintuitions.org/wp-content/ql-cache/quicklatex.com-3cb3c9c2685648c6c9d8bdd8745b1085_l3.png "Rendered by QuickLaTeX.com")
Now, the result is non-zero due to the fourth component, in which both vectors have a 1. Now, let us think what that 1 means in each of them:
– first row -> first node (A) is linked to fourth node (D)
– second column -> second node (B) is linked to fourth node (D)
So overall this means that A and B are both linked to the same intermediate node, they share a node in some sense. Thus we can go from A to B in two steps: going through their common node.
The same intuition will work for longer paths: when two dot products agree on some component, it means that those two nodes are both linked to another common node. For paths of length three, for example, instead of thinking in terms of two nodes, think in terms of paths of length 2 linked to other nodes: when there is a node in common between a 2-path and another node, it means there is a 3-path!
