Mark Gritter (markgritter) wrote,
Mark Gritter

Eigenvector decomposition on finite fields

I thought this question on Quora about eigenvalue decomposition of matrices over finite fields was interesting, and I answered it (in the affirmative, the eigenvalue decomposition is possible but sometimes the eigenvalues require an extension to the field.) Unfortunately "polynomial time" does not mean "feasible" when your matrix becomes large.

For real-valued matrices there are a variety of algorithms that do clever things I don't understand to compute the eigenvalues quickly as limiting sequences.

To experiment: what happens if you run these algorithms with finite fields instead? Seems like you either ought to get convergence or cycles, but it's not clear that either would tell you anything about the eigenvalues.

All this reminds me that I should post my Tubulo solver on Combinatorium, as long as I've got the domain registered... and I still have some work I'd like to do on sliding and match-3 games.
Tags: linear algebra, mathematics
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.