12
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

12
$\begingroup$

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.
$\endgroup$
1
  • 2
    $\begingroup$ Thanks for the detailed response. Do you happen to know a reference discussing these in more detail? By spectral theorem I meant the existence of a complete set of eigenvectors, i.e., a set of eigenvectors which serves as the basis of the whole space. According to your post, the answer is negative. $\endgroup$
    – passerby51
    Commented Feb 22, 2014 at 15:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .