# A method for finding the number of eigenvectors with a given, known eigenvalue

Is there a method for finding the number of eigenvectors with a given eigenvalue? I do not need the eigenvectors themselves, and to find the eigenvectors seems quite tough, given the comments on the answer to the question Compute eigenvectors of a matrix with known eigenvalue spectrum.

I have many randomly-generated adjacency matrices $$M$$ with dimensions roughly $$10^5$$ x $$10^5$$ with elements $$0$$ or $$1$$. I can show analytically that these matrices are very likely to have many (roughly $$10^3$$) eigenvalues that are exactly $$1$$. The other eigenvalues are within a roughly symmetric eigenspectrum about $$0$$ and have a rough spacing of around $$10^{-4}$$ between adjacent eigenvalues, including near $$1$$. I am interested in the number of degenerate eigenvalues at $$1$$.

I'm tempted to try shift-invert with Scipy's sparse package which uses ARPACK and LAPACK, though I've often found that shift-invert struggles with interior eigenvalues when the level spacing is small.

However, I am wondering if there's a way to avoid interior eigensolving altogether and to estimate instead the number of degenerate eigenvalues through more clever means.

As an aside, for my particular problem, I am happy with approximate algorithms so long as the error in the degeneracy is bounded by $$5$$% of the true degeneracy, or, maybe more practically, if a $$95$$% confidence interval has a width of $$10%$$.

• If this is a symmetric matrix with entries 0/1, then it seems to me that there can only be a 1 in each row, otherwise you'd have eigenvalues larger than 1. Is that correct? Or is there some scaling missing in your description? Nov 2, 2021 at 7:53
• Anyhow, if you are doing this to compute the number of connected component of a graph, probably a "normal" connectivity check via a graph visit would be cheaper. Nov 2, 2021 at 7:55
• @FedericoPoloni There can be eigenvalues larger than $1$; I just expect there to be a very large number of eigenvalues that are exactly $1$. Nov 2, 2021 at 23:06

## 1 Answer

If you know $$\lambda$$, then the eigenvalue problem $$Ax=\lambda x$$ comes down to finding a vector $$x$$ so that $$(A-\lambda I)x=0$$. In other words, you want to characterize the null space of the matrix $$B=A-\lambda I$$. If all you care about is the multiplicity of $$\lambda$$, what you are asking is about the dimension of the null space of $$B$$.

You can do this via a rank-revealing QR decomposition, for example. That may still be more work that you are looking to do, though.

• Thanks, this is useful, since I know there exist certain rank estimating algorithms, like scipy's estimate_rank. The output rank being about $8x$ larger is a bit too much for that particular algorithm, but I think I'd be good with $5% error, which I'll add to the question statement. Nov 2, 2021 at 6:30 • @user196574 If I read the docs correctly, "8 larger" means$r+8$, not$8r\$. Nov 2, 2021 at 23:24
• @FedericoPoloni Thanks, I misread that! I'll give it a try for some smaller toy matrices to see if it works speedily. Nov 2, 2021 at 23:34
• @FedericoPoloni Confirming that scipy's estimate rank worked well for my sparse matrices. Nov 12, 2021 at 10:21