2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$
    – M. Vinay
    Commented Mar 29, 2019 at 1:38
  • 1
    $\begingroup$ 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$). $\endgroup$
    – M. Vinay
    Commented Mar 29, 2019 at 1:52
  • $\begingroup$ Thank you so much. Now it is a bit clearer. Can you also derive the largest eigenvalue? I want to tick your answer :) $\endgroup$ Commented Mar 29, 2019 at 1:52
  • $\begingroup$ I think you already editted. Thanks!! $\endgroup$ Commented Mar 29, 2019 at 1:53
  • $\begingroup$ That $i$ shouldn't be there. Anyway, I'm typing it up as a complete answer now. $\endgroup$
    – M. Vinay
    Commented Mar 29, 2019 at 2:17

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Can you please explain the part where you start introducing cos? Where does it come from? What is $RE \omega^k$ $\endgroup$ Commented Mar 29, 2019 at 21:35
  • $\begingroup$ I think it is n-th root of unity $\endgroup$ Commented Mar 29, 2019 at 21:36
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – M. Vinay
    Commented Mar 30, 2019 at 2:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .