Eigenvalues of Graphs

Graph Theory · Axiom Academy

Understanding graph spectra and the eigenvalues of adjacency and Laplacian matrices Definition: The spectrum of a graph G is the multiset of eigenvalues of its adjacency matrix A (or Laplacian matrix L), counting multiplicities. For a graph with n vertices, the adjacency matrix A is an n × n symmetric matrix where A ij = 1 if vertices i and j are adjacent, and 0 otherwise. We denote the eigenvalues as λ 1 ≥ λ 2 ≥ ... ≥ λ n , ordered from largest to smallest. A fundamental property of graph spectra follows from linear algebra: Theorem: Since both the adjacency matrix A and Laplacian matrix L are real symmetric matrices, all their eigenvalues are real numbers. This is a consequence of the Spectral Theorem for symmetric matrices. Moreover, these matrices can be diagonalized by orthogonal matrices, meaning there exists an orthonormal basis of eigenvectors. 3. Sum of Eigenvalues: The Trace The trace of a matrix (sum of diagonal entries) equals the sum of its eigenvalues: For the adjacency matrix A of a simple graph, the diagonal entries are all 0 (no self-loops), so: Property: For a simple graph, tr(A) = 0, therefore the sum of all eigenvalues equals 0. This means positive eigenvalues must be balanced by negative eigenvalues (or zeros). 4. The Largest Eigenvalue (Spectral Radius) The largest eigenvalue λ 1 , called the spectral radius , reveals information about the graph's structure: Lower bound: λ 1 ≥ δ(G), where δ(G) is the minimum degree

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