I am struggling to understand how diagonalization works in finite field matrices.
For instance, if I want ot find the characteristic polynomial of the matrix \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} I have to find the determinant of \begin{bmatrix} -\lambda & 0 & 0 & 1 \\ 1 & -\lambda & 0 & 0 \\ 0 & 1 & -\lambda & 0 \\ 0 & 0 & 1 & 1-\lambda \end{bmatrix}
That is $\lambda^4 + \lambda^3 +1$. But then how to find the roots since in $\mathbb{F}_2$, $1$ is also $-1$ ?
I think that since the matrix is full rank, it can be written as $M = QDQ^{-1}$, but I cannot find D...
Can you help me ?
Observe that the given matrix $A$ is the companion matrix of the irreducible polynomial $p(x) = x^4 + x^3 + 1$ over $\mathbb F_2.$ Given a root $\alpha$ of $p(x)$ in some extension of $\mathbb F_2,$ the evaluation homomorphism $\mathbf{ev}_\alpha : \mathbb F_2[x] \to \mathbb F_2[\alpha]$ defined by $\mathbf{ev}_\alpha(f(x)) = f(\alpha)$ induces an isomorphism $\mathbb F_2[x] / (p(x)) \cong \mathbb F_2[\alpha].$ By the Freshman's Dream, the roots of $p(x)$ in $\mathbb F_2[\alpha]$ are $\alpha,$ $\alpha^2,$ $\alpha^4 = \alpha^3 + 1,$ and $\alpha^8 = (\alpha^3 + 1)^2 = \alpha^3 + \alpha^2 + \alpha$ so that $$p(x) = (x - \alpha)(x - \alpha^2)(x - \alpha^3 - 1)(x - \alpha^3 - \alpha^2 - \alpha) \text{ in } \mathbb F_2[\alpha].$$
In order to find the Jordan Canonical Form of the given matrix $A$ over $\mathbb F_2,$ we will find the Smith Normal Form of $xI - A$ over $\mathbb F_2$ and so obtain the elementary divisors of $A.$ We do this by performing elementary row and column operators on the matrix $xI - A$ until we obtain a diagonal matrix whose diagonal entries are nonzero polynomials $f_1(x),$ $f_2(x),$ $f_3(x),$ and $f_4(x)$ such that $f_1(x) \,|\, f_2(x) \,|\, f_3(x) \,|\, f_4(x),$ $\mu(x) = f_4(x)$ is the minimal polynomial of $A$ over $\mathbb F_2,$ and $\chi(x) = f_1(x) f_2(x) f_3(x) f_4(x)$ is the characteristic polynomial of $A$ over $\mathbb F_2.$ Check that $$xI - A = \begin{pmatrix} \phantom -x & \phantom - 0 & \phantom -0 & -1 \\ -1 & \phantom -x & \phantom -0 & \phantom -0 \\ \phantom -0 & -1 & \phantom -x & \phantom -0 \\ \phantom -0 & \phantom -0 & -1 & x - 1 \end{pmatrix} \sim \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & x^4 + x^3 + 1 \end{pmatrix} = \operatorname{SNF}_{\mathbb F_2}(xI - A).$$ (Observe that the matrix $A$ is the companion matrix of the irreducible polynomial $p(x) = x^4 + x^3 + 1$ in $\mathbb F_2[x],$ so this should not be surprising.) Considering that the Smith Normal Form does not change when we pass to $\mathbb F_2[\alpha],$ we find that the only invariant factor of $A$ in $\mathbb F_2[\alpha]$ is $p(x).$ Consequently, the elementary divisors of $A$ are the linear polynomials $x - \alpha,$ $x - \alpha^2,$ $x - \alpha^3 - 1,$ and $x - \alpha^3 - \alpha^2 - \alpha,$ from which it follows that $$\operatorname{JCF}_{\mathbb F_2[\alpha]}(A) = \begin{pmatrix} \alpha & 0 & 0 & 0 \\ 0 & \alpha^2 & 0 & 0 \\ 0 & 0 & \alpha^3 + 1 & 0 \\ 0 & 0 & 0 & \alpha^3 + \alpha^2 + \alpha \end{pmatrix}.$$
One can find a discussion of the Jordan Canonical Form via the elementary divisor decomposition in (for instance) Chapter 12 of Dummit and Foote.