Adjacency Matrices & Walks

Label the vertices of a graph with integers 1 through n. The adjacency matrix A is an n×n matrix where entry A_{ij} = 1 if there is an edge from vertex i to vertex j, and A_{ij} = 0 otherwise. For an undirected graph the matrix is symmetric (A_{ij} = A_{ji}). For a directed graph (digraph), rows represent the source and columns the destination, so A need not be symmetric. Self-loops are recorded on the main diagonal. Example: for the graph with vertices {1,2,3,4} and undirected edges {1-2, 1-3, 2-3, 3-4}, the adjacency matrix is: A = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]. Always check: the sum of row i equals the degree of vertex i.

The central theorem: the (i,j) entry of A^k gives the number of walks of length exactly k from vertex i to vertex j. For example, A^2_{ij} = Σ_m A_{im}·A_{mj}, which counts intermediate vertices m that are neighbours of both i and j — precisely the walks i→m→j of length 2. To find all walks of length 2 in the four-vertex example, compute A² by standard matrix multiplication. The diagonal entry A²_{ii} equals the degree of vertex i (number of triangles times 2 for length-2 closed walks). To count walks of length 3, compute A³ = A²·A. This works for any k, making the algorithm extremely efficient using repeated squaring: A^8 = (A^4)^2 requires only 3 multiplications instead of 7.

In many real networks, edges carry weights: road distances, transmission probabilities, or hyperlink counts. The weighted adjacency matrix W has W_{ij} = w_{ij} (the weight of edge i→j) and W_{ij} = 0 if no edge exists. Powers of W still count paths, but now (W^k)_{ij} accumulates the sum of products of weights along all k-step walks from i to j. In a road network where weights are distances, (W^2)_{ij} gives the sum of all 2-hop path lengths from i to j — useful for finding minimum or average detours.

A transition matrix (also called a stochastic matrix) is formed by normalising each row of a weighted adjacency matrix so that each row sums to 1. Define T_{ij} = W_{ij} / (Σ_k W_{ik}). Each entry T_{ij} is the probability of moving from vertex i to vertex j in one random step. A probability vector p (a row vector where all entries are non-negative and sum to 1) represents the current distribution over vertices. After one step the distribution is p·T; after k steps it is p·T^k. Under mild conditions (the graph is connected and aperiodic), the distribution converges to a unique stationary vector π satisfying π·T = π regardless of starting point. Finding π is an eigenvector problem: π is the left eigenvector of T corresponding to eigenvalue 1.

PageRank models the internet as a directed graph where pages are vertices and hyperlinks are directed edges. The web has roughly 60 billion pages. Google's original algorithm (Brin & Page, 1998) builds a transition matrix from the link structure: if page i has L_i outgoing links, then T_{ij} = 1/L_i for each linked page j (and 0 otherwise). The PageRank vector π is the stationary distribution of this Markov chain — intuitively, π_i is the fraction of time a random web surfer spends on page i. Because some pages have no outbound links ('dangling nodes'), the raw matrix is modified using a damping factor d ≈ 0.85: M = d·T + (1-d)·(1/n)·J, where J is the n×n all-ones matrix. This guarantees convergence. PageRank is computed iteratively: start with π^(0) = (1/n, 1/n, …, 1/n) and repeatedly apply π^(t+1) = π^(t)·M until convergence, which typically takes 50–100 iterations for the full web.

• A — Adjacency matrix (dimensionless): An n×n matrix with A_{ij}=1 if an edge joins vertex i to vertex j, and 0 otherwise.
• k — Walk length (dimensionless (integer)): The number of edges traversed; equivalently the exponent to which A is raised.
• i, j — Vertex indices (dimensionless): Row and column indices identifying the starting and ending vertices of the walks.
• m_1, \ldots, m_{k-1} — Intermediate vertices (dimensionless): The sequence of vertices visited along the walk between i and j.

Problem. Consider the directed graph with 3 vertices and edges: 1→2, 2→3, 3→1, and 1→3. (a) Write the adjacency matrix A. (b) Compute A² and interpret the entry (A²)_{13}. (c) How many walks of length 3 start and end at vertex 1?

Answer. A² = [[1,0,1],[1,0,0],[0,1,0]]; there is 1 walk of length 2 from vertex 1 to vertex 3 (namely 1→2→3); there is 1 walk of length 3 from vertex 1 back to vertex 1 (namely 1→2→3→1).

• Matrix Multiplication — Computing A^k to count k-length walks requires repeated matrix multiplication; understanding the row-times-column dot product is essential.
• Eigenvalues and Eigenvectors — The PageRank stationary vector is a left eigenvector of the transition matrix corresponding to eigenvalue 1, directly linking graph theory to spectral linear algebra.
• Markov Chains — Transition matrices built from weighted graphs define Markov chains; the long-run stationary distribution is the basis of PageRank and network analysis.
• Shortest Path Algorithms (Dijkstra, Floyd-Warshall) — Weighted adjacency matrices are the input to shortest-path algorithms; understanding walk-counting illuminates why matrix-based approaches like Floyd-Warshall work.
• Introduction to Graph Theory: Vertices, Edges, and Degrees — Adjacency matrices encode the fundamental graph-theoretic concepts of vertices and edges; degree sequences appear directly on the row sums of A.