home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / rowmodul.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  13.6 KB  |  461 lines
  1. #############################################################################
  2. ##
  3. #A  rowmodul.g                  GAP library                    J\"urgen Mnich
  4. ##
  5. #A  @(#)$Id: rowmodul.g,v 3.4 1992/04/07 16:15:32 jmnich Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains all functions for row modules.
  10. ##
  11. #H  $Log: rowmodul.g,v $
  12. #H  Revision 3.4  1992/04/07  16:15:32  jmnich
  13. #H  adapted to changes in the finite field module
  14. #H
  15. #H  Revision 3.3  1992/03/17  12:31:20  jmnich
  16. #H  minor style changes, more bug fixes
  17. #H
  18. #H  Revision 3.2  1992/02/29  13:25:11  jmnich
  19. #H  general library review, some bug fixes
  20. #H
  21. #H  Revision 3.1  1992/02/12  15:37:22  martin
  22. #H  initial revision under RCS
  23. #H
  24. ##
  25.  
  26.  
  27. #############################################################################
  28. ##
  29. #F  InfoModule1(...)  . . . . . . . . . . . . . . . . . . package information
  30. #F  InfoModule2(...)  . . . . . . . . . . . . . . . package debug information
  31. ##
  32. if not IsBound( InfoModule1 )  then  InfoModule1 := Ignore;  fi;
  33. if not IsBound( InfoModule2 )  then  InfoModule2 := Ignore;  fi;
  34.  
  35.  
  36. #############################################################################
  37. ##
  38. #V  RowModuleOps  . . . . . . . . . . . . . operations record for row modules
  39. ##
  40. RowModuleOps := ShallowCopy( ModuleOps );
  41.  
  42.  
  43. #############################################################################
  44. ##
  45. #F  RowModuleOps.Print( <obj> ) . . . . . . . . . . . . .  print a row module
  46. ##
  47. RowModuleOps.Print := function( M )
  48.     if IsBound( M.name ) then
  49.         Print( M.name );
  50.     else
  51.         Print( "RowModule( ", M.ring, ", ", M.abelianGroup, " )" );
  52.     fi;
  53. end;
  54.  
  55.  
  56. #############################################################################
  57. ##
  58. #F  RowModule( <matgroup> ) . . . . . . . . . . . . . . . create a row module
  59. #F  RowModule( <ring>, <rowspace> ) . . . . . . . . . . . create a row module
  60. #F  RowModule( <ring>, <dimension>, <field> ) . . . . . . create a row module
  61. ##
  62. RowModule := function( arg )
  63.     local   ring, rspace;
  64.  
  65.     if Length( arg ) = 1 then
  66.         ring   := arg[1];
  67.         rspace := RowSpace( ring.dimension, ring.field );
  68.     elif Length( arg ) = 2 then
  69.         ring   := arg[1];
  70.         rspace := arg[2];
  71.     elif Length( arg ) = 3 then
  72.         ring   := arg[1];
  73.         rspace := RowSpace( arg[2], arg[3] );
  74.     else
  75.         Error(  "usage: RowModule( <matgroup> )\n",
  76.                 "usage: RowModule( <ring>, <rowspace> )\n",
  77.                 "   or: RowModule( <ring>, <dimension>, <field> )" );
  78.     fi;
  79.  
  80.     return rec(
  81.         abelianGroup := rspace,
  82.         ring         := ring,
  83.         isRowModule  := true,
  84.         isModule     := true,
  85.         isDomain     := true,
  86.         isFinite     := IsFinite( rspace ),
  87.         operations   := RowModuleOps
  88.     );
  89. end;
  90.  
  91.  
  92. #############################################################################
  93. ##
  94. #F  IsRowModule( <obj> )  . . . . . . . . . test if an object is a row module
  95. ##
  96. IsRowModule := function( obj )
  97.     return IsRec( obj )
  98.         and IsBound( obj.isRowModule ) and obj.isRowModule;
  99. end;
  100.  
  101.  
  102. #############################################################################
  103. ##
  104. #F  RowModuleOps.Base( <rowmodule> )  . . . . . . . . . . . . . . . . . . . .
  105. #F  . . . . . . . . . determines a standard form for the base of a row module
  106. ##
  107. ##  This  function determines a standard form for the base of a row module as
  108. ##  proposed by R.A.  Parker for a meataxe program.
  109. ##  This  base  has  properties  that enables meataxe programs to decide, for
  110. ##  example,  whether  two  given  cyclic modules are isomorphic or not.  See
  111. ##  'EquivalenceTest' for details on this special example.
  112. ##
  113. ##  returns
  114. ##
  115. ##      <base>
  116. ##
  117. RowModuleOps.Base := function( module )
  118.     local   base, sbase, insub, wgts, dim, len, v, w, wc, z, m, i, j;
  119.  
  120.  
  121.     if module.abelianGroup.generators = [] then  return [];  fi;
  122.  
  123.     # base will hold the normalized, sorted base and sbase will hold
  124.     # the unnormalized, chronological (Parker-) base
  125.  
  126.     len   := Length( module.abelianGroup.zero );
  127.     base  := [];
  128.     sbase := [];
  129.     insub := BlistList( [1..len], [] );
  130.  
  131.     ## first insert the module generators themselves
  132.  
  133.     for w in module.abelianGroup.generators do
  134.         wc := ShallowCopy( w );
  135.         i  := 1;
  136.         while i <= len do
  137.             if w[i] <> module.abelianGroup.field.zero then
  138.                 if insub[i] then
  139.                     w := w - w[i] * base[i];
  140.                 else
  141.                     w := w[i] ^ -1 * w;
  142.                     Add( sbase, wc );
  143.                     insub[i] := true;
  144.                     base[i]  := w;
  145.                     i        := len;
  146.                 fi;
  147.             fi;
  148.             i := i + 1;
  149.         od;
  150.     od;
  151.  
  152.  
  153.     ## next handle the generator-images under ring operation
  154.  
  155.     for v in sbase do
  156.         for m in module.ring.generators do
  157.             w  := v * m;
  158.             wc := ShallowCopy( w );
  159.             i  := 1;
  160.             while i <= len do
  161.                 if w[i] <> module.abelianGroup.field.zero then
  162.                     if insub[i] then
  163.                         w := w - w[i] * base[i];
  164.                     else
  165.                         w := w[i] ^ -1 * w;
  166.                         Add( sbase, wc );
  167.                         insub[i] := true;
  168.                         base[i]  := w;
  169.                         i        := len;
  170.                     fi;
  171.                 fi;
  172.                 i := i + 1;
  173.             od;
  174.         od;
  175.     od;
  176.  
  177.     # see whether the base should be normalized or not
  178.  
  179.     if not IsBound( module.isNormalizedBase ) or module.isNormalizedBase then
  180.  
  181.         # collect the base and remember the elements' weights
  182.  
  183.         sbase := [];
  184.         wgts  := [];
  185.         dim   := 0;
  186.         for i in [1..len] do
  187.             if insub[i] then
  188.                 Add( sbase, base[i] );
  189.                 dim := dim + 1;
  190.                 wgts[dim] := i;
  191.             fi;
  192.         od;
  193.  
  194.         # now finally normalize the found base
  195.  
  196.         for i in [2..dim] do
  197.             for j in [1..i-1] do
  198.                 z := sbase[j][wgts[i]];
  199.                 if z <> module.abelianGroup.field.zero then
  200.                     sbase[j] := sbase[j] - z * sbase[i];
  201.                 fi;
  202.             od;
  203.         od;
  204.     fi;
  205.  
  206.     return sbase;
  207. end;
  208.  
  209.  
  210. #############################################################################
  211. ##
  212. #F  RowModuleOps.Submodule( <rowmodule>, <rowspace> ) . . . . . . . . . . . .
  213. #F  . . . . . . . . . . . . . . . . . . . . . submodule induced by <rowspace>
  214. ##
  215. RowModuleOps.Submodule := function( module, vs )
  216.     module := RowModule( module.ring, vs );
  217.     module := RowModule( module.ring,
  218.                          RowSpace( Base( module ), vs.field, vs.zero ) );
  219.     return module;
  220. end;
  221.  
  222.  
  223. #############################################################################
  224. ##
  225. #F  Submodule( <domain>, <object> ) . . . . . . . . . . . . . . . . . . . . .
  226. ##
  227. Submodule := function( D, obj )
  228.     local   subm;
  229.  
  230.     if IsDomain( D ) and IsBound( D.operations.Submodule ) then
  231.         subm := D.operations.Submodule( D, obj );
  232.     else
  233.         Error( "sorry, can't compute submodules for <domain>" );
  234.     fi;
  235.     return subm;
  236. end;
  237.  
  238.  
  239. #############################################################################
  240. ##
  241. #F  RowModuleOps.Representation( <rowmodule>[, <submodule>] ) . . . . . . . .
  242. #F  . . . . . . . . . . . . . . . . . representation afforded by a row module
  243. ##
  244. RowModuleOps.Representation := function( arg )
  245.     local   ring, vs, base, mats, id, hom, r, b, m;
  246.  
  247.  
  248.     if Length( arg ) = 1 then
  249.         ring := arg[1].ring;
  250.         vs   := arg[1].abelianGroup;
  251.     elif Length( arg ) = 2 then
  252.         ring := arg[1].ring;
  253.         vs   := arg[1].abelianGroup mod arg[2].abelianGroup;
  254.     fi;
  255.  
  256.     # if the base of the row space is the standardbase there is nothing to do
  257.  
  258.     if Information( vs ).isStandardBase then
  259.         hom := GroupHomomorphismByImages( ring, ring, ring.generators, ring.generators );
  260.         hom.base := Base( vs );
  261.         return hom;
  262.     fi;
  263.  
  264.  
  265.     # calculate the matrices of the representation
  266.  
  267.     base := Base( vs );
  268.     mats := [];
  269.     for r in ring.generators do
  270.         m := [];
  271.         for b in base do
  272.             Add( m, Coefficients( vs, b * r ) );
  273.         od;
  274.         Add( mats, m );
  275.     od;
  276.  
  277.  
  278.     # the representation is the homomorphism of the module's ring
  279.     # into the matrix group
  280.  
  281.     if mats = [] then
  282.         id  := IdentityMat( Length( base ), vs.field );
  283.         hom := GroupHomomorphismByImages( ring,
  284.                              MatGroup( mats, vs.field, id ),
  285.                              ring.generators, mats );
  286.     else
  287.         hom := GroupHomomorphismByImages( ring,
  288.                              MatGroup( mats, vs.field ),
  289.                              ring.generators, mats );
  290.     fi;
  291.  
  292.     hom.base := base;
  293.     hom.range.images := mats;
  294.  
  295.     return hom;
  296. end;
  297.  
  298.  
  299. #############################################################################
  300. ##
  301. #F  Representation( <domain>[, <subdomain>] ) . . . . . . . . . . . . . . . .
  302. ##
  303. Representation := function( arg )
  304.     local   rep;
  305.  
  306.     if IsDomain( arg[1] ) and IsBound( arg[1].operations.Representation ) then
  307.         if Length( arg ) = 1 then
  308.             rep := arg[1].operations.Representation( arg[1] );
  309.         elif Length( arg ) = 2 then
  310.             rep := arg[1].operations.Representation( arg[1], arg[2] );
  311.         else
  312.             Error( "usage: Representation( <domain>[, <subdomain>] )" );
  313.         fi;
  314.     else
  315.         Error( "sorry, can't representation for <domain>" );
  316.     fi;
  317.     return rep;
  318. end;
  319.  
  320.  
  321. #############################################################################
  322. ##
  323. #F  RowModuleOps.CompositionFactors( <rowmodule> )  . . . . . . . . . . . . .
  324. #F  . . . . . . . . . . . . . . . . . . . composition factors of a row module
  325. ##
  326. RowModuleOps.CompositionFactors := function( module )
  327.     local   rep, comp;
  328.  
  329.     rep  := Representation( module );
  330.     comp := CompositionFactors( rep.range );
  331.  
  332.     Apply( comp.bases, x -> x * rep.base );
  333.  
  334.     return comp;
  335. end;
  336.  
  337.  
  338. #############################################################################
  339. ##
  340. #F  RowModuleOps.ProperSubmodule( <rowmodule>[, <matrix>] ) . . . . . . . . .
  341. #F  . . . . . . . . . . . . . . . . . . . . . . . . . find a proper submodule
  342. ##
  343. RowModuleOps.ProperSubmodule := function( arg )
  344.     local   rep, subs;
  345.  
  346.     rep := Representation( arg[1] );
  347.     if Length( arg ) = 1 then
  348.         subs := InvariantSubspace( rep.range );
  349.     elif Length( arg ) = 2 then
  350.         subs := InvariantSubspace( rep.range, arg[2] ^ rep );
  351.     else
  352.         Error( "usage: ProperSubmodule( <rowmodule>[, <matrix>] )" );
  353.     fi;
  354.  
  355.     if IsInt( subs ) then
  356.         return subs;
  357.     else
  358.         return RowModule(
  359.             arg[1].ring,
  360.             RowSpace( Base( subs ) * rep.base, arg[1].abelianGroup.field ) );
  361.     fi;
  362. end;
  363.  
  364.  
  365. #############################################################################
  366. ##
  367. #F  ProperSubmodule( <domain> ) . . . . . . . . . . . . . . . . . . . . . . .
  368. ##
  369. ProperSubmodule := function( D )
  370.     local   subm;
  371.  
  372.     if IsDomain( D ) and IsBound( D.operations.ProperSubmodule ) then
  373.         subm := D.operations.ProperSubmodule( D );
  374.     else
  375.         Error( "sorry, can't compute a proper submodule for <domain>" );
  376.     fi;
  377.     return subm;
  378. end;
  379.  
  380.  
  381. #############################################################################
  382. ##
  383. #F  RowModuleOps.IrreducibilityTest( <rowmodule>[, <matrix>] )  . . . . . . .
  384. #F  . . . . . . . . . . . . . . . .  test whether a row module is irreducible
  385. ##
  386. RowModuleOps.IrreducibilityTest := function( arg )
  387.     local   rep, test;
  388.  
  389.     rep := Representation( arg[1] );
  390.     if Length( arg ) = 1 then
  391.         test := IrreducibilityTest( rep.range );
  392.     elif Length( arg ) = 2 then
  393.         test := IrreducibilityTest( rep.range, arg[2] ^ rep );
  394.     else
  395.         Error( "usage: IrreducibilityTest( <rowmodule>[, <matrix>] )" );
  396.     fi;
  397.  
  398.     if IsBound( test.invariantSubspace ) then
  399.         test.submodule := RowModule(
  400.             arg[1].ring,
  401.             RowSpace( Base( test.invariantSubspace ) * rep.base,
  402.                       arg[1].abelianGroup.field ) );
  403.         Unbind( test.invariantSubspace );
  404.     fi;
  405. end;
  406.  
  407.  
  408. #############################################################################
  409. ##
  410. #F  RowModuleOps.AbsoluteIrreducibilityTest( <rowmodule>[, <matrix>] )  . . .
  411. #F  . . . . . . . . . . . . test whether a row module is absolute irreducible
  412. ##
  413. RowModuleOps.AbsoluteIrreducibilityTest := function( arg )
  414.     local   rep, test;
  415.  
  416.     rep := Representation( arg[1] );
  417.     if Length( arg ) = 1 then
  418.         test := AbsoluteIrreducibilityTest( rep.range );
  419.     elif Length( arg ) = 2 then
  420.         test := AbsoluteIrreducibilityTest( rep.range, arg[2] ^ rep );
  421.     else
  422.         Error( "usage: AbsoluteIrreducibilityTest( <rowmodule>[, <matrix>] )" );
  423.     fi;
  424.  
  425.     if IsBound( test.invariantSubspace ) then
  426.         test.submodule := RowModule(
  427.             arg[1].ring,
  428.             RowSpace( Base( test.invariantSubspace ) * rep.base,
  429.                       arg[1].abelianGroup.field ) );
  430.         Unbind( test.invariantSubspace );
  431.     fi;
  432. end;
  433.  
  434.  
  435. #############################################################################
  436. ##
  437. #F  RowModuleOps.EquivalenceTest( <rowmodule>, <rowmodule> )  . . . . . . . .
  438. #F  . . . . . . . . . . . . . . perform a test for equivalence of row modules
  439. ##
  440. RowModuleOps.EquivalenceTest := function( module1, module2 )
  441.     local   rep1, rep2;
  442.  
  443.     rep1 := Representation( module1 );
  444.     rep2 := Representation( module2 );
  445.     return EquivalenceTest( rep1.range, rep2.range );
  446. end;
  447.  
  448.  
  449. #############################################################################
  450. ##
  451. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  452. ##
  453. ##  Local Variables:
  454. ##  mode:               outline
  455. ##  outline-regexp:     "#F\\|#V\\|#E"
  456. ##  fill-column:        73
  457. ##  fill-prefix:        "##  "
  458. ##  eval:               (hide-body)
  459. ##  End:
  460. ##
  461.