7
$\begingroup$

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?

  • 0
    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 matrices2011-07-06
  • 0
    Then perhaps, I am wrong. I shall delete my comment.2011-07-06
  • 0
    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?2011-07-06
  • 1
    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.2011-07-06
  • 0
    Yeah. Berlekamp's algorithm seems to kill this question. Thanks.2011-07-06
  • 1
    If you replace the matrix with a module over a non-communicative ring the problems can be much harder, e.g. computing determinant of them is as hard as computing their permanent, in the non-commutative case the Gaussian elimination algorithm stop being efficient.2011-07-09
  • 0
    Thanks a lot Kaveh! That was exactly what I wanted to know. Actually, this case had occurred to me - I just wasn't sure what notions still make sense, but apparently people have papers about this, which I am now reading.2011-07-11

0 Answers 0