AHL 3.15 (HL)—Adjacency matrices and transition matrices

An adjacency matrix records which vertices are directly connected. For an unweighted graph, Aᵢⱼ=1 means an edge from i to j under the chosen row/column convention.

The entry (A^k)ᵢⱼ counts walks of length k from i to j. Matrix multiplication works because each intermediate vertex is summed over, linking consecutive steps.

If two different two-step routes connect A to C, the corresponding entry of A² is 2. In a weighted matrix, the same multiplication may represent a different quantity, so do not mix conventions.

A walk may revisit vertices; it is not automatically a simple path. Check whether the graph is directed and what the matrix entries mean.

A weighted adjacency table stores a cost, distance or time rather than just 0 or 1. A transition matrix converts each vertex's outgoing weights or links into probabilities whose relevant row or column sums to 1 under the declared convention; repeated multiplication models movement through a strongly connected graph, as in a simplified PageRank model. Do not interpret powers of a weighted cost matrix as counts of walks unless that convention is explicitly justified.