next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
InvariantRing :: generateGroup

generateGroup -- a brute-force algorithm to generate a group from a list of matrices

Synopsis

Description

The example below computes the dihedral group of order 6 from the two matrices in L. K is the field obtained by by adjoining a primitive third root of unity to QQ.

i1 : K=toField(QQ[w]/(w^2+w+1));
i2 : L={matrix{{0,1},{1,0}},matrix{{w,0},{0,w^2}}} 

o2 = {| 0 1 |, | w 0    |}
      | 1 0 |  | 0 -w-1 |

o2 : List
i3 : generateGroup(L,K)

o3 = {| 0 1 |, | 1 0 |, | -w-1 0 |, | 0    w |, | w 0    |, | 0 -w-1 |}
      | 1 0 |  | 0 1 |  | 0    w |  | -w-1 0 |  | 0 -w-1 |  | w 0    |

o3 : List

generateGroup can also be used to check whether a given List of matrices forms a group or not. This is done in the next example.

i4 : A=sub(matrix{{0,1,0},{0,0,1},{1,0,0}},QQ)

o4 = | 0 1 0 |
     | 0 0 1 |
     | 1 0 0 |

              3        3
o4 : Matrix QQ  <--- QQ
i5 : B=sub(matrix{{0,1,0},{1,0,0},{0,0,1}},QQ)

o5 = | 0 1 0 |
     | 1 0 0 |
     | 0 0 1 |

              3        3
o5 : Matrix QQ  <--- QQ
i6 : G0={A,A^2,B,A*B,A^2*B}

o6 = {| 0 1 0 |, | 0 0 1 |, | 0 1 0 |, | 1 0 0 |, | 0 0 1 |}
      | 0 0 1 |  | 1 0 0 |  | 1 0 0 |  | 0 0 1 |  | 0 1 0 |
      | 1 0 0 |  | 0 1 0 |  | 0 0 1 |  | 0 1 0 |  | 1 0 0 |

o6 : List
i7 : set(generateGroup(G0,QQ))===set(G0)

o7 = false
i8 : G1={A^0,A,A^2,B,A*B,A^2*B}

o8 = {| 1 0 0 |, | 0 1 0 |, | 0 0 1 |, | 0 1 0 |, | 1 0 0 |, | 0 0 1 |}
      | 0 1 0 |  | 0 0 1 |  | 1 0 0 |  | 1 0 0 |  | 0 0 1 |  | 0 1 0 |
      | 0 0 1 |  | 1 0 0 |  | 0 1 0 |  | 0 0 1 |  | 0 1 0 |  | 1 0 0 |

o8 : List
i9 : set(generateGroup(G1,QQ))===set(G1)

o9 = true

WARNING: the user needs to be careful to ensure that the entries in the matrices are preserved when using substitute. Observe how the matrix defined over K changes when its entries are substituted for values in QQ in the next example.

i10 : sub(matrix{{w,0},{0,w^2}},QQ)

o10 = | 0 0  |
      | 0 -1 |

               2        2
o10 : Matrix QQ  <--- QQ

This function is provided by the package InvariantRing.

Caveat

Care needs to be taken when choosing a field to enter in the second argument. The first step generateGroup performs is to use substitute on the matrices in the first argument and the field in the second argument. The field needs to be chosen so that this process preserves the matrices; see the last example above.

generateGroup is an implementation of an iterative 'brute-force' group generation algorithm. At each stage of the iteration it takes a List L of matrices and forms all possible words of length two from the alphabet L. The resulting List L' is compared to L (as Sets) and termination of the algorithm occurs if L'=L, otherwise the iteration proceeds with L=L'. This is an adequate algorithm for small groups, but is cumbersome otherwise. A better implementation for inputting groups may be desirable.

Ways to use generateGroup :