# Largest eigenvalue of the Laplacian Matrix in an odd cycle

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).

• For a cycle graph on $n$ vertices, $L$ is a circulant matrix, so we know all its eigenvalues and eigenvectors. (And the proof is as easy as observing that every vector of the form $\begin{bmatrix}1 & \omega^k & \omega^{2k} & \cdots & \omega^{n - 1}\end{bmatrix}^T$, where $\omega = \exp\left(\frac{2\pi i}{n}\right)$, is an eigenvector). Mar 29 '19 at 1:38
• For a cycle on $2n + 1$ vertices, we therefore have $$\lambda_{\max} = \max_k (2 - \omega^k - \omega^{-k}) = \max_k 2(1 - \operatorname{Re} \omega^k) = \max_k 2\left(1 - \cos \dfrac{2k\pi i}{2n + 1} \right)$$ (in which $k$ runs from $0$ to $2n$). Mar 29 '19 at 1:52
• Thank you so much. Now it is a bit clearer. Can you also derive the largest eigenvalue? I want to tick your answer :) Mar 29 '19 at 1:52
• I think you already editted. Thanks!! Mar 29 '19 at 1:53
• That $i$ shouldn't be there. Anyway, I'm typing it up as a complete answer now. Mar 29 '19 at 2:17

## 1 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].$$

• Can you please explain the part where you start introducing cos? Where does it come from? What is $RE \omega^k$ Mar 29 '19 at 21:35
• I think it is n-th root of unity Mar 29 '19 at 21:36
• @independentvariable Yes, $\omega = \exp \dfrac{2\pi i}{2n + 1}$ is the $(2n + 1)$-th root of unity. So $\omega^k$ and $\omega^{-k}$ are mutually conjugate and $\omega^k + \omega^{-k}$ is twice the real part of $\omega^k$, which is $\cos \dfrac{2k\pi}{2n + 1}$. Mar 30 '19 at 2:03