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

<p>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?)</p>

<p>How about finding eigenvalues/eigenvectors of sparse matrices? </p>

CC BY-SA 3.0
2011-07-06T16:07:39.560Z
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
CC BY-SA 3.0
2011-07-06T17:57:06.610Z
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
CC BY-SA 3.0
2011-07-06T18:17:04.877Z
Well, it seems finding eigenvalues/eigenvectors of matrices over finite fields is easy, thanks to Berlekamp's algorithm, etc.
WuTheFWasThat
CC BY-SA 3.0
2011-07-07T04:32:41.493Z
so that part of the question is resolved ?
Suresh Venkat
CC BY-SA 3.0
2011-07-21T23:56:21.690Z
[corss-posted on MSE](http://math.stackexchange.com/questions/49770/hardness-of-finding-eigenvalues-over-finite-fields)
Kaveh
CC BY-SA 3.0
2012-03-19T12:28:16.013Z
Is the complexity of finding eigenvalues any easier if we consider symmetric matrices over the non negative integers?
Jernej
<linear-algebra>
Hardness of finding eigenvalues?
WuTheFWasThat
# Hardness of finding eigenvalues?

(Asked by: username_0 on 2011-07-06)

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?

**Tags:** linear-algebra

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: Well, it seems finding eigenvalues/eigenvectors of matrices over finite fields is easy, thanks to Berlekamp's algorithm, etc.  
> **username_1**: so that part of the question is resolved ?  
> **username_2**: [corss-posted on MSE](http://math.stackexchange.com/questions/49770/hardness-of-finding-eigenvalues-over-finite-fields)  
> **username_3**: Is the complexity of finding eigenvalues any easier if we consider symmetric matrices over the non negative integers?  

---

## 0 answers

