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?
1 Answer
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.
finite-fields
tag, it might bring the attention of some who know more about them than I do. $\endgroup$