Eigenvalue problems for matrices over finite fields

Question

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?

Answer 1

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.