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

Eigenvalues for a 400x400 normalized laplacian of a graph

  1. Dec 28, 2011 #1
    This is related to spectral graph theory. I am getting the following eigenvalues for a 400x400 matrix which is a normalized laplacian matrix of a graph. The graph is not connected. So why am i getting a> a negative eigenvalue. b> why is not second eigenvalue 0? ..... I used colt(java) and octave to generate the eigenvalues and get the same eigenvalues from both.

    -96.40542543750111
    0.9999999999996338
    0.9999999999999974
    0.9999999999999979
    0.9999999999999981
    0.9999999999999983
    0.9999999999999984
    0.9999999999999984
    0.9999999999999984
    0.9999999999999986
    0.9999999999999987
    0.9999999999999988
    0.9999999999999988
    0.9999999999999988
    0.9999999999999988
    0.9999999999999988
    0.9999999999999988
    0.9999999999999988
    0.9999999999999989
    0.999999999999999
    0.999999999999999
    0.999999999999999
    0.999999999999999
    0.999999999999999
    0.999999999999999
    0.9999999999999991
    0.9999999999999991
    0.9999999999999991
    0.9999999999999991
    0.9999999999999991
    0.9999999999999992
    0.9999999999999992
    0.9999999999999992
    0.9999999999999992
    0.9999999999999992
    0.9999999999999992
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999993
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999994
    0.9999999999999996
    0.9999999999999996
    0.9999999999999996
    0.9999999999999996
    0.9999999999999996
    0.9999999999999996
    0.9999999999999996
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999997
    0.9999999999999998
    0.9999999999999998
    0.9999999999999998
    0.9999999999999998
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    0.9999999999999999
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000002
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000004
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000007
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.0000000000000009
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.000000000000001
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000013
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000016
    1.0000000000000018
    1.0000000000000018
    1.0000000000000018
    1.0000000000000018
    1.0000000000000018
    1.0000000000000018
    1.000000000000002
    1.000000000000002
    1.000000000000002
    1.000000000000002
    1.000000000000002
    1.0000000000000022
    1.0000000000000022
    1.0000000000000022
    1.0000000000000022
    1.0000000000000022
    1.0000000000000022
    1.0000000000000022
    1.0000000000000024
    1.0000000000000024
    1.0000000000000027
    1.0000000000000027
    1.0000000000000027
    1.0000000000000027
    1.000000000000003
    1.3333333333333321
    1.3333333333333324
    1.3333333333333328
    1.3333333333333333
    1.333333333333334
    1.3333333333333344
    1.345014696576227
    1.4999999999999982
    1.4999999999999982
    1.4999999999999984
    1.4999999999999991
    1.4999999999999991
    1.4999999999999993
    1.4999999999999996
    1.5
    1.5
    1.5000000000000002
    1.5000000000000004
    1.5000000000000004
    1.5000000000000004
    1.5000000000000007
    1.500000000000001
    1.5000000000000013
    1.5000000000000018
    1.5000000000000024
    1.5000000000000027
    1.5000000000000029
    1.500000000000003
    1.5604107409249577
    1.9999999999999971
    1.9999999999999978
    1.9999999999999982
    1.9999999999999984
    1.9999999999999987
    1.999999999999999
    1.9999999999999991
    1.9999999999999998
    2.0
    2.0
    2.0
    2.0000000000000004
    2.0000000000000004
    2.0000000000000004
    2.0000000000000004
    2.0000000000000004
    2.0000000000000004
    2.0000000000000004
    2.000000000000001
    2.000000000000001
    2.000000000000001
    2.000000000000001
    2.000000000000001
    2.0000000000000013
    2.0000000000000013
    2.0000000000000013
    2.0000000000000013
    2.0000000000000013
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.0000000000000018
    2.000000000000002
    2.000000000000002
    2.000000000000002
    2.000000000000002
    2.000000000000002
    2.000000000000002
    2.000000000000002
    2.0000000000000027
    2.0000000000000027
    2.0000000000000027
    2.0000000000000027
    2.0000000000000027
    2.0000000000000027
    2.0000000000000027
    2.000000000000003
    2.000000000000003
    2.000000000000003
    2.000000000000003
    2.0000000000000036
    2.0000000000000036
    2.0000000000000036
    2.0000000000000036
    2.0000000000000036
    2.000000000000004
    2.000000000000004
    2.000000000000004
    2.000000000000004
    2.000000000000004
    2.0000000000000044
    2.0000000000000044
    2.0000000000000044
    2.0000000000000044
    2.000000000000005
    2.000000000000005
    2.000000000000005
    2.0000000000000058
    2.0000000000000058
    2.0000000000000058
    2.000000000000006
    2.000000000000007
    2.000000000000007
    2.000000000000008
    2.000000000000008
    2.000000000000008
    2.0000000000000084
    2.0000000000000107
     
  2. jcsd
  3. Dec 28, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Looks like a problem with the lowest index of a matrix or array.

    In java 0 is the lowest index.
    That is v[0] is the first element of an array v.

    Did you perchance fill your matrix starting at index 1?
    (Or did you use a math package that expects 1 as the lowest index?)
     
  4. Dec 28, 2011 #3
    Hi ... I used 0 as the index. Also exported my 400x400 matrix to a csv file and got the same
    result using Octave too. So I guess there is nothing wrong with implementation. Something wrong with my matrix. But its symmetric ... I checked in the excel sheet.
     
  5. Dec 28, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    A property of the matrix is that all columns (or rows) should add to zero.
    This is also the reason that zero should be an eigenvalue.

    Do they?
     
  6. Dec 28, 2011 #5
    No they do not. But why should that be the case, because the diagonals of a normalized laplacian are all 1s. And rest of the cells are filled by -1/sqrt(degree_u*degree_v). So they need not add to -1. I am using this source for reference. www.math.ucla.edu/~butler/PDF/spectral1.pdf [Broken]
     
    Last edited by a moderator: May 5, 2017
  7. Dec 28, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

    Sorry, I was looking at the Laplacian matrix instead of the normalized Laplacian matrix.

    Still, you should have the eigenvalue 0 with the eigenvector ##D^{-\frac 1 2}\textbf{1}##.
    This is something you can verify by multiplying your matrix with this vector.
     
  8. Dec 28, 2011 #7
    Oh yes... that will crosscheck my implementation to generate normLaplacian of the graph. Thanks!! ... Let me try that and come back!
     
  9. Dec 28, 2011 #8
    The problem was with the reference I was using. It defined that entry is 1 whenever i==j and missed out the consition deg(i)!=0 ...... thanks for your help!!

    But though I do get the 0 as eigenvalues but the first eigenvalue is still coming out to be negative. That is supposed to be a zero as I counted from the number of zero eigenvalues needed from the configuration of my graph. It comes zero when the number of nodes i s less but becomes negative when it raises.
     
  10. Dec 28, 2011 #9

    I like Serena

    User Avatar
    Homework Helper

    Perhaps you can reduce the matrix to a manageable size?
    Say you select a few entries including an isolated vertex?
    Check you still get a negative eigenvalue.

    You could post the matrix then if you don't already see the problem yourself...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook