Re: [igraph] Negative eigenvalues of a laplacian matrix

[Gabor Csardi]

Ok, the results are all right for me, this is about numeric accuracy 
only. These are the smallest eigenvalues:

[106]  6.992917e-01  4.151255e-01  5.454894e-15  6.661338e-16  6.661338e-16
[111]  3.522995e-16  4.097342e-17  3.422020e-17  0.000000e+00 -9.300142e-17

The last eight are zero, that means that there are eight components 
in the graph:

> no.clusters(cg)
[1] 8

Probably you want to round the 'almost zero' values to zero:

eig$values <- ifelse(eig$values > 1e-14, eig$values, 0)

G.

On Mon, Jul 14, 2008 at 06:35:27PM +0900, MATSUDA, Noriyuki wrote:
> Sorry:
>
>    Here are the correct URL:
>      http://www.sk.tsukuba.ac.jp/~mazda/dUG/dA/cg.Rdata
>      http://www.sk.tsukuba.ac.jp/~mazda/dUG/dA/cg.pdf
>
> On 2008/07/14, at 18:04, Gabor Csardi wrote:
>
>> On Mon, Jul 14, 2008 at 06:00:10PM +0900, MATSUDA, Noriyuki wrote:
>>> Hello:
>>>
>>>    I am having a problem with my graph which produces negative
>>> eigenvalues of its laplacian matrix:
[...]
>>>     graph plot: http:www.sk.tsukuba.ac.jp/~mazda/dA/cg.Rdata
>>>     Rscript:
>>>        library(igraph)
>>>        load(file="..../cg.Rdata)
>>>        lap <- graph.laplacian(cg)
>>>        eig <- eigen(lap)
>>>    Results:  the smallest three eigen values
>>>        0.000, -1.822e-15, -7.549e-15
>>
>> These are not negative, these are in reality zero, only the numeric
>> precision/computation makes them look like negative.
>>
>>>    The problem:
>>>       All the eigenvalues of a laplacian matrix are non-negative
>>> according to the references, e.g.,
>>>           http://www.cs.berkeley.edu/~demmel/cs267/lecture20/
>>> lecture20.html
>>>     The possible cause:
>>>         eig[,113] is zero with an exception of eig[114,113]=-1
>>>
[...]

-- 
Csardi Gabor <address@hidden>    UNIL DGM