Over $\mathbb{F}_2$, find a $5\times 5$ matrix of order 31.

Question

So I found that $x^5+x+1$ is irreducible over $\mathbb{F}_2$ and produced the quotient, a field of order $32$. Now, I need to find a $5\times 5$ matrix of order 31 over $\mathbb{F}_2$. I don't see the direction to take here. Could someone point me in the right direction?

Answer 1

Unfortunately, Anurag A deleted his answer, so I can’t comment. He misunderstood your question, but he still basically gave the answer.

He suggested finding a generator $g$ of $\mathbb F_{2^5}^× = \mathbb F_{32}^×$, which is a group of order $31$ and then use the diagonal matrix $gI$, which would be a matrix with coefficients in $\mathbb F_{2^5}$, not $\mathbb F_2$.

But instead, you can take any $\mathbb F_2$-basis of $\mathbb F_{2^5}$ and calculate the transformation matrix of $g$ as an $\mathbb F_2$-linear map $\mathbb F_{2^5} → \mathbb F_{2^5}$, corresponding to that basis. This yields a matrix of the same muliplicative order as $g$, that is of order $31$.

Finally, since $31$ is prime, any nontrivial element of $\mathbb F_{2^5}^×$ is a generator of it, for example $[x]$ itself. Using $[x]^5 + [x]^2 + 1 = 0$, its transformation matrix for the basis $1, [x], …, [x]^4$ is easy to calculate.

Answer 2

The other answers show what you could do to get an order 31 matrix over $\mathbb{F}_{2^5}$, assuming you have an irreducible polynomial to construct $\mathbb{F}_{2^5}$ from. The trouble you're having is probably due to the fact that $x^5+x+1$ is not actually irreducible over $\mathbb{F}_2$: it factors as $(x^2+x+1)(x^3+x^2+1)$.

Answer 3

Take the companion matrix of the irreducible polynomial $x^5+x^2+1$ (thanks @Jyrki Lahtonen): $$ A = \pmatrix{ 0&0&0&0&1 \\1&0&0&0&0 \\0&1&0&0&1 \\0&0&1&0&0 \\0&0&0&1&0 }. $$