Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Eigenvalues of Laplacian Matrix

  1. Jan 16, 2015 #1

    joshmccraney

    User Avatar
    Gold Member

    hi pf!

    I am reading a text and am stuck at a part. this is what is being said:

    If ##g## is a graph we have ##L(g) + L(\bar{g}) = nI - J## where ##J## is the matrix of ones. Let ##f^1,...f^n## be an orthogonal system of eigenvectors to ##L(g) : f^1 = \mathbb{1}## and ##L(g)f^i = \lambda_i f^i##. Evidently ##L(g) + L(\bar{g}) = nI - J## implies ##L(\bar{g}) f^1 = 0##.

    Now for ##2 \leq i \leq n## we have ##L(\bar{g}) f^i = (n-\lambda_i)f^i##

    The text continues by saying ##\lambda_1(\bar{g}) = 0##

    Thus we have that ##\lambda_i(\bar{g}) = n - \lambda_{n-i+2}(g) : i \geq 2##. This is the part I don't understand. If eigenvalues of ##L(g)## are eigenvalues to ##L(\bar{g})## then I see that ##\lambda_i (\bar{g})f^i = (n-\lambda_i)f^i \implies \lambda_i (\bar{g}) = n-\lambda_i(g)## but the index is now wrong...please help me out!

    Thanks so much!

    Josh
     
    Last edited: Jan 16, 2015
  2. jcsd
  3. Jan 17, 2015 #2

    joshmccraney

    User Avatar
    Gold Member

    Can anyone help me out? Am I in the wrong section?
     
  4. Jan 17, 2015 #3
    That is because the author puts eigenvalues in the increasing (non-decreasing, to be precise) order. You are correct that ##L(\overline g) f^i = (n-\lambda_i) f^i## for ##i\ge2##, so ##n-\lambda_i##, ##i\ge 2## are eigenvectors of ##L(\overline g)##. Putting them into non-decreasing order you get exactly the formula you quoted.
     
  5. Jan 17, 2015 #4

    joshmccraney

    User Avatar
    Gold Member

    Could you elaborate a little? I'm a little confused on what you mean by "putting" them in non-decreasing order.
     
  6. Jan 18, 2015 #5
    The eigenvalues of ##L(g)## are ##0=\lambda_1\le \lambda_2\le\lambda_3 \le \ldots \le \lambda_n##. The eigenvalues of ##L(\overline g)## are ##0, n-\lambda_1, n-\lambda_2, \ldots, n-\lambda_n##. From the above inequalities for ##\lambda_i## we can write ##n-\lambda_n\le n-\lambda_{n-1}\le\ldots\le n-\lambda_2##. A Laplacian is always positive semidefinite, so all eigenvalues are non-negative. So, ##0=\lambda_1\le n-\lambda_n\le n-\lambda_{n-1}\le\ldots\le n-\lambda_2## gives us all eigenvalues of ##L(\overline g)## in non-decreasing order. And by ##\lambda_k(\overline g)## the author means item # ##k## on this list.
     
  7. Jan 19, 2015 #6

    joshmccraney

    User Avatar
    Gold Member

    Thanks so much! I really appreciate this Hawkeye!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook