A matrix of order 8 over $\mathbb{F}_3$

Question

What is an example of an invertible matrix of size 2x2 with coefficients in $\mathbb{F}_3$ that has exact order 8?

I have found by computation that the condition that the 8th power of a matrix $\begin{bmatrix}a & b\\c & d\end{bmatrix}$ is the identity is $$ b c (a + d)^2 (a^2 + 2 b c + d^2)^2 + ((a^2 + b c)^2 + b c (a + d)^2)^2=1, \qquad b (a + d) (a^2 + 2 b c + d^2) (a^4 + 4 a^2 b c + 2 b^2 c^2 + 4 a b c d + 4 b c d^2 + d^4)=0, \qquad c (a + d) (a^2 + 2 b c + d^2) (a^4 + 4 a^2 b c + 2 b^2 c^2 + 4 a b c d + 4 b c d^2 + d^4)=0, \qquad b c (a + d)^2 (a^2 + 2 b c + d^2)^2 + (b c (a + d)^2 + (b c + d^2)^2)^2=1 $$ and the condition for invertibility is $ad\neq bc$. If the 4th power is not the identity, then no power that is not a multiple of 8 is not the identity (because we could cancel out to either get that the first power is the identity or that the second power is the identity, both lead to contradiction). That is another cumbersome condition to write out.

I hope somebody can suggest a nicer way.

Answer 1

Using a similar strategy to Travis, we can actually answer this question quite nicely: $$A \text{ has order 8 if and only if }\det(A) = 2 \text{ and } \text{tr}(A) \neq 0.$$ We can do this by looking at the characteristic polynomial $p(x)$ of $A$, with which we can utilize the fact that $p(A) = 0$ as shown below.

Since $A$ is a $2\times 2$ matrix, this takes the simple form $p(x) = x^2 - tx + d$ where $t$ is the trace of $A$ and $d$ the determinant (which cannot be 0 since $A$ is invertible). If the trace is 0, then $A^2 = dI$ and so has order $2$ if $d = 1$ and 4 if $d = 2$. Thus if we are looking for an invertible matrix $A$ with order 8, we know that $d$ and $t$ must be nonzero.

We can now calculate powers of $A$ quite readily through successive squaring, use two key observations to simplify the calculations: 1)in $\mathbb{F}_3$, 2 is the same as $-1$ and so we can replace any appearance of 2 with a negative sign and 2) since $t$ and $d$ are both either $1$ or $2 = -1$, it is always true that $t^2 = d^2 = 1$. The calculations in $\mathbb{F}_3$ are as follows, using the fact that $p(A) = 0$: $$A^2 = tA-dI$$ $$ A^4 = (tA-dI)^2 = A^2+tdA + I = t(1+d)A + (1-d)I,$$ $$ A^8 = (1+d)^2A^2+(1-d)^2I = -(d+1)A^2 + (d-1)I$$ $$\implies A^8 = [d(d+1)+(d-1)]I - t(d+1)A = -dI - t(d+1)A.$$ We can therefore conclude that the order of $A$ is 8 if and only if $-d = 1$ and $t(d+1) = 0$, which since $t \neq 0$ are both equivalent to $d = 2$. Therefore, an invertible matrix $A \in GL(2,\mathbb{F}_3)$ has order 8 iff $\det(A) = 2$ and tr$(A) \neq 0$ (which we showed is necessary before). You'll notice that this agrees with the concrete examples given by Travis and Chris Culter.

Answer 2

We can use the same approach but reduce drastically the complexity of the system in the entries $a, b, c, d$ if we instead look for a square root of some matrix with order $4$.

The matrix $A = \pmatrix{0&-1\\1&0}$ satisfies $A^2 = -I$ and so has order $4$ over any field of characteristic not $2$. In particular, if we can find a matrix $B$ such that $B^2 = A$, then $B$ will have order $8$.

Writing $B = \pmatrix{a&b\\c&d}$, the condition is equivalent to the system \begin{align} a^2 + bc &= 0\\ b(a + d) &= -1\\ c(a + d) &= 1\\ d^2 + bc &= 0 \end{align} The second equation implies that $b = \pm 1$, and by negating the matrix (which preserves the property that $B^2 = I$) we may assume $b = 1$, and substituting gives $a + d = -1$ and $c = -1$. The first and fourth equations give that $a, d = \pm 1$, and then the third equation gives that $$a = d = 1 ,$$ yielding the solution $$\pmatrix{1&1\\-1&1} .$$

Answer 3

If you're curious to know all matrices having order $8$, that can be done by brute force. In Python:

# Returns True if m is the 2x2 identity matrix.
def one(m):
  return np.array_equal(m, np.identity(2))

# Returns the square of m, reduced modulo 3.
def square(m):
  return np.vectorize(lambda n: n % 3)(np.dot(m, m))

# Iterate over all 81 2x2 matrices with values in F_3.
for (a,b,c,d) in itertools.product(range(3), repeat=4):
  if (a or b or c or d) == 2:
    # Choose the +/- representative that starts with a 1.
    continue
  m = np.array([[a,b],[c,d]])
  m_2 = square(m)
  m_4 = square(m_2)
  m_8 = square(m_4)
  if one(m_8) and not one(m_4):
    print '\\pm\\pmatrix{%d&%d\\\\%d&%d},\\;' % (a,b,c,d)

This outputs $12$ solutions:

$ \pm\pmatrix{0&1\\1&1},\; \pm\pmatrix{0&1\\1&2},\; \pm\pmatrix{1&1\\1&0},\; \pm\pmatrix{1&1\\2&1},\; \pm\pmatrix{1&2\\1&1},\; \pm\pmatrix{1&2\\2&0} $

Answer 4

If $A$ satisfies $A^8 = I$, then all of the eigenvalues $\lambda$ of $A$ satisfy $\lambda^8 = 1$. Rearranging and factoring gives $$0 = \lambda^8 - 1 = (\lambda^4 + 1)(\lambda^4 - 1) .$$ Since we want $A^4 \neq I$ (otherwise the order of $A$ divides $4$), at least one eigenvalue of $A$ must be a solution of $\lambda^4 + 1$.

But $$0 = \lambda^4 + 1 = (\lambda^2 - \lambda - 1) (\lambda^2 + \lambda - 1) ,$$ and both of the quadratic factors are irreducible, so the eigenvalues of $A$ must be the roots of $\lambda^2 \pm \lambda - 1$ for some choice of $\pm$, and hence that quantity is the characteristic polynomial of $A$. Any monic polynomial is the characteristic polynomial of its companion matrix, giving the solutions $$\pmatrix{0 & 1 \\ 1 & \mp 1} .$$ In fact, the uniqueness of the Jordan normal form implies that all matrices of order $8$ in $GL(2, \Bbb F_3)$ are conjugates of these.

Answer 5

An intuitive way to find a solution is to remember the connection between 2x2 matrices and complex numbers.

In the complex numbers, an element of order 8 is $e^{2\pi i/8}=(1+i)/\sqrt{2}$. The solution you're looking for is the corresponding matrix, multiplied by $\sqrt{2}$ to have integer entries. (The fact that this multiplication doesn't change the fact that it is a unit root is the only surprising bit (to me))

Answer 6

You already have quite a few nice solutions. So let's add another one, shall we? :)

Using the theory of finite fields: The field $\mathbb{F}_9$ is generated by an element of (multiplicative) order $8$, as all unit groups of finite fields are cyclic. Can you find such an element?

Now the unit group of $\mathbb{F}_{p^n}$ can, for all primes $p$ and all $n$, be found in $GL_n(\mathbb{F}_p)$ by taking companion matrices. Let $\alpha$ be a cyclic generator of the unit group, having minimal polynomial $f(x) \in \mathbb{F}_p[x]$. Then the companion matrix of $f(x)$ has the same order as $\alpha$.

So for your example, you only need to find a cyclic generator of the unit group of $\mathbb{F}_9$ and its minimal polynomial. This polynomial will be irreducible and monic over $\mathbb{F}_3$, there aren't that many choices to check there.

If you don't know enough about finite fields yet, you can take from this post that there is a matrix over order $8$ of the form $$\begin{pmatrix} 0 & a \\ 1 & b\end{pmatrix}.$$ As this matrix has to be invertible, we directly see $a \neq 0$, so there are only $6$ matrices to check here. It should also be quick to see that $b = 0$ will not work, so that only leaves you $4$ matrices.