Algebraic Graph Theory Summary

Graph Theory · Axiom Academy

SUMMARY Algebraic Graph Theory Let's review how matrices and linear algebra unlock powerful insights into graph structure, connectivity, and spectral properties. Adjacency Matrix A : Entry A[i,j] = 1 if vertices i and j are adjacent, 0 otherwise Symmetric for undirected graphs: A[i,j] = A[j,i] reflects the bidirectional nature of edges Encodes graph structure: Converts the visual graph into a mathematical object amenable to linear algebra techniques Foundation for computation: Enables efficient algorithms and spectral analysis through matrix operations Walk counting: Entry A k [i,j] counts the number of walks of length k from vertex i to vertex j Diagonal entries: A k [i,i] counts closed walks (cycles) of length k starting and ending at vertex i Matrix multiplication: Each multiplication extends walks by one more edge, accumulating all possible paths Applications: Connectivity analysis, shortest paths (unweighted), and network reachability Definition: L = D - A , where D is the degree matrix (diagonal) and A is the adjacency matrix Degree matrix D : Diagonal matrix with D[i,i] = deg(v i ) , the degree of vertex i Row sums are zero: Each row of L sums to zero, making the all-ones vector an eigenvector with eigenvalue 0 Encodes graph structure: Captures both adjacency (edges) and vertex degrees in a single matrix, revealing connectivity patterns Eigenvalues and eigenvectors: The spectrum of L (its eigenvalues) reveals deep structural properties of the graph

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