Solve a polynomial equation over a given ring of matrices

Find (representatives of) all the similarity classes of $3 \times 3$ matrices over $\mathbb{Z}/(2)$ which satisfy $p(x) = x^6 - 1$. Do the same for $4 \times 4$ matrices which satisfy $q(x) = x^{20} - 1$.

We begin by factoring $p(x)$ into irreducibles. Note that $p(x) = (x^3+1)(x^3-1) = (x^3-1)^2$ since $1 = -1$ in $\mathbb{Z}/(2)$. Moreover, $x^3-1 = (x-1)(x^2+x+1)$, and $x^2+x+1$ is irreducible over $\mathbb{Z}/(2)$ since it has no roots. Thus we have the irreducible factorization $p(x) = (x-1)^2(x^2-x-1)^2$.

Suppose now that $A$ is a $3 \times 3$ matrix over $\mathbb{Z}/(2)$ satisfying $p(x)$; then the minimal polynomial of $A$ divides $p(x)$ and has degree at most 3 (since it divides the characteristic polynomial, which has degree 3). The divisors of $p(x)$ having degree at most 3 are $x-1$, $(x-1)^2$, $x^2-x-1$, and $(x-1)(x^2-x-1)$. Note that the third polynomial, $x^2-x-1$, cannot be the minimal polynomial of a $3 \times 3$ matrix since no power of $x^2-x-1$ is divisible by a degree 3 polynomial. (See Prop. 20 in D&F.) For each remaining divisor of $p(x)$, once fixed as the minimal polynomial of $A$, the remaining invariant factors are determined. The possible lists of invariant factors for $A$ are thus as follows.

1. $x-1$, $x-1$, $x-1$
2. $x-1$, $(x-1)^2$
3. $(x-1)(x^2-x-1)$

The corresponding matrices in rational canonical form are then as follows.

1. $\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$
2. $\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$
3. $\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$

(Note that these matrices are also representatives of the conjugacy classes of the representation of $S_3$ by permutation matrices. Does this mean anything?)

Next we factor $q(x) = x^{20}-1$. We have $q(x) = (x^{10}+1)(x^{10}-1)$ $= (x^{10}-1)^2$, $x^{10}-1 = (x^5-1)^2$, and $x^5-1 = (x-1)(x^4+x^3+x^2+x+1)$. We claim that $r(x) = x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{Z}/(2)$. Certainly $r(x)$ has no roots, and thus no linear factors. Suppose now that $r(x) = (x^2+ax+b)(x^2+cx+d)$ has a quadratic factor. Multiplying out and comparing coefficients, we have $a+c=1$, $d+b+ac=1$, $ad+bc = 1$, and $bd=1$. Now $b=d=1$ by the fourth equation, that $ac=1$ by the second. Now $a=c=1$. But then $1 = a+c = 0$, a contradiction. So $r(x)$ has no quadratic factors, and thus is irreducible over $\mathbb{Z}/(2)$. So $q(x)$ factors into irreducibles as $q(x) = (x-1)^4(x^4-x^3-x^2-x-1)^4$.

Suppose now that $B$ is a $4 \times 4$ matrix satisfying $q(x)$. Then the minimal polynomial divides $q(x)$ and has degree at most 4. The divisors of $q(x)$ with this property are $x-1$, $(x-1)^2$, $(x-1)^3$, $(x-1)^4$, and $x^4-x^3-x^2-x-1$. The possible lists of invariant factors for $B$ are then as follows.

1. $x-1$, $x-1$, $x-1$, $x-1$
2. $x-1$, $x-1$, $(x-1)^2$
3. $(x-1)^2$, $(x-1)^2$
4. $x-1$, $(x-1)^3$
5. $(x-1)^4$
6. $x^4-x^3-x^2-x-1$

The corresponding matrices in rational canonical form are thus as follows.

1. $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$
2. $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$
3. $\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$
4. $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$
5. $\begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$
6. $\begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$

Every $4 \times 4$ matrix $B$ over $\mathbb{Z}/(2)$ such that $B^{20} = I$ is similar to exactly one matrix in this list.