Represent networks with adjacency matrices and use matrix powers to count walks of a given length between vertices.

What this dot point is asking

You must build an adjacency matrix from a graph, interpret its entries, and use $A^2$ or higher powers to count multi-step connections.

Building an adjacency matrix

A network (graph) has vertices joined by edges. Its adjacency matrix $A$ is square, with one row and one column per vertex. Each entry counts the edges joining that pair of vertices.

For an undirected network the matrix is symmetric (a link from $A$ to $B$ is also a link from $B$ to $A$). For a directed network the entry in row $i$, column $j$ counts only edges pointing from $i$ to $j$, so the matrix need not be symmetric.

Counting two-step walks with matrix powers

A walk of length 2 uses two edges, passing through one intermediate vertex. The entry of $A^2$ in row $i$, column $j$ counts exactly these two-edge walks from $i$ to $j$.

Reading the diagonal and the row sums

The diagonal entries of $A^2$ count two-step walks that return to the starting vertex. In the example each diagonal entry is 2, because each town can reach two others and come straight back, giving two such loops.

Row sums of $A$ are also useful: in an undirected network the sum of row $i$ gives the degree of vertex $i$, the number of edges meeting it.

Why matrix powers count walks

The walk-counting property follows directly from how matrix multiplication works. The entry in row $i$, column $j$ of $A^2$ is the sum over every intermediate vertex $k$ of $a_{ik}a_{kj}$ - the number of edges from $i$ to $k$ times the number from $k$ to $j$. Each such product counts the two-edge routes that pass through $k$, and summing over all $k$ counts every two-step walk from $i$ to $j$. The same reasoning extends to higher powers: $A^3$ sums over all pairs of intermediate vertices, so it counts three-step walks, and so on. Understanding this explains why the technique works rather than treating it as a rule to memorise.

Directed networks and dominance

For a directed network, where edges have a direction, the adjacency matrix is generally not symmetric, and its powers count directed walks that respect the arrows. A common application is a dominance matrix for a round-robin competition, where $a_{ij} = 1$ if player $i$ beat player $j$. The row sums of $A$ give first-order dominance (direct wins), and the row sums of $A + A^2$ combine direct wins with "wins over someone who beat someone", giving an overall ranking. This is a standard SACE context for adjacency matrices beyond simple road maps.

Direct plus indirect connections

A common task is to add matrices to combine route lengths. For example, $A + A^2$ gives the number of routes of length 1 or 2 between each pair of vertices, useful for asking "in how many ways can I get from P to R in at most two steps?"