home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / grphomom.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  34.9 KB  |  1,103 lines
  1. #############################################################################
  2. ##
  3. #A  grphomom.g                  GAP library                      Frank Celler
  4. #A                                                         & Martin Schoenert
  5. ##
  6. #A  @(#)$Id: grphomom.g,v 3.29 1993/02/09 14:25:55 martin Rel $
  7. ##
  8. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  9. ##
  10. ##  This file contains dispatcher and default functions for grp homomorphism.
  11. ##
  12. #H  $Log: grphomom.g,v $
  13. #H  Revision 3.29  1993/02/09  14:25:55  martin
  14. #H  made undefined globals local
  15. #H
  16. #H  Revision 3.28  1993/01/27  11:27:14  martin
  17. #H  fixed 'IsGroupHomomorphism' to return 'false' for field homomorphisms
  18. #H
  19. #H  Revision 3.27  1992/12/16  19:47:27  martin
  20. #H  replaced quoted record names with escaped ones
  21. #H
  22. #H  Revision 3.26  1992/06/04  12:50:57  martin
  23. #H  changed 'GroupHomomorphismsByImages' to accept empty lists
  24. #H
  25. #H  Revision 3.25  1992/06/03  17:26:20  martin
  26. #H  improved 'GroupHomomorphismByImages'
  27. #H
  28. #H  Revision 3.24  1992/03/31  09:13:07  martin
  29. #H  changed 'ConjugationGroupHomomorphism' and added 'InnerAutomorphism'
  30. #H
  31. #H  Revision 3.23  1992/03/27  11:14:51  martin
  32. #H  changed mapping to general mapping and function to mapping
  33. #H
  34. #H  Revision 3.22  1992/02/21  13:33:31  martin
  35. #H  fixed a minor bug in 'GroupHomomorphismByImages'
  36. #H
  37. #H  Revision 3.21  1992/02/11  12:44:04  martin
  38. #H  added 'SmallestGenerators'
  39. #H
  40. #H  Revision 3.20  1992/02/10  15:14:35  martin
  41. #H  added the domain 'Mappings'
  42. #H
  43. #H  Revision 3.19  1992/02/10  15:04:48  martin
  44. #H  fixed comparison of homomorphisms to check for mapping first
  45. #H
  46. #H  Revision 3.18  1992/02/07  10:39:36  martin
  47. #H  improved the homomorphism test slightly
  48. #H
  49. #H  Revision 3.17  1992/01/31  12:31:31  martin
  50. #H  added 'GroupHomomorphismByImagesOps.PreImagesRepresentative'
  51. #H
  52. #H  Revision 3.16  1992/01/20  13:51:46  martin
  53. #H  fixed 'GroupHomomorphismByImagesOps.CompositionMapping' argument order
  54. #H
  55. #H  Revision 3.15  1992/01/20  09:52:29  martin
  56. #H  improved the argument check in 'GroupHomomorphismsByImages'
  57. #H
  58. #H  Revision 3.14  1992/01/14  16:48:03  martin
  59. #H  fixed a minor problem in 'GroupHomomorphismByImages'
  60. #H
  61. #H  Revision 3.13  1992/01/07  12:44:14  martin
  62. #H  changed everything
  63. #H
  64. #H  Revision 3.12  1991/11/07  09:36:15  fceller
  65. #H  More new names because of new domain concept.
  66. #H
  67. #H  Revision 3.11  1991/09/30  10:53:45  fceller
  68. #H  New Parent Group and Subgroup concept.
  69. #H
  70. #H  Revision 3.10  1991/09/25  13:02:28  fceller
  71. #H  Add 'HomomorphicPreImage'.
  72. #H
  73. #H  Revision 3.9  1991/09/24  13:52:34  fceller
  74. #H  '~.inverseMapping' is now installed for every homomorphism.
  75. #H
  76. #H  Revision 3.8  1991/09/19  07:55:04  fceller
  77. #H  Homomorphism printing improved.
  78. #H
  79. #H  Revision 3.7  1991/09/18  13:58:19  fceller
  80. #H  Fixed a minor bug in '='
  81. #H
  82. #H  Revision 3.6  1991/09/11  09:03:27  fceller
  83. #H  Homomorphism '/' now allows lists as first argument.
  84. #H
  85. #H  Revision 3.5  1991/09/11  08:29:00  fceller
  86. #H  Cosets improved
  87. #H
  88. #H  Revision 3.4  1991/09/09  07:51:36  fceller
  89. #H  'SomethingAgGroup' is now 'AgGroupOps.Something'
  90. #H
  91. #H  Revision 3.3  1991/09/04  11:25:45  fceller
  92. #H  'IsElement' is completely replaced by 'in'.
  93. #H
  94. #H  Revision 3.2  1991/09/04  10:35:25  fceller
  95. #H  Cosets have moved from "group.g" to here
  96. #H
  97. #H  Revision 3.1  1991/09/04  10:14:25  fceller
  98. #H  Initial release under RCS
  99. #H
  100. ##
  101.  
  102.  
  103. #############################################################################
  104. ##
  105. #F  IsGroupHomomorphism(<fun>)  .  test if a function is a group homomorphism
  106. ##
  107. IsGroupHomomorphism := function ( fun )
  108.     if not IsBound( fun.isGroupHomomorphism )  then
  109.         fun.isGroupHomomorphism := fun.operations.IsGroupHomomorphism( fun );
  110.     fi;
  111.     return fun.isGroupHomomorphism;
  112. end;
  113.  
  114.  
  115. #############################################################################
  116. ##
  117. #F  GroupOps.IsHomomorphism(<fun>) test if a function is a group homomorphism
  118. ##
  119. GroupOps.IsHomomorphism := IsGroupHomomorphism;
  120.  
  121.  
  122. #############################################################################
  123. ##
  124. #F  MappingOps.IsGroupHomomorphism(<fun>) . . . test if a function is a group
  125. #F                                                               homomorphism
  126. ##
  127. MappingOps.IsGroupHomomorphism := function ( fun )
  128.     local   isHom;      # 'true' if <fun> is a homomorphism, result
  129.  
  130.     # check that <fun> is a function
  131.     if not IsMapping( fun )  then
  132.         Error("<fun> must be a single valued mapping");
  133.     fi;
  134.  
  135.     # test that source and range are groups
  136.     if not IsGroup( fun.source )  then
  137.         return false;
  138.     fi;
  139.     if not IsGroup( fun.range )  then
  140.         return false;
  141.     fi;
  142.  
  143.     # test the linearity explicitely if the source is finite
  144.     if IsFinite( fun.source )  then
  145.         isHom := ForAll( Elements(fun.source),
  146.                         x -> ForAll( fun.source.generators,
  147.                                   y -> Image( fun, x * y )
  148.                                      = Image( fun, x ) * Image( fun, y ) ) );
  149.  
  150.     # otherwise give up
  151.     else
  152.         Error("sorry, can not test if <fun> is a hom., infinite source");
  153.     fi;
  154.  
  155.     # return the result
  156.     return isHom;
  157. end;
  158.  
  159.  
  160. #############################################################################
  161. ##
  162. #F  KernelGroupHomomorphism(<fun>)  . . . . .  kernel of a group homomorphism
  163. ##
  164. KernelGroupHomomorphism := function ( fun )
  165.     if not IsBound( fun.kernelGroupHomomorphism )  then
  166.         fun.kernelGroupHomomorphism
  167.             := fun.operations.KernelGroupHomomorphism(fun);
  168.     fi;
  169.     return fun.kernelGroupHomomorphism;
  170. end;
  171.  
  172.  
  173. #############################################################################
  174. ##
  175. #F  GroupOps.Kernel(<fun>)  . . . . . . . . .  kernel of a group homomorphism
  176. ##
  177. GroupOps.Kernel := KernelGroupHomomorphism;
  178.  
  179.  
  180. #############################################################################
  181. ##
  182. #F  MappingOps.KernelGroupHomomorphism(<hom>)  kernel of a group homomorphism
  183. ##
  184. MappingOps.KernelGroupHomomorphism := function ( hom )
  185.     local   krn,        # kernel of <hom>, result
  186.             g;          # random element of source
  187.  
  188.     # check that <hom> is a homomorphism
  189.     if not IsHomomorphism(hom)  then
  190.         Error("<hom> must be a homomorphism");
  191.     fi;
  192.     if not IsFinite( hom.source )  then
  193.         Error("sorry, cannot compute kernel of <hom>, infinite source");
  194.     fi;
  195.  
  196.     #N  16-Dec-91 martin this used to be
  197.     #N  krn := AsSubgroup( Parent(hom.source),
  198.     #N              Filtered( Elements(hom.source),
  199.     #N                  elm -> Image(hom,elm) = hom.range.identity ) );
  200.  
  201.     # compute the kernel by trying random elements
  202.     krn := TrivialSubgroup( Parent( hom.source ) );
  203.     while Size( hom.source ) / Size( krn ) <> Size( Image( hom ) )  do
  204.         g := Random( hom.source );
  205.         if hom.operations.ImageElm( hom, g ) = hom.range.identity
  206.             and not g in krn
  207.         then
  208.             krn := Closure( krn, g );
  209.         fi;
  210.     od;
  211.  
  212.     # return the kernel
  213.     return krn;
  214. end;
  215.  
  216.  
  217. #############################################################################
  218. ##
  219. #F  GroupHomomorphismOps  . . . . . operations record for group homomorphisms
  220. ##
  221. GroupHomomorphismOps := Copy( MappingOps );
  222.  
  223.  
  224. #############################################################################
  225. ##
  226. #F  GroupHomomorphismOps.IsInjective(<hom>) . . . . .  test if a homomorphism
  227. #F                                                               is injective
  228. ##
  229. GroupHomomorphismOps.IsInjective := function ( hom )
  230.     return IsTrivial( KernelGroupHomomorphism( hom ) );
  231. end;
  232.  
  233.  
  234. #############################################################################
  235. ##
  236. #F  GroupHomomorphismOps.IsSurjective(<hom>)  . . . .  test if a homomorphism
  237. #F                                                              is surjective
  238. ##
  239. GroupHomomorphismOps.IsSurjective := function ( hom )
  240.     return Size( hom.range ) = Size( Image( hom ) );
  241. end;
  242.  
  243.  
  244. #############################################################################
  245. ##
  246. #F  GroupHomomorphismOps.IsGroupHomomorphism(<hom>) . . . . . . . always true
  247. ##
  248. GroupHomomorphismOps.IsGroupHomomorphism := function ( hom )
  249.     return true;
  250. end;
  251.  
  252.  
  253. #############################################################################
  254. ##
  255. #F  GroupHomomorphismOps.\=(<hom1>,<hom2>) . . . comparison of homomorphisms
  256. ##
  257. GroupHomomorphismOps.\= := function ( hom1, hom2 )
  258.     local   isEql;
  259.  
  260.     # if <hom1> is a homomorphisms
  261.     if IsGeneralMapping( hom1 )  and IsHomomorphism( hom1 )  then
  262.  
  263.         # and if <hom2> is a homomorphisms
  264.         if IsGeneralMapping( hom2 )  and IsHomomorphism( hom2 )  then
  265.  
  266.             # maybe the properties we already know determine the result
  267.             if (IsBound(hom1.isInjective) and IsBound(hom2.isInjective)
  268.                 and hom1.isInjective <> hom2.isInjective)
  269.             or (IsBound(hom1.isSurjective) and IsBound(hom2.isSurjective)
  270.                 and hom1.isSurjective <> hom2.isSurjective)
  271.             then
  272.                 isEql := false;
  273.  
  274.             # otherwise we must really test the equality
  275.             else
  276.                 isEql := hom1.source = hom2.source
  277.                     and hom1.range  = hom2.range
  278.                     and ForAll( hom1.source.generators,
  279.                            elm -> Image(hom1,elm) = Image(hom2,elm) );
  280.             fi;
  281.  
  282.         # a homomorphism and an object of another type are never equal
  283.         else
  284.             isEql := false;
  285.         fi;
  286.  
  287.     # if <hom1> is not a homomorphism
  288.     else
  289.  
  290.         # a homomorphism and an object of another type are never equal
  291.         if IsHomomorphism( hom2 )  then
  292.             isEql := false;
  293.  
  294.         # at least one argument must be a mapping
  295.         else
  296.             Error("panic, either <hom1> or <hom2> must be a mapping");
  297.         fi;
  298.  
  299.     fi;
  300.  
  301.     # return the result
  302.     return isEql;
  303. end;
  304.  
  305.  
  306. #############################################################################
  307. ##
  308. #F  GroupHomomorphismOps.\<(<hom1>,<hom2>) . . . comparison of homomorphisms
  309. ##
  310. GroupHomomorphismOps.\< := function ( hom1, hom2 )
  311.     local   isLess,     # 'true' if <hom1> is less than <hom2>, result
  312.             gens,       # smallest gens of the source of <hom1> and <hom2>
  313.             i;          # loop variable
  314.  
  315.     # if <hom1> is a homomorphism
  316.     if IsGeneralMapping( hom1 )  and IsHomomorphism( hom1 )  then
  317.  
  318.         # and if <hom2> is also a homomorphism
  319.         if IsGeneralMapping( hom2 )  and IsHomomorphism( hom2 )  then
  320.  
  321.             # compare the sources and the ranges
  322.             if hom1.source <> hom2.source  then
  323.                 isLess := hom1.source < hom2.source;
  324.             elif hom1.range <> hom2.range  then
  325.                 isLess := hom1.range < hom2.range;
  326.  
  327.             # otherwise compare the images lexicographically
  328.             else
  329.  
  330.                 # find the first element where the images differ
  331.                 gens := SmallestGenerators( hom1.source );
  332.                 i := 1;
  333.                 while i <= Length( gens )
  334.                   and hom1.operations.ImagesElm( hom1, gens[i] )
  335.                     = hom2.operations.ImagesElm( hom2, gens[i] )  do
  336.                     i := i + 1;
  337.                 od;
  338.  
  339.                 # compare the image sets
  340.                 if i <= Length( gens )  then
  341.                     isLess := hom1.operations.ImagesElm( hom1, gens[i] )
  342.                             < hom2.operations.ImagesElm( hom2, gens[i] );
  343.                 else
  344.                     isLess := false;
  345.                 fi;
  346.  
  347.             fi;
  348.  
  349.         # delegate the comparison of a homomorphism and a mapping
  350.         elif IsGeneralMapping( hom2 )  then
  351.             isLess := MappingOps.\<( hom1, hom2 );
  352.  
  353.         # a homomorphism and an object of another type are never equal
  354.         else
  355.             isLess := IsBool( hom2 ) or IsString( hom2 )
  356.                    or IsList( hom2 ) or IsRec( hom2 );
  357.         fi;
  358.  
  359.     # if <hom1> is a mapping (but not a homomorphism)
  360.     elif IsGeneralMapping( hom1 )  then
  361.  
  362.         # delegate the comparison of a mapping and a homomorphism
  363.         if IsGeneralMapping( hom2 )  and IsHomomorphism( hom2 )  then
  364.             isLess := MappingOps.\<( hom1, hom2 );
  365.  
  366.         # at least one argument must be a homomorphism
  367.         else
  368.             Error("panic, either <hom1> or <hom2> must be a homomorphism");
  369.         fi;
  370.  
  371.     # if <hom1> is not even a mapping
  372.     else
  373.  
  374.         # an object of another type and a homormorphism are never equal
  375.         if IsGeneralMapping( hom2 )  and IsHomomorphism( hom2 )  then
  376.             isLess := not (IsBool( hom1 ) or IsString( hom1 )
  377.                         or IsList( hom1 ) or IsRec( hom1 ));
  378.  
  379.         # at least one argument must be a mapping
  380.         else
  381.             Error("panic, either <hom1> or <hom2> must be a homorphism");
  382.         fi;
  383.  
  384.     fi;
  385.  
  386.     # return the result
  387.     return isLess;
  388. end;
  389.  
  390.  
  391. #############################################################################
  392. ##
  393. #F  GroupHomomorphismOps.ImagesSet(<hom>,<elms>)  images of a set under a hom
  394. ##
  395. GroupHomomorphismOps.ImagesSet := function ( hom, elms )
  396.     if IsGroup( elms )  and IsSubset( hom.source, elms )  then
  397.         return Parent( hom.range ).operations.Subgroup( Parent( hom.range ),
  398.                         List( elms.generators, gen -> Image( hom, gen ) ) );
  399.     else
  400.         return MappingOps.ImagesSet( hom, elms );
  401.     fi;
  402. end;
  403.  
  404.  
  405. #############################################################################
  406. ##
  407. #F  GroupHomomorphismOps.PreImagesElm(<hom>,<elm>)  . . .  preimage of an elm
  408. ##
  409. GroupHomomorphismOps.PreImagesElm := function ( hom, elm )
  410.     return Coset( KernelGroupHomomorphism( hom ),
  411.                   PreImagesRepresentative( hom, elm ) );
  412. end;
  413.  
  414.  
  415. #############################################################################
  416. ##
  417. #F  GroupHomomorphismOps.PreImagesSet(<hom>,<elm>)  . . . . preimage of a set
  418. ##
  419. GroupHomomorphismOps.PreImagesSet := function ( hom, elms )
  420.     if IsGroup( elms )  and IsSubset( hom.range, elms )  then
  421.         return Closure( KernelGroupHomomorphism( hom ),
  422.                     Parent( hom.source ).operations.Subgroup(
  423.                         Parent( hom.source ),
  424.                         List( elms.generators,
  425.                             gen -> PreImagesRepresentative( hom, gen ) ) ) );
  426.     else
  427.         return MappingOps.PreImagesSet( hom, elms );
  428.     fi;
  429. end;
  430.  
  431.  
  432. #############################################################################
  433. ##
  434. #F  GroupHomomorphismOps.CompositionMapping(<map1>,<map2>)composition of homs
  435. ##
  436. GroupHomomorphismOps.CompositionMapping := function ( map1, map2 )
  437.     local   com;        # composition of <map1> and <map2>, result
  438.  
  439.     # handle the composition of two homomorphisms
  440.     if IsGroupHomomorphism( map1 )  and IsGroupHomomorphism( map2 )  then
  441.  
  442.         # make the mapping record
  443.         com := rec();
  444.         com.isGeneralMapping := true;
  445.         com.domain          := Mappings;
  446.  
  447.         # enter the source and the range
  448.         com.source          := map2.source;
  449.         com.range           := map1.range;
  450.  
  451.         # maybe we know that the mapping is a function
  452.         com.isMapping       := true;
  453.         com.isHomomorphism  := true;
  454.  
  455.         # enter the identifying information
  456.         com.map1            := map1;
  457.         com.map2            := map2;
  458.  
  459.         # enter the operations record
  460.         com.operations      := CompositionGroupHomomorphismOps;
  461.  
  462.     # handle other mappings
  463.     else
  464.  
  465.         com := MappingOps.CompositionMapping( map1, map2 );
  466.  
  467.     fi;
  468.  
  469.     # return the composition
  470.     return com;
  471. end;
  472.  
  473. CompositionGroupHomomorphismOps := Copy( CompositionMappingOps );
  474.  
  475. CompositionGroupHomomorphismOps.IsInjective :=
  476.            GroupHomomorphismOps.IsInjective;
  477.  
  478. CompositionGroupHomomorphismOps.IsSurjective :=
  479.            GroupHomomorphismOps.IsSurjective;
  480.  
  481. CompositionGroupHomomorphismOps.IsGroupHomomorphism :=
  482.            GroupHomomorphismOps.IsGroupHomomorphism;
  483.  
  484. CompositionGroupHomomorphismOps.\= :=
  485.            GroupHomomorphismOps.\=;
  486.  
  487. CompositionGroupHomomorphismOps.ImageElm := function ( com, elm )
  488.     return com.map1.operations.ImageElm( com.map1,
  489.                com.map2.operations.ImageElm( com.map2,
  490.                    elm ) );
  491. end;
  492.  
  493. CompositionGroupHomomorphismOps.PreImagesElm :=
  494.            GroupHomomorphismOps.PreImagesElm;
  495.  
  496. CompositionGroupHomomorphismOps.KernelGroupHomomorphism := function ( com )
  497.     return com.map2.operations.PreImagesSet( com.map2,
  498.                com.map1.operations.KernelGroupHomomorphism( com.map1 ) );
  499. end;
  500.  
  501. CompositionGroupHomomorphismOps.Print := function ( com )
  502.     Print( "(", com.map2, " * ", com.map1, ")" );
  503. end;
  504.  
  505.  
  506. #############################################################################
  507. ##
  508. #F  GroupOps.IdentityMapping(<G>) . . . . . . . . identity mapping on a group
  509. ##
  510. GroupOps.IdentityMapping := function ( G )
  511.     local   id;         # identity mapping on <G>, result
  512.  
  513.     # make the mapping
  514.     id := rec();
  515.     id.isGeneralMapping := true;
  516.     id.domain           := Mappings;
  517.  
  518.     # enter the identification
  519.     id.isIdentity       := true;
  520.     id.source           := G;
  521.     id.range            := G;
  522.  
  523.     # enter usefull information
  524.     id.isMapping        := true;
  525.     id.isInjective      := true;
  526.     id.isSurjective     := true;
  527.     id.isBijection      := true;
  528.     id.isHomomorphism   := true;
  529.     id.isMonomorphism   := true;
  530.     id.isEpimorphism    := true;
  531.     id.isIsomorphism    := true;
  532.     id.isEndomorphism   := true;
  533.     id.isAutomorphism   := true;
  534.     id.image            := G;
  535.     id.preImage         := G;
  536.     id.kernel           := TrivialSubgroup( G );
  537.  
  538.     # enter the operations record
  539.     id.operations       := IdentityGroupHomomorphismOps;
  540.  
  541.     # return the mapping
  542.     return id;
  543. end;
  544.  
  545. IdentityGroupHomomorphismOps := Copy( MappingOps );
  546.  
  547. IdentityGroupHomomorphismOps.ImageElm := function ( id, elm )
  548.     return elm;
  549. end;
  550.  
  551. IdentityGroupHomomorphismOps.ImagesElm := function ( id, elm )
  552.     return [ elm ];
  553. end;
  554.  
  555. IdentityGroupHomomorphismOps.ImagesSet := function ( id, elms )
  556.     return elms;
  557. end;
  558.  
  559. IdentityGroupHomomorphismOps.PreImageElm := function ( id, elm )
  560.     return elm;
  561. end;
  562.  
  563. IdentityGroupHomomorphismOps.PreImagesElm := function ( id, elm )
  564.     return [ elm ];
  565. end;
  566.  
  567. IdentityGroupHomomorphismOps.PreImagesSet := function ( id, elms )
  568.     return elms;
  569. end;
  570.  
  571. IdentityGroupHomomorphismOps.\= := GroupHomomorphismOps.\=;
  572.  
  573. IdentityGroupHomomorphismOps.\< := GroupHomomorphismOps.\<;
  574.  
  575. IdentityGroupHomomorphismOps.CompositionMapping := function ( map1, map2 )
  576.     if IsBound( map1.isIdentity )  then
  577.         return map2;
  578.     elif IsBound( map2.isIdentity )  then
  579.         return map1;
  580.     else
  581.         Error("panic, neither <map1> nor <map2> is the identity");
  582.     fi;
  583. end;
  584.  
  585. IdentityGroupHomomorphismOps.InverseMapping := function ( id )
  586.     return id;
  587. end;
  588.  
  589. IdentityGroupHomomorphismOps.Print := function ( id )
  590.     Print("IdentityMapping( ",id.source," )");
  591. end;
  592.  
  593.  
  594. #############################################################################
  595. ##
  596. #F  ConjugationGroupHomomorphism(<G>,<H>,<g>) . . . group homomorphism taking
  597. #F                                                each element to a conjugate
  598. ##
  599. ConjugationGroupHomomorphism := function ( G, H, g )
  600.     local   cnj;        # conjugation homomorphism, result
  601.  
  602.     # check the arguments
  603.     if not IsGroup( G )  then
  604.         Error("<G> must be a group");
  605.     fi;
  606.     if not IsGroup( H )  then
  607.         Error("<H> must be a group");
  608.     fi;
  609.     if not g in Parent( G, H )  then
  610.         Error("<g> must lie in the common parent group of <G> and <H>");
  611.     fi;
  612.     if not ForAll( G.generators, gen -> gen ^ g in H )  then
  613.         Error("<g> must map <G> into <H>");
  614.     fi;
  615.  
  616.     # make the homomorphism
  617.     cnj := rec();
  618.     cnj.isGeneralMapping := true;
  619.     cnj.domain          := Mappings;
  620.  
  621.     # enter the identifying information
  622.     cnj.isConjugation   := true;
  623.     cnj.source          := G;
  624.     cnj.range           := H;
  625.     cnj.element         := g;
  626.  
  627.     # enter usefull information
  628.     cnj.isMapping       := true;
  629.     cnj.isInjective     := true;
  630.     cnj.isHomomorphism  := true;
  631.     cnj.isMonomorphism  := true;
  632.     cnj.isEndomorphism  := G = H;
  633.     cnj.preImage        := G;
  634.     cnj.kernel          := TrivialSubgroup( G );
  635.  
  636.     # enter the operations record
  637.     cnj.operations      := ConjugationGroupHomomorphismOps;
  638.  
  639.     # return the homomorphism
  640.     return cnj;
  641. end;
  642.  
  643. ConjugationGroupHomomorphismOps := Copy( GroupHomomorphismOps );
  644.  
  645. ConjugationGroupHomomorphismOps.ImageElm := function ( cnj, elm )
  646.     return elm ^ (cnj.element);
  647. end;
  648.  
  649. ConjugationGroupHomomorphismOps.ImagesElm := function ( cnj, elm )
  650.     return [ elm ^ (cnj.element) ];
  651. end;
  652.  
  653. ConjugationGroupHomomorphismOps.ImagesSet := function ( cnj, elms )
  654.     if IsGroup( elms )  and IsSubset( cnj.source, elms )  then
  655.         return elms ^ (cnj.element);
  656.     else
  657.         return GroupHomomorphismOps.ImagesSet( cnj, elms );
  658.     fi;
  659. end;
  660.  
  661. ConjugationGroupHomomorphismOps.ImageRepresentative := function ( cnj, elm )
  662.     return elm ^ (cnj.element);
  663. end;
  664.  
  665. ConjugationGroupHomomorphismOps.PreImageElm := function ( cnj, elm )
  666.     if not IsBound( cnj.inverseElement )  then
  667.         cnj.inverseElement := cnj.element ^ -1;
  668.     fi;
  669.     return elm ^ (cnj.inverseElement);
  670. end;
  671.  
  672. ConjugationGroupHomomorphismOps.PreImagesElm := function ( cnj, elm )
  673.     if not IsBound( cnj.inverseElement )  then
  674.         cnj.inverseElement := cnj.element ^ -1;
  675.     fi;
  676.     return [ elm ^ (cnj.inverseElement) ];
  677. end;
  678.  
  679. ConjugationGroupHomomorphismOps.PreImagesSet := function ( cnj, elms )
  680.     if IsGroup( elms )  and IsSubset( cnj.source, elms )  then
  681.         if not IsBound( cnj.inverseElement )  then
  682.             cnj.inverseElement := cnj.element ^ -1;
  683.         fi;
  684.         return elms ^ (cnj.inverseElement);
  685.     else
  686.         return GroupHomomorphismOps.ImagesSet( cnj, elms );
  687.     fi;
  688. end;
  689.  
  690. ConjugationGroupHomomorphismOps.PreImageRepresentative := function (cnj, elm)
  691.     if not IsBound( cnj.inverseElement )  then
  692.         cnj.inverseElement := cnj.element ^ -1;
  693.     fi;
  694.     return elm ^ (cnj.inverseElement);
  695. end;
  696.  
  697. ConjugationGroupHomomorphismOps.CompositionMapping := function ( cnj1, cnj2 )
  698.     if      IsBound( cnj1.isConjugation )  and cnj1.isConjugation
  699.         and IsBound( cnj2.isConjugation )  and cnj2.isConjugation
  700.         and IsSubgroup( cnj1.source, cnj2.range )
  701.     then
  702.         return ConjugationGroupHomomorphism( cnj2.source, cnj1.range,
  703.                                              cnj2.element * cnj1.element );
  704.     else
  705.         return GroupHomomorphismOps.CompositionMapping( cnj1, cnj2 );
  706.     fi;
  707. end;
  708.  
  709. ConjugationGroupHomomorphismOps.PowerMapping := function ( cnj, n )
  710.     if IsEndomorphism( cnj )  then
  711.         return ConjugationGroupHomomorphism( cnj.source, cnj.range,
  712.                                              cnj.element^n );
  713.     else
  714.         return GroupHomomorphismOps.PowerMapping( cnj, n );
  715.     fi;
  716. end;
  717.  
  718. ConjugationGroupHomomorphismOps.InverseMapping := function ( cnj )
  719.     if not IsBound( cnj.inverseElement )  then
  720.         cnj.inverseElement := cnj.element ^ -1;
  721.     fi;
  722.     if IsSurjective( cnj )  then
  723.         return ConjugationGroupHomomorphism( cnj.range, cnj.source,
  724.                                              cnj.inverseElement );
  725.     else
  726.         return GroupHomomorphismOps.InverseMapping( cnj );
  727.     fi;
  728. end;
  729.  
  730. ConjugationGroupHomomorphismOps.Print := function ( cnj )
  731.    if cnj.source = cnj.range  then
  732.         Print( "InnerAutomorphism( ",cnj.source,", ",cnj.element," )");
  733.    else
  734.        Print( "ConjugationGroupHomomorphism( ",
  735.                 cnj.source,", ",cnj.range,", ",cnj.element," )");
  736.    fi;
  737. end;
  738.  
  739.  
  740. #############################################################################
  741. ##
  742. #F  InnerAutomorphism(<G>,<g>)  . . . . . . . .  create an inner automorphism
  743. ##
  744. InnerAutomorphism := function ( G, g )
  745.     local   cnj;        # conjugation homomorphism, result
  746.  
  747.     # check the arguments
  748.     if not IsGroup( G )  then
  749.         Error("<G> must be a group");
  750.     fi;
  751.     if not g in Parent( G )  then
  752.         Error("<g> must lie in the parent group of <G>");
  753.     fi;
  754.     if not ForAll( G.generators, gen -> gen ^ g in G )  then
  755.         Error("<g> must map <G> into <H>");
  756.     fi;
  757.  
  758.     # make the homomorphism
  759.     cnj := rec();
  760.     cnj.isGeneralMapping := true;
  761.     cnj.domain          := Mappings;
  762.  
  763.     # enter the identifying information
  764.     cnj.isConjugation   := true;
  765.     cnj.source          := G;
  766.     cnj.range           := G;
  767.     cnj.element         := g;
  768.  
  769.     # enter usefull information
  770.     cnj.isMapping       := true;
  771.     cnj.isInjective     := true;
  772.     cnj.isSurjective    := true;
  773.     cnj.isBijection     := true;
  774.     cnj.isHomomorphism  := true;
  775.     cnj.isMonomorphism  := true;
  776.     cnj.isEpimorphism   := true;
  777.     cnj.isIsomorphism   := true;
  778.     cnj.isEndomorphism  := true;
  779.     cnj.isAutomorphism  := true;
  780.     cnj.image           := G;
  781.     cnj.preImage        := G;
  782.     cnj.kernel          := TrivialSubgroup( G );
  783.  
  784.     # enter the operations record
  785.     cnj.operations      := ConjugationGroupHomomorphismOps;
  786.  
  787.     # return the homomorphism
  788.     return cnj;
  789. end;
  790.  
  791.  
  792. #############################################################################
  793. ##
  794. #F  GroupHomomorphismByImages(<G>,<H>,<gens>,<imgs>)  . . . .  create a group
  795. #F                          homomorphism by the images of a generating system
  796. ##
  797. GroupHomomorphismByImages := function ( G, H, gens, imgs )
  798.     local   hom;        # homomorphism from <G> to <H>, result
  799.  
  800.     # check the arguments
  801.     if not IsGroup( G )  then
  802.         Error("<G> must be a group");
  803.     elif not IsGroup( H )  then
  804.         Error("<H> must be a group");
  805.     #N  03-Jun-92 martin <gens> need no longer generate <G>
  806.     # elif not IsEqualSet(gens,G.generators)
  807.     #  and not G=Subgroup(Parent(G),gens)  then
  808.     #    Error("<gens> must be a generating system for <G>");
  809.     elif not IsEqualSet(imgs,H.generators) and not IsSubset(H,Set(imgs)) then
  810.         Error("<imgs> must lie in <H>");
  811.     elif Length( gens ) <> Length( imgs )  then
  812.         Error("<gens> and <imgs> must have the same length");
  813.     fi;
  814.  
  815.     # dispatch to the appropriate function
  816.     hom := G.operations.GroupHomomorphismByImages( G, H, gens, imgs );
  817.  
  818.     # return the homomorphism
  819.     return hom;
  820. end;
  821.  
  822. GroupOps.GroupHomomorphismByImages := function ( G, H, gens, imgs )
  823.     local   hom;        # homomorphism from <G> to <H>, result
  824.  
  825.     # make the homomorphism
  826.     hom := rec( );
  827.     hom.isGeneralMapping := true;
  828.     hom.domain          := Mappings;
  829.  
  830.     # enter the identifying information
  831.     hom.source          := G;
  832.     hom.range           := H;
  833.     hom.generators      := gens;
  834.     hom.genimages       := imgs;
  835.  
  836.     # enter usefull information (precious little)
  837.     if IsEqualSet( gens, G.generators )  then
  838.         hom.preimage    := G;
  839.     else
  840.         hom.preimage    := Parent(G).operations.Subgroup( Parent(G), gens );
  841.     fi;
  842.     if IsEqualSet( imgs, H.generators )  then
  843.         hom.image       := H;
  844.     else
  845.         hom.image       := Parent(H).operations.Subgroup( Parent(H), imgs );
  846.     fi;
  847.  
  848.     # enter the operations record
  849.     hom.operations      := GroupHomomorphismByImagesOps;
  850.  
  851.     # return the homomorphism
  852.     return hom;
  853. end;
  854.  
  855. GroupHomomorphismByImagesOps := Copy( GroupHomomorphismOps );
  856.  
  857. GroupHomomorphismByImagesOps.MakeMapping := function( hom )
  858.     local   elms,       # elements of subgroup of '<hom>.source'
  859.             elmr,       # representatives of <elms> in '<hom>.elements'
  860.             imgs,       # elements of subgroup of '<hom>.range'
  861.             imgr,       # representatives of <imgs> in '<hom>.images'
  862.             rep,        # one new element of <elmr> or <imgr>
  863.             i, j, k;    # loop variables
  864.  
  865.     # if necessary compute the mapping with a Dimino algorithm
  866.     if not IsBound( hom.elements )  then
  867.         hom.elements := [ hom.source.identity ];
  868.         hom.images   := [ hom.range.identity ];
  869.         for i  in [ 1 .. Length( hom.generators ) ]  do
  870.             elms := ShallowCopy( hom.elements );
  871.             elmr := [ hom.source.identity ];
  872.             imgs := ShallowCopy( hom.images );
  873.             imgr := [ hom.range.identity ];
  874.             j := 1;
  875.             while j <= Length( elmr )  do
  876.                 for k  in [ 1 .. i ]  do
  877.                     rep := elmr[j] * hom.generators[k];
  878.                     if not rep in hom.elements  then
  879.                         Append( hom.elements, elms * rep );
  880.                         Add( elmr, rep );
  881.                         rep := imgr[j] * hom.genimages[k];
  882.                         Append( hom.images, imgs * rep );
  883.                         Add( imgr, rep );
  884.                     fi;
  885.                 od;
  886.                 j := j + 1;
  887.             od;
  888.             SortParallel( hom.elements, hom.images );
  889.             IsSet( hom.elements );      # give a hint that this is a set
  890.         od;
  891.     fi;
  892. end;
  893.  
  894. GroupHomomorphismByImagesOps.CoKernel := function ( hom )
  895.     local   C,          # co kernel of <hom>, result
  896.             gen,        # one generator of <C>
  897.             i, k;       # loop variables
  898.  
  899.     # make sure we have the mapping
  900.     if not IsBound( hom.elements )  then
  901.         hom.operations.MakeMapping( hom );
  902.     fi;
  903.  
  904.     # start with the trivial co kernel
  905.     C := TrivialSubgroup( Parent( hom.range ) );
  906.  
  907.     # for each element of the source and each generator of the source
  908.     for i  in [ 1 .. Length( hom.elements ) ]  do
  909.         for k  in [ 1 .. Length( hom.generators ) ]  do
  910.  
  911.             # the co kernel must contain the corresponding Schreier generator
  912.             gen := hom.images[i] * hom.genimages[k]
  913.                  / hom.images[ Position( hom.elements,
  914.                                          hom.elements[i]*hom.generators[k])];
  915.             C := Closure( C, gen );
  916.  
  917.         od;
  918.     od;
  919.  
  920.     # return the co kernel
  921.     return C;
  922. end;
  923.  
  924. GroupHomomorphismByImagesOps.IsMapping := function ( hom )
  925.     if not IsBound( hom.coKernel )  then
  926.         hom.coKernel := hom.operations.CoKernel( hom );
  927.     fi;
  928.     return hom.source = hom.preimage
  929.        and IsTrivial( hom.coKernel );
  930. end;
  931.  
  932. GroupHomomorphismByImagesOps.IsGroupHomomorphism := function ( hom )
  933.     return IsMapping( hom );
  934. end;
  935.  
  936. GroupHomomorphismByImagesOps.ImageElm := function ( hom, elm )
  937.     if not IsMapping( hom )  then
  938.         Error("<hom> must be a single valued mapping");
  939.     fi;
  940.     if not IsBound( hom.elements )  then
  941.         hom.operations.MakeMapping( hom );
  942.     fi;
  943.     return hom.images[ Position( hom.elements, elm ) ];
  944. end;
  945.  
  946. GroupHomomorphismByImagesOps.ImagesElm := function ( hom, elm )
  947.     local   p;
  948.     if not IsBound( hom.elements )  then
  949.         hom.operations.MakeMapping( hom );
  950.     fi;
  951.     if not IsBound( hom.coKernel )  then
  952.         hom.coKernel := hom.operations.CoKernel( hom );
  953.     fi;
  954.     p := Position( hom.elements, elm );
  955.     if p <> false  then
  956.         return hom.coKernel * hom.images[ p ];
  957.     else
  958.         return [];
  959.     fi;
  960. end;
  961.  
  962. GroupHomomorphismByImagesOps.ImagesSet := function ( hom, elms )
  963.     if IsGroup( elms )  and IsSubset( hom.source, elms )  then
  964.         if hom.preimage <> hom.source  then
  965.             elms := Intersection( hom.preimage, elms );
  966.         fi;
  967.         if not IsBound( hom.coKernel )  then
  968.             hom.coKernel := hom.operations.CoKernel( hom );
  969.         fi;
  970.         return Closure( hom.coKernel,
  971.                         Parent( hom.range ).operations.Subgroup(
  972.                                 Parent( hom.range ),
  973.                                 List( elms.generators,
  974.                                       gen -> ImagesRepresentative( hom,
  975.                                                                    gen ) )));
  976.     else
  977.         return GroupHomomorphismOps.ImagesSet( hom, elms );
  978.     fi;
  979. end;
  980.  
  981. GroupHomomorphismByImagesOps.ImagesRepresentative := function ( hom, elm )
  982.     local   p;
  983.     if not IsBound( hom.elements )  then
  984.         hom.operations.MakeMapping( hom );
  985.     fi;
  986.     p := Position( hom.elements, elm );
  987.     if p <> false  then
  988.         return hom.images[ p ];
  989.     else
  990.         Error("<elm> has no image under <hom>");
  991.     fi;
  992. end;
  993.  
  994. GroupHomomorphismByImagesOps.PreImagesRepresentative := function ( hom, elm )
  995.     if IsBound( hom.images )  and elm in hom.images  then
  996.         return hom.elements[ Position( hom.images, elm ) ];
  997.     else
  998.         return ImagesRepresentative( InverseMapping( hom ), elm );
  999.     fi;
  1000. end;
  1001.  
  1002. GroupHomomorphismByImagesOps.KernelGroupHomomorphism := function ( hom )
  1003.     local   krn,        # kernel of <hom>, result
  1004.             inv;        # inverse mapping of <hom>
  1005.  
  1006.     # compute the kernel as the co kernel of the inverse mapping
  1007.     inv := InverseMapping( hom );
  1008.     krn := inv.operations.CoKernel( inv );
  1009.  
  1010.     # return the kernel
  1011.     return krn;
  1012. end;
  1013.  
  1014. GroupHomomorphismByImagesOps.CompositionMapping := function ( hom1, hom2 )
  1015.     local   prd;        # product of <hom1> and <hom2>, result
  1016.  
  1017.     # product of a homomorphism by generator images
  1018.     if IsHomomorphism( hom1 )  and IsBound( hom1.genimages )  then
  1019.  
  1020.         # with another homomorphism by generator images
  1021.         if IsHomomorphism( hom2 )  and IsBound( hom2.genimages )  then
  1022.  
  1023.             # make sure we have all the images of both homomorphisms
  1024.             if not IsBound( hom1.images )  then
  1025.                 hom1.operations.MakeMapping( hom1 );
  1026.             fi;
  1027.             if not IsBound( hom2.images )  then
  1028.                 hom2.operations.MakeMapping( hom2 );
  1029.             fi;
  1030.  
  1031.             # make the homomorphism
  1032.             prd := rec( );
  1033.             prd.isGeneralMapping := true;
  1034.             prd.domain          := Mappings;
  1035.  
  1036.             # enter the identifying information
  1037.             prd.source          := hom2.source;
  1038.             prd.range           := hom1.range;
  1039.             prd.generators := ShallowCopy( hom2.generators );
  1040.             prd.genimages := List( [ 1 .. Length( prd.generators ) ],
  1041.                                 i -> hom1.images[
  1042.                                         Position( hom1.elements,
  1043.                                                   hom2.genimages[i] ) ] );
  1044.  
  1045.             # enter usefull information
  1046.             prd.isMapping       := true;
  1047.             prd.isHomomorphism  := true;
  1048.             prd.preimage        := hom2.source;
  1049.             prd.elements := ShallowCopy( hom2.elements );
  1050.             prd.images := List( [ 1 .. Length( prd.elements ) ],
  1051.                                 i -> hom1.images[
  1052.                                         Position( hom1.elements,
  1053.                                                   hom2.images[i] ) ] );
  1054.  
  1055.             # enter the operations record
  1056.             prd.operations      := GroupHomomorphismByImagesOps;
  1057.  
  1058.         # with another mapping
  1059.         else
  1060.  
  1061.             prd := MappingOps.CompositionMapping( hom1, hom2 );
  1062.  
  1063.         fi;
  1064.  
  1065.     # of something else
  1066.     else
  1067.         prd := MappingOps.CompositionMapping( hom1, hom2 );
  1068.     fi;
  1069.  
  1070.     # return the product
  1071.     return prd;
  1072. end;
  1073.  
  1074. GroupHomomorphismByImagesOps.InverseMapping := function ( hom )
  1075.     return GroupHomomorphismByImages( hom.range,
  1076.                                       hom.source,
  1077.                                       hom.genimages,
  1078.                                       hom.generators );
  1079. end;
  1080.  
  1081. GroupHomomorphismByImagesOps.Print := function ( hom )
  1082.     Print( "GroupHomomorphismByImages( ",
  1083.            hom.source, ", ", hom.range, ", ",
  1084.            hom.generators, ", ", hom.genimages, " )" );
  1085. end;
  1086.  
  1087.  
  1088. #############################################################################
  1089. ##
  1090. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1091. ##
  1092. ##  Local Variables:
  1093. ##  mode:               outline
  1094. ##  outline-regexp:     "#F\\|#V\\|#E"
  1095. ##  fill-column:        73
  1096. ##  fill-prefix:        "##  "
  1097. ##  eval:               (hide-body)
  1098. ##  End:
  1099. ##
  1100.  
  1101.  
  1102.  
  1103.