2
$\begingroup$

I'm newbie in mathematica. I would like to construct a conjugacy class of an involution in GL over a finite field, but have no idea how to make the group and a matrix over the field. I'm sure that there is an easy way constructing such group but cannot find it in the tutorial. Is there any way to make this?

$\endgroup$
5
  • $\begingroup$ Me (and probably the vast majority of the other users) are more familiar with Mathematica than mathematics. I could try to help but I have no idea what you are trying to do. Can you please clarify? $\endgroup$
    – Kiro
    Aug 26, 2016 at 8:18
  • $\begingroup$ What im trying to do is to construct a general linear group over a finite field ( a group of invertible matrices over a finite field ) and a matrix in it. I thought I could find the way to construct them in the group theory section of the tutorial, but couldn't find it. I even cannot find how to construct the group over the ordinary field, real. $\endgroup$
    – vicent
    Aug 26, 2016 at 8:31
  • 1
    $\begingroup$ Okay, I think I have a better grasp of what you want to do. Do you have some specific finite field in mind? By constructing the general linear group, do you mean you want to generate all of its elements? $\endgroup$
    – Kiro
    Aug 26, 2016 at 9:25
  • $\begingroup$ I'm thinking about GF(2) through GF(5), and yes. I want to generate all 4 by 4 matrices in the general linear group $\endgroup$
    – vicent
    Aug 27, 2016 at 6:17
  • $\begingroup$ You might want to add the finite-fields tag, it might bring the attention of some who know more about them than I do. $\endgroup$
    – Kiro
    Aug 29, 2016 at 8:24

1 Answer 1

4
$\begingroup$

This does not completely answer your question, but at least it's a start; I will show how to construct a matrix over a finite field in Mathematica.

First, load the Finite Fields package.

<< FiniteFields`

Let's work with $GF(2)$. This is the number of elements it has.

FieldSize[GF[2]]
(*2*)

These are the elements.

GF[2][{0}]
GF[2][{1}]
(*0*)
(*Subscript[{1}, 2]*)

Let's make a matrix out of these.

gf2matrix = {{GF[2][{1}], GF[2][{1}]}, {GF[2][{0}], GF[2][{1}]}};
Det[gf2matrix]
(*Subscript[{1}, 2]*)

In addition to Det, at least Dot and Inverse work on these kind of matrices. There is more information in the package tutorial. I hope this helps!

EDIT: After a bit more work I believe I have a solution for the $GL(4,2)$ case. While in principle this could be easily generalized to other cases, I'm afraid my code is far too slow to generate all of the elements of larger general linear groups you are interested in. More about that later.

According to Wikipedia, the order (number of elements) of $GL(n,q)$ is $\prod _{k=0}^{n-1} \left(q^n-q^k\right)$. The expression in the parentheses is basically the number of colums to choose from when constructing a matrix of this group.

Let's make a function that checks the linear independence of vectors over $GF(2)$. The one below should do the trick. The inputs are lists of vectors over $GF(2)$ and the output are those elements of the first list that are linearly independent with the elements of the second list.

Clear[linearlyIndependentGF2];

linearlyIndependentGF2[fulllist_?ListQ, elemlist_?ListQ] := 
 linearlyIndependentGF2[fulllist, elemlist] = Module[{listsa, a},
   listsa = Tuples[{GF[2][{0}], GF[2][{1}]}, Length@elemlist];

   Pick[fulllist, 
    Not /@ Table[
      MemberQ[(Table[
          Plus @@ (x*elemlist) - i == {0, 0, 0, 0}, {x, listsa}] /. 
         GF[2][{0}] -> 0), True],
      {i, fulllist}]]
   ]

linearlyIndependentGF2[fulllist_?ListQ, elemlist_?ListQ] /; 
  ArrayDepth[elemlist] == 1 := 
 linearlyIndependentGF2[fulllist, {elemlist}]

The basic idea now is as follows. We build up the matrices row by row, at each step taking care that linear independence of rows holds.

(*build a list of indices to enumerate the matrices of the group*)
indexlist = 
  Tuples[{Range[(2^4 - 2^0)], Range[(2^4 - 2^1)], Range[(2^4 - 2^2)],Range[(2^4 - 2^3)]}];

(*these rows will be the building blocks of the matrices*)
rows = Rest@Tuples[{GF[2][{0}] , GF[2][{1}]}, n];

(*initialize the list of group matrices*)
gf2matrices = ConstantArray[0, Length@indexlist];

(*fill the list*)
Do[
  indices = indexlist[[i]];
  firstrow = rows[[indices[[1]]]];
  secondrow = linearlyIndependentGF2[rows, firstrow][[indices[[2]]]];
  thirdrow = 
   linearlyIndependentGF2[rows, {firstrow, secondrow}][[indices[[3]]]];
  fourthrow = 
   linearlyIndependentGF2[
     rows, {firstrow, secondrow, thirdrow}][[indices[[4]]]];
  gf2matrices[[i]] = {firstrow, secondrow, thirdrow, fourthrow};,
  {i, 1, Length@indexlist}];

(*check*)
Det /@ gf2matrices // Tally
(*{{GF[2][{1}], 20160}}*)

Evaluation of the code took around 2 minutes on my pc, which brings me to the subject of larger finite fields. While my code seems to work, it is too slow to generate general linear groups over larger finite fields, at least with $n=4$. The bottleneck is the check for linear independence. For example, assuming that finding a single element of $GL(n,q)$ always takes the same time, generating $GL(4,3)$ with my code would take around 48 hours, which is why I presented a solution to the special case of $q=2$ only. Let's hope my answer can inspire others to try to find more efficient solutions.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.