The Spectrum of Complete Graphs

Why Complete Graphs Have a Simple Spectrum

In a complete graph, every pair of distinct vertices is adjacent. This uniform structure makes the adjacency matrix especially amenable to calculation: its action on a vector depends only on the sum of that vector's coordinates and on each coordinate itself. Splitting a vector into a constant part and a part whose coordinates sum to zero reveals both eigenspaces directly.

Throughout, \(K_n\) is the simple undirected complete graph on \(n\geq 1\) vertices, labelled \(1,\dots,n\). Its edge set contains every pair \(ij\) with \(1\leq i<j\leq n\). The adjacency matrix \(\mathbf{A}(K_n)\) has entry \(1\) in position \(i,j\) when \(ij\) is an edge and \(0\) otherwise. In particular, its diagonal entries are zero. We study its adjacency spectrum: the eigenvalues of this matrix, counted with their algebraic multiplicities.

The all-ones vector records constant values on the vertices. The zero-sum subspace consists of vectors orthogonal to it. For any \(x=(x_1,\dots,x_n)^\mathsf{T}\), define its coordinate mean \(\bar{x}=(x_1+\cdots+x_n)/n\). Then \(x=\bar{x}\mathbf{1}+y\), where \(y=x-\bar{x}\mathbf{1}\) has coordinate sum zero. Thus every vector splits into a constant component and a zero-sum component. The two parts intersect only in the zero vector: a constant vector \(c\mathbf{1}\) has sum \(nc\), which is zero only when \(c=0\).

The Matrix Action and the Main Result

Let \(\mathbf{J}\) be the \(n\) by \(n\) all-ones matrix and \(\mathbf{I}\) the identity matrix. The complete graph has every off-diagonal adjacency entry equal to \(1\), and every diagonal entry equal to \(0\). Consequently, \(\mathbf{A}(K_n)=\mathbf{J}-\mathbf{I}\). For any vector \(x\), every coordinate of \(\mathbf{J}x\) equals the sum of the coordinates of \(x\), so

This formula is the key calculation. On a constant vector, the coordinate sum contributes a factor of \(n\); on a zero-sum vector, that contribution vanishes.

Proof. First apply the matrix-action formula to \(\mathbf{1}\). Its coordinate sum is \(n\), so \(\mathbf{A}(K_n)\mathbf{1}=n\mathbf{1}-\mathbf{1}=(n-1)\mathbf{1}\). Thus \(n-1\) is an eigenvalue, and every scalar multiple of \(\mathbf{1}\) is in its eigenspace.

Now take \(y\in\mathbf{1}^{\perp}\). Its coordinate sum is zero, so the same formula gives \(\mathbf{A}(K_n)y=-y\). Thus every vector in \(\mathbf{1}^{\perp}\) is an eigenvector for \(-1\), unless it is the zero vector. Conversely, if \(\mathbf{A}(K_n)x=-x\), then the formula implies \((\sum_i x_i)\mathbf{1}-x=-x\), hence \((\sum_i x_i)\mathbf{1}=0\). Since \(\mathbf{1}\neq 0\), the sum of the coordinates of \(x\) is zero. Therefore this eigenspace is exactly \(\mathbf{1}^{\perp}\).

Likewise, if \(\mathbf{A}(K_n)x=(n-1)x\), then \((\sum_i x_i)\mathbf{1}-x=(n-1)x\), or \((\sum_i x_i)\mathbf{1}=nx\). Since \(n\geq1\), this says \(x=(\sum_i x_i/n)\mathbf{1}\); the eigenspace is exactly \(\operatorname{span}\{\mathbf{1}\}\). The constant subspace has dimension \(1\). The zero-sum subspace has dimension \(n-1\), because its vectors are determined freely by their first \(n-1\) coordinates, with the last coordinate forced to be the negative of their sum. These subspaces have zero intersection and their dimensions add to \(n\). Choosing a basis from each therefore gives a basis of \(\mathbb{R}^n\) consisting of eigenvectors. In this basis the matrix is diagonal, with one diagonal entry \(n-1\) and \(n-1\) diagonal entries \(-1\). This proves the stated algebraic multiplicities as well as the eigenspaces. If \(n=1\), the zero-sum subspace has dimension zero; the only eigenvalue is \(n-1=0\). \(\square\)

In particular, the characteristic polynomial, with the convention \(\det(\lambda\mathbf{I}-\mathbf{A})\), is

The basis argument in the proof justifies this product: in an eigenvector basis, \(\lambda\mathbf{I}-\mathbf{A}(K_n)\) is diagonal, and its determinant is the product of its diagonal entries. For \(n=1\), the factor \((\lambda+1)^0\) is \(1\), leaving the characteristic polynomial \(\lambda\).

Worked Examples

Common Mistakes and Useful Checks

A common error is to infer that the degree of a regular graph is an eigenvalue of multiplicity \(n\). Regularity does show that the all-ones vector is an eigenvector: for \(K_4\), every row sum is \(3\), so \(\mathbf{A}\mathbf{1}=3\mathbf{1}\). But this establishes just one eigenvector direction, not that every vector has eigenvalue \(3\). For example, \(u=(1,-1,0,0)^\mathsf{T}\) has coordinate sum zero, and the complete-graph formula gives \(\mathbf{A}(K_4)u=-u\), not \(3u\). The correct spectrum is \(3\) once and \(-1\) three times.

For \(K_n\) with \(n\geq2\), quick consistency checks are available. The eigenvalue multiplicities must add to \(1+(n-1)=n\), the matrix order. Their sum is \((n-1)+(n-1)(-1)=0\), which agrees with the trace because the adjacency matrix has zero diagonal. These checks can catch an arithmetic or multiplicity error, but the vector decomposition is what proves the spectrum. The \(n=1\) case is covered separately by the same formula: the multiplicities are \(1\) and \(0\), and the only eigenvalue is \(0\).

The split also explains why no other eigenvalues can occur. Every vector is a sum of a constant vector and a zero-sum vector, and the matrix acts on those two subspaces by scalar multiplication. Since those subspaces together span the entire vector space, there is no remaining direction on which a different eigenvalue could appear.