What does the (i, j) entry of the matrix A³ represent for an undirected graph with adjacency matrix A?
A1 if vertices i and j are connected by a path of length exactly 3, 0 otherwise
BThe number of walks of length 3 from vertex i to vertex j
CThe number of edges on the shortest path between vertices i and j
DThe degree of vertex i if i = j, and 0 otherwise
A³[i,j] counts the number of *walks* of length 3 from i to j — sequences where each consecutive pair is adjacent, with possible vertex repetition. This is not the same as *paths* (which require no repeated vertices). The result follows from matrix multiplication: (A²)[i,j] = Σₖ A[i,k]·A[k,j] counts length-2 walks; multiplying by A again extends to length 3. The diagonal entries tr(A³) count closed walks of length 3, giving 6 × (number of triangles).
Question 2 Multiple Choice
A connected graph has a large spectral gap — the difference between its largest and second-largest eigenvalue of the adjacency matrix is close to the maximum degree. What does this imply?
AThe graph has very few edges relative to its vertex count
BRandom walks on the graph mix rapidly and no small cut separates the graph into large pieces
CThe graph is bipartite
DThe graph has a unique Hamiltonian cycle
A large spectral gap is the hallmark of an expander graph — one with strong expansion properties. It means for any set of vertices, many edges leave the set, so no small cut isolates a large portion. Random walks on such graphs also mix to the stationary distribution rapidly. Expanders with large spectral gaps are used in network design, error-correcting codes, and derandomization in theoretical computer science.
Question 3 True / False
The adjacency matrix of an undirected graph can have complex (non-real) eigenvalues.
TTrue
FFalse
Answer: False
The adjacency matrix of an undirected graph is symmetric (A[i,j] = A[j,i]). By the spectral theorem, every real symmetric matrix has real eigenvalues. Complex eigenvalues can appear in adjacency matrices of *directed* graphs, where A is not necessarily symmetric. This is one reason undirected graphs are algebraically simpler — their spectrum is always a real set of numbers.
Question 4 True / False
The number of triangles in a graph can be determined from the trace of A³, where A is the adjacency matrix.
TTrue
FFalse
Answer: True
tr(A³) = Σᵢ (A³)[i,i] sums the number of closed walks of length 3 starting and ending at each vertex. Each triangle contributes exactly 6 such walks (two directions of traversal × three choices of starting vertex), so the number of triangles = tr(A³) / 6. This is a direct example of how spectral information encodes combinatorial structure without explicit edge enumeration.
Question 5 Short Answer
Why is the spectrum of the adjacency matrix considered a 'structural fingerprint' of a graph rather than simply a convenient way to store edge information?
Think about your answer, then reveal below.
Model answer: The eigenvalues of the adjacency matrix encode combinatorial properties not obvious from the edge list: the largest eigenvalue bounds maximum degree, the spectral gap measures connectivity and expansion, bipartite graphs have spectra symmetric around zero, and matrix powers count closed walks and detect substructures like triangles. These properties emerge from the eigenvalues themselves, making the spectrum a compressed description of global graph topology.
The deep point is that algebraic properties (eigenvalues) map to combinatorial properties (connectivity, expansion, bipartiteness, subgraph counts). This bridge between linear algebra and graph theory is what makes spectral graph theory powerful: you can analyze global graph structure using efficient matrix tools rather than exhaustive graph traversal.