adjacency matrix & its spectrum
The adjacency matrix is the most direct way to turn a graph into a matrix: put a 1 in position (i,j) if node i connects to node j, and 0 otherwise. For an undirected graph A is symmetric. Its list of eigenvalues, the spectrum, is a fingerprint that encodes surprising amounts of graph structure.
The cleanest fact is about walks: the (i,j) entry of A^k counts the number of length-k walks from i to j. Summed over the diagonal, this ties powers of A to the eigenvalues, since trace(A^k) = sum of lambda^k. So the spectrum literally counts closed walks of every length, including triangles via trace(A^3).
The extreme eigenvalues carry meaning too. The largest eigenvalue lambda_max is squeezed between the average and the maximum degree and controls growth of walk counts; for a connected graph Perron-Frobenius makes it simple with a positive eigenvector. A graph is bipartite if and only if its spectrum is symmetric about zero, so the smallest eigenvalue equals -lambda_max.
Why it matters: the spectrum bounds expansion and mixing (the spectral gap), detects structure (bipartiteness, regularity), and underlies graph isomorphism heuristics. The caveat: the spectrum is not a complete invariant. Different graphs can be cospectral, sharing eigenvalues yet being genuinely different shapes.
Powers of the adjacency matrix count walks; a zero-symmetric spectrum signals bipartiteness.
Adjacency and Laplacian spectra answer different questions. For a d-regular graph they are simple translates (L = dI - A), but in general the Laplacian is the right tool for cuts and connectivity, while the adjacency matrix is the right tool for walks and centrality.