# 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 $$\mbox{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?

• 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$.