THE ADJACENCY MATRIX the graph as a matrix — and its powers count the walks
Write a graph as a matrix A where A[i][j] = 1 if there is an edge from i to j. This is more than storage — it turns graph questions into linear algebra. The striking fact: the entry (A²)[i][j] counts the walks of length 2 from i to j, and in general Aⁿ counts walks of length k — because matrix multiplication sums over every intermediate node. (Walks, not paths: vertices may repeat — counting length-k paths is #P-hard.) Reachability, triangle-counting, and Google’s original PageRank (the dominant eigenvector of a graph matrix) all flow from this. Here there are exactly 2 length-2 walks from node 0 to node 3 (via node 1 and via node 2 — both also paths), and none from 0 to 4.
THE TECHNIQUE (Aⁿ)[i][j] = number of length-k walks from i to j
The demo computes A²[0][3] — the number of length-2 walks from node 0 to node 3 — which is 2 (via 1 and via 2): live demo
HISTORY & CREDIT adjacency matrix · Aⁿ walk counts
“A matrix is just a way to store the edges.” — its powers count walks, turning graph questions into linear algebra. cited
the matrix · A[i][j]=1 for an edge i→j — the graph as a table. the powers · (Aⁿ)[i][j] = number of length-k walks — multiplication sums over intermediates. the reach · reachability, triangle counts, PageRank’s eigenvector — graphs as linear algebra.
A graph written as a matrix whose squares and powers count its walks — combinatorics as multiplication. encoding
RECOMMEND FOR I-13 the length-2 walks, on the compiler
On the canonical compiler, A²[0][3] = 2 (the walks 0-1-3 and 0-2-3), and A²[0][4] = 0:
$ i13 run nw_adjacencymatrix.i13 # (A^2)[i][j] = length-2 walks
RUN OK · 386 step(s) · peak stack 25 · call depth 6
walk_0_3 = 2 -- via node 1 and via node 2
walk_0_4 = 0
two_walks = 1
Recommend as a NULL — an encoding + a theorem. The adjacency matrix is a representation of the graph (B44), and “Aⁿ counts length-k walks” is a theorem (B39) that follows from the definition of matrix multiplication. Its powers are forall-pinned by the graph. No new invariant. NULL — the graph as linear algebra, walk-counts and all.