Suppose I have an $n \times n$ matrix with $O(n)$ nonzero elements.
With what time complexity could the eigenvalues or characteristic polynomial of this matrix be computed?
More easily, suppose I already know that $1$ is an eigenvalue of this matrix. With what time complexity could I check if $1$ is a simple eigenvalue?
If it helps, I can assume that the number of nonzero in entries in each column is bounded by a constant.
While this question is very far away from my area of expertise, I gathered from a brief search that algorithms of Keller-Gehrig can calculate the characteristic polynomial, and hence the eigenvalues, of a matrix in approximately the same number of steps as general matrix multiplication. However, these algorithms involve putting a matrix to a very high power, and in my case, after I put my matrix to a high power, it will lose its sparsity, and calculations will not be any faster than in the general case. I'm curious if there is a way around this. It would be great if, for example, one could check if the eigenvalue $1$ of my matrix is simple in, say, $O(n)$ time.