What is the origin of negative eigenvalues for Laplacian matrix?

Question

I'm trying to write some small clustering program in Python. I've constructed the Laplacian matrix L = D - W using symmetric adjacency matrix W and diagonal degree matrix D, D_ii = sum_j W_ij. Then I solved the generalized eigenvalue problem LC = qDC but get the few negative eigenvalues. The matrix is positive semi-definite, and should not have negative eigenvalues. But some why it does, does anybody know the reason and the remedy?

My code:

from scipy import linalg
import numpy as np


Lgth = len(W)
    D = np.zeros((Lgth, Lgth))
    L = np.zeros((Lgth, Lgth))
    for i, row in enumerate(W):
        D[i][i] = np.sum(row)
        for j, col in enumerate(row):
            if i != j:
                L[i][j] = -W[i][j]
            else:
                L[i][i] = D[i][i] - W[i][i]
    # Solve generalized eigenvalue problem for Laplacian.
    Vals, Vecs = linalg.eigh(L, D)

print "Eigenvalues: "
for i in range(0, 20, 1):
    print Vals[i]

And adjacency matrix W:

[[  1.00000000e+00   0.00000000e+00   0.00000000e+00   5.05923711e-01
    5.59769236e-01   0.00000000e+00   5.59769236e-01   0.00000000e+00
    5.36926368e-01   5.36926368e-01   5.83333333e-01   5.59769236e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.48258581e-01   0.00000000e+00   0.00000000e+00   5.36926368e-01
    5.36926368e-01   0.00000000e+00]
 [  2.57649644e-01   1.00000000e+00   0.00000000e+00   4.02503879e-01
    3.10858551e-01   0.00000000e+00   3.10858551e-01   0.00000000e+00
    0.00000000e+00   0.00000000e+00   2.57649644e-01   2.62028536e-01
    0.00000000e+00   5.11814230e-01   0.00000000e+00   5.59769236e-01
    3.42998367e-01   5.23416766e-01   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   0.00000000e+00   1.00000000e+00   2.82542119e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   3.00024531e-01
    2.82542766e-01   2.82542766e-01   3.00617698e-01   2.82542119e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    2.82542119e-01   0.00000000e+00   0.00000000e+00   2.82542766e-01
    2.82542766e-01   3.25760488e-01]
 [  5.05923711e-01   0.00000000e+00   0.00000000e+00   1.00000000e+00
    5.48258581e-01   0.00000000e+00   5.48258581e-01   0.00000000e+00
    4.28654701e-01   0.00000000e+00   5.05923711e-01   5.25770742e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   4.56059560e-01
    5.59769236e-01   0.00000000e+00   0.00000000e+00   4.28654701e-01
    4.28654701e-01   0.00000000e+00]
 [  5.59769236e-01   0.00000000e+00   0.00000000e+00   5.48258581e-01
    1.00000000e+00   0.00000000e+00   5.83333333e-01   0.00000000e+00
    5.14789860e-01   5.14789860e-01   5.59769236e-01   5.59769236e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.71460196e-01   0.00000000e+00   0.00000000e+00   5.14789860e-01
    5.14789860e-01   0.00000000e+00]
 [  0.00000000e+00   1.77312875e-04   0.00000000e+00   2.56797444e-05
    0.00000000e+00   1.00000000e+00   8.64182241e-06   0.00000000e+00
    0.00000000e+00   0.00000000e+00   8.64247435e-06   8.64182241e-06
    5.51127472e-01   3.05012287e-04   1.03764018e-02   3.46789942e-04
    0.00000000e+00   1.04752730e-03   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  5.59769236e-01   0.00000000e+00   0.00000000e+00   5.48258581e-01
    5.83333333e-01   0.00000000e+00   1.00000000e+00   0.00000000e+00
    5.14789860e-01   5.14789860e-01   5.59769236e-01   5.59769236e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.71460196e-01   0.00000000e+00   0.00000000e+00   5.14789860e-01
    5.14789860e-01   0.00000000e+00]
 [  0.00000000e+00   0.00000000e+00   3.00024531e-01   0.00000000e+00
    0.00000000e+00   0.00000000e+00   0.00000000e+00   1.00000000e+00
    1.58838568e-01   1.58838568e-01   1.25562386e-01   1.41467576e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    1.24174609e-01   0.00000000e+00   1.46121173e-01   1.58838568e-01
    1.58838568e-01   1.81745401e-01]
 [  5.36926368e-01   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.14789860e-01   0.00000000e+00   5.14789860e-01   0.00000000e+00
    1.00000000e+00   5.83333333e-01   5.36926368e-01   5.36926368e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    4.84757921e-01   0.00000000e+00   5.33347787e-01   5.83333333e-01
    5.83333333e-01   0.00000000e+00]
 [  5.36926368e-01   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.14789860e-01   0.00000000e+00   5.14789860e-01   0.00000000e+00
    5.83333333e-01   1.00000000e+00   5.36926368e-01   5.36926368e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    4.84757921e-01   0.00000000e+00   5.33347787e-01   5.83333333e-01
    5.83333333e-01   0.00000000e+00]
 [  5.83333333e-01   0.00000000e+00   0.00000000e+00   5.05923711e-01
    5.59769236e-01   0.00000000e+00   5.59769236e-01   0.00000000e+00
    5.36926368e-01   5.36926368e-01   1.00000000e+00   5.59769236e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.48258581e-01   0.00000000e+00   0.00000000e+00   5.36926368e-01
    5.36926368e-01   0.00000000e+00]
 [  5.59769236e-01   0.00000000e+00   0.00000000e+00   5.25770742e-01
    5.59769236e-01   0.00000000e+00   5.59769236e-01   0.00000000e+00
    5.36926368e-01   5.36926368e-01   5.59769236e-01   1.00000000e+00
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    5.48258581e-01   0.00000000e+00   0.00000000e+00   5.36926368e-01
    5.36926368e-01   0.00000000e+00]
 [  1.40009443e-04   2.12857698e-03   0.00000000e+00   5.12628159e-04
    0.00000000e+00   5.51127472e-01   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00   1.40009443e-04   0.00000000e+00
    1.00000000e+00   3.66159446e-03   3.26399375e-02   4.16311889e-03
    2.73808987e-04   8.01015216e-03   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  2.83700626e-01   5.11814230e-01   0.00000000e+00   4.16333173e-01
    3.34216982e-01   0.00000000e+00   3.34216982e-01   0.00000000e+00
    0.00000000e+00   0.00000000e+00   2.83700626e-01   2.92867446e-01
    0.00000000e+00   1.00000000e+00   0.00000000e+00   3.56963923e-01
    2.42357402e-01   2.99519337e-01   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   2.57603859e-01   5.68044344e-02   7.33051584e-02
    6.31949522e-02   0.00000000e+00   6.31949522e-02   0.00000000e+00
    0.00000000e+00   0.00000000e+00   4.72517992e-02   0.00000000e+00
    0.00000000e+00   1.45217080e-01   1.00000000e+00   1.51267211e-01
    0.00000000e+00   3.10277091e-01   5.05103349e-02   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  3.10858551e-01   5.59769236e-01   0.00000000e+00   4.56059560e-01
    3.66214895e-01   0.00000000e+00   3.66214895e-01   0.00000000e+00
    0.00000000e+00   0.00000000e+00   3.10858551e-01   3.20903611e-01
    0.00000000e+00   3.56963923e-01   0.00000000e+00   1.00000000e+00
    4.02503879e-01   5.02186439e-01   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  5.48258581e-01   0.00000000e+00   0.00000000e+00   5.59769236e-01
    5.71460196e-01   0.00000000e+00   5.71460196e-01   0.00000000e+00
    4.84757921e-01   4.84757921e-01   5.48258581e-01   5.48258581e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    1.00000000e+00   0.00000000e+00   0.00000000e+00   4.84757921e-01
    4.84757921e-01   0.00000000e+00]
 [  0.00000000e+00   5.23416766e-01   0.00000000e+00   3.45975244e-01
    2.57603859e-01   0.00000000e+00   2.57603859e-01   0.00000000e+00
    0.00000000e+00   0.00000000e+00   2.12514220e-01   2.16986592e-01
    0.00000000e+00   2.99519337e-01   3.10277091e-01   5.02186439e-01
    2.84910039e-01   1.00000000e+00   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00]
 [  4.91816808e-01   0.00000000e+00   0.00000000e+00   3.93924057e-01
    4.71560149e-01   0.00000000e+00   4.71560149e-01   0.00000000e+00
    5.33347787e-01   5.33347787e-01   4.91816808e-01   4.91816808e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    4.45381336e-01   0.00000000e+00   1.00000000e+00   0.00000000e+00
    3.56963923e-01   0.00000000e+00]
 [  5.36926368e-01   0.00000000e+00   0.00000000e+00   4.28654701e-01
    5.14789860e-01   0.00000000e+00   5.14789860e-01   0.00000000e+00
    5.83333333e-01   5.83333333e-01   5.36926368e-01   5.36926368e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    4.84757921e-01   0.00000000e+00   0.00000000e+00   1.00000000e+00
    5.83333333e-01   0.00000000e+00]
 [  5.36926368e-01   0.00000000e+00   0.00000000e+00   4.28654701e-01
    5.14789860e-01   0.00000000e+00   5.14789860e-01   0.00000000e+00
    5.83333333e-01   5.83333333e-01   5.36926368e-01   5.36926368e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    4.84757921e-01   0.00000000e+00   0.00000000e+00   5.83333333e-01
    1.00000000e+00   0.00000000e+00]
 [  2.56083291e-01   0.00000000e+00   3.25760488e-01   0.00000000e+00
    2.58159874e-01   0.00000000e+00   2.58159874e-01   0.00000000e+00
    3.26061780e-01   3.26061780e-01   2.56083291e-01   2.71995270e-01
    0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00
    0.00000000e+00   0.00000000e+00   0.00000000e+00   3.26061780e-01
    3.26061780e-01   1.00000000e+00]]

Thanks for help!

Answer 1

The problem was that the adjacency matrix is not symmetric as pointed by Rocherz. When fixed and W is made symmetric, the eigenvalues are correct, although some are still negative but those have an order of magnitude consistent with round-off error. Thanks for your time guys!

Answer 2

Does your Laplacian matrix come from an undirected graph?

1. $W$ should be symmetric, with zeros along the main diagonal, and either zeros or ones elsewhere.
2. The diagonal entries of $L$ must be exactly those of $D$ but they aren't. One does not substract the diagonal entries of $W$ (which should be zeros anyway) as in your else statement.