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$
  • $\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 '16 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 '16 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 '16 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 '16 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 '16 at 8:24
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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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