Is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or at least, not known to be computationally easy?

For example, how computationally hard or easy is it to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the dimension. (Does the QR algorithm still converge?)

How about finding eigenvalues/eigenvectors of sparse matrices?

  • 2
    $\begingroup$ to determine hardness, you'll need to specify the input more precisely. How is the finite field presented to the algorithm ? Also, sparse matrices can only potentially make it easier to find eigenvalues, so the $O(n^3)$ procedure still applies, and therefore the problem is not hard. $\endgroup$ – Suresh Venkat Jul 6 '11 at 16:07
  • $\begingroup$ Good point - Let's just say that the finite field is F_p for prime p. Then just represent the field elements as you would integers. $\endgroup$ – WuTheFWasThat Jul 6 '11 at 17:57
  • $\begingroup$ Well, it seems finding eigenvalues/eigenvectors of matrices over finite fields is easy, thanks to Berlekamp's algorithm, etc. $\endgroup$ – WuTheFWasThat Jul 6 '11 at 18:17
  • 1
    $\begingroup$ so that part of the question is resolved ? $\endgroup$ – Suresh Venkat Jul 7 '11 at 4:32
  • 1
    $\begingroup$ corss-posted on MSE $\endgroup$ – Kaveh Jul 21 '11 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.