home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / matgrp.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  53.5 KB  |  1,786 lines
  1. #############################################################################
  2. ##
  3. #A  matgrp.g                    GAP library                  Martin Schoenert
  4. ##
  5. #A  @(#)$Id: matgrp.g,v 3.13 1993/02/09 14:27:19 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains  those  functions that mainly deal with matrix groups.
  10. ##
  11. #H  $Log: matgrp.g,v $
  12. #H  Revision 3.13  1993/02/09  14:27:19  martin
  13. #H  made undefined globals local
  14. #H
  15. #H  Revision 3.12  1992/12/16  19:47:27  martin
  16. #H  replaced quoted record names with escaped ones
  17. #H
  18. #H  Revision 3.11  1992/12/03  10:03:28  fceller
  19. #H  changed 'MatGroupOps.PermGroup' to return a bijection
  20. #H
  21. #H  Revision 3.10  1992/05/08  16:21:25  martin
  22. #H  added 'MatGroupOps.RightCoset'
  23. #H
  24. #H  Revision 3.9  1992/05/04  19:04:28  martin
  25. #H  fixed 'MatGroupOps.Intersection' to assign '<X>.permDomain'
  26. #H
  27. #H  Revision 3.8  1992/04/04  15:27:07  martin
  28. #H  added many more special functions for matrix groups
  29. #H
  30. #H  Revision 3.7  1992/04/03  16:45:12  martin
  31. #H  fixed 'MatricesOps.Group' to check the arguments
  32. #H
  33. #H  Revision 3.6  1992/02/29  13:25:11  jmnich
  34. #H  general library review, some bug fixes
  35. #H
  36. #H  Revision 3.5  1992/02/14  09:46:19  jmnich
  37. #H  changed call of 'Order'
  38. #H
  39. #H  Revision 3.4  1992/01/29  09:09:38  martin
  40. #H  changed 'Order' to take two arguments, group and element
  41. #H
  42. #H  Revision 3.3  1992/01/09  13:25:48  jmnich
  43. #H  added the meataxe functions
  44. #H
  45. #H  Revision 3.2  1992/01/03  15:44:57  martin
  46. #H  changed 'Matrix' to 'Mat'
  47. #H
  48. #H  Revision 3.1  1991/12/06  16:45:52  martin
  49. #H  changed 'MatricesOps.Group' to default to 'GroupElementsOps.Group'
  50. #H
  51. #H  Revision 3.0  1991/11/08  15:09:30  martin
  52. #H  initial revision under RCS
  53. #H
  54. ##
  55.  
  56.  
  57. #############################################################################
  58. ##
  59. #F  IsMatGroup(<obj>) . . . . . . . . . . test if an object is a matrix group
  60. ##
  61. IsMatGroup := function ( obj )
  62.     return IsRec( obj )
  63.        and IsBound( obj.isMatGroup )  and obj.isMatGroup;
  64. end;
  65.  
  66.  
  67. #############################################################################
  68. ##
  69. #F  MatricesOps.Group(<gens>,<id>)  . . . . . . . . . . create a matrix group
  70. ##
  71. MatricesOps.Group := function ( Matrices, gens, id )
  72.     local   G,
  73.             d,
  74.             g;
  75.  
  76.     # check that the generators are all of the same size and invertable
  77.     d := Length(id);
  78.     for g  in gens  do
  79.         if Length(g) <> d  or Length(g[1]) <> d  or RankMat(g) <> d  then
  80.             Error("<gens> must be a list of invertable square matrices");
  81.         fi;
  82.     od;
  83.  
  84.     # make the group record
  85.     G := GroupElementsOps.Group( Matrices, gens, id );
  86.  
  87.     # add the matrix group tag
  88.     G.isMatGroup     := true;
  89.  
  90.     # add the known information
  91.     G.dimension         := Length(id);
  92.     G.field             := Field( Flat( Concatenation( gens, [ id ] ) ) );
  93.  
  94.     # add the operations record
  95.     G.operations        := MatGroupOps;
  96.  
  97.     # return the group record
  98.     return G;
  99. end;
  100.  
  101.  
  102. #############################################################################
  103. ##
  104. #V  MatGroupOps . . . . . . . . .  operation record for matrix group category
  105. ##
  106. ##  'MatGroupOps' is the operation  record  for  matrix  groups.  It contains
  107. ##  the domain  functions,  e.g., 'Size'  and 'Intersection',   and the group
  108. ##  functions, e.g., 'Centralizer' and 'SylowSubgroup'.
  109. ##
  110. ##  'MatGroupOps' is initially a copy of 'GroupOps', and  thus  inherits  the
  111. ##  default group  functions.    Currently  we overlay    very few of   those
  112. ##  functions.    We should, however,   handle  matrix groups  over small and
  113. ##  medium sized finite vector spaces by  treating them as permutation groups
  114. ##  over those vector spaces and using the permutation group functions.
  115. ##
  116. MatGroupOps := Copy( GroupOps );
  117.  
  118.  
  119. #############################################################################
  120. ##
  121. #F  MatGroupOps.Subgroup(<G>,<gens>)  . . . make a subgroup of a matrix group
  122. ##
  123. MatGroupOps.Subgroup := function ( G, gens )
  124.     local   S;
  125.     S := GroupOps.Subgroup( G, gens );
  126.     S.isMatGroup := true;
  127.     S.field      := G.field;
  128.     S.operations := MatGroupOps;
  129.     return S;
  130. end;
  131.  
  132.  
  133. #############################################################################
  134. ##
  135. #F  MatGroupOps.IsFinite(<G>) . . . . . . .  test if a matrix group is finite
  136. ##
  137. MatGroupOps.IsFinite := function ( G )
  138.     if IsFinite( G.field )  then
  139.         return true;
  140.     else
  141.         return GroupOps.IsFinite( G );
  142.     fi;
  143. end;
  144.  
  145.  
  146. #############################################################################
  147. ##
  148. #F  MatGroupOps.MakePermGroupP(<G>) . . . make a isomorphic permutation group
  149. ##
  150. ##  The difference between this function and the usual  'PermGroup'  is  that
  151. ##  the permutation group constructed for <G>  will  be  a  subgroup  of  the
  152. ##  corresponding permutation group of <G>\'s parent.
  153. ##
  154. MatGroupOps.MakePermGroupP := function ( G )
  155.     local   P;
  156.  
  157.     # compute the isomorphic permutation group for the pareng group of <G>
  158.     P := Parent( G );
  159.     if not IsBound( P.permDomain )  then
  160.         P.permDomain := Union( Orbits( P, P.identity ) );
  161.         P.permGroupP  := Operation( P, P.permDomain );
  162.     fi;
  163.  
  164.     # compute the isomorphic permutation group for <G>
  165.     if not IsBound( G.permGroupP )  then
  166.         G.permDomain := P.permDomain;
  167.         G.permGroupP := Subgroup( P.permGroupP,
  168.                                   Operation( G, P.permDomain ).generators );
  169.     fi;
  170.  
  171. end;
  172.  
  173.  
  174. #############################################################################
  175. ##
  176. #F  MatGroupOps.Size(<G>) . . . . . . . . . . . . . .  size of a matrix group
  177. ##
  178. MatGroupOps.Size := function ( G )
  179.  
  180.     # compute the isomorphic permutation group for <G> and its parent
  181.     G.operations.MakePermGroupP( G );
  182.  
  183.     # return the size of the permutation group
  184.     return Size( G.permGroupP );
  185. end;
  186.  
  187.  
  188. #############################################################################
  189. ##
  190. #F  MatGroupOps.\in( <obj>, <G> )  . . . . membership test for matrix groups
  191. ##
  192. MatGroupOps.\in := function ( obj, G )
  193.     local   l,          # <obj> as a permutation represented by a list
  194.             v,          # vector from the operation domain of <P>
  195.             p;          # position of '<v> \^\ <obj>' in the operation domain
  196.  
  197.     # first a quick test
  198.     if     not IsMat( obj )
  199.         or Length(obj) <> Length(G.identity)
  200.         or Length(obj[1]) <> Length(G.identity[1])
  201.         or RankMat(obj) <> Length(G.identity)
  202.         or not IsSubset( G.field, Field( Flat(obj) ) )
  203.     then
  204.         return false;
  205.     fi;
  206.  
  207.     # compute the isomorphic permutation group for <G> and its parent
  208.     G.operations.MakePermGroupP( G );
  209.  
  210.     # try to transform <obj> to a permutation
  211.     l := [];
  212.     for v  in G.permDomain  do
  213.         p := Position( G.permDomain, v ^ obj );
  214.         if p = false  then
  215.             return false;
  216.         fi;
  217.         Add( l, p );
  218.     od;
  219.  
  220.     # test if the permutation is in the permutation group
  221.     return PermList(l) in G.permGroupP;
  222. end;
  223.  
  224.  
  225. #############################################################################
  226. ##
  227. #F  MatGroupOps.Intersection(<G>,<H>) . . . . . intersection of matrix groups
  228. ##
  229. MatGroupOps.Intersection := function ( G, H )
  230.     local   I,          # intersection of <G> and <H>, result
  231.             P;          # permutation representation of <I>
  232.  
  233.     # handle the intersection of two matrix groups with the same parent
  234.     if IsMatGroup(G)  and IsMatGroup(H)  and Parent(G) = Parent(H)  then
  235.  
  236.         # compute the isomorphic permutation groups for <G> and <H>
  237.         G.operations.MakePermGroupP( G );
  238.         H.operations.MakePermGroupP( H );
  239.  
  240.         # intersect the permutation groups and translate back
  241.         P := Intersection( G.permGroupP, H.permGroupP );
  242.         I := Subgroup( Parent( G ), List( P.generators, gen ->
  243.                     List( G.identity,
  244.                         v -> G.permDomain[Position(G.permDomain,v)^gen] ) ));
  245.         if not IsBound( I.permGroupP )  then
  246.             I.permDomain := G.permDomain;
  247.             I.permGroupP := P;
  248.         fi;
  249.  
  250.     # delegate other cases
  251.     else
  252.         I := GroupOps.Intersection( G, H );
  253.     fi;
  254.  
  255.     # return the intersection
  256.     return I;
  257. end;
  258.  
  259.  
  260. #############################################################################
  261. ##
  262. #F  MatGroupOps.Random(<G>) . . . . . . . .  random element in a matrix group
  263. ##
  264. MatGroupOps.Random := function ( G )
  265.     local   rnd;        # random element of '<G>.permGroupP'
  266.  
  267.     # compute the isomorphic permutation group for <G> and its parent
  268.     G.operations.MakePermGroupP( G );
  269.  
  270.     # take a random permutation and translate it back
  271.     rnd := Random( G.permGroupP );
  272.     return List( G.identity,
  273.                  v -> G.permDomain[Position(G.permDomain,v)^rnd] );
  274. end;
  275.  
  276.  
  277. #############################################################################
  278. ##
  279. #F  MatGroupOps.Centralizer(<G>,<U>)  . . . . . centralizer in a matrix group
  280. ##
  281. MatGroupOps.Centralizer := function ( G, U )
  282.     local    C,         # centralizer of <U> in <G>, result
  283.              P;         # permutation group isomorphic to <C> or <U>
  284.  
  285.     # compute the isomorphic permutation group for <G> and its parent
  286.     G.operations.MakePermGroupP( G );
  287.  
  288.     # compute the isomorphic permutation or permutation group for <U>
  289.     if IsMat(U)  then
  290.         P := Permutation( U, G.permDomain );
  291.     else
  292.         U.operations.MakePermGroupP( U );
  293.         P := U.permGroupP;
  294.     fi;
  295.  
  296.     # compute the centralizer in the permutation group and translate back
  297.     P := Centralizer( G.permGroupP, P );
  298.     C := Subgroup( Parent( G ),
  299.             List( P.generators, gen ->
  300.                 List( G.identity,
  301.                     v -> G.permDomain[Position(G.permDomain,v)^gen] ) ) );
  302.     if not IsBound( C.permGroupP )  then
  303.         C.permDomain := G.permDomain;
  304.         C.permGroupP := P;
  305.     fi;
  306.  
  307.     # return the centralizer
  308.     return C;
  309. end;
  310.  
  311.  
  312. #############################################################################
  313. ##
  314. #F  MatGroupOps.Normalizer(<G>,<U>) . . . . . .  normalizer in a matrix group
  315. ##
  316. MatGroupOps.Normalizer := function ( G, U )
  317.     local    N,         # normalizer of <U> in <G>, result
  318.              P;         # permutation group isomorphic to <N> or <U>
  319.  
  320.     # compute the isomorphic permutation group for <G> and its parent
  321.     G.operations.MakePermGroupP( G );
  322.  
  323.     # compute the isomorphic permutation or permutation group for <U>
  324.     if IsMat(U)  then
  325.         P := Permutation( U, G.permDomain );
  326.     else
  327.         U.operations.MakePermGroupP( U );
  328.         P := U.permGroupP;
  329.     fi;
  330.  
  331.     # compute the normalizer in the permutation group and translate back
  332.     P := Normalizer( G.permGroupP, P );
  333.     N := Subgroup( Parent( G ),
  334.             List( P.generators, gen ->
  335.                 List( G.identity,
  336.                     v -> G.permDomain[Position(G.permDomain,v)^gen] ) ) );
  337.     if not IsBound( N.permGroupP )  then
  338.         N.permDomain := G.permDomain;
  339.         N.permGroupP := P;
  340.     fi;
  341.  
  342.     # return the normalizer
  343.     return N;
  344. end;
  345.  
  346.  
  347. #############################################################################
  348. ##
  349. #F  MatGroupOps.SylowSubgroup(<G>,<p>)  . . . Sylowsubgroup of a matrix group
  350. ##
  351. MatGroupOps.SylowSubgroup := function ( G, p )
  352.     local   S,          # <p>-Sylow subgroup of <G>, result
  353.             P;          # permutation group isomorphic to <S>
  354.  
  355.     # compute the isomorphic permutation group for <G> and its parent
  356.     G.operations.MakePermGroupP( G );
  357.  
  358.     # compute the Sylow subgroup in the permutation group and translate back
  359.     P := SylowSubgroup( G.permGroupP, p );
  360.     S := Subgroup( Parent( G ),
  361.             List( P.generators, gen ->
  362.                 List( G.identity,
  363.                     v -> G.permDomain[Position(G.permDomain,v)^gen] ) ) );
  364.     if not IsBound( S.permGroupP )  then
  365.         S.permDomain := G.permDomain;
  366.         S.permGroupP := P;
  367.     fi;
  368.  
  369.     # return the Sylow subgroup
  370.     return S;
  371. end;
  372.  
  373.  
  374. #############################################################################
  375. ##
  376. #F  MatGroupOps.ConjugacyClasses(<G>) . . conjugacy classes of a matrix group
  377. ##
  378. MatGroupOps.ConjugacyClasses := function ( G )
  379.     local   classes,    # conjugacy classes of <G>, result
  380.             pclasses,   # conjugacy classes of '<G>.permGroupP'
  381.             class,      # one conjugacy class in <pclasses>
  382.             rep;
  383.  
  384.     # compute the isomorphic permutation group for <G> and its parent
  385.     G.operations.MakePermGroupP( G );
  386.  
  387.     # compute the conjugacy classes in the permutation group
  388.     pclasses := ConjugacyClasses( G.permGroupP );
  389.  
  390.     # translate every conjugacy class back
  391.     classes := [];
  392.     for class in pclasses  do
  393.         rep := Representative( class );
  394.         rep := List( G.identity,
  395.                      v -> G.permDomain[Position(G.permDomain,v)^rep] );
  396.         Add( classes, ConjugacyClass( G, rep ) );
  397.     od;
  398.  
  399.     # return the classes
  400.     return classes;
  401. end;
  402.  
  403.  
  404. #############################################################################
  405. ##
  406. #F  MatGroupOps.PermGroup(<G>)  . . . . convert a matrix group to a permgroup
  407. ##
  408. MatGroupOps.PermGroup := function ( G )
  409.     local   P;
  410.  
  411.     # construct the permutation group
  412.     P := Operation( G, Union( Orbits( G, G.identity ) ) );
  413.  
  414.     # construct the bijection
  415.     P.bijection := GroupHomomorphismByImages( P, G,
  416.                                               P.operationImages,
  417.                                               G.generators );
  418.     P.bijection.isMapping           := true;
  419.     P.bijection.isGroupHomomorphism := true;
  420.     P.bijection.isInjective         := true;
  421.     P.bijection.isMonomorphism      := true;
  422.     P.bijection.isSurjective        := true;
  423.     P.bijection.isEpimorphism       := true;
  424.     P.bijection.isBijection         := true;
  425.     P.bijection.isIsomorphism       := true;
  426.  
  427.     # return the permutation group
  428.     return P;
  429. end;
  430.  
  431.  
  432. #############################################################################
  433. ##
  434. #F  MatGroupOps.Stabilizer(<G>,<d>,<opr>) . . .  stabilizer in a matrix group
  435. ##
  436. MatGroupOps.Stabilizer := function ( G, d, opr )
  437.     local   S,          # stabilizer of <d> in <G>, result
  438.             P;          # permutation group isomorphic to <S>
  439.  
  440.     # special case to find the stabilizer of a vector
  441.     if IsVector(d)  and opr = OnPoints  then
  442.  
  443.         # compute the isomorphic permutation group for <G> and its parent
  444.         G.operations.MakePermGroupP( G );
  445.  
  446.         # test whether we can handle this case
  447.         if not d in G.permDomain  then
  448.             return GroupOps.Stabilizer( G, d, opr );
  449.         fi;
  450.  
  451.         # translate the vector to a point
  452.         d := Position( G.permDomain, d );
  453.  
  454.         # find the stabilizer in the permutation group and translate back
  455.         P := Stabilizer( G.permGroupP, d );
  456.         S := Subgroup( Parent( G ),
  457.             List( P.generators, gen ->
  458.                 List( G.identity,
  459.                     v -> G.permDomain[Position(G.permDomain,v)^gen] ) ) );
  460.         if not IsBound( S.permGroupP )  then
  461.             S.permDomain := G.permDomain;
  462.             S.permGroupP := P;
  463.         fi;
  464.  
  465.     # delegate other cases
  466.     else
  467.         S := GroupOps.Stabilizer( G, d, opr );
  468.     fi;
  469.  
  470.     # return the stabilizer
  471.     return S;
  472. end;
  473.  
  474.                       
  475. #############################################################################
  476. ##
  477. #F  MatGroupOps.RepresentativeOperation(<G>,<d>,<e>,<opr>)  .  representative
  478. #F                                               of a point in a matrix group
  479. ##
  480. MatGroupOps.RepresentativeOperation := function ( G, d, e, opr )
  481.     local   rep;        # representative taking <d> to <e>, result
  482.  
  483.     # special case to find a conjugating element
  484.     if d in G  and e in G  and opr = OnPoints  then
  485.  
  486.         # compute the isomorphic permutation group for <G> and its parent
  487.         G.operations.MakePermGroupP( G );
  488.  
  489.         # translage the two matrices
  490.         d := Permutation( d, G.permDomain );
  491.         e := Permutation( e, G.permDomain );
  492.  
  493.         # find a conjugating permutation and translate back
  494.         rep := RepresentativeOperation( G.permGroupP, d, e );
  495.         if rep <> false  then
  496.             rep := List( G.identity,
  497.                          v -> G.permDomain[Position(G.permDomain,v)^rep] );
  498.         fi;
  499.  
  500.     # special case to find a matrix taking one vector to another
  501.     elif IsVector(d)  and IsVector(e)  and opr = OnPoints  then
  502.  
  503.         # compute the isomorphic permutation group for <G> and its parent
  504.         G.operations.MakePermGroupP( G );
  505.  
  506.         # make sure we can handle this case
  507.         if not d in G.permDomain  or not e in G.permDomain  then
  508.             return GroupOps.RepresentativeOperation( G, d, e, opr );
  509.         fi;
  510.  
  511.         # translate the two vector to points
  512.         d := Position( G.permDomain, d );
  513.         e := Position( G.permDomain, e );
  514.  
  515.         # find a representative and translate back
  516.         rep := RepresentativeOperation( G.permGroupP, d, e );
  517.         if rep <> false  then
  518.             rep := List( G.identity,
  519.                          v -> G.permDomain[Position(G.permDomain,v)^rep] );
  520.         fi;
  521.  
  522.     # delegate other cases
  523.     else
  524.         rep := GroupOps.RepresentativeOperation( G, d, e, opr );
  525.     fi;
  526.  
  527.     # return the representative
  528.     return rep;
  529. end;
  530.  
  531.  
  532. #############################################################################
  533. ##
  534. #F  MatGroupOps.Order(<G>,<g>)  . . . . . . . . . . . . . . order of a matrix
  535. ##
  536. MatGroupOps.Order := MatricesOps.Order;
  537.  
  538.  
  539. #############################################################################
  540. ##
  541. #F  MatGroupOps.RightCoset(<U>,<g>) . . . . . . right coset in a matrix group
  542. #V  RightCosetMatGroupOps operations record of right cosets in a matrix group
  543. ##
  544. ##  'MatGroupOps.RightCoset'  is the  function to create a  right coset in  a
  545. ##  matrix   group.   It  computes  a  special  element  (namely  the  matrix
  546. ##  corresponding to the  smallest element  of the corresponding coset in the
  547. ##  permutation group) of the coset and stores <U> together with this special
  548. ##  element as  representative in a record, and  enters the operations record
  549. ##  'RightCosetMatGroupOps'.
  550. ##
  551. ##  'RightCosetMatGroupOps'  is the operations  record of  right cosets in  a
  552. ##  matrix    group.     It    inherits   the    default    functions    from
  553. ##  'RightCosetGroupOps', and  overlays  the comparison function,  using  the
  554. ##  fact  that  matrix  group   cosets  have  a  special  unique  element  as
  555. ##  representative.
  556. ##
  557. MatGroupOps.RightCoset := function ( U, g )
  558.     local   C,          # right coset of <U> and <g>, result
  559.             p;          # permutation corresponding to <g>
  560.  
  561.     # compute the isomorphic permutation group for <G> and its parent
  562.     U.operations.MakePermGroupP( U );
  563.  
  564.     # compute the isomorphic permutation for <g>
  565.     p := Permutation( g, U.permDomain );
  566.  
  567.     # compute the right coset in the permutation group
  568.     C := U.permGroupP.operations.RightCoset( U.permGroupP, p );
  569.  
  570.     # take its representative and translate it back
  571.     p := C.representative;
  572.     g := List( U.identity, v -> U.permDomain[Position(U.permDomain,v)^p] );
  573.  
  574.     # make the domain
  575.     C := rec( );
  576.     C.isDomain          := true;
  577.     C.isRightCoset      := true;
  578.  
  579.     # enter the identifying information
  580.     C.group             := U;
  581.     C.representative    := g;
  582.     C.special           := g;
  583.  
  584.     # enter knowledge
  585.     if IsBound( U.isFinite )  then
  586.         C.isFinite      := U.isFinite;
  587.     fi;
  588.     if IsBound( U.size )  then
  589.         C.size          := U.size;
  590.     fi;
  591.  
  592.     # enter the operations record
  593.     C.operations        := RightCosetMatGroupOps;
  594.  
  595.     # return the coset
  596.     return C;
  597. end;
  598.  
  599. RightCosetMatGroupOps := Copy( RightCosetGroupOps );
  600.  
  601. RightCosetMatGroupOps.\= := function ( C, D )
  602.     local   isEql;
  603.  
  604.     # compare a right coset with minimal representative
  605.     if IsRightCoset( C )  and IsBound( C.special )  then
  606.  
  607.         # with another right coset with minimal representative
  608.         if IsRightCoset( D )  and IsBound( D.special )  then
  609.             if C.group = D.group  then
  610.                 isEql := C.special = D.special;
  611.             else
  612.                 isEql := RightCosetGroupOps.\=( C, D );
  613.             fi;
  614.  
  615.         # with a subgroup, which is a special right coset
  616.         elif IsGroup( D )  then
  617.             if C.group = D  then
  618.                 isEql := C.special = D.identity;
  619.             else
  620.                 isEql := RightCosetGroupOps.\=( C, D );
  621.             fi;
  622.  
  623.         # with something else
  624.         else
  625.             isEql := RightCosetGroupOps.\=( C, D );
  626.         fi;
  627.  
  628.     # compare a subgroup, which is a special right coset
  629.     elif IsGroup( C )  then
  630.  
  631.         # with a right coset with minimal representative
  632.         if IsRightCoset( D )  and IsBound( D.special )  then
  633.             if C = D.group  then
  634.                 isEql := C.identity = D.special;
  635.             else
  636.                 isEql := RightCosetGroupOps.\=( C, D );
  637.             fi;
  638.  
  639.         # with something else
  640.         else
  641.             isEql := RightCosetGroupOps.\=( C, D );
  642.         fi;
  643.  
  644.     # compare something else
  645.     else
  646.         isEql := RightCosetGroupOps.\=( C, D );
  647.     fi;
  648.  
  649.     # return the result
  650.     return isEql;
  651. end;
  652.  
  653.  
  654. #############################################################################
  655. ##
  656. #F  MatGroup( <gens>, <field>[, <identity>] ) . . . . . create a matrix group
  657. ##
  658. MatGroup := function( arg )
  659.     local   gens, m, idmat;
  660.  
  661.     if Length( arg ) = 2 then
  662.         if arg[1] = [] then
  663.             Error( "sorry, need at least one element" );
  664.         fi;
  665.         idmat := arg[1][1] ^ 0;
  666.     elif Length( arg ) = 3 then
  667.         idmat := arg[3];
  668.     else
  669.         Error( "usage: MatGroup( <generators>, <field>[, <identity>] )" );
  670.     fi;
  671.  
  672.     gens := [];
  673.     for m in arg[1] do
  674.         if m <> idmat then  Add( gens, m );  fi;
  675.     od;
  676.  
  677.     return rec(
  678.         generators := gens,
  679.         field      := arg[2],
  680.         identity   := idmat,
  681.         dimension  := Length( idmat ),
  682.         isMatGroup := true,
  683.         isGroup    := true,
  684.         isDomain   := true,
  685.         operations := MatGroupOps
  686.     );
  687. end;
  688.  
  689.  
  690. #############################################################################
  691. ##
  692. #F  RandomMatGroup( <dim>, <field>, <numgens> ) .  create random matrix group
  693. ##
  694. RandomMatGroup := function( dim, field, k )
  695.     local   group, mats, id, i;
  696.  
  697.     id := IdentityMat( dim, field );
  698.     mats := [1..k];
  699.     for i in [1..k] do
  700.         mats[i] := RandomInvertableMat( dim, field );
  701.     od;
  702.     return MatGroup( mats, field, id );
  703. end;
  704.  
  705.  
  706. #############################################################################
  707. ##
  708. #F  MatGroupOps.Transposed( <matgroup> )  . . . . . . . . . . . . . . . . . .
  709. ##
  710. MatGroupOps.Transposed := function( group )
  711.     local   mats, m;
  712.  
  713.     mats := [];
  714.     for m in group.generators do
  715.         Add( mats, TransposedMat( m ) );
  716.     od;
  717.     return MatGroup( mats, group.field, group.identity );
  718. end;
  719.  
  720.  
  721. #############################################################################
  722. ##
  723. #F  Transposed( <domain> )  . . . . . . . . . . . . . . . . . . . . . . . . .
  724. ##
  725. Transposed := function( D )
  726.     local   trans;
  727.  
  728.     if IsMat( D ) then
  729.         trans := TransposedMat( D );
  730.     elif IsDomain( D ) and IsBound( D.operations.Transposed ) then
  731.         trans := D.operations.Transposed( D );
  732.     else
  733.         Error( "sorry, can't compute transposed <domain>" );
  734.     fi;
  735.     return trans;
  736. end;
  737.  
  738.  
  739. #############################################################################
  740. ##
  741. #F  MatGroupOps.InvariantSubspace( <matgroup>[, <matrix>] ) . . . . . . . . .
  742. #F  . . . . . . . . . . . . . . . . . . . . . . .  find an invariant subspace
  743. ##
  744. ##  This function tries to find an invariant Subspace for the matrix group as
  745. ##  suggested  by  Norton's criterion for irreducibility.  However some basic
  746. ##  calculations  have  to  be  made  if  reducibility  is  concluded  in the
  747. ##  transposed case.
  748. ##
  749. MatGroupOps.InvariantSubspace := function( arg )
  750.     local   group, m, module, subm, sdim, ns, tmodule, tsubm, tsdim, tns,
  751.             base, tbase, enum, line, wgts, perm, i, j;
  752.  
  753.     if Length( arg ) = 1 then
  754.         group := arg[1];
  755.         m     := SmallCorankMatrixRecord( group );
  756.     elif Length( arg ) = 2 then
  757.         group := arg[1];
  758.         m     := arg[2];
  759.         ns    := NullspaceMat( m );
  760.         if ns = [] then
  761.             Error( "sorry, <matrix> has to be singular" );
  762.         fi;
  763.         m := rec(
  764.             matrix    := m,
  765.             corank    := Length( ns ),
  766.             nullspace := RowSpace( ns, group.field ),
  767.             corankGcd := Length( ns )
  768.         );
  769.     else
  770.         Error( "usage: InvariantSubspace( <matgroup>[, <matrix>] )" );
  771.     fi;
  772.  
  773.     module := RowModule( group );
  774.     enum   := LineEnumeration( m.nullspace );
  775.     line   := 1;
  776.     while line <= enum.numberLines do
  777.         subm := Submodule( module,
  778.                            RowSpace( [ enum.line( line ) ], group.field ) );
  779.         sdim := Dimension( subm );
  780.         line := line + 1;
  781.         if 0 < sdim and sdim < group.dimension then
  782.             return subm.abelianGroup;
  783.         fi;
  784.     od;
  785.  
  786.  
  787.     # try to find a proper submodule in the transposed matrix group
  788.  
  789.     tmodule := RowModule( Transposed( module.ring ), module.abelianGroup );
  790.     tns     := NullspaceMat( Transposed( m.matrix ) );
  791.     tsubm   := Submodule(  tmodule,
  792.                            RowSpace( [ tns[1] ], group.field ) );
  793.     tsdim   := Dimension( tsubm );
  794.  
  795.     if 0 < tsdim and tsdim < group.dimension then
  796.  
  797.         # determine the permutation that sorts the base by weights
  798.  
  799.         wgts := Information( tsubm.abelianGroup ).weights;
  800.         perm := PermList( Concatenation( wgts, Difference( [1..group.dimension], wgts ) ) );
  801.  
  802.  
  803.         # determine the submodule base for the normal case
  804.  
  805.         sdim  := group.dimension - tsdim;
  806.         tbase := Base( tsubm );
  807.         base  := [];
  808.  
  809.         for i in [1..sdim] do
  810.             base[i] := ShallowCopy( module.abelianGroup.zero );
  811.             base[i][tsdim+i] := module.abelianGroup.field.one;
  812.             for j in [1..tsdim] do
  813.                 base[i][j] := -tbase[j][(tsdim+i)^perm];
  814.             od;
  815.         od;
  816.  
  817.         return RowSpace(  base,
  818.                           module.abelianGroup.field,
  819.                           module.abelianGroup.zero );
  820.     else
  821.         return m.corankGcd;
  822.     fi;
  823. end;
  824.  
  825.  
  826. #############################################################################
  827. ##
  828. #F  InvariantSubspace( <domain> ) . . . . . . . . . . . . . . . . . . . . . .
  829. ##
  830. InvariantSubspace := function( D )
  831.     local   subs;
  832.  
  833.     if IsDomain( D ) and IsBound( D.operations.InvariantSubspace ) then
  834.         subs := D.operations.InvariantSubspace( D );
  835.     else
  836.         Error( "sorry, can't compute an invariant subspace for <domain>" );
  837.     fi;
  838.     return subs;
  839. end;
  840.  
  841.  
  842. #############################################################################
  843. ##
  844. #F  MatGroupOps.IsInvariantSubspace( <matgroup>, <rowspace> ) . . . . . . . .
  845. #F  . . . . . . . . . . . . . . . . . . . . . . test if is invariant subspace
  846. ##
  847. MatGroupOps.IsInvariantSubspace := function( group, vs )
  848.     return Submodule( RowModule( group ), vs ).abelianGroup = vs;
  849. end;
  850.  
  851.  
  852. #############################################################################
  853. ##
  854. #F  IsInvariantSubspace( <domain>, <object> ) . . . . . . . . . . . . . . . .
  855. ##
  856. IsInvariantSubspace := function( D, obj )
  857.     local   isinv;
  858.  
  859.     if IsDomain( D ) and IsBound( D.operations.IsInvariantSubspace ) then
  860.         isinv := D.operations.IsInvariantSubspace( D, obj );
  861.     else
  862.         Error( "sorry, can't test on invariant subspace for <domain>" );
  863.     fi;
  864.     return isinv;
  865. end;
  866.  
  867.  
  868. #############################################################################
  869. ##
  870. #F  MatGroupOps.IrreducibilityTest( <matgroup>[, <matrix>] )  . . . . . . . .
  871. #F  . . . . . . . . . . . . . .  test whether a matrix group acts irreducible
  872. ##
  873. MatGroupOps.IrreducibilityTest := function( arg )
  874.     local   subs;
  875.  
  876.     if Length( arg ) = 1 then
  877.         subs := InvariantSubspace( arg[1] );
  878.     elif Length( arg ) = 1 then
  879.         subs := InvariantSubspace( arg[1], arg[2] );
  880.     else
  881.         Error( "usage: IrreducibilityTest( <matgroup>[, <matrix>] )" );
  882.     fi;
  883.  
  884.     if IsInt( subs ) then
  885.         return rec(
  886.             isIrreducible := true,
  887.             isReducible   := false,
  888.             degree        := subs
  889.         );
  890.     else
  891.         return rec(
  892.             isIrreducible     := false,
  893.             isReducible       := true,
  894.             invariantSubspace := subs
  895.         );
  896.     fi;
  897. end;
  898.  
  899.  
  900. #############################################################################
  901. ##
  902. #F  IrreducibilityTest( <domain> )  . . . . . . . . . . . . . . . . . . . . .
  903. ##
  904. IrreducibilityTest := function( D )
  905.     local   test;
  906.  
  907.     if IsDomain( D ) and IsBound( D.irreducibilityTest ) then
  908.         test := D.irreducibilityTest;
  909.     elif IsDomain( D ) and IsBound( D.operations.IrreducibilityTest ) then
  910.         D.irreducibilityTest := D.operations.IrreducibilityTest( D );
  911.         test := D.irreducibilityTest;
  912.     else
  913.         Error( "sorry, can't test <domain> for irreducibility" );
  914.     fi;
  915.     return test;
  916. end;
  917.  
  918.  
  919. #############################################################################
  920. ##
  921. #F  MatGroupOps.AbsoluteIrreducibilityTest( <matgroup>[, <matrix>] )  . . . .
  922. #F  . . . . . . . . . . test whether a matrix group acts absolute irreducible
  923. ##
  924. MatGroupOps.AbsoluteIrreducibilityTest := function( arg )
  925.     local   subs, deg, group, mats, field, m;
  926.  
  927.     if Length( arg ) = 1 then
  928.         group := arg[1];
  929.         subs  := InvariantSubspace( arg[1] );
  930.     elif Length( arg ) = 1 then
  931.         group := arg[1];
  932.         subs  := InvariantSubspace( arg[1], arg[2] );
  933.     else
  934.         Error( "usage: AbsoluteIrreducibilityTest( <matgroup>[, <matrix>] )" );
  935.     fi;
  936.  
  937.     if IsInt( subs ) then
  938.         deg := subs;
  939.         if deg = 1 then
  940.             return rec(
  941.                 isIrreducible         := true,
  942.                 isReducible           := false,
  943.                 isAbsoluteIrreducible := true,
  944.                 degree                := deg
  945.             );
  946.         fi;
  947.  
  948.         if IsFinite( arg[1] ) then
  949.  
  950.             # construct the new matrix group over the bigger field
  951.  
  952.             field := GF( Size( group.field ) ^ deg );
  953.             mats  := [];
  954.             for m in group.generators do
  955.                 Add( mats, field.one * m );
  956.             od;
  957.             if mats = [] then
  958.                 group := MatGroup( mats, field, field.one * group.identity );
  959.             else
  960.                 group := MatGroup( mats, field );
  961.             fi;
  962.  
  963.             if Length( arg ) = 1 then
  964.                 subs := InvariantSubspace( group );
  965.             else
  966.                 subs := InvariantSubspace( group, arg[2] );
  967.             fi;
  968.  
  969.             if IsInt( subs ) then
  970.                 return rec(
  971.                     isIrreducible         := true,
  972.                     isReducible           := false,
  973.                     isAbsoluteIrreducible := true,
  974.                     degree                := deg * subs
  975.                 );
  976.             else
  977.                 return rec(
  978.                     isIrreducible         := true,
  979.                     isReducible           := false,
  980.                     isAbsoluteIrreducible := false,
  981.                     degree                := deg,
  982.                     invariantSubspace     := subs
  983.                     
  984.                 );
  985.             fi;
  986.  
  987.         else
  988.             Error( "sorry, don't know how to extend infinte fields" );
  989.         fi;
  990.     else
  991.         return rec(
  992.             isIrreducible         := false,
  993.             isReducible           := true,
  994.             isAbsoluteIrreducible := false,
  995.             invariantSubspace     := subs
  996.         );
  997.     fi;
  998. end;
  999.  
  1000.  
  1001. #############################################################################
  1002. ##
  1003. #F  AbsoluteIrreducibilityTest( <domain> )  . . . . . . . . . . . . . . . . .
  1004. ##
  1005. AbsoluteIrreducibilityTest := function( D )
  1006.     local   test;
  1007.  
  1008.     if IsDomain( D ) and IsBound( D.absoluteIrreducibilityTest ) then
  1009.         test := D.absoluteIrreducibilityTest;
  1010.     elif IsDomain( D ) and IsBound( D.operations.AbsoluteIrreducibilityTest ) then
  1011.         D.absoluteIrreducibilityTest := D.operations.AbsoluteIrreducibilityTest( D );
  1012.         test := D.absoluteIrreducibilityTest;
  1013.     else
  1014.         Error( "sorry, can't test <domain> for absolute irreducibility" );
  1015.     fi;
  1016.     return test;
  1017. end;
  1018.  
  1019.  
  1020. #############################################################################
  1021. ##
  1022. #F  MatGroupOps.CompositionFactors( <matgroup> )  . . . . . . . . . . . . . .
  1023. #F  . . . . . . . . . . . . . . . . . . composition factors of a matrix group
  1024. ##
  1025. MatGroupOps.CompositionFactors := function( group )
  1026.     local   decompose, groups, bases;
  1027.  
  1028.     decompose := function ( m, b )
  1029.         local subs, rep;
  1030.  
  1031.         subs := InvariantSubspace( m );
  1032.         if IsInt( subs ) then
  1033.             Add( groups, m );
  1034.             Add( bases, b );
  1035.         else
  1036.             rep := Representation( RowModule( m ), RowModule( m, subs ) );
  1037.             decompose( rep.range, rep.base * b );
  1038.             rep := Representation( RowModule( m, subs ) );
  1039.             decompose( rep.range, rep.base * b );
  1040.         fi;
  1041.     end;
  1042.  
  1043.     groups := [];
  1044.     bases  := [];
  1045.     decompose( group, IdentityMat( group.dimension, group.field ) );
  1046.  
  1047.     return rec(
  1048.         groups := groups,
  1049.         bases  := bases
  1050.     );
  1051. end;
  1052.  
  1053.  
  1054. #############################################################################
  1055. ##
  1056. #F  CompositionFactors( <domain> )  . . . . . . composition factors of domain
  1057. ##
  1058. CompositionFactors := function( D )
  1059.     local   comp;
  1060.  
  1061.     if IsDomain( D ) and IsBound( D.compositionFactors ) then
  1062.         comp := D.compositionFactors;
  1063.     elif IsDomain( D ) and IsBound( D.operations.CompositionFactors ) then
  1064.         D.compositionFactors := D.operations.CompositionFactors( D );
  1065.         comp := D.compositionFactors;
  1066.     else
  1067.         Error( "sorry, can't compute composition factors for <domain>" );
  1068.     fi;
  1069.     return comp;
  1070. end;
  1071.  
  1072.  
  1073. #############################################################################
  1074. ##
  1075. #F  MatGroupOps.EquivalenceTest( <matgroup>, <matgroup> ) . . . . . . . . . .
  1076. #F  . . . . . . . . . . . . . perform a test for equivalence of matrix groups
  1077. ##
  1078. MatGroupOps.EquivalenceTest := function( group1, group2 )
  1079.     local   fp1, fp2, module, minpos, ns1, ns2, crk, result, base, line,
  1080.             enum, y1, x, x_inv, i;
  1081.  
  1082.     if group1.identity <> group2.identity
  1083.       or group1.field <> group2.field
  1084.       or Length( group1.generators ) <> Length( group2.generators ) then
  1085.         return rec( areequivalent := false );
  1086.     fi;
  1087.  
  1088.     # first check the trivial cases
  1089.  
  1090.     if group1.generators = group2.generators then
  1091.         return rec(
  1092.             areequivalent        := true,
  1093.             transformationMatrix := group1.identity
  1094.         );
  1095.     elif group1.dimension = 1 then
  1096.         return rec( areequivalent := false );
  1097.     fi;
  1098.  
  1099.     fp1 := Fingerprint( group1 );
  1100.     AddNextMatrixFunction( group2, group1.operations.NextMatrix );
  1101.     fp2 := Fingerprint( group2 );
  1102.  
  1103.     if fp1.coranks <> fp2.coranks then
  1104.         return rec( areequivalent := false );
  1105.     fi;
  1106.     if fp1.failed then
  1107.         Error( "sorry, fingerprint failed" );
  1108.     fi;
  1109.  
  1110.     minpos := Position( fp1.coranks,
  1111.                         Minimum( Filtered( fp1.coranks, x -> x <> 0 ) ) );
  1112.  
  1113.     ns1 := fp1.nullspaces[minpos];
  1114.     ns2 := fp2.nullspaces[minpos];
  1115.     crk := fp1.coranks[minpos];
  1116.  
  1117.     result := rec( areequivalent := false );
  1118.  
  1119.     enum := LineEnumeration( ns1 );
  1120.     line := 1;
  1121.     repeat
  1122.         module := RowModule( group1,
  1123.                     RowSpace( [ enum.line( line ) ], group1.field ) );
  1124.         module.isNormalizedBase := false;
  1125.         base := Base( module );
  1126.         line := line + 1;
  1127.     until Length( base ) = group1.dimension or line > enum.numberLines;
  1128.  
  1129.     if Length( base ) = group1.dimension then
  1130.         y1   := base;
  1131.         enum := LineEnumeration( ns2 );
  1132.         line := 1;
  1133.  
  1134.         repeat
  1135.  
  1136.             module := RowModule( group2,
  1137.                         RowSpace( [ enum.line( line ) ], group2.field ) );
  1138.             module.isNormalizedBase := false;
  1139.             base := Base( module );
  1140.             line := line + 1;
  1141.  
  1142.             if Length( base ) = group2.dimension then
  1143.                 x     := base^-1 * y1;
  1144.                 x_inv := x ^ -1;
  1145.                 i     := 1;
  1146.                 result.areequivalent := true;
  1147.                 while i <= Length( group1.generators ) and result.areequivalent do
  1148.                     if x * group1.generators[i] * x_inv <> group2.generators[i] then
  1149.                         result.areequivalent := false;
  1150.                     fi;
  1151.                     i := i + 1;
  1152.                 od;
  1153.                 if result.areequivalent then
  1154.                     result.transformationMatrix := x;
  1155.                 fi;
  1156.             fi;
  1157.  
  1158.         until result.areequivalent or line > enum.numberLines;
  1159.  
  1160.     else
  1161.         Error( "sorry, failed finding a cyclic generator" );
  1162.     fi;
  1163.     return result;
  1164. end;
  1165.  
  1166.  
  1167. #############################################################################
  1168. ##
  1169. #F  EquivalenceTest( <domain>, <domain> ) . . . . . .  equivalence of domains
  1170. ##
  1171. EquivalenceTest := function( D1, D2 )
  1172.     local   equiv;
  1173.  
  1174.     if IsDomain( D1 ) and IsBound( D1.operations.EquivalenceTest ) then
  1175.         equiv := D1.operations.EquivalenceTest( D1, D2 );
  1176.     else
  1177.         Error( "sorry, can't test equivalence of the given domains" );
  1178.     fi;
  1179.     return equiv;
  1180. end;
  1181.  
  1182.  
  1183. #############################################################################
  1184. ##
  1185. #F  AddNextMatrixFunction( <matgroup>, <function> ) . . . . . . . . . . . . .
  1186. #F  . . . . . . . . . . . . .  set the NextMatrix function for a matrix group
  1187. ##
  1188. AddNextMatrixFunction := function( group, func )
  1189.    group.operations.NextMatrix := func;
  1190. end;
  1191.  
  1192.  
  1193. #############################################################################
  1194. ##
  1195. #F  NextMatrix( <matgroup>, <info> )  . . . . . . . . .  generate next matrix
  1196. ##
  1197. NextMatrix := function( group, info )
  1198.     local   m;
  1199.  
  1200.     if IsMatGroup( group ) then
  1201.         if not IsBound( group.operations.NextMatrix ) then
  1202.             AddNextMatrixFunction( group, NextMatrix2 );
  1203.         fi;
  1204.         m := group.operations.NextMatrix( group, info );
  1205.     else
  1206.         Error( "sorry, I only can compute a next matrix for matrix groups" );
  1207.     fi;
  1208.     return m;
  1209. end;
  1210.  
  1211.  
  1212. #############################################################################
  1213. ##
  1214. #F  SmallCorankMatrixRecord( <matgroup> ) .  choose random matrix of low rank
  1215. ##
  1216. SmallCorankMatrixRecord := G -> RandomMatrixRecord( G, 1 );
  1217.  
  1218.  
  1219. #############################################################################
  1220. ##
  1221. #F  RandomMatrixRecord( <matgroup>[, <integer>] ) . . .  choose random matrix
  1222. ##
  1223. ##
  1224. ##
  1225. ##  returns
  1226. ##
  1227. ##      rec(
  1228. ##          matrix    := <matrix>,
  1229. ##          corank    := <integer>,
  1230. ##          nullspace := <rowspace>,
  1231. ##          corankGcd := <integer>
  1232. ##      )
  1233. ##
  1234. RandomMatrixRecord := function( arg )
  1235.     local   group, maxcrk, m, crk, gcd, ns, minmat, mincrk, minns, zero, info;
  1236.  
  1237.     if   Length( arg ) = 1 then   group := arg[1];  maxcrk := group.dimension;
  1238.     elif Length( arg ) = 2 then   group := arg[1];  maxcrk := arg[2];
  1239.     else Error( "usage: RandomMatrixRecord( <matgroup>[, <maxcorank>] )" );
  1240.     fi;
  1241.  
  1242.     if group.generators = [] or group.dimension = 1 then
  1243.         return rec(
  1244.             matrix    := 0 * group.identity,
  1245.             corank    := group.dimension,
  1246.             nullspace := RowSpace( group.dimension, group.field ),
  1247.             corankGcd := group.dimension
  1248.         );
  1249.     fi;
  1250.  
  1251.     zero := 0 * group.identity[1];
  1252.     info := rec();
  1253.     m    := NextMatrix( group, info );
  1254.  
  1255.     ns  := NullspaceMat( m );
  1256.     crk := Length( ns );
  1257.     gcd := crk;
  1258.     if 0 < crk and crk <= maxcrk then
  1259.         return rec(
  1260.             matrix    := m,
  1261.             corank    := crk,
  1262.             nullspace := RowSpace( ns, group.field, zero ),
  1263.             corankGcd := gcd
  1264.         );
  1265.     elif 0 < crk then
  1266.         minmat := m;
  1267.         mincrk := crk;
  1268.         minns  := ns;
  1269.     else
  1270.         minmat := 0 * m;
  1271.         mincrk := group.dimension;
  1272.         minns  := RowSpace( group.dimension, group.field ).generators;
  1273.         gcd    := group.dimension;
  1274.     fi;
  1275.  
  1276.     m := NextMatrix( group, info );
  1277.     while m <> false do
  1278.         ns  := NullspaceMat( m );
  1279.         crk := Length( ns );
  1280.         gcd := Gcd( gcd, crk );
  1281.         if 0 < crk and crk <= maxcrk then
  1282.             return rec(
  1283.                 matrix    := m,
  1284.                 corank    := crk,
  1285.                 nullspace := VectorSpace( ns, group.field, zero ),
  1286.                 corankGcd := gcd
  1287.             );
  1288.         elif 0 < crk and crk < mincrk then
  1289.             minmat := m;
  1290.             mincrk := crk;
  1291.             minns  := ns;
  1292.         fi;
  1293.  
  1294.         m := NextMatrix( group, info );
  1295.     od;
  1296.  
  1297.     return rec(
  1298.         matrix    := minmat,
  1299.         corank    := mincrk,
  1300.         nullspace := VectorSpace( minns, group.field, zero ),
  1301.         corankGcd := gcd
  1302.     );
  1303. end;
  1304.  
  1305.  
  1306. #############################################################################
  1307. ##
  1308. #F  Fingerprint( <matgroup>[, <integer>] )  . . . . . . . . . . . . . . . . .
  1309. ##
  1310. ##
  1311. ##
  1312. ##  returns
  1313. ##
  1314. ##      rec(
  1315. ##          matrices   := [ <matrix> ],
  1316. ##          coranks    := [ <integer> ],
  1317. ##          nullspaces := [ <rowspace> ],
  1318. ##          corankGcd  := <integer>,
  1319. ##          failed     := <boolean>
  1320. ##      )
  1321. ##
  1322. Fingerprint := function( arg )
  1323.     local group, maxcrk, corank, nullspace, matrix, m, zero, info, gcd, i;
  1324.  
  1325.     if   Length( arg ) = 1 then   group := arg[1];  maxcrk := 0;
  1326.     elif Length( arg ) = 2 then   group := arg[1];  maxcrk := arg[2];
  1327.     else Error( "usage: Fingerprint( <matgroup>[, <maxcorank>] )" );
  1328.     fi;
  1329.  
  1330.     # if the group is easy to handle do it now. Remember that a corank of
  1331.     # one (although possibly trivial) means the fingerprint did not fail.
  1332.  
  1333.     if group.generators = [] or group.dimension = 1 then
  1334.         return rec(
  1335.             coranks    := [ 1 ],
  1336.             nullspaces := [ RowSpace( 1, group.field ) ],
  1337.             matrices   := [ 0 * group.identity ],
  1338.             failed     := false
  1339.         );
  1340.     fi;
  1341.  
  1342.     corank    := [];
  1343.     nullspace := [];
  1344.     matrix    := [];
  1345.  
  1346.     zero := 0 * group.identity[1];
  1347.     gcd  := group.dimension;
  1348.     info := rec();
  1349.     m    := NextMatrix( group, info );
  1350.     i    := 0;
  1351.  
  1352.     while m <> false do
  1353.  
  1354.         i := i + 1;
  1355.         nullspace[i] := RowSpace( NullspaceMat( m ), group.field, zero );
  1356.         corank[i] := Dimension( nullspace[i] );
  1357.         matrix[i] := m;
  1358.         gcd := Gcd( gcd, corank[i] );
  1359.  
  1360.         if 0 < corank[i] and corank[i] <= maxcrk then
  1361.             return rec(
  1362.                 coranks    := corank,
  1363.                 nullspaces := nullspace,
  1364.                 matrices   := matrix,
  1365.                 corankGcd  := gcd,
  1366.                 failed     := false
  1367.             );
  1368.         fi;
  1369.  
  1370.         m := NextMatrix( group, info );
  1371.     od;
  1372.  
  1373.     return rec(
  1374.         coranks    := corank,
  1375.         nullspaces := nullspace,
  1376.         matrices   := matrix,
  1377.         corankGcd  := gcd,
  1378.         failed     := maxcrk <> 0 or Maximum( corank ) = 0
  1379.     );
  1380. end;
  1381.  
  1382.  
  1383. #############################################################################
  1384. ##
  1385. #F  ClassicNextMatrix( <matgroup>, <info> ) . . . . . . . . . . . . . . . . .
  1386. ##
  1387. ##  This  function  implements  the  classical  fingerprint  methods  for two
  1388. ##  matrices  as  proposed  by  R.A.   Parker  in  his  first paper about the
  1389. ##  meat-axe system.
  1390. ##
  1391. ClassicNextMatrix := function( group, info )
  1392.     local   m;
  1393.  
  1394.     if info = rec() then
  1395.         info.R := [];
  1396.         info.number := 0;
  1397.  
  1398.         if Length( group.generators ) >= 2 then
  1399.             info.R[1] := group.generators[1];
  1400.             info.R[2] := group.generators[2];
  1401.         elif Length( group.generators ) = 1 then
  1402.             info.R[1] := group.generators[1];
  1403.             info.R[2] := group.identity;
  1404.         else
  1405.             info.R[1] := group.identity;
  1406.             info.R[2] := group.identity;
  1407.         fi;
  1408.  
  1409.         info.R[3] := info.R[1] * info.R[2];
  1410.         info.R[4] := info.R[1] + info.R[2];
  1411.         info.R[5] := info.R[3] + info.R[4];
  1412.     fi;
  1413.  
  1414.     info.number := info.number + 1;
  1415.  
  1416.     if   info.number = 1 then
  1417.         m := info.R[5];
  1418.     elif info.number = 2 then
  1419.         info.R[6] := info.R[3] * info.R[2];
  1420.         info.R[7] := info.R[5] + info.R[6];
  1421.         m         := info.R[7];
  1422.     elif info.number = 3 then
  1423.         info.R[8] := info.R[2] * info.R[7];
  1424.         info.R[9] := info.R[1] + info.R[8];
  1425.         m         := info.R[9];
  1426.     elif info.number = 4 then
  1427.         info.R[10] := info.R[2] + info.R[9];
  1428.         m          := info.R[10];
  1429.     elif info.number = 5 then
  1430.         info.R[11] := info.R[3] + info.R[10];
  1431.         m          := info.R[11];
  1432.     elif info.number = 6 then
  1433.         info.R[12] := info.R[1] + info.R[11];
  1434.         m          := info.R[12];
  1435.     else
  1436.         m := false;
  1437.     fi;
  1438.  
  1439.     return m;
  1440. end;
  1441.  
  1442.  
  1443. #############################################################################
  1444. ##
  1445. #F  ExtendedClassicNextMatrix( <matgroup>, <info> ) . . . . . . . . . . . . .
  1446. ##
  1447. ##  This  function  implements  the  classical  fingerprint  methods  for two
  1448. ##  matrices  as  proposed  by  R.A.   Parker  in  his  first paper about the
  1449. ##  meat-axe  system, extended for the case when more generating matrices are
  1450. ##  given.
  1451. ##
  1452. ExtendedClassicNextMatrix := function( group, info )
  1453.     local   m;
  1454.  
  1455.     if info = rec() then
  1456.  
  1457.         info.R      := [];
  1458.         info.number := 0;
  1459.         info.next   := false;
  1460.         if Length( group.generators ) >= 2 then
  1461.             info.R[1] := group.generators[1];   info.1 := 1;
  1462.             info.R[2] := group.generators[2];   info.2 := 2;
  1463.         elif Length( group.generators ) = 1 then
  1464.             info.R[1] := group.identity;        info.2 := 0;
  1465.             info.R[2] := group.generators[1];   info.1 := 1;
  1466.         else
  1467.             info.R[1] := group.identity;        info.1 := 0;
  1468.             info.R[2] := group.identity;        info.2 := 0;
  1469.         fi;
  1470.         info.R[3] := info.R[1] * info.R[2];
  1471.         info.R[4] := info.R[1] + info.R[2];
  1472.         info.R[5] := info.R[3] + info.R[4];
  1473.  
  1474.     elif info.next then
  1475.  
  1476.         info.2 := info.2 + 1;
  1477.         if info.2 > Length( group.generators ) then
  1478.             info.1 := info.1 + 1;
  1479.             info.2 := info.1 + 1;
  1480.         fi;
  1481.         if info.2 > Length( group.generators ) then
  1482.             return false;
  1483.         fi;
  1484.  
  1485.         info.R      := [];
  1486.         info.number := 0;
  1487.         info.next   := false;
  1488.         info.R[1] := group.generators[info.1];
  1489.         info.R[2] := group.generators[info.2];
  1490.         info.R[3] := info.R[1] * info.R[2];
  1491.         info.R[4] := info.R[1] + info.R[2];
  1492.         info.R[5] := info.R[3] + info.R[4];
  1493.  
  1494.     fi;
  1495.  
  1496.     info.number := info.number + 1;
  1497.  
  1498.     if   info.number = 1 then
  1499.         m := info.R[5];
  1500.     elif info.number = 2 then
  1501.         info.R[6] := info.R[3] * info.R[2];
  1502.         info.R[7] := info.R[5] + info.R[6];
  1503.         m         := info.R[7];
  1504.     elif info.number = 3 then
  1505.         info.R[8] := info.R[2] * info.R[7];
  1506.         info.R[9] := info.R[1] + info.R[8];
  1507.         m         := info.R[9];
  1508.     elif info.number = 4 then
  1509.         info.R[10] := info.R[2] + info.R[9];
  1510.         m          := info.R[10];
  1511.     elif info.number = 5 then
  1512.         info.R[11] := info.R[3] + info.R[10];
  1513.         m          := info.R[11];
  1514.     elif info.number = 6 then
  1515.         info.R[12] := info.R[1] + info.R[11];
  1516.         m          := info.R[12];
  1517.     else
  1518.         info.next := true;
  1519.         m := NextMatrix( group, info );
  1520.     fi;
  1521.  
  1522.     return m;
  1523. end;
  1524.  
  1525.  
  1526. #############################################################################
  1527. ##
  1528. #F  NextMatrix1( <matgroup>, <info> ) . . . . . . . . . . . . . . . . . . . .
  1529. ##
  1530. ##
  1531. NextMatrix1 := function( group, info )
  1532.     local   m, g, i;
  1533.  
  1534.     if info = rec() then
  1535.         if group.generators = [] then
  1536.             m := group.identity;
  1537.         else
  1538.             m := group.generators[1];
  1539.             for i in [2..Length( group.generators )] do
  1540.                 m := m * group.generators[i];
  1541.             od;
  1542.             info.product := m;
  1543.             for i in [1..Length( group.generators )] do
  1544.                 m := m + group.generators[i];
  1545.             od;
  1546.         fi;
  1547.  
  1548.         info.matrix    := m;
  1549.         info.generator := 0;
  1550.         info.nextgen   := true;
  1551.  
  1552.         return m;
  1553.     fi;
  1554.  
  1555.     if info.nextgen then
  1556.         info.generator := info.generator + 1;
  1557.         if info.generator > Length( group.generators ) then
  1558.             return false;
  1559.         fi;
  1560.  
  1561.         m := info.matrix;
  1562.         g := group.generators[info.generator];
  1563.  
  1564.         m := m * g;
  1565.         for i in [1..info.generator] do
  1566.             m := m + group.generators[i];
  1567.         od;
  1568.         info.matrix  := m;
  1569.         info.nextgen := false;
  1570.     else
  1571.         m := info.matrix;
  1572.         m := m + info.product;
  1573.         info.matrix  := m;
  1574.         info.nextgen := true;
  1575.     fi;
  1576.  
  1577.     return m;
  1578. end;
  1579.  
  1580.  
  1581. #############################################################################
  1582. ##
  1583. #F  NextMatrix2( <matgroup>, <info> ) . . . . . . . . . . . . . . . . . . . .
  1584. ##
  1585. ##
  1586. NextMatrix2 := function( group, info )
  1587.     local   m, g, ew, ew2, i;
  1588.  
  1589.     if info = rec() then
  1590.         if group.generators = [] then
  1591.             m := group.identity;
  1592.         else
  1593.             m := group.generators[1];
  1594.             for i in [2..Length( group.generators )] do
  1595.                 m := m * group.generators[i];
  1596.             od;
  1597.             info.product := m;
  1598.             for i in [1..Length( group.generators )] do
  1599.                 m := m + group.generators[i];
  1600.             od;
  1601.         fi;
  1602.  
  1603.         if IsFinite( group.field ) then
  1604.             ew     := group.field.one;
  1605.             ew2    := group.field.zero;
  1606.             info.eigenvalues := [ ew2 ];
  1607.             for i in [2..Order( group.field, group.field.root )+1] do
  1608.                 ew := ew * group.field.root;
  1609.                 info.eigenvalues[i] := ew - ew2;
  1610.                 ew2 := ew;
  1611.             od;
  1612.         else
  1613.             info.eigenvalues := [ 0, -3, 1, 1, 2, 1, 1 ];
  1614.         fi;
  1615.  
  1616.         info.matrix    := m;
  1617.         info.generator := 0;
  1618.         info.nextgen   := true;
  1619.         info.nextev    := 1;
  1620.  
  1621.         return m;
  1622.     fi;
  1623.  
  1624.     if info.nextgen then
  1625.         if info.nextev = 1 then
  1626.  
  1627.             info.generator := info.generator + 1;
  1628.             if info.generator > Length( group.generators ) then
  1629.                 return false;
  1630.             fi;
  1631.  
  1632.             m := info.matrix;
  1633.             g := group.generators[info.generator];
  1634.  
  1635.             m := m * g;
  1636.             for i in [1..info.generator] do
  1637.                 m := m + group.generators[i];
  1638.             od;
  1639.             info.matrix := m;
  1640.             info.nextev := info.nextev + 1;
  1641.             if info.nextev > Length( info.eigenvalues ) then
  1642.                 info.nextgen := false;
  1643.                 info.nextev  := 1;
  1644.             fi;
  1645.         else
  1646.             if info.nextev = 2 then
  1647.                 info.matrix2 := info.matrix;
  1648.             fi;
  1649.  
  1650.             m := Copy( info.matrix2 );
  1651.             for i in [1..group.dimension] do
  1652.                 m[i][i] := m[i][i] + info.eigenvalues[info.nextev];
  1653.             od;
  1654.             info.matrix2 := m;
  1655.  
  1656.             info.nextev := info.nextev + 1;
  1657.             if info.nextev > Length( info.eigenvalues ) then
  1658.                 info.nextgen := false;
  1659.                 info.nextev  := 1;
  1660.             fi;
  1661.         fi;
  1662.     else
  1663.         if info.nextev = 1 then
  1664.             m := info.matrix;
  1665.             m := m + info.product;
  1666.             info.matrix := m;
  1667.             info.nextev := info.nextev + 1;
  1668.             if info.nextev > Length( info.eigenvalues ) then
  1669.                 info.nextgen := true;
  1670.                 info.nextev  := 1;
  1671.             fi;
  1672.         else
  1673.             if info.nextev = 2 then
  1674.                 info.matrix2 := info.matrix;
  1675.             fi;
  1676.  
  1677.             m := Copy( info.matrix2 );
  1678.             for i in [1..group.dimension] do
  1679.                 m[i][i] := m[i][i] + info.eigenvalues[info.nextev];
  1680.             od;
  1681.             info.matrix2 := m;
  1682.  
  1683.             info.nextev := info.nextev + 1;
  1684.             if info.nextev > Length( info.eigenvalues ) then
  1685.                 info.nextgen := true;
  1686.                 info.nextev  := 1;
  1687.             fi;
  1688.         fi;
  1689.     fi;
  1690.  
  1691.     return m;
  1692. end;
  1693.  
  1694.  
  1695. #############################################################################
  1696. ##
  1697. #F  NextMatrix3( <matgroup>, <info> ) . . . . . . . . . . . . . . . . . . . .
  1698. ##
  1699. ##
  1700. NextMatrix3 := function( group, info )
  1701.     local   m;
  1702.  
  1703.     if info = rec() then
  1704.         info.R      := [];
  1705.         info.number := 0;
  1706.         info.next   := false;
  1707.         if Length( group.generators ) >= 2 then
  1708.             info.R[1] := group.generators[1];   info.1 := 1;
  1709.             info.R[2] := group.generators[2];   info.2 := 2;
  1710.         elif Length( group.generators ) = 1 then
  1711.             info.R[1] := group.identity;        info.2 := 0;
  1712.             info.R[2] := group.generators[1];   info.1 := 1;
  1713.         else
  1714.             info.R[1] := group.identity;        info.1 := 0;
  1715.             info.R[2] := group.identity;        info.2 := 0;
  1716.         fi;
  1717.  
  1718.     elif info.next then
  1719.  
  1720.         info.2 := info.2 + 1;
  1721.         if info.2 > Length( group.generators ) then
  1722.             info.1 := info.1 + 1;
  1723.             info.2 := info.1 + 1;
  1724.         fi;
  1725.         if info.2 > Length( group.generators ) then
  1726.             return false;
  1727.         fi;
  1728.  
  1729.         info.R      := [];
  1730.         info.number := 0;
  1731.         info.next   := false;
  1732.     fi;
  1733.  
  1734.     info.number := info.number + 1;
  1735.  
  1736.     if info.number = 1 then
  1737.         info.R[3] := info.R[1] * info.R[2];
  1738.         info.R[4] := info.R[1] + info.R[2];
  1739.         info.R[5] := info.R[3] + info.R[4];
  1740.         m := info.R[5];
  1741.     elif info.number = 2 then
  1742.         info.R[6] := info.R[3] * info.R[2];
  1743.         info.R[7] := info.R[5] + info.R[6];
  1744.         m := info.R[7];
  1745.     elif info.number = 3 then
  1746.         info.R[8] := info.R[2] * info.R[7];
  1747.         info.R[9] := info.R[1] + info.R[8];
  1748.         m := info.R[9];
  1749.     elif info.number = 4 then
  1750.         info.R[10] := info.R[2] + info.R[9];
  1751.         m := info.R[10];
  1752.     elif info.number = 5 then
  1753.         info.R[11] := info.R[3] + info.R[10];
  1754.         m := info.R[11];
  1755.     elif info.number = 6 then
  1756.         info.R[12] := info.R[1] + info.R[11];
  1757.         m := info.R[12];
  1758.     elif 7 <= info.number and info.number <= 18 then
  1759.         m := info.R[info.number-6] - group.identity;
  1760.     elif 19 <= info.number and info.number <= 30 then
  1761.         m := info.R[info.number-18] + group.identity;
  1762.     else
  1763.         info.next := true;
  1764.         m := NextMatrix( group, info );
  1765.     fi;
  1766.  
  1767.     return m;
  1768. end;
  1769.  
  1770.  
  1771. #############################################################################
  1772. ##
  1773. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1774. ##
  1775. ##  Local Variables:
  1776. ##  mode:               outline
  1777. ##  outline-regexp:     "#F\\|#V\\|#E"
  1778. ##  fill-column:        73
  1779. ##  fill-prefix:        "##  "
  1780. ##  eval:               (hide-body)
  1781. ##  End:
  1782. ##
  1783.  
  1784.  
  1785.  
  1786.