Count directed walks with matrix powers

Try

A synthetic network has three labeled vertices, 0, 1 and 2. Its directed edges are 0→1, 0→2, 1→2 and 2→0. Starting at 0, how many ways can you arrive at 2 after exactly two edges? The direct edge 0→2 is not a two-edge answer. The walk 0→1→2 is an answer. Following 0→2 forces the next move to 0, so that alternative ends elsewhere.

A walk records a vertex sequence connected by directed edges. Its length counts edges, not vertices, and repeated vertices are allowed. A simple path, as used here, has no repeated vertices. Reachability asks whether a walk of some length exists. These are different questions: a zero count at one length does not settle reachability.

Predict

Encode the graph in a matrix A. Row i is the source; column j is the destination. Entry Aᵢⱼ is 1 if i→j exists and 0 otherwise. For this graph the rows are (0,1,1), (0,0,1), (1,0,0). Reading columns as sources instead would reverse all edges, so write the convention above any calculation.

Predict the count of two-edge walks from 0 back to 0. Then predict the count of zero-edge walks from 0 to 0. The first uses 0→2→0. The second uses no edge at all: staying at the initial vertex is the unique zero-edge walk. It does not imply an edge 0→0 exists.

Experiment

Use the explorer to choose endpoints and an exact length. Its labels A, B and C correspond respectively to vertices 0, 1 and 2 in this explanation. Before revealing the count, list possible intermediate vertices. Compare lengths zero, one and two. Add the optional loop at A (vertex 0) and identify a new walk that uses that loop together with an original edge. Do not assume all new walks consist entirely of new edges.

Predict a fixed-length walk count

A walk follows arrow directions and may revisit vertices. Its length is the number of edges, not the number of listed vertices. Predict the count before revealing the calculation.

Walk length0 edges1 edges2 edges3 edges4 edges5 edges6 edges Start vertexABC End vertexABC

Add a loop A → A

Current edges: A → B, A → C, B → C, C → A. Positions are schematic; line length has no numerical meaning.

The adjacency matrix has row = departure and column = arrival. Entry 1 means that directed edge exists. Entries here are counts, not transition probabilities.

Adjacency matrix A

From / to	A	B	C
A	0	1	1
B	0	0	1
C	1	0	0

Reveal walk countReset walk experiment

No count revealed. Predict the result for the selected endpoints and length.

Try A to B at length two, then at length one. Try A to A at length zero and then length two. Explain why a zero entry at one length does not settle reachability, and why a repeated-vertex walk need not be a simple path.

This bounded, temporary explorer uses three vertices and lengths zero through six. It saves no answers, awards no mastery and runs no animation.

Here is a fixed worked multiplication for the original graph, without the optional loop. In (A²)₀₂, split the walks by their intermediate vertex t:

Intermediate t	A₀ₜ	Aₜ₂	Product	Interpretation
0	0	1	0	No first edge 0→0
1	1	1	1	Walk 0→1→2
2	1	0	0	No final edge 2→2

Adding the products gives 1. Computing all endpoints yields A² with rows (1,0,1), (1,0,0), (0,1,1). Check the last row directly: from 2 the first move is to 0, then the second can end at 1 or 2. These entries are counts, not probabilities. A row can sum to more than 1, and no random edge-selection rule has been supplied.

Understand

For every nonnegative integer k, (Aᵏ)ᵢⱼ counts the walks of exactly k edges from i to j. The theorem assumes a finite directed graph with at most one edge per ordered pair; loops are permitted. Powers use ordinary integer matrix multiplication, not entrywise multiplication.

At k=0 the count is 1 when i=j and 0 otherwise. This is the identity matrix I, with ones on its diagonal and zeros elsewhere. We define A⁰=I, even when A has no loop edges or is the zero matrix.

Assume the theorem holds for k. A walk of length k+1 has a unique penultimate vertex t. Its first k edges form a walk from i to t, and its last edge is t→j. There are (Aᵏ)ᵢₜ choices for the prefix and Aₜⱼ choices for that last edge. Multiplying counts counts the choices together. Summing over t counts disjoint classes, because a single walk has only one penultimate vertex. Conversely, every counted prefix followed by that edge makes a valid walk. Thus the sum is both complete and free of double counting, and it equals the matrix entry (AᵏA)ᵢⱼ. Induction proves the claim at all lengths, including repeated visits and returns.

Now separate exact-length counting from reachability. On the directed cycle 0→1→2→0, vertex 1 is reachable from 0, but no length-two walk from 0 ends there. Testing only A² would miss that reachable pair.

For a graph on n≥1 vertices, the finite sum I+A+⋯+Aⁿ⁻¹ detects reachability when zero edges are allowed: its ij entry is positive exactly when j is reachable from i. A positive entry gives an actual walk because every summand is a nonnegative count. Conversely, for distinct reachable endpoints choose a shortest walk. If a vertex repeats, remove the segment between two occurrences; the shared vertex makes the remaining edges join correctly. This creates a shorter walk with the same endpoints, a contradiction. A shortest walk therefore uses at most n vertices and n−1 edges. For equal endpoints the zero-edge walk already suffices.

This diagonal convention matters. Every diagonal entry of the reachability sum is positive because of I; it does not certify a positive-length cycle. A directed n-cycle first returns to its starting vertex after n edges. To test positive returns, omit I and allow powers through n. A shortest positive closed walk has no repeated vertex except its endpoints, since an earlier return or internal repetition could be removed to shorten it.

Apply

Draw a fresh four-vertex graph consisting only of the cycle 0→1→2→3→0. Construct its matrix, and determine row 0 of I, A, A², A³ and A⁴ without multiplying every entry. Explain why exactly one destination is reached at each fixed length, yet every vertex is reachable within three edges. Why does the first positive diagonal count occur at length four?

For review, the successive rows are (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,0,0). The count records a deterministic route here, not an assumption that other graphs have one outgoing edge. Modify the graph by adding 0→2, then list the new length-two walks from 0. They end at 2 and 3, one each; the intermediate vertices distinguish them.

When interpreting a larger matrix, first name the counted objects. If parallel edges are distinguishable, an adjacency entry must record their number to count edge sequences; a 0/1 matrix collapses those distinctions. If entries instead represent transition probabilities, the same multiplication operation has a weighted interpretation that requires a different model and proof. Do not silently change counts into probabilities.

Continue

In the practice, prove the last-edge decomposition, repair a fixed-length reachability claim and compare parallel-edge conventions. A finite explorer can verify selected entries; the induction establishes the statement at every length. Return to the declared source-row convention whenever multiplying matrices or comparing a diagram with a table.

The next representation question is different: when do two drawings describe the same graph? A few equal walk counts can supply useful comparisons, but they do not by themselves give a vertex correspondence preserving every edge and nonedge.