3
$\begingroup$

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%$.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2021 at 7:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2021 at 7:55
  • $\begingroup$ @FedericoPoloni There can be eigenvalues larger than $1$; I just expect there to be a very large number of eigenvalues that are exactly $1$. $\endgroup$
    – user196574
    Commented Nov 2, 2021 at 23:06

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user196574
    Commented Nov 2, 2021 at 6:30
  • $\begingroup$ @user196574 If I read the docs correctly, "8 larger" means $r+8$, not $8r$. $\endgroup$
    – Federico Poloni
    Commented Nov 2, 2021 at 23:24
  • $\begingroup$ @FedericoPoloni Thanks, I misread that! I'll give it a try for some smaller toy matrices to see if it works speedily. $\endgroup$
    – user196574
    Commented Nov 2, 2021 at 23:34
  • 2
    $\begingroup$ @FedericoPoloni Confirming that scipy's estimate rank worked well for my sparse matrices. $\endgroup$
    – user196574
    Commented Nov 12, 2021 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.