The Cyclic Eigenvector Equation
A cycle differs from a path at its endpoints: the last vertex is adjacent to the first. That extra edge changes the eigenvector equations at both ends, and the resulting wraparound condition determines which eigenvalues are allowed. For a cycle, the condition is especially tractable: it says that a certain complex number must be an \(n\)th root of unity.
Throughout, \(n\ge 3\), and \(C_n\) is the finite simple graph with vertex set \(V(C_n)=\{1,2,\ldots,n\}\) and edge set \(E(C_n)=\{12,23,\ldots,(n-1)n,n1\}\). Let \(\mathbf A(C_n)\) be its adjacency matrix. An eigenpair consists of a scalar \(\lambda\) and a nonzero vector \(x=(x_1,\ldots,x_n)\) such that \(\mathbf A(C_n)x=\lambda x\). Since each vertex is adjacent to its two cyclic neighbors, this equation gives
where indices wrap around: \(x_0=x_n\) and \(x_{n+1}=x_1\). In ordinary indexed form, the endpoint equations are \(\lambda x_1=x_n+x_2\) and \(\lambda x_n=x_{n-1}+x_1\); the interior equations apply for \(2\le j\le n-1\).
Why the Wraparound Condition Is \(z^n=1\)
The eigenvector calculation can be done over the complex numbers. This is useful because the \(n\)th roots of unity give a convenient set of trial vectors; the resulting eigenvalues will all be real.
Proof. Suppose first that \(x_j=z^{j-1}\) is an eigenvector. At an interior vertex, the equation is \(\lambda z^{j-1}=z^{j-2}+z^j\). Dividing by the nonzero number \(z^{j-1}\) gives \(\lambda=z^{-1}+z\). At vertex \(1\), the cycle equation is \(\lambda x_1=x_n+x_2\). Substituting the trial vector gives \(\lambda= z^{n-1}+z\). Comparing with \(\lambda=z^{-1}+z\) yields \(z^{n-1}=z^{-1}\), and multiplying by \(z\) gives \(z^n=1\). Conversely, suppose \(z^n=1\) and \(\lambda=z+z^{-1}\). The interior equations hold by direct substitution. At vertex \(1\), \(x_n=z^{n-1}=z^{-1}\), so \(x_n+x_2=z^{-1}+z=\lambda x_1\), since \(x_1=1\). At vertex \(n\), \(x_{n-1}+x_1=z^{n-2}+1\), while \(\lambda x_n=(z+z^{-1})z^{n-1}=z^n+z^{n-2}=1+z^{n-2}\). These are equal, so both endpoint equations hold. The trial vector is nonzero because its first entry is \(1\). Thus the condition is necessary and sufficient. \(\square\)
For each integer \(k\) with \(0\le k\le n-1\), let \(z_k=e^{2\pi i k/n}\). These are exactly the \(n\) distinct complex solutions of \(z^n=1\). The corresponding trial vector has entries \(z_k^{j-1}\), and its eigenvalue is \(z_k+z_k^{-1}\). Using \(e^{i\theta}+e^{-i\theta}=2\cos\theta\), the value becomes \(2\cos(2\pi k/n)\).
Proof. For each \(k\), define \(u^{(k)}\) by \(u^{(k)}_j=z_k^{j-1}\) for \(1\le j\le n\). The proposition shows that \(u^{(k)}\) is a nonzero eigenvector with eigenvalue \(\lambda_k=z_k+z_k^{-1}=2\cos(2\pi k/n)\). It remains to show that these \(n\) eigenvectors account for the full spectrum, including when some of their eigenvalues coincide.
Use the usual complex inner product. If \(k\ne \ell\), then $$ \langle u^{(k)},u^{(\ell)}\rangle =\sum_{j=1}^{n}\overline{z_k^{j-1}}z_\ell^{j-1} =\sum_{r=0}^{n-1}(z_\ell z_k^{-1})^r. $$
The ratio \(q=z_\ell z_k^{-1}\) satisfies \(q^n=1\), and \(q\ne1\) because \(z_k\ne z_\ell\). The finite geometric sum is \((1-q^n)/(1-q)=0\). Thus the vectors are pairwise orthogonal and nonzero, so they are linearly independent. There are \(n\) such vectors in an \(n\)-dimensional vector space, hence they form a basis. In this basis the adjacency matrix acts diagonally with the listed eigenvalues, proving that the list is complete. Each value is real because it is twice a cosine. If two different indices give the same value, both entries remain in the list, as required when eigenvalues are counted with multiplicity. \(\square\)
Worked Spectra
Worked Example: The Triangle \(C_3\)
Let \(V(C_3)=\{1,2,3\}\) and \(E(C_3)=\{12,23,31\}\). Here \(n=3\), so the formula gives one value for each of \(k=0,1,2\).
For \(k=0\), \(\lambda_0=2\cos(0)=2\). For \(k=1\), the angle is \(2\pi/3\), so \(\lambda_1=2(-1/2)=-1\). For \(k=2\), the angle is \(4\pi/3\), whose cosine is also \(-1/2\), so \(\lambda_2=2(-1/2)=-1\). The full list is \(2,-1,-1\).
For a direct eigenvector check, take \(z_0=1\), \(z_1=e^{2\pi i/3}\), and \(z_2=e^{4\pi i/3}\). The first vector is \((1,1,1)\); at each vertex, the sum of the two neighbor entries is \(2\), confirming eigenvalue \(2\). For \(k=1\), the vector is \((1,z_1,z_1^2)\). The identity \(1+z_1+z_1^2=0\) gives \(1+z_1^2=-z_1\), so the neighbor sum at vertex \(2\) is \(-z_1\); cyclically, the same equation holds at the other vertices, confirming eigenvalue \(-1\). The \(k=2\) vector satisfies the same identity and check.
Check: The sum of the listed eigenvalues is \(2+(-1)+(-1)=0\), matching the zero diagonal sum of the adjacency matrix. Their squared sum is \(2^2+(-1)^2+(-1)^2=4+1+1=6\). Independently, \(C_3\) has \(3\) edges and each edge contributes \(1\) to each endpoint's diagonal entry in \(\mathbf A^2\), so \(\operatorname{tr}(\mathbf A^2)=2\cdot3=6\).
Worked Example: The Square \(C_4\)
Let \(V(C_4)=\{1,2,3,4\}\) and \(E(C_4)=\{12,23,34,41\}\). For \(k=0,1,2,3\), the angles \(2\pi k/4\) are respectively \(0,\pi/2,\pi,3\pi/2\). Their cosines are \(1,0,-1,0\), so the eigenvalue list is \(2,0,-2,0\).
The root-of-unity vectors make the endpoint check explicit. For \(k=0\), the vector \((1,1,1,1)\) has neighbor sum \(2\) at every vertex. For \(k=1\), \(z_1=i\) and the vector is \((1,i,-1,-i)\). At vertex \(1\), the neighbor sum is \(i+(-i)=0\), and at vertex \(2\), it is \(1+(-1)=0\); the other two equations also have neighbor sum zero. For \(k=2\), \(z_2=-1\) and the vector is \((1,-1,1,-1)\). Every vertex has two neighbors with value opposite its own, so its neighbor sum is \(-2\) times its entry. For \(k=3\), the vector is \((1,-i,-1,i)\), and the neighbor sums cancel at each vertex, giving eigenvalue \(0\).
Check: The eigenvalue sum is \(2+0+(-2)+0=0\). The squared sum is \(2^2+0^2+(-2)^2+0^2=4+0+4+0=8\). Independently, \(C_4\) has \(4\) edges, so \(\operatorname{tr}(\mathbf A^2)=2\cdot4=8\). The two zero entries in the list are retained because they come from two indices, \(k=1\) and \(k=3\).
Worked Example: The Six-Cycle \(C_6\)
Let \(V(C_6)=\{1,2,3,4,5,6\}\) and \(E(C_6)=\{12,23,34,45,56,61\}\). Substituting \(k=0,1,2,3,4,5\) into the formula gives the angles \(0,\pi/3,2\pi/3,\pi,4\pi/3,5\pi/3\). Their cosine values are \(1,1/2,-1/2,-1,-1/2,1/2\), respectively. Multiplying each by \(2\), the list is \(2,1,-1,-2,-1,1\).
For each \(k\), let \(z_k=e^{2\pi i k/6}\) and use \(u^{(k)}_j=z_k^{j-1}\). At an interior vertex, the neighbor entries are \(z_k^{j-2}\) and \(z_k^j\), whose sum is \((z_k^{-1}+z_k)z_k^{j-1}=\lambda_k u^{(k)}_j\). At vertex \(1\), the wraparound entry is \(u^{(k)}_6=z_k^5=z_k^{-1}\), since \(z_k^6=1\); adding \(u^{(k)}_2=z_k\) gives \(\lambda_k u^{(k)}_1\). At vertex \(6\), the neighbor sum is \(z_k^4+1\), while \(\lambda_k u^{(k)}_6=(z_k+z_k^{-1})z_k^5=z_k^6+z_k^4=1+z_k^4\). Thus the endpoint equations also hold for all six listed indices.
Check: The sum is \(2+1+(-1)+(-2)+(-1)+1=0\). The squared sum is \(2^2+1^2+(-1)^2+(-2)^2+(-1)^2+1^2=4+1+1+4+1+1=12\). Independently, \(C_6\) has \(6\) edges, giving \(\operatorname{tr}(\mathbf A^2)=2\cdot6=12\).
What the Formula Captures
The index \(k\) identifies a particular cyclic pattern in an eigenvector: moving one step around the graph multiplies its entry by \(e^{2\pi i k/n}\). After \(n\) steps, the multiplier must return to \(1\); this is precisely why the endpoint condition matters. The eigenvalue is the sum of the two neighbor multipliers, \(z_k+z_k^{-1}\), which is real and equals \(2\cos(2\pi k/n)\).
The formula is a list, not a promise that all values are different. Distinct indices can yield the same cosine and therefore the same eigenvalue. The proof of completeness does not require distinct eigenvalues: it establishes that the \(n\) eigenvectors are linearly independent. The detailed patterns of repeated values are a separate question.
As another useful check, the index \(k=0\) always gives eigenvalue \(2\), with the constant vector as an eigenvector. This agrees directly with the fact that every vertex of \(C_n\) has two neighbors: applying the adjacency matrix to the all-ones vector gives \(2\) in every coordinate.
Common Pitfall: Forgetting the Closing Edge
A frequent error is to use the path endpoint condition \(x_0=x_{n+1}=0\) for a cycle. Those conditions remove the edges from vertex \(1\) to vertex \(n\) and from vertex \(n\) back to vertex \(1\); they do not describe \(C_n\). For example, on \(C_4\), the constant vector has neighbor sum \(2\) at vertex \(1\), since its neighbors are \(2\) and \(4\). The cycle equation therefore gives \(\lambda x_1=2x_1\), and the constant vector has eigenvalue \(2\). If one incorrectly sets \(x_0=0\), the first recurrence becomes \(\lambda x_1=x_2\), which for the constant vector would give \(\lambda=1\). That contradicts the actual cycle equation. The correction is to retain both wraparound equations, or equivalently to impose \(z^n=1\) on the trial vector.
Check Your Understanding
Use the cyclic recurrence and the roots-of-unity formula to answer the following questions.
- Write all adjacency eigenvalues of \(C_5\) as \(2\cos(2\pi k/5)\) for \(k=0,1,2,3,4\).
- For a trial vector \(x_j=z^{j-1}\), show directly from the vertex \(1\) equation why the condition \(z^n=1\) is needed.
- For \(C_6\), verify the eigenvector equation at vertex \(6\) using \(z^6=1\).
- Explain why the \(n\) root-of-unity eigenvectors are linearly independent even if some eigenvalues coincide.
- Give the eigenvalue associated with the constant vector on \(C_n\), and verify it from the two neighbors of each vertex.