Calculate the algebraic multiplicity of known eigenvalues of a large, sparse matrix

Question

I have a large (and sparse) matrix with size 1000x1000 -- 10000x10000. I believe i know all eigenvalues for the matrices. All entries are integers and so are the eigenvalues.

I want to check this by calculating the algebraic multiplicity of the eigenvalues and see if they sum up to the dimension my matrix implying I have all the eigenvalues. I know the matrices to be non-diagonalizable, which makes it non-sufficient to calculate the dimension of each corresponding nullspace. I also need to do the calculations symbolically (numerically I seem to have found them all at least within error margin). I have tried calculation the characteristic polynomial but this seems to be very slow. Once I have the characteristic polynomial checking multiplicity would have been a simple task.

Anyone have any ideas?

I guess the question simplifies to: How do i find the algebraic multiplicity of a known eigenvalue when the matrix is large and sparse?

Answer 1

This is not a complete answer (no code) but really too long for a comment.

First, you might try computing the characteristic polynomial by interpolation. To do this you would need to compute Det[mat-j*identity] for n distinct values of j, where mat is nxn and identity is the identity matrix of same dimension. My guess is built in CharacteristicPolynomial is getting bogged down in attempting this. You might, possibly, be able to do it numerically and still get sufficient accuracy to obtain the correct exact form after rounding. This could give a speed boost over the internal method.

Second is that, if you have to work with null spaces, the multiplicity of an eigenvalue lambda corresponds to the size of the largest null space for MatrixPower[(mat-lambda*identity),k] as k is increased (could use n but really that's overkill). Unless you suspect there are eigenvalues of high multiplicity, you could simply iterate this null space computation until the dimension stabilizes; once the dimension stops increasing from k to k+1, it cannot increase later.