Why Cycle Eigenvalues Repeat
The adjacency spectrum of a cycle is easy to list once its length is known, but a list with repetitions can hide its structure. The repeated values are not accidental: two different frequency indices produce the same cosine whenever they are negatives of one another modulo the cycle length. The even and odd cases differ only in which indices are fixed by this pairing.
All graphs below are finite and simple. For an integer \(n\ge 3\), let \(C_n\) have vertex set \(\{0,1,\ldots,n-1\}\), with edges between consecutive indices modulo \(n\). Its adjacency matrix \(\mathbf A(C_n)\) has entry \(1\) in positions corresponding to adjacent vertices and \(0\) elsewhere. The spectrum lists its eigenvalues with algebraic multiplicity.
To see the formula, allow complex vectors temporarily. Put \(\zeta=e^{2\pi i/n}\), and for each \(k\) define a vector \(x^{(k)}\) whose coordinate at vertex \(j\) is \(\zeta^{kj}\). The neighbors of \(j\) are \(j-1\) and \(j+1\), with indices taken modulo \(n\). Therefore \((\mathbf A(C_n)x^{(k)})_j=x^{(k)}_{j-1}+x^{(k)}_{j+1}=(\zeta^{-k}+\zeta^k)x^{(k)}_j=2\cos(2\pi k/n)x^{(k)}_j\). So \(x^{(k)}\) is an eigenvector with the displayed eigenvalue.
These \(n\) vectors are linearly independent. Indeed, for distinct \(k,\ell\) in \(\{0,\ldots,n-1\}\), the inner product of their coordinate lists is \(\sum_{j=0}^{n-1}\zeta^{(k-\ell)j}=0\): this is a geometric sum with ratio different from \(1\), whose \(n\)th power is \(1\). Each vector is nonzero, so the \(n\) mutually orthogonal vectors form a basis over the complex numbers. Thus the formula accounts for all eigenvalues, including their multiplicities. The eigenvalues are real; for a real eigenvalue, the real and imaginary parts of a complex eigenvector are real eigenvectors, so the multiplicity count also describes the real eigenspaces.
The Pairing Rule and the Parity Cases
Proof. By the formula, equality of \(\lambda_k\) and \(\lambda_\ell\) is equality of \(\cos(2\pi k/n)\) and \(\cos(2\pi\ell/n)\). The identity \(\cos u-\cos v=-2\sin((u+v)/2)\sin((u-v)/2)\) shows that \(\cos u=\cos v\) exactly when \(u+v\) or \(u-v\) is an integer multiple of \(2\pi\). Substituting \(u=2\pi k/n\) and \(v=2\pi\ell/n\) gives \(k+\ell\) or \(k-\ell\) divisible by \(n\), which is the stated congruence condition.
Thus the indices are paired by the map \(k\mapsto -k\pmod n\). An index is unpaired precisely when \(k\equiv-k\pmod n\), or \(2k\equiv0\pmod n\). In the range \(0\le k<n\), \(k=0\) always satisfies this condition. If \(n\) is even, \(k=n/2\) satisfies it as well; if \(n\) is odd, there is no other solution, since \(n\mid 2k\) and odd \(n\) imply \(n\mid k\). Every remaining index forms a two-element pair \(\{k,n-k\}\), so its eigenvalue occurs twice. Finally, substituting \(k=0\) gives \(2\), and, when \(n\) is even, substituting \(k=n/2\) gives \(2\cos\pi=-2\). This proves all the claims. \(\square\)
In an even cycle, both endpoint frequencies \(0\) and \(n/2\) are unpaired, and the other \(n-2\) indices make \((n-2)/2\) pairs. In an odd cycle, only \(0\) is unpaired, and the other \(n-1\) indices make \((n-1)/2\) pairs. These counts add to \(n\) in each case, as required for an \(n\)-vertex adjacency matrix.
Four Worked Spectra
Worked Example: The Triangle \(C_3\)
Let \(V=\{0,1,2\}\) and \(E=\{01,12,20\}\). The indices are \(k=0,1,2\). Substitution into the formula gives \(\lambda_0=2\cos 0=2\), \(\lambda_1=2\cos(2\pi/3)=2(-1/2)=-1\), and \(\lambda_2=2\cos(4\pi/3)=2(-1/2)=-1\). The indices \(1\) and \(2\) pair, so \(-1\) has multiplicity two. The spectrum is \(2,-1,-1\), and the characteristic polynomial is \((x-2)(x+1)^2=x^3-3x-2\).
Check: The sum of the eigenvalues is \(2-1-1=0\), which is the trace of the adjacency matrix because all its diagonal entries are \(0\). The sum of squared eigenvalues is \(2^2+(-1)^2+(-1)^2=4+1+1=6\). Each of the three vertices has degree \(2\), so the trace of \(\mathbf A(C_3)^2\) is \(2+2+2=6\), in agreement.
Worked Example: The Square \(C_4\)
Let \(V=\{0,1,2,3\}\) and \(E=\{01,12,23,30\}\). For \(k=0,1,2,3\), the formula gives \(2\cos 0=2\), \(2\cos(\pi/2)=0\), \(2\cos\pi=-2\), and \(2\cos(3\pi/2)=0\). The indices \(1\) and \(3\) pair, while \(0\) and \(2=n/2\) are unpaired. Hence the spectrum is \(2,0,0,-2\), and the characteristic polynomial is \((x-2)x^2(x+2)=x^4-4x^2\).
Check: The eigenvalues sum to \(2+0+0-2=0\). Their squares sum to \(2^2+0^2+0^2+(-2)^2=4+0+0+4=8\). The graph has four vertices of degree \(2\), so \(\operatorname{tr}(\mathbf A(C_4)^2)=2+2+2+2=8\).
Worked Example: The Pentagon \(C_5\)
Let \(V=\{0,1,2,3,4\}\) and \(E=\{01,12,23,34,40\}\). The index \(0\) gives eigenvalue \(2\). The indices \(1,4\) give \(a=2\cos(2\pi/5)\), and indices \(2,3\) give \(b=2\cos(4\pi/5)\). Evaluating these cosine values gives \(a=(\sqrt5-1)/2\) and \(b=-(\sqrt5+1)/2\). Thus the spectrum is \(2,a,a,b,b\): there is one unpaired eigenvalue and two paired values, as the odd-length rule predicts.
Check: We have \(a+b=-1\), so the eigenvalues sum to \(2+2(a+b)=2-2=0\). Also \(a^2=1-a\), since \(a^2+a-1=0\), and \(b=-1-a\), so \(b^2=(1+a)^2=1+2a+a^2=1+2a+(1-a)=2+a\). Therefore \(a^2+b^2=(1-a)+(2+a)=3\), and the sum of squared eigenvalues is \(2^2+2a^2+2b^2=4+2(3)=10\). This equals \(\operatorname{tr}(\mathbf A(C_5)^2)=5\cdot2=10\), since each of the five vertices has degree \(2\). The characteristic polynomial is \((x-2)(x^2+x-1)^2=x^5-5x^3+5x-2\).
Worked Example: The Hexagon \(C_6\)
Let \(V=\{0,1,2,3,4,5\}\) and \(E=\{01,12,23,34,45,50\}\). Evaluating the formula at \(k=0,1,2,3,4,5\) gives \(2,1,-1,-2,-1,1\), respectively: the cosine angles are \(0,\pi/3,2\pi/3,\pi,4\pi/3,5\pi/3\). The pairs \((1,5)\) and \((2,4)\) yield \(1\) and \(-1\), while \(0\) and \(3=n/2\) yield \(2\) and \(-2\). The spectrum is \(2,1,1,-1,-1,-2\). Its characteristic polynomial factors as \((x-2)(x+2)(x-1)^2(x+1)^2=(x^2-4)(x^2-1)^2\).
Check: The eigenvalues sum to \(2+1+1-1-1-2=0\). Their squares sum to \(4+1+1+1+1+4=12\), matching \(\operatorname{tr}(\mathbf A(C_6)^2)=6\cdot2=12\).
Reading Multiplicities Correctly
Multiplicity counts how many times an eigenvalue appears in the spectrum, not how many different numerical values the spectrum contains. For example, \(C_6\) has four distinct eigenvalues, \(2,1,-1,-2\), but six eigenvalues counted with multiplicity. The paired frequencies \(1,5\) and \(2,4\) account for the two repeated values. In an odd cycle there is no unpaired frequency corresponding to \(-2\), because there is no integer \(k=n/2\).
A useful independent check for each calculation comes from the diagonal of \(\mathbf A^2\). Its entry at vertex \(v\) counts the length-two walks from \(v\) back to \(v\), one for each neighbor of \(v\), so that diagonal entry is \(\deg(v)\). Thus \(\operatorname{tr}(\mathbf A^2)=\sum_{v\in V}\deg(v)\). Every cycle has degree \(2\) at each of its \(n\) vertices, giving \(\sum_k\lambda_k^2=2n\). This check can detect an omitted or incorrectly evaluated repeated eigenvalue.
Common mistake. For \(C_5\), writing \(b=-1-a\) and then claiming \(b^2=1+a\) leads to \(a^2+b^2=2\), which is false. The correct calculation is \(b^2=(1+a)^2=2+a\), using \(a^2=1-a\). Therefore \(a^2+b^2=(1-a)+(2+a)=3\), and the squared-eigenvalue sum is \(4+2(3)=10\), not \(8\). The trace check independently gives \(5\cdot2=10\).
Check Your Understanding
Use the pairing rule and the trace checks from this tutorial to verify your reasoning.
- For \(C_7\), how many eigenvalues are unpaired, and how many distinct eigenvalues have multiplicity two?
- For \(C_8\), identify the indices that give unpaired eigenvalues and calculate those eigenvalues.
- Explain why the eigenvalue \(2\) has multiplicity one for every cycle \(C_n\) with \(n\ge3\).
- For \(C_5\), verify that the sum of the eigenvalues is zero using \(a+b=-1\).
- Give the sum of squared adjacency eigenvalues of \(C_9\), and justify it using the degrees rather than evaluating nine cosines.