Eigenvalues for a 400x400 normalized laplacian of a graph

Click For Summary

Discussion Overview

The discussion revolves around the eigenvalues of a 400x400 normalized Laplacian matrix derived from a graph that is not connected. Participants are exploring the implications of obtaining a negative eigenvalue and questioning why the second eigenvalue is not zero.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant reports obtaining a negative eigenvalue and questions its validity in the context of a normalized Laplacian matrix.
  • The same participant notes that the second eigenvalue is not zero, which raises further questions about the properties of the matrix.
  • Another participant suggests that the issue may stem from the indexing of the matrix or array in Java, proposing that the matrix might have been filled starting at index 1 instead of index 0.

Areas of Agreement / Disagreement

Participants have not reached a consensus on the reasons behind the negative eigenvalue or the non-zero second eigenvalue. The discussion includes competing views regarding potential indexing issues.

Contextual Notes

There is uncertainty regarding the assumptions made about the matrix's indexing and how it may affect the eigenvalue calculations. The implications of the graph's connectivity on the eigenvalues are also not fully resolved.

kosmos
Messages
11
Reaction score
0
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
 
Physics news on Phys.org
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?)
 
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.
 
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?
 
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
 
Last edited by a moderator:
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.
 
Oh yes... that will crosscheck my implementation to generate normLaplacian of the graph. Thanks! ... Let me try that and come back!
 
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.
 
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...