Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that each one of them obeys $${\bf A}{\bf x} = {\bf x}$$ again over $\mathbb{GF}(2)$.
Complexity to calculate a full set of eigenvectors over a finite field
cc.complexity theory;linear algebra;matrices
There will generally not exist a set of $n$ linearly independent vectors $x$ such that $Ax = x$; this can only happen for $A$ being the identity matrix. On the other extreme, there may be no such vectors at all. For example, the matrix$$ A = \left(\begin{array}{cc} 0 & 1\\ 1 & 1 \end{array}\right) $$has full rank, but there are no nonzero vectors $x$ such that $Ax = x$. This is consistent with the fact that the characteristic polynomial of $A$ is $\lambda^2 + \lambda + 1$, which is irreducible over GF(2).If you want to find the maximum number $k$ of linearly independent vectors $x$ such that $Ax=x$, compute the nullspace of $A - I$. This can be done using Gaussian elimination in time $O(n^3)$. Several other algorithms for this task also exist, and are described in textbooks on computational linear algebra.