Compute the spectrum of a cycle length $n (n\ge 3)$.

Question

I've found the adjacency matrix and thus the eigenvalue equation: $$A(G) = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 1\\ 1 & 0 & 1 & \cdots & 0 & 0\\ 0 & 1 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 0 & 0 & \cdots & 1 & 0\\ \end{pmatrix} $$ $$\phi(G) = det(xI-A(G))= \begin{vmatrix} x & -1 & 0 & \cdots & 0 & -1\\ -1 & x & -1 & \cdots & 0 & 0\\ 0 & -1 & x & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ -1 & 0 & 0 & \cdots & -1 & x\\ \end{vmatrix} $$

From here I've tried doing some row reduction but can't seem to form an upper or lower diagonal matrix to take the determinant easily. I also tried expanding the determinant along the first or last rows since there are only $3$ non zero elements but the determinants of the $(n-1)\times(n-1)$ matrices don't seem to simplify either!

Answer 1

Let $D$ be the adjacency matrix of the directed cycle graph. Observe that $D^{n} = I$. Recall that if $(\lambda, v)$ is an eigenpair of $D$, then $(\lambda^{n}, v)$ is an eigenpair of $D^{n} = I$. As $1$ is the unique eigenvalue of $I$, with multiplicity $n$, it follows that the nth roots of unity are exactly the eigenvalues of $D$.

Observe $A(C_{n}) = D + D^{T}$. Furthermore, note $DD^{T} = I$. It follows that if $v$ is an eigenvector of $D$ corresponding to the eigenvalue $\lambda$, then $v$ is also an eigenvector of $D + D^{T}$ with corresponding eigenvalue $\lambda + \lambda^{n-1}$. As $\lambda$ is a root of unity, $\lambda^{n-1}$ is the complex conjugate of $\lambda$. Thus, the eigenvalues of $C_{n}$ are $\lambda_{k+1} = 2cos(\frac{2k\pi}{n})$ where $k \in \{0, ..., n-1\}$.

Answer 2

Let $V$ be the vector space of complex-valued functions from the vertex set to $\mathbb{C}$, then the adjacency operator acts on $f \in V$ by $(Af)(j) = f(j-1) + f(j+1)$, where arithmetic on the $j$ is done modulo $n$. The problem is to find the eigenvalues of the operator $A$.

The cycle graph on $n$ vertices has a natural kind of rotation symmetry. If we denote by $R: V \to V$ the operator $(Rf)(j) = f(j-1)$ which rotates functions on vertices, it is not hard to see that $R$ commutes with $A$, and so eigenvectors for $R$ will also be eigenvectors of $A$.

After playing around a little, you can find $n$ linearly independent eigenvectors $f_m(j) = \operatorname{exp}(2 \pi m i / n)$ for $R$, where $j = 0, 1, \ldots, n-1$. These must also be eigenvectors for $A$. All that remains is to plug them into the operator $A$ and see what their eigenvalues are.