I'm interested in finding the eigenvalues and eigenvectors of the Laplacian matrix of a cycle graph with $n$ vertices (so – a 2-regular connected graph with $n$ vertices). The degree matrix is $D=2I$, and the adjacency matrix is (if I'm not mistaken):
$$A=\begin{bmatrix}0 & 1 & 0 & … &0 & 1 \\ 1 & 0 & 1 & 0 & … & 0 \\ 0 & 1 & 0 & 1 & … & 0 \\ . & . & . & . & . & . \\ . & . & . & . & 0 & 1 \\ 1 & 0 & . & . & 1 & 0 \end{bmatrix}$$
So overall the Laplacian matrix is:
$$L=D-A=\begin{bmatrix}2 & -1 & 0 & … &0 & -1 \\ -1 & 2 & -1 & 0 & … & 0 \\ 0 & -1 & 2& -1 & … & 0 \\ . & . & . & . & . & . \\ . & . & . & . & 2 & -1 \\ -1 & 0 & . & . & -1 & 2 \end{bmatrix}$$
Now I need to find the eigenvalues and eigenvectors of this matrix.
Since the sum of each row is $0$, I can already see that $0$ is an eigenvalue with eigenvector $(1,1,…)$. I think it's also pretty clear that $0$ is a simple eigenvalue from the shape of the matrix.
Does anyone have an idea on how to find the remaining eigenvalues and eigenvectors? Can this even be done for general $n$?
Thanks in advance.
Best Answer
Hint: $L$ is a circulant matrix.
Therefore, the vector
$$(\lambda_0,\lambda_1,\cdots, \lambda_{n-1})$$ of its eigenvalues is obtained by taking the Discrete Fourier Transform of the generating sequence (first line of matrix $L$).
$$(c_0,c_1,c_2,\cdots,c_{n-1})=(2, -1, 0, \cdots, 0, -1)$$
i.e.:
$$\lambda_k=\sum_{j=0}^{n-1}c_j e^{\tfrac{2i\pi jk}{n}}, \ \ \ (k=0,1,2, \cdots n-1)$$
which in fact can be given a real expression:
$$\lambda_k=2-2 \cos(2 \pi k)/n)=4 \sin^2 (\pi k/n) \ \ k=0,1,\cdots (n-1)$$
Nothing surprizing, matrix $L$ is symmetric with real entries. See p.7 of this reference.
The associated eigenvectors are the columns of $F_n$, the Discrete Fourier matrix of order $n$, i.e.,
$$V_k=\begin{pmatrix}e^{\tfrac{2i\pi 0k}{n}}\\e^{\tfrac{2i\pi 1k}{n}}\\ \vdots \\ e^{\tfrac{2i\pi (n-1)k}{n}}\end{pmatrix}$$
See this document where the initial example is precisely matrix $L$...