Spectral Methods & Spectral Graph Theory

By the end, you can

• Construct the adjacency matrix A, degree matrix D, and Laplacian L = D − A for a small graph.
• Explain why every row of L sums to zero and why that implies lambda-1 = 0 with eigenvector 1.
• State why L is positive semidefinite using the quadratic form identity.
• Determine the number of connected components from the multiplicity of eigenvalue 0.
• Describe what the Fiedler value and Fiedler vector are, and how the sign of the Fiedler vector partitions the graph.
• List the four steps of spectral clustering and explain why the spectral embedding helps k-means on tangled clusters.
• Distinguish the plain Laplacian from the normalized variants and explain when normalization matters.
• Apply Cheeger's inequality to interpret what a small lambda-2 guarantees about the graph's cut structure.
• Identify at least three applications of spectral graph theory (image segmentation, community detection, PageRank).
• Avoid the four common pitfalls: disconnected graphs (lambda-2 = 0), sign ambiguity in the Fiedler vector, skewed degrees, and random k-means initialization.