# Hardness of finding eigenvalues?

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?

• 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. – Suresh Venkat Jul 6 '11 at 16:07
• 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. – WuTheFWasThat Jul 6 '11 at 17:57
• Well, it seems finding eigenvalues/eigenvectors of matrices over finite fields is easy, thanks to Berlekamp's algorithm, etc. – WuTheFWasThat Jul 6 '11 at 18:17
• so that part of the question is resolved ? – Suresh Venkat Jul 7 '11 at 4:32
• corss-posted on MSE – Kaveh Jul 21 '11 at 23:56