Finding the eigenvalues of a sparse, symmetric, binary matrix with all zeros in the diagonal?

Question

What would be the best way? (By binary I mean that all of the elements are either zero or one.)

Answer 1

Maybe the direct way will do: eigenvalues would be the solutions to the equation det(X-Lambda)=0, where X - your matrix, and Lambda=diagonal matrix with lambda on the diagonal. Hopefully the determinant will be not so hard to find for a sparse binary matrix.

Also: check if this matrix is an orthogonal projection matrix on some subspace. Then eigenvalues should be 1 and 0 (I think). You remember how to check if it's an orthogonal projection? X*X=X and symmetric (I think so, but double-check me).

Add: no, I don't know a thing about graph theory, so it wouldn't have told me anything :)