A graph is a picture of relationships — friends, web pages, atoms in a molecule, cities joined by flights. But a picture is awkward for a computer, and hard to reason about with algebra. So we do something audacious: we turn the whole graph into a single matrix of 0s and 1s, and then let all the machinery of linear algebra loose on it.

That matrix is the adjacency matrix A. This one idea is the doorway to spectral graph theory — reading the shape of a network from the eigenvalues of its matrix. It is how Google's original PageRank ranked the web, how chemists (Hückel theory) predict which molecules are stable, and how "centrality" scores decide who the most influential person in a network is. All of it starts here.

Building the matrix

Number the vertices 1, 2, \dots, n. The adjacency matrix A is the n \times n table whose entry A_{ij} is 1 if vertices i and j are joined by an edge, and 0 if they are not. That is the entire definition. Here is a graph on four vertices:

Reading it off row by row — vertex 1 touches 2 and 3; vertex 2 touches 1 and 3; vertex 3 touches 1, 2 and 4; vertex 4 touches only 3 — gives

Three facts are worth pinning down straight away:

• It is symmetric. For an undirected graph, "i is joined to j" is the same statement as "j is joined to i", so A_{ij} = A_{ji}, i.e. A = A^{\mathsf T}.
• Each row sum is a degree. Adding up a row counts the 1s in it, which counts the neighbours of that vertex — its degree. Rows here sum to 2, 2, 3, 1: exactly the degrees.
• The diagonal is all 0. In a simple graph no vertex is joined to itself (no loops), so A_{ii} = 0 for every i.

From an edge list, in code

In practice a graph usually arrives as a list of edges. Filling in the matrix is a two-line loop — and, because the graph is undirected, each edge sets two symmetric entries:

Press Run — the printed rows are exactly the matrix above.

The magic of powers: counting walks

Here is where the matrix earns its keep. A walk of length k is a sequence of k edges you can traverse in a row (revisits allowed). Counting walks by hand is fiddly — but matrix multiplication does it for free.

Why? An entry of A^2 is (A^2)_{ij} = \sum_{m} A_{im} A_{mj}. Each term is 1 exactly when i\!-\!m and m\!-\!j are both edges — i.e. when m is a stepping-stone giving a two-step route i \to m \to j. The sum simply tallies the stepping-stones. Squaring our matrix:

Read it: (A^2)_{14} = 1 — there is exactly one length-2 walk from 1 to 4, namely 1 \to 3 \to 4. And (A^2)_{34} = 0 — you cannot get from 3 to 4 in two steps (they are neighbours, an odd distance). Best of all, the diagonal reads 2, 2, 3, 1: the degrees again. As a bonus, the trace \operatorname{tr}(A^2) = 2+2+3+1 = 8 is the sum of the degrees — twice the number of edges.

The spectrum: hearing the graph

Now the payoff. The spectrum of a graph is the set of eigenvalues of its adjacency matrix, usually written \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n. Because A is symmetric, a theorem of linear algebra (the spectral theorem) guarantees these eigenvalues are all real — a lovely and non-obvious gift. Spectral graph theory reads structure straight off these numbers:

• Largest eigenvalue and degree. \lambda_1 is squeezed between the average and the maximum degree: \bar d \leq \lambda_1 \leq d_{\max}. For the complete graph K_n every vertex has degree n-1, and indeed \lambda_1 = n-1.
• Connectivity. The number of connected components equals the multiplicity of the eigenvalue 0 of the closely related Laplacian L = D - A (with D the diagonal degree matrix). A connected graph has exactly one such zero.
• Bipartite ⇔ symmetric spectrum. A graph is 2-colourable (bipartite) precisely when its spectrum is symmetric about 0: every eigenvalue \lambda is matched by -\lambda.

The graph did not change; we just listened to its matrix. Eigenvalues turn a hand-drawn network into a handful of numbers that expose its connectivity, its symmetry and its bottlenecks.