How to generate a matrix group?

Question

I have three $7\times 7$ matrices (with real entries, lots of zeros) and I'd like to check if they generate a finite group (or, more precisely, if the group they generate is of precise order). Would it be possible to do with Mathematica?

---

These are the matrices. All of order 3. I expect this group to be of order 6048 or 12096.

gMatrix = 
  SparseArray[{{1, 3} -> 1, {2, 1} -> 1, {3, 2} -> 
     1, {4, 4} -> -(1/2), {4, 5} -> -(1/2), {4, 6} -> -(1/2), {4, 
      7} -> -(1/2), {5, 4} -> 1/2, {5, 5} -> -(1/2), {5, 6} -> 
     1/2, {5, 7} -> -(1/2), {6, 4} -> 
     1/2, {6, 5} -> -(1/2), {6, 6} -> -(1/2), {6, 7} -> 1/2, {7, 4} ->
      1/2, {7, 5} -> 
     1/2, {7, 6} -> -(1/2), {7, 7} -> -(1/2), {_, _} -> 0}, 7];

hMatrix = 
  SparseArray[{{1, 5} -> 
     1, {2, 2} -> -(1/2), {2, 3} -> -(1/2), {2, 6} -> 1/2, {2, 7} -> 
     1/2, {3, 2} -> 1/2, {3, 3} -> -(1/2), {3, 6} -> -(1/2), {3, 7} ->
      1/2, {4, 1} -> 1, {5, 4} -> 1, {6, 2} -> -(1/2), {6, 3} -> 
     1/2, {6, 6} -> -(1/2), {6, 7} -> 
     1/2, {7, 2} -> -(1/2), {7, 3} -> -(1/2), {7, 6} -> -(1/2), {7, 
      7} -> -(1/2), {_, _} -> 0}, 7];

kMatrix = 
  SparseArray[{{1, 4} -> -1, {2, 2} -> -(1/2), {2, 3} -> -(1/2), {2, 
      6} -> -(1/2), {2, 7} -> 1/2, {3, 2} -> 
     1/2, {3, 3} -> -(1/2), {3, 6} -> -(1/2), {3, 7} -> -(1/2), {4, 
      5} -> -1, {5, 1} -> 1, {6, 2} -> 1/2, {6, 3} -> 
     1/2, {6, 6} -> -(1/2), {6, 7} -> 1/2, {7, 2} -> -(1/2), {7, 3} ->
      1/2, {7, 6} -> -(1/2), {7, 7} -> -(1/2), {_, _} -> 0}, 7];

Answer 1

The group has 6048 elements. (Could it be isomorphic to $U_3(3)$?--see below.)

count = 0; (matrices = NestWhile[(Print[count++]; 
             Union[#~Join~Flatten[Outer[Dot, {gMatrix, hMatrix, kMatrix}, #, 1], 1]]) &, 
               {IdentityMatrix[7]}, Length[#2] != Length[#1] &, 2, 99]) // Length // Timing

$\{2.2, 6048\}$

This code begins with the identity matrix (IdentityMatrix) and iteratively adjoins (Join) any new matrices (Union) created by left multiplication of all previous matrices (Outer, Dot) by the three generators defined in the question. (Flatten unravels the 2D array of matrices into a simple list of matrices.) It stops when no new matrices appear (the Length test). In the process, it prints out an iteration count to verify that the loop did not terminate because the calculation had simply gone on too long (limited to $99$ iterations here; only $13$ were needed). In addition to reporting the total time ($2.2$ seconds), the output consists of the number of unique matrices ($6048$) and a list of them all (matrices), useful for further processing. For instance, we can compute and visualize the orders of the group elements:

matrixOrder[a_, maxIter_: 9999] := Module[{n = 1, i = IdentityMatrix[Length[a]]},
   NestWhile[(n++; a.#) &, a, ! And @@ (PossibleZeroQ /@ Flatten[# - i]) &, 1, maxIter]; n];
Histogram[matrixOrder /@ matrices, {1/2, 25/2, 1}]

---

$U_3(3)$, a sporadic simple group of Lie type modeled on $G_2$, has a seven-dimensional integral representation generated by matrices of orders $2$ and $6$,

a = {{-1, 0, 0, 0, 0, 0, 0}, {0, -1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 0}, {-1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 0}, {0, 1, 1, 0, 0, 0, 0}, {-1, 0, 0, 1, 0, 0, 0}};
b = {{0, -1, 0, 0, 0, -1, 0}, {0, 1, 1, 0, 0, 0, 0}, {0, -1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, -1, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 1}};

Using the preceding code, it takes a quarter second to generate all $6048$ elements from these two matrices. The histogram of orders of its elements is identical to the previous figure. An exhaustive search among our group for such matrices (c. $17$ seconds) finds at least one such pair of matrices that satisfy all the required relations, proving this group is isomorphic to $U_3(3)$.

(* By construction, the last element of `matrices` is the identity. *)
i7 = IdentityMatrix[7];
order2 = Select[Most@matrices, MatrixPower[#, 2] == i7 &];
order6 = Select[Most@matrices, MatrixPower[#, 6] == i7 && 
                               MatrixPower[#, 3] != i7 && MatrixPower[#, 2] != i7 &];
commutator[a_, b_] := a.b.Inverse[a].Inverse[b];
(* `generate` assumes `a` has order 2 and `b` has order 6. *)
generate[a_, b_] := MatrixPower[a.b, 7] == i7  &&  
  commutator[a, MatrixPower[a.b.b, 3]] == i7  && 
  MatrixPower[b, 3].MatrixPower[commutator[b.b, a.MatrixPower[b, 3].a], 2] == i7;
(* Does any pair at all qualify as generators? *)
Or @@ Flatten@Outer[generate, order2, order6, 1] 

$\text{True}$

(Specifically, among many possibilities, $a'=(ghk)^2$ (which is integral) and $b'=ghg$ generate $U_3(3)$.)

Answer 2

A brute-force approach would be to define the set of matrices and form all products of them:

FixedPoint[Union[#, Dot @@@ Tuples[#, 2]] &, set]

The Union sorts the entries so that duplicates are eliminated. The length of the resulting list is the order of the group.

Edit to explain the code

In the command FixedPoint, the first argument is a function that will be applied repeatedly to the second argument (set), until the result no longer changes.

So I need a function, and that's provided by the construct Union[#,...]& where the # stands for the Slot (or function parameter) and the & says that it's a Function.

Inside the function is the instruction to form the Union of two sets, namely the original one (from the previous iteration), and the outcome of forming the Dot products between all Tuples of matrices in the previous list. To get the latter, the Dot command is applied to all members of the list generated by Tuples; this is what the command @@@ does.

Edit to avoid crashes

Since the number of tuples explodes with the number of elements, brute force approaches like this can easily cause the computation to hang. Either try MemoryConstrained as nikie mentioned, or alternatively add a termination condition to FixedPoint that stops it before the explosion happens. This could be done by adding the option SameTest -> ((Length[#] == Length[#2]) || Length[#] > 50 &) to FixedPoint. Here, the length cutoff 50 is meant to limit the number of Tuples to a manageable size.