I am trying to find the 2 eignevectors of the 2 smallest eigenvalues of a laplacian. I do this by 

[v,c]=eigs(L,M,2,'SM');

Where L is the lapalcian and M is the mass matrix.

As a result I get the error 

Error using eigs/checkInputs/LUfactorAminusSigmaB (line 1041) The shifted operator is singular. The shift is an eigenvalue. Try to use some other shift please. Error in eigs/checkInputs (line 855) [L,U,pp,qq,dgAsB] = LUfactorAminusSigmaB; Error in eigs (line 94) [A,Amatrix,isrealprob,issymA,n,B,classAB,k,eigs_sigma,whch, ...

Does this mean I am doing something wrong, or is this just matlab choosing a bad initial guess for its iteration process?

The matrices I am using should have a descent condition number... 

Answers: 

I ran into the same problem while implementing normalized cuts segmentation. The condition number is actually infinite because the smallest eigenvalue is 0, and this is basically what MATLAB's error message is about. It's running LU decomposition first.

I just added a multiple of I, 10*eps*speye, to the normalized Laplacian to improve conditioning and that fixed it.