Problem:
We have an odd cycle, $C_{2n+1}$, for $n \geq 1$, and the edges $e \in E\ $ have all one weights $w \in \{1\}^E$.
Question: Denote the largest eigenvalue of the Laplacian matrix of this graph as $\lambda_{\max}(L_w)$. What is the value of $\lambda_{\max}(L_w)$?
My attempt:
The Laplacian Matrix will look like:
$$ L_w = \begin{bmatrix}2 & -1 & 0 & 0 & \ldots & -1 \\
-1 & 2 & -1 & 0 & \ldots & 0 \\
0 & -1 & 2 & -1 & \ldots & 0 \\ \vdots &\vdots & \vdots &\vdots &\vdots & \vdots \end{bmatrix} $$
And I think to solve eigenvalue problem, we need to consider $det(L_w – \lambda I) =0$, take the characteristic function and then somehow we should conclude that the max value is a function of $n$ including $cos()$ operator.
I also think cofactor expansion can be a potential direction. Here on Chapter 3.2 there is an example, but that is on Paths and does the calculations for the adjacency matrix. I need to find the exact solution of the Laplacian form's maximum eigenvalue (because I will use it to find the result of the semidefinite program of MAX-CUT problem reduced to vertex-transitive graphs).
Best Answer
For a cycle, the Laplacian matrix and the adjacency matrix as well are circulant matrices, and we know all the eigenvalues and eigenvectors of a circulant matrix. If $L$ is the Laplacian matrix of the odd cycle on $2n + 1$ vertices, and $\omega = \exp \frac{2\pi i}{2n + 1}$ the $(2n + 1)$th root of unity, then every eigenvalue of $L$ is of the form $$2 - \omega^k - \omega^{-k} = 2 - 2\operatorname{Re} \omega^k = 2 - 2 \cos \dfrac{2k\pi}{2n + 1},$$ $k = 0, \ldots, 2n$.
This is maximum when the cosine is minimum, which happens when $\dfrac{2k\pi}{2n + 1}$ is closest to $\pi$, i.e., when $k = n$ or $n + 1$ (both choices giving the same value).
Thus, the largest eigenvalue of $L$ is $$\lambda_{\max} = 2\left[1 - \cos \dfrac{2n\pi}{2n + 1} \right].$$