Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?)

How about sparse matrices? What are the best known algorithms for finding eigenvalues/eigenvectors of a matrix which is exponential in the input size (number of non-zero entries)?

In general, is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or rather, not known to be computationally easy?

share|cite|improve this question
Sorry, but I'm not sure how this answers my question. Can you elaborate? It seems like none of the content of this article is obviously applicable/adaptable to finite fields or sparse matrices – Jeff Jul 6 '11 at 8:43
Then perhaps, I am wrong. I shall delete my comment. – user9413 Jul 6 '11 at 8:44
Pardon my ignorance, but finite fields don't really have a useful topology. Therefore I don't understand what you mean by convergence? Also vector spaces over finite fields are not equipped with anything resembling the real inner product, so the concept of QR-algorithm doesn't make sense at all. Would something like Berlekamp's factorization algorithm help you? – Jyrki Lahtonen Jul 6 '11 at 11:05
Sorry, my wording was confusing. I don't mean convergence topologically. I believe a QR decomposition still makes sense over a finite field. The question is whether repeatedly doing the QR algorithm iteration would eventually give you an upper triangular matrix. – Jeff Jul 6 '11 at 17:45
Yeah. Berlekamp's algorithm seems to kill this question. Thanks. – Jeff Jul 6 '11 at 18:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.