Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 36 · Spectral Graph Theory

Graph Matrices and the Spectrum

Turn graphs into matrices: count walks and triangles with adjacency powers, read eigenvalues of cycles, complete and bipartite graphs, and meet cospectral graphs in NumPy.

A graph is a picture, but it is also a table of numbers. Once you write a graph as a matrix, the whole toolbox of linear algebra opens up: matrix multiplication counts walks, eigenvalues describe global structure, and eigenvectors reveal clusters. This branch is called spectral graph theory, and it powers search engines, image segmentation and network analysis. In this lesson you build the basic matrices and read information off their eigenvalues; the next two lessons use the Laplacian for connectivity and clustering.

The adjacency matrix and counting walks

For a graph with vertices 0 … n−1, the adjacency matrix A has A[i][j] = 1 if there is an edge i – j and 0 otherwise. For an undirected simple graph A is symmetric with zeros on the diagonal. You may have met adjacency matrices as a data structure in the chapter on representations; here the interest is algebraic.

The most useful fact is about powers: the entry (A^k)[i][j] is the number of walks of length k from i to j. For k = 2 this is the sum over the middle vertex, which is exactly matrix multiplication. Consequently:

  • trace(A^2) = 2·|E| (each edge is a closed walk of length 2 in two directions at each end).
  • trace(A^3) = 6·(number of triangles) (each triangle gives 6 closed walks: 3 starting points and 2 directions).
  • The graph is connected iff (I + A)^(n−1) has no zero entry.
Python Count walks, edges and triangles with matrix powers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The spectrum

The spectrum of a graph is the multiset of eigenvalues of A, sorted λ1 ≥ λ2 ≥ … ≥ λn. Because A is real and symmetric, all eigenvalues are real and the eigenvectors can be chosen orthogonal (numpy.linalg.eigh computes them). A few facts worth memorizing:

  • The sum of the eigenvalues is trace(A) = 0.
  • The largest eigenvalue satisfies average degree ≤ λ1 ≤ Δ. For a d-regular graph λ1 = d, with the all-ones vector as eigenvector.
  • If G is connected, λ1 is a simple eigenvalue and its eigenvector can be chosen with all positive entries (Perron-Frobenius).
  • A graph is bipartite iff its spectrum is symmetric about 0 (if λ is an eigenvalue, so is −λ); equivalently λn = −λ1.
  • The number of distinct eigenvalues is at least the diameter plus one.

Reading the spectrum

λ1 Between average degree and max degree
Symmetric about 0 Exactly for bipartite graphs
Sum is 0 The trace of A
Sum of cubes Six times the triangle count

Global structure from a single matrix

1 / 2

Some spectra have closed forms: the complete graph K_n has eigenvalues n−1 (once) and −1 (n−1 times); the cycle C_n has eigenvalues 2·cos(2πk/n) for k = 0 … n−1; the star K_{1,m} has ±√m and zeros.

Python Spectra of familiar graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Petersen graph has spectrum 3, 1 (×5), −2 (×4): only three distinct eigenvalues, a sign of its very high symmetry. It has no triangles because its girth is 5, and the trace of A^3 confirms it.

Cospectral graphs

Does the spectrum identify a graph? No. Two non-isomorphic graphs can have exactly the same spectrum; they are called cospectral (or isospectral). The smallest example is the star K_{1,4} and the disjoint union of a 4-cycle with an isolated vertex: both have spectrum 2, 0, 0, 0, −2, yet one is connected and the other is not. So the spectrum determines a lot (number of edges, triangles, whether it is bipartite, regularity) but not everything. Almost all trees are cospectral with another tree, while some graphs are determined by their spectrum.

Python A cospectral pair that is not isomorphic

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The degree sequences differ, so the graphs are certainly not isomorphic, even though the spectrum cannot tell them apart.

Other matrices of a graph

  • Degree matrix D: diagonal matrix of degrees.
  • Laplacian L = D − A: the star of the next lesson.
  • Normalized adjacency D^(−1/2) A D^(−1/2) and random-walk matrix D^(−1) A: used for random walks and spectral clustering.
  • Incidence matrix: rows are vertices and columns are edges; L = B Bᵀ for an oriented incidence matrix B.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does the entry (A^k)[i][j] of the k-th power of the adjacency matrix count?

    Matrix multiplication sums over intermediate vertices, so A^k counts walks (paths that may revisit vertices) of length exactly k.
  2. 2. How many triangles does a graph have if trace(A^3) = 24?

    Each triangle contributes 6 closed walks of length 3 (three starting vertices and two directions), so the count is 24 / 6 = 4.
  3. 3. What does a spectrum symmetric about zero indicate?

    Bipartite graphs have eigenvalues that come in ± pairs. The converse holds for undirected graphs as well.
  4. 4. Are two graphs with the same spectrum always isomorphic?

    The star K1,4 and C4 plus an isolated vertex have identical spectra but different structure.

Summary

  • The adjacency matrix makes graph questions algebraic: A^k counts walks, trace(A^2) = 2|E|, trace(A^3) = 6·triangles.
  • The spectrum is real; λ1 lies between the average and maximum degree and equals d for d-regular graphs.
  • A symmetric spectrum means bipartite; the sum of eigenvalues is zero.
  • Spectra reveal a lot but not everything: cospectral non-isomorphic graphs exist.

Next: The Laplacian and the Fiedler Vector