<p>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 &amp; 1\\ 1 &amp; 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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-11-15T14:49:40.363Z
2011-11-15T14:49:40.363Z
John Watrous
<p>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)$.</p>

CC BY-SA 3.0
2011-11-15T18:18:25.983Z
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.
Mahdi Cheraghchi
<cc.complexity-theory><linear-algebra><matrices>
Complexity to calculate a full set of eigenvectors over a finite field
Dimitris
# Complexity to calculate a full set of eigenvectors over a finite field

(Asked by: username_0 on 2011-11-15)

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

**Tags:** cc.complexity-theory, linear-algebra, matrices
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-11-15. Score: 16 | Accepted answer

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.


---

