I am applying Normalized Cuts on images of size 1024 x 1024, but the eigenvalues are coming very small and some are negative.

I am when following the literature and trying to apply bi-partition via normalized cuts, my Laplacian matrix is not coming positive definite and hence the first eigen value is coming negative and the correct partition is been done by 6 th or 7th eigen vector. It means that the eigen values till 5th place or 6th place are of order 10^-17 to 10^-4 .

Can any one suggests why this is happening. I used gaussian similarity to find weight and followed Jean's Gallier spectral clustering tutorial. I am using Matlab and eigs(Lsym,10,'SM') to find eigenvalues. Kindly help.