3
$\begingroup$

I would want to make an example of a matrix $M \in GL_3(\mathbb{Z}_7)$ such that $\langle M; +, \cdot \rangle \simeq GF(7^3)$ and the multiplicative order of $M$ is $3$.

Any hints how to do that with a computer algebra system would be appreciated.

  • 3
    Are you sure that you copied the problem correctly? If $M$ has multiplicative order $3$, and $M$ belongs to a field of characteristic seven, then $M$ has to be in the prime field, because $x^3-1=(x-1)(x-2)(x-4)$ modulo 7. Therefore $M$ will not generate a cubic extension. Please check/comment! BTW I find the notation $\langle M;+,\cdot\rangle$ a little bit non-standard. I assume that it means the structure generated by $M$ that is closed under matrix addition and multiplication. Is this correct?2011-10-27
  • 0
    Thank you for the answer! I am sorry for the late reply. I have been ill. I indeed meant by ⟨M;+,⋅⟩ the structure generated by $M$ that is closed under matrix addition and multiplication. Let us denote it by $S$. Actually I would want to make an example of a matrix $M \in GL_3(\mathbb{Z}_p)$, where $p$ is a prime number, such that $M$ has prime order $q$, $q \neq p$, and $S \simeq GF(p^3)$. If there are not any such matrices for some $p$ and $q$, then it is ok as well. I do not understand at the moment how exactly you implied from that equation that $M$ must be in the prime field.2011-11-01
  • 0
    Ok. For the field $GF(p^3)$ to have an element of multiplicative order $q$ it is necessary and sufficient that $q\mid p^3-1$. This is because the multiplicative group of $GF(p^3)$ is cyclic of order $p^3-1$. What went wrong in your example case was that with $q=3$, $p=7$ we already have $q\mid p-1$. Therefore the elements of order $q$ all belong to the smaller field $GF(p)$. So we can say that such a matrix $M$ exists, if and only if $q\mid p^3-1$, but $q\nmid p-1$.2011-11-01
  • 0
    Finding such a matrix $M$ is more difficult. If your CAS can factor $x^q-1$ over $GF(p)$, then I would pick a cubic factor and use a companion matrix of that.2011-11-01
  • 0
    My argument leading to the conclusion that $M$ has to be in the prime field only works, if we already know that the algebra genereated by $M$ is a field. The example from Jack's answer shows that it is possible to find a matrix $M$ of order 3 that generates an algebra of the correct size. That matrix is not in the prime field (=not a scalar matrix), but the algebra that it generates isn't a field.2011-11-02
  • 0
    I have to study some notation that I am not so used to in the first paragraph of the answer you posted to understand some blanks I have. Factoring $x^q-1$ over $GF(p)$ in GAP should be possible. I will inform about the progress later. I appreciate the hints.2011-11-02
  • 0
    I seem to have left out that what always holds is $$\langle M,+,\cdot\rangle\simeq GF(p)[x]/\langle \chi_M(x)\rangle,$$ where $\chi_M(x)$ is the characteristic polynomial of $M$.2011-11-03

2 Answers 2

6

While you figure out what the question is supposed to be, here is some advice on using GAP to find an answer:

The naive way of looking for such a matrix is just to walk through the elements of GL(3,7):

First( GL(3,7), m -> Order(m) = 3 and Size(Algebra(GF(7),[m])) = 7^3 );

However, this runs into a performance problem as GL(3,7) is quite large:

gap> Size(GL(3,7));
33784128

Instead, we use the fact that GL(3,7) has relatively few and relatively well understood conjugacy classes:

gap> ccreps := List( ConjugacyClasses( GL( 3, 7 ) ), Representative );;
gap> Size( ccreps );
336

Now we can examine those 336 conjugacy class representatives to see if any satisfy your question:

gap> ms := Filtered( ccreps, m -> Order(m) = 3 and
> Size(Algebra(GF(7),[m])) = 7^3 );; Size( ms );
1
gap> Perform( ms, Display );
 4 . .
 . 1 .
 . . 2

So we see there is only one matrix of order 3 in GL(3,7), up to conjugacy, such that $\langle M,+,\cdot\rangle$ has $7^3$ elements. Unfortunately, it is isomorphic to $GF(7)^3$ not $GF(7^3)$.

It is quite easy to find an M that generates a copy of $GF(7^3)$: one simply looks for a matrix whose order divides $7^3-1$ but not $7-1$. In other words, we just want a matrix of order 57:

gap> ms := Filtered( ccreps, m -> Order(m) = 57 );;
gap> Size( ms );
12

We get 12 conjugacy classes, but in fact these form a single rational class:

gap> ForAll( ms, m -> ForAny(PrimeResidues(57),
> k -> IsConjugate(GL(3,7),m,m^k)));
true

Now we want to check the algebras just to make sure:

gap> as:=List( ms, m -> Algebra(GF(7),[m]));;
gap> ForAll( as, IsSimple );
true
gap> ForAll( as, IsCommutative );
true
gap> ForAll( as, a -> Size(a) = 7^3 );
true
  • 0
    +1 Nice! I should really install and learn to use an algebra CAS as opposed to just being stuck with Mathematica!2011-10-27
  • 0
    Thank you for the answer! I appreciate the hints including advanced GAP commands.2011-11-02
2

Actually you can do the generalized version (described in pol's comment) with Mathematica, too. The task at hand is to find a 3x3 matrix $M$ with entries in $GF(p)=\mathbf{Z}/p\mathbf{Z}$ such that $M$ has multiplicative order $q$, and that the algebra it generates is isomorphic to $GF(p^3)$. The multiplicative group of $GF(p^3)$ is cyclic of order $p^3-1$, so for such an $M$ to exist, it is necessary that $q\mid p^3-1$. For the algebra $GF(p)[M]$ to be a field, it is necessary that the minimal polynomial of $M$ is cubic, and that it does not split into lower degree factors over $GF(p)$. The minimal polynomial of a matrix is always a factor of its characteristic polynomial $\chi_M(x)$, so we only need $\chi_M(x)$ to be irreducible over $GF(p)$. Then $\langle M,+,\cdot\rangle=GF(p)[x]\langle \chi_M(x)\rangle$, which is isomorphic to $GF(p^3)$.

But the constraint on the order of $M$ forces the minimal polynomial to be a factor of $x^q-1$. So we need $x^q-1$ to have an irreducible factor of degree three. Note that when $q\mid p-1$, then the polynomial $x^q-1$ splits into a product of linear factors over $GF(p)$, so we have to avoid that.

Following Jack's suggestion ($57=3\cdot19$) let's try with $p=7$, $q=19$ with Mathematica

In[1]:=Factor[x^19-1,Modulus->7]
Out[1]=(6+x)(6+2x+x^3)(6+3x+3x^2+x^3)(6+x+4x^2+x^3)(6+4x+4x^2+x^3)(6+5x^2+x^3)(6+3x+6x^2+x^3)

So we have no less than six cubic factors (it was actually possible to tell this in advance, but let's skip that). Let's use the first: $6+2x+x^3$. We use a standard recipe of companion matrix to produce a matrix with a given minimal polynomial, and pick $$ M=\pmatrix{0&0&-6\cr 1&0&-2\cr 0&1&0\cr}. $$ It is straightforward to verify that $M^{19}\equiv I_3 \pmod 7$.

As a final check we see that $q=3, p=7$ does not work:

In[2]:=Factor[x^3-1,Modulus->7]
Out[2]=(3+x)(5+x)(6+x)

confirming the findings from my comments and Jack's answer that the third roots of unity in a field of characteristic seven are $4=-3$, $5=-2$, and $1=-6$.