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)$.
$\begingroup$
$\endgroup$
-
2$\begingroup$ In general, such a set of vectors exists over the "algebraic closure" of GF(2). Just in the same way that for real matrices one occasionally has look at complex eigenvalues/vectors. $\endgroup$ – Mahdi Cheraghchi Nov 15 '11 at 18:18
$\begingroup$
$\endgroup$
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.
