Dgdrxrt

Forgetting the musical notes while performing in concert

intersection of two sorted vectors in C++

Anagram holiday

Can a rocket refuel on Mars from water?

Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?

Were any external disk drives stacked vertically?

Withdrawals from HSA

Doing something right before you need it - expression for this?

I Accidentally Deleted a Stock Terminal Theme

Watching something be written to a file live with tail

How to say in German "enjoying home comforts"

What's the point of deactivating Num Lock on login screens?

What to put in ESTA if staying in US for a few days before going on to Canada

90's TV series where a boy goes to another dimension through portal near power lines

Reserved de-dupe rules

Blender 2.8 I can't see vertices, edges or faces in edit mode

Western buddy movie with a supernatural twist where a woman turns into an eagle at the end

Is "remove commented out code" correct English?

What is the intuition behind short exact sequences of groups; in particular, what is the intuition behind group extensions?

How can I make my BBEG immortal short of making them a Lich or Vampire?

What killed these X2 caps?

How much of data wrangling is a data scientist's job?

Infinite Abelian subgroup of infinite non Abelian group example

A reference to a well-known characterization of scattered compact spaces

Largest eigenvalue of the Laplacian Matrix in an odd cycle

Largest eigenvalue, semidefinite programmingMaximum eigenvalue and a corresponding eigenvector of an infinite Hilbert matrixProve that the largest singular value of a matrix is greater than the largest eigenvalueConditions to preserve Laplacian matrixeigenvalue problem of a simple circulant matrixadjacency matrix, maximal eigenvalueConjecture regarding second smallest eigenvalue of a Laplacian matrixMaximizing the smallest positive eigenvalue of the Laplacian matrix via SDPLower-bound on the size of the largest eigenvalues of the laplacian matrix in random graphsWhy is the largest eigenvalue of a laplacian matrix equal to the number of nodes in the graph?

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 = beginbmatrix2 & -1 & 0 & 0 & ldots & -1 \
-1 & 2 & -1 & 0 & ldots & 0 \
0 & -1 & 2 & -1 & ldots & 0 \ vdots &vdots & vdots &vdots &vdots & vdots endbmatrix $$
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).

linear-algebra graph-theory eigenvalues-eigenvectors characteristic-functions graph-laplacian

share|cite|improve this question

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

$endgroup$

• 
  
  
  

  
  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 $beginbmatrix1 & omega^k & omega^2k & cdots & omega^n - 1endbmatrix^T$, where $omega = expleft(frac2pi inright)$, is an eigenvector).
  $endgroup$
  – M. Vinay
  Mar 29 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 - operatornameRe omega^k) = max_k 2left(1 - cos dfrac2kpi i2n + 1 right)$$ (in which $k$ runs from $0$ to $2n$).
  $endgroup$
  – M. Vinay
  Mar 29 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$
  – independentvariable
  Mar 29 at 1:52
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you already editted. Thanks!!
  $endgroup$
  – independentvariable
  Mar 29 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 at 2:17
  

  
  
  
  

add a comment | 

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 = beginbmatrix2 & -1 & 0 & 0 & ldots & -1 \
-1 & 2 & -1 & 0 & ldots & 0 \
0 & -1 & 2 & -1 & ldots & 0 \ vdots &vdots & vdots &vdots &vdots & vdots endbmatrix $$
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).

linear-algebra graph-theory eigenvalues-eigenvectors characteristic-functions graph-laplacian

share|cite|improve this question

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

$endgroup$

• 
  
  
  

  
  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 $beginbmatrix1 & omega^k & omega^2k & cdots & omega^n - 1endbmatrix^T$, where $omega = expleft(frac2pi inright)$, is an eigenvector).
  $endgroup$
  – M. Vinay
  Mar 29 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 - operatornameRe omega^k) = max_k 2left(1 - cos dfrac2kpi i2n + 1 right)$$ (in which $k$ runs from $0$ to $2n$).
  $endgroup$
  – M. Vinay
  Mar 29 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$
  – independentvariable
  Mar 29 at 1:52
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you already editted. Thanks!!
  $endgroup$
  – independentvariable
  Mar 29 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 at 2:17
  

  
  
  
  

add a comment | 

$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 = beginbmatrix2 & -1 & 0 & 0 & ldots & -1 \
-1 & 2 & -1 & 0 & ldots & 0 \
0 & -1 & 2 & -1 & ldots & 0 \ vdots &vdots & vdots &vdots &vdots & vdots endbmatrix $$
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).

linear-algebra graph-theory eigenvalues-eigenvectors characteristic-functions graph-laplacian

share|cite|improve this question

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

$endgroup$

share|cite|improve this question

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

share|cite|improve this question

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

asked Mar 29 at 1:13

independentvariableindependentvariable

302111

1 Answer
1

active

oldest

votes

2

$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 frac2pi i2n + 1$ the $(2n + 1)$^th root of unity, then every eigenvalue of $L$ is of the form
$$2 - omega^k - omega^-k = 2 - 2operatornameRe omega^k = 2 - 2 cos dfrac2kpi2n + 1,$$
$k = 0, ldots, 2n$.

This is maximum when the cosine is minimum, which happens when $dfrac2kpi2n + 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 = 2left[1 - cos dfrac2npi2n + 1 right].$$

share|cite|improve this answer

edited Mar 30 at 2:04

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you please explain the part where you start introducing cos? Where does it come from? What is $RE omega^k$
  $endgroup$
  – independentvariable
  Mar 29 at 21:35
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it is n-th root of unity
  $endgroup$
  – independentvariable
  Mar 29 at 21:36
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @independentvariable Yes, $omega = exp dfrac2pi i2n + 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 dfrac2kpi2n + 1$.
  $endgroup$
  – M. Vinay
  Mar 30 at 2:03
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3166610%2flargest-eigenvalue-of-the-laplacian-matrix-in-an-odd-cycle%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$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 frac2pi i2n + 1$ the $(2n + 1)$^th root of unity, then every eigenvalue of $L$ is of the form
$$2 - omega^k - omega^-k = 2 - 2operatornameRe omega^k = 2 - 2 cos dfrac2kpi2n + 1,$$
$k = 0, ldots, 2n$.

This is maximum when the cosine is minimum, which happens when $dfrac2kpi2n + 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 = 2left[1 - cos dfrac2npi2n + 1 right].$$

share|cite|improve this answer

edited Mar 30 at 2:04

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you please explain the part where you start introducing cos? Where does it come from? What is $RE omega^k$
  $endgroup$
  – independentvariable
  Mar 29 at 21:35
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it is n-th root of unity
  $endgroup$
  – independentvariable
  Mar 29 at 21:36
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @independentvariable Yes, $omega = exp dfrac2pi i2n + 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 dfrac2kpi2n + 1$.
  $endgroup$
  – M. Vinay
  Mar 30 at 2:03
  

  
  
  
  

add a comment | 

2

$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 frac2pi i2n + 1$ the $(2n + 1)$^th root of unity, then every eigenvalue of $L$ is of the form
$$2 - omega^k - omega^-k = 2 - 2operatornameRe omega^k = 2 - 2 cos dfrac2kpi2n + 1,$$
$k = 0, ldots, 2n$.

This is maximum when the cosine is minimum, which happens when $dfrac2kpi2n + 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 = 2left[1 - cos dfrac2npi2n + 1 right].$$

share|cite|improve this answer

edited Mar 30 at 2:04

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you please explain the part where you start introducing cos? Where does it come from? What is $RE omega^k$
  $endgroup$
  – independentvariable
  Mar 29 at 21:35
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think it is n-th root of unity
  $endgroup$
  – independentvariable
  Mar 29 at 21:36
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @independentvariable Yes, $omega = exp dfrac2pi i2n + 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 dfrac2kpi2n + 1$.
  $endgroup$
  – M. Vinay
  Mar 30 at 2:03
  

  
  
  
  

add a comment | 

$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 frac2pi i2n + 1$ the $(2n + 1)$^th root of unity, then every eigenvalue of $L$ is of the form
$$2 - omega^k - omega^-k = 2 - 2operatornameRe omega^k = 2 - 2 cos dfrac2kpi2n + 1,$$
$k = 0, ldots, 2n$.

This is maximum when the cosine is minimum, which happens when $dfrac2kpi2n + 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 = 2left[1 - cos dfrac2npi2n + 1 right].$$

share|cite|improve this answer

edited Mar 30 at 2:04

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

$endgroup$

share|cite|improve this answer

edited Mar 30 at 2:04

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135

answered Mar 29 at 2:43

M. VinayM. Vinay

7,28822135