Questions: Adjacency Matrix and Spectral Graph Theory

Question 1

What does the (i, j) entry of A³ — the cube of an adjacency matrix — represent?

• A. 1 if there is a path of length at most 3 from vertex i to vertex j, and 0 otherwise
• B. The number of walks of length 3 from vertex i to vertex j
• C. The number of triangles in the graph that contain both vertex i and vertex j
• D. The third power of the edge weight between vertices i and j

Answer: (B)

Matrix multiplication gives (A²)ᵢⱼ = Σₖ AᵢₖAₖⱼ, counting 2-step walks by summing over intermediate vertices. Extending to A³, (A³)ᵢⱼ counts all 3-step walks from i to j. Crucially, this is the number of walks (allowing revisits of vertices), not paths (which require distinct vertices) — option A confuses walks with shortest paths. Option C is related but not exact: triangle counting uses the trace of A³, not off-diagonal entries.

Question 2

A network designer measures the spectral gap (λ₁ − λ₂) of two proposed topologies: topology A has spectral gap 0.05 while topology B has spectral gap 2.3. Which is preferable for rapid information broadcast, and why?

• A. Topology A, because a small spectral gap means the network has more uniform edge distribution
• B. Topology A, because small λ₂ indicates the network has fewer bottlenecks for routing
• C. Topology B, because a large spectral gap characterizes good expanders where random walks mix quickly
• D. Topology B, because a large spectral gap means the network is nearly complete (fully connected)

Answer: (C)

A large spectral gap (topology B's 2.3) means the graph is a good expander — random walks mix rapidly, information spreads quickly, and no sparse cut traps traffic in a cluster. A small spectral gap (topology A's 0.05) means the graph is nearly disconnected — a sparse cut separates large components. The Cheeger inequality makes this precise by bounding edge expansion above and below by functions of the spectral gap. Option D is wrong: expander families have bounded degree and large spectral gap without being near-complete.

Question 3

For a d-regular graph (every vertex has exactly d neighbors), the largest eigenvalue of the adjacency matrix equals d.

• T. True
• F. False

Answer: True

For a d-regular graph, the all-ones vector 𝟏 is an eigenvector of A with eigenvalue d, because (A𝟏)ᵢ = Σⱼ Aᵢⱼ = degree of i = d for every vertex i. By the Perron-Frobenius theorem, the largest eigenvalue of a non-negative matrix equals its maximum row sum, confirming λ₁ = d exactly. The corresponding eigenvector 𝟏 reflects the graph's uniform degree structure.

Question 4

The eigenvalues of the adjacency matrix can primarily tell us how many edges a graph has — they cannot reveal global connectivity or structural properties.

• T. True
• F. False

Answer: False

The spectrum encodes rich structural information far beyond edge count. The spectral gap determines expansion and connectivity; the multiplicity of eigenvalue 0 is related to bipartiteness; and the smallest eigenvalues' eigenvectors reveal community structure, forming the mathematical basis of spectral clustering. A graph's edge count is captured by Tr(A²)/2 = |E|, but eigenvalues collectively reveal global topological properties that are invisible from individual matrix entries.

Question 5

Why does the spectral gap — the difference between the two largest eigenvalues — determine how quickly a random walk on a graph converges to its stationary distribution?

Model answer: A random walk is governed by the (normalized) adjacency matrix. Its powers converge to the stationary distribution at a rate determined by how quickly non-dominant eigenvector components decay. The dominant eigenvector (eigenvalue λ₁) represents the stationary distribution; the second eigenvector (eigenvalue λ₂) is the slowest-decaying deviation from stationarity. After each step, this deviation shrinks by a factor of λ₂/λ₁. A large spectral gap means λ₂/λ₁ is small — the deviation decays rapidly and the walk mixes quickly. A small spectral gap means slow decay and slow mixing.

This connection is the core of expander graph theory. Expanders are designed to have large spectral gaps with sparse graphs (few edges), ensuring rapid mixing despite low connectivity — which is why they appear in derandomization, error-correcting codes, and network design.