Eigenvalue problems for matrices over finite fields Suppose I have a symmetric matrix A with entries in a finite field. In particular, I have the case in mind where $A \in \{0,1\}^{n \times n}$ and want to treat the entries as elements of $GF(2)$. How much is known about the eigenvalue problem in this case? Is there a spectral theorem? Are there fast algorithms for computing eigenvectors?
 A: I'm not quite sure what you mean by a spectral theorem in this context. So I will list some thoughts/facts that come to mind, and may be related to what you want to ask about.


*

*More often than not the eigenvalues belong to an extension field of $GF(2)$. Therefore finding eigenvectors and eigenvalues forces us to first define those extensioin fields. That is straightforward.

*Jordan canonical form of any matrix is still there. Nominally it exists over an algebraic closure $K$ of $GF(2)$, but we obviously get away with a finite subfield of $K$ generated over $GF(2)$ by the eigenvalues.

*You specifically ask about symmetric matrices. Here there is a marked difference to the case of symmetric real matrices. Symmetry of a matrix does not mesh at all well with it being over a field of characteristic two. There is no reason to expect such a matrix to be diagonalizable (not even over $K$). As examples I proffer
$$
A=\left(\begin{array}{cc}0&1\\1&0\end{array}\right)\quad\text{and}\quad
B=\left(\begin{array}{cc}1&1\\1&1\end{array}\right).
$$
The characteristic polynomial of $A$ is $x^2+1=(x+1)^2$. But we see that the eigenspace of the sole eigenvalue $\lambda=1$ is just 1-dimensional, and hence $A$ is not diagonalizable. Similarly the characteristic polynomial of $B$ is $x^2$, and again the eigenspace of the sole eigenvalue $\lambda=0$ is 1-dimensional. In both cases the eigenspace is spanned by $(1,1)^T$.

*Algorithmically finding a generalized eigenspace decomposition (=the Jordan blocks) should not be any harder than factoring the characteristic polynomial. There is an algorithm due to Berlekamp for doing that. I have not thought this through in detail, so please take this with a grain of salt.

