eig and zero eigenvalues

I am working with a Laplacian matrix, L, and my understanding is that 0 will always be an eigenvalue of L with an algebraic multiplicity of at least 1. However, when I take

L = [2 -1 -1 0 0; 0 2 -1 -1 0; 0 0 2 -1 -1; -1 0 0 2 -1; -1 -1 0 0 2]

and compute eig(L), the result displays as

0.0000

2.5000 + 1.5388i

2.5000 - 1.5388i

2.5000 + 0.3633i

2.5000 - 0.3633i

but nnz(e) gives 5, and e > eps gives [1 1 1 1 1].

How do I get MATLAB to produce or recognize a truly 0 first/smallest eigenvalue? On my machine (MacBook Pro, OS X (10.6.8), MATLAB 7.12.0 (R2011a)), eps = 2.2204e-16 and that "zero" eigenvalue is actually 4.0392e-16.

I am interested in the algebraic multiplicity of the 0 eigenvalue and the smallest non-zero eigenvalue.

Answer 1

[Titus Edelhofer]

Hi,

your test is slightly wrong:

abs(e)>eps
ans =
   0
   1
   1
   1
   1

Titus

[Matt]

I still get [1 1 1 1 1] when I try abs(e) > eps.

[Titus Edelhofer]

Hi Matt,

sorry, I did not read your post carefully enough. On my machine I got -6e-17 as the first entry (smaller then eps). The test needs to be somewhat more careful:

abs(e)>eps(2)

because you have values of 2 on your diagonal. Then it should work.

Titus

[Matt]

Ah, there we go. That works for me now.

Since values of 2 on my diagonal mean I need to compare to eps(2), would a max value of k on my diagonal mean I need to compare to eps(k)? Or equivalently, determine ((1.0/k)*e) > eps?

[Titus Edelhofer]

Hi Matt,

what the "exact" factor would be, I don't know (L_inf norm of L, L_2 norm of L, something like that). Using norm(L, inf) should be a good value.

Titus

[Matt]

Hi Titus,

That's working well. Thanks.