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
    Mar 29 '19 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
    Mar 29 '19 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$ Mar 29 '19 at 1:52
  • $\begingroup$ I think you already editted. Thanks!! $\endgroup$ Mar 29 '19 at 1:53
  • $\begingroup$ That $i$ shouldn't be there. Anyway, I'm typing it up as a complete answer now. $\endgroup$
    – M. Vinay
    Mar 29 '19 at 2:17
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$ Mar 29 '19 at 21:35
  • $\begingroup$ I think it is n-th root of unity $\endgroup$ Mar 29 '19 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
    Mar 30 '19 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.