How to find the Laplacian Eigen Values of the given graph

Question

Find the Laplacian eigen-values of the of the graph on $N$ vertices whose edge set is given by $\{(i,i+1),1\le i<n\}$ and the edge $(1,n)$ .

The answer is given to be $2-2\cos{\frac{2k\pi}{n}}$ .

My try:

I tried to proceed by induction. For the case $n=3$ ;I got the matrix as $L$= \begin{array}{cccc} 2& -1 &-1\\ -1& 2 &-1\\ -1 & -1 &2 \end{array}

I got the eigen values as $0,3,3$ which are nowhere near the given the eigen values.

How should I do it? Please give some ways to solve this problem.

Answer 1

Consider the Laplacian matrix of the cycle on $n$ vertices, given by \begin{equation*} L = \begin{bmatrix} 2 & - 1 & 0 & \cdots & 0 & -1\\ -1 & 2 & -1 & \cdots & 0 & 0\\ 0 & -1 & 2 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 2 & -1\\ -1 & 0 & 0 & \cdots & -1& 2\\ \end{bmatrix}. \end{equation*}

$L$ is an example of a circulant matrix. Any circulant matrix is fully determined by its first row $[a_0\ a_1\ \cdots\ a_{n-1}]$, and its eigenvalues are given by a general formula. However, I will demonstrate the method of computation here (for the special case $L$).

Let $\omega = \exp\left( \dfrac{2i\pi}{n} \right)$, the primitive $n$-th root of unity, and let $v_1 = [1\ \omega\ \omega^2\ \cdots \omega^{n-1}]^T$. Then, \begin{align*} Lv_1 = \begin{bmatrix} 2 - \omega - \omega^{n-1}\\ 2 \omega - \omega^2 - 1\\ 2 \omega^2 - \omega^3 - \omega\\ \vdots\\ 2\omega^{n-1} - 1 - \omega^{n-2} \end{bmatrix} = (2 - \omega - \omega^{n-1})\begin{bmatrix} 1 \\ \omega \\ \omega^2\\ \vdots\\ \omega^{n-1} \end{bmatrix}, \end{align*} (keeping in mind that $\omega^n = 1$).

Thus, $2 - \omega - \omega^{n-1} = 2 - \omega - \omega^{-1}$ is an eigenvalue of $L$, with eigenvector $v_1$.

Similarly, for $k = 2, \cdots, n$, define $v_k = [1\ \omega^k\ \cdots\ \omega^{k(n-1)}]^T$, the vector obtained by taking the $k$-th power of each entry of $v_1$. Note that $v_n$ is the all-ones vector. Then, a computation exactly similar to the above one shows that $v_k$ is an eigenvector of $L$ for the eigenvalue $2 - \omega^k - \omega^{-k} = 2 - (\omega^k + \omega^{-k})$.

Simplifying, $\omega^k + \omega^{-k} = \exp\left( \dfrac{2ki\pi}{n} \right) + \exp\left( -\dfrac{2ki\pi}{n} \right) = 2 \cos \left( \dfrac{2k\pi}{n} \right)$. Thus, the eigenvalues of $L$ are \begin{align*}\large\boxed{ 2 \left( 1 - \cos \dfrac{2k\pi}{n} \right), \quad k = 1, 2, \ldots, n.} \end{align*}

---

Alternatively, you can find the eigenvalues $\lambda_k$ of the adjacency matrix $A$ (which is also circulant), and use the fact that $L = 2I - A$ to get the eigenvalues $2 - \lambda_k$ of $L$.

Answer 2

The Laplacian is given by:

$$ L = \begin{pmatrix} 2 & -1 & 0 & \cdots & -1 \\ -1 & 2 & -1 & \cdots & 0 \\ 0 & -1 & 2 & \cdots & 0 \\ \vdots & & & \vdots & \\ -1 & 0 & 0 & \cdots & 2 \end{pmatrix} $$

and indeed you have recovered the $n=3$ case. Observe that: $$\cos(2 \pi \cdot (0/3))=1, \, \cos(2\pi \cdot (1/3))=-1/2, \, \cos(2\pi \cdot (2/3))=-1/2 .$$