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.

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?"