Properties of Adjacency Matrix

Graph Theory · Axiom Academy

LESSON Properties of Adjacency Matrix Exploring how matrix powers count walks, reveal connectivity patterns, and encode fundamental graph structure through linear algebra. A k [i,j] = number of walks of length k from vertex i to vertex j A walk allows repeated vertices and edges Each entry counts all possible paths of exactly k steps This remarkable theorem connects graph theory to linear algebra. When we multiply the adjacency matrix by itself k times, each entry tells us how many different ways we can walk from one vertex to another using exactly k edges. Let's visualize this for k = 1, 2, and 3. The trace of a matrix is the sum of its diagonal entries. For powers of the adjacency matrix, this has a beautiful interpretation related to cycles and closed walks in the graph. tr(A k ) = total number of closed walks of length k A closed walk starts and ends at the same vertex tr(A 2 ) = 2|E| (each edge traversed both ways) tr(A 3 ) counts all triangles (times 6, as they can be traversed 6 ways) 3. Row and Column Sums Give Degrees The row and column sums of the adjacency matrix directly encode vertex degrees, providing instant access to this fundamental graph property. For undirected graphs: row sum = column sum = degree of vertex For directed graphs: row sum = out-degree, column sum = in-degree Sum of all entries = 2|E| for undirected, |E| for directed 4. Detecting Paths and Connectivity

This is the written version of the interactive lesson above. See the full Graph Theory course.