<s>[INST] How to find the Laplacian Eigen Values of the given graph 
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.
 [/INST] 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$.
</s>