%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A module.tex GAP documentation Thomas Breuer %% %A @(#)$Id: module.tex,v 3.2 1994/06/10 02:44:39 vfelsch Rel $ %% %Y Copyright 1994-1995, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file contains the description of the module record and polymorphic %% functions for modules. %% %H $Log: module.tex,v $ %H Revision 3.2 1994/06/10 02:44:39 vfelsch %H updated examples %H %H Revision 3.1 1994/05/31 10:53:11 vfelsch %H fixed overfull box %H %H Revision 3.0 1994/05/19 13:56:34 sam %H Initial Revision under RCS %H %% \def\MeatAxe{\sf MeatAxe} \Chapter{Modules} This chapter describes the data structures and functions for modules in {\GAP}. After the introduction of the data structures (see "More about Modules", "Row Modules", "Free Modules") the functions for constructing modules and submodules (see "Module", "Submodule", "AsModule", "AsSubmodule", "AsSpace for Modules") and testing for modules (see "IsModule", "IsFreeModule") are described. The next sections describe operations and functions for modules (see "Operations for Row Modules", "Functions for Row Modules", "StandardBasis for Row Modules", "IsEquivalent for Row Modules", "FixedSubmodule"). The next section describes available module homomorphisms. At the moment only operation homomorphisms are supported (see "Module Homomorphisms"). The last sections describe the implementation of the data structures (see "Row Module Records", "Module Homomorphism Records"). \vspace{5mm} Many examples in this chapter use the natural permutation module for the symmetric group $S_3$. If you want to run the examples you must first define this module, as is done using the following commands. | gap> mat1:= PermutationMat( (1,2,3), 3, GF(2) );; gap> mat2:= PermutationMat( (1,2), 3, GF(2) );; gap> a:= UnitalAlgebra( GF(2), [ mat1, mat2 ] );; a.name:= "a";; gap> nat:= NaturalModule( a );; gap> nat.name:= "nat";; | \vspace{5mm} There is no possibility to compute the lattice of submodules with the implementations in {\GAP}. However, it is possible to use the {\MeatAxe} share library (see chapter "The MeatAxe") to compute the lattice, and then (perhaps) to carry back interesting parts to {\GAP} format using "GapObject" 'GapObject'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{More about Modules} Let $R$ be a ring. An $R$-*module* (or, more exactly, an $R$-right module) is an additive abelian group on that $R$ acts from the right. A module is of interest mainly as operation domain of an algebra (see chapter "Algebras"). Thus it is the natural place to store information about the operation of the algebra, for example whether it is irreducible. But since a module is a domain it has also properties of its own, independent of the algebra. According to the different types of algebras in {\GAP}, namely matrix algebras and finitely presented algebras, at the moment two types of modules are supported in {\GAP}, namely *row modules* and their quotients for matrix algebras and *free modules* and their submodules and quotients for finitely presented algebras. See "Row Modules" and "Free Modules" for more information. For modules, the same concept of parent and substructures holds as for row spaces. That is, a module is stored either as a submodule of a module, or it is not (see "Submodule", "AsSubmodule" for the details). Also the concept of factor structures and cosets is the same as that for row spaces (see "Quotient Spaces", "Row Space Cosets"), especially the questions about a factor module is mainly delegated to the numerator and the denominator, see also "Operations for Row Modules". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Row Modules} A *row module* for a matrix algebra $A$ is a row space over a field $F$ on that $A$ acts from the right via matrix multiplication. All operations, set theoretic functions and vector space functions for row spaces are applicable to row modules, and the conventions for row spaces also hold for row modules (see chapter "Row Spaces"). For the notion of a standard basis of a module, see "StandardBasis for Row Modules". It should be mentioned, however, that the functions and their results have to be interpreted in the module context. For example, 'Generators' returns a list of module generators not vector space generators (see "AsSpace for Modules"), and 'Closure' or 'Sum' for modules return a module (namely the smallest module generated by the arguments). *Quotient modules* $Q = V / W$ of row modules are quotients of row spaces $V$, $W$ that are both (row) modules for the same matrix algebra $A$. All operations and functions for quotient spaces are applicable. The element of such quotient modules are *module cosets*, in addition to the operations and functions for row space cosets they can be multiplied by elements of the acting algebra. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Free Modules} A *free module* of dimension $n$ for an algebra $A$ consists of all $n$-tuples of elements of $A$, the action of $A$ is defined as component-wise multiplication from the right. Submodules and quotient modules are defined in the obvious way. In {\GAP}, elements of free modules are stored as lists of algebra elements. Thus there is no difference to row modules with respect to addition of elements, and operation of the algebra. However, the applicable functions are different. At the moment, only free modules for finitely presented algebras are supported in {\GAP}, and only very few functions are available for free modules at the moment. Especially the set theoretic and vector space functions do not work for free modules and their submodules and quotients. Free modules were only introduced as operation domains of finitely presented algebras. \vspace{5mm} ' \^\ ' returns a free module of dimension for the algebra . | gap> a:= FreeAlgebra( Rationals, 2 );; a.name:= "a";; gap> a^2; Module( a, [ [ a.one, a.zero ], [ a.zero, a.one ] ] ) | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Module} 'Module( , )' \\ 'Module( , , )' \\ 'Module( , , \"basis\" )' returns the module for the ring that is generated by the elements in the list . If is empty then the zero element of the module must be entered. If the third argument is the string '\"basis\"' then the generators are assumed to form a vector space basis. | gap> a:= UnitalAlgebra( GF(2), GL(2,2).generators );; gap> a.name:="a";; gap> m1:= Module( a, [ a.1[1] ] ); Module( a, [ [ Z(2)^0, Z(2)^0 ] ] ) gap> Dimension( m1 ); 2 gap> Basis( m1 ); SemiEchelonBasis( Module( a, [ [ Z(2)^0, Z(2)^0 ] ] ), [ [ Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0 ] ] ) gap> m2:= Module( a, a.2, "basis" );; gap> Basis( m2 ); Basis( Module( a, [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ] ), [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ] ) gap> a.2; [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ] gap> m1 = m2; true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Submodule} 'Submodule( , )' returns the submodule of the parent of the module that is generated by the elements in the list . If is a factor module, may also consist of representatives instead of the cosets themselves. | gap> a:= UnitalAlgebra( GF(2), [ mat1, mat2 ] );; a.name:= "a";; gap> nat:= NaturalModule( a );; gap> nat.name:= "nat";; gap> s:= Submodule( nat, [ [ 1, 1, 1 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> Dimension( s ); 1 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AsModule} 'AsModule( )' returns a module that is isomorphic to the module or submodule . | gap> s:= Submodule( nat, [ [ 1, 1, 1 ] * Z(2) ] );; gap> s2:= AsModule( s ); Module( a, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> s = s2; true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AsSubmodule} 'AsSubmodule( , )' returns a submodule of the parent of that is isomorphic to the module which can be a parent module or a submodule with a different parent. Note that the same ring must act on and . | gap> s2:= Module( a, [ [ 1, 1, 1 ] * Z(2) ] );; gap> s:= AsSubmodule( nat, s2 ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> s = s2; true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AsSpace for Modules} 'AsSpace( )' returns a (quotient of a) row space that is equal to the (quotient of a) row module . | gap> s:= Submodule( nat, [ [ 1, 1, 0 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ) gap> Dimension( s ); 2 gap> AsSpace( s ); RowSpace( GF(2), [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] ) gap> q:= nat / s; nat / [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] gap> AsSpace( q ); RowSpace( GF(2), [ [ Z(2)^0, 0*Z(2), 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ] ] ) / [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsModule} 'IsModule( )' returns 'true' if , which may be an object of arbitrary type, is a module, and 'false' otherwise. | gap> IsModule( nat ); true gap> IsModule( AsSpace( nat ) ); false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsFreeModule} 'IsFreeModule( )' returns 'true' if , which may be an object of arbitrary type, is a free module, and 'false' otherwise. | gap> IsFreeModule( nat ); false gap> IsFreeModule( a^2 ); true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Row Modules} Here we mention only those facts about operations that have to be told in addition to those for row spaces (see "Operations for Row Spaces"). *Comparisons of Modules* ' = ' \\ ' \<\ ' Equality and ordering of (quotients of) row modules are defined as equality resp. ordering of the modules as vector spaces (see "Operations for Row Spaces"). This means that equal modules may be inequivalent as modules, and even the acting rings may be different. For testing equivalence of modules, see "IsEquivalent for Row Modules". | gap> s:= Submodule( nat, [ [ 1, 1, 1 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> s2:= Submodule( nat, [ [ 1, 1, 0 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ) gap> s = s2; false gap> s < s2; true | *Arithmetic Operations of Modules* ' + ' : \\ returns the sum of the two modules and , that is, the smallest module containing both and . Note that the same ring must act on and . ' / ' : \\ returns the factor module of the module by its submodule . Note that the same ring must act on and . | gap> s1:= Submodule( nat, [ [ 1, 1, 1 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> q:= nat / s1; nat / [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] gap> s2:= Submodule( nat, [ [ 1, 1, 0 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ) gap> s3:= s1 + s2; Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ], [ 0*Z(2), 0*Z(2), Z(2)^0 ] ] ) gap> s3 = nat; true | For forming the sum and quotient of row spaces, see "Operations for Row Spaces". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Functions for Row Modules} As stated in "Row Modules", row modules behave like row spaces with respect to *set theoretic* and *vector space* functions (see "Functions for Row Spaces"). The functions in the following sections use the module structure (see "StandardBasis for Row Modules", "IsEquivalent for Row Modules", "IsIrreducible for Row Modules", "FixedSubmodule", "Module Homomorphisms"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{StandardBasis for Row Modules} 'StandardBasis( )' \\ 'StandardBasis( , )' returns the standard basis of the row module with respect to the seed vectors in the list . If no second argument is given the generators of are taken. The *standard basis* is defined as follows. Take the first seed vector $v$, apply the generators of the ring $R$ acting on in turn, and if the image is linearly independent of the basis vectors found up to this time, it is added to the basis. When the space becomes stable under the action of $R$, proceed with the next seed vector, and so on. Note that you do not get a basis of the whole module if all seed vectors lie in a proper submodule. | gap> s:= Submodule( nat, [ [ 1, 1, 0 ] * Z(2) ] ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ) gap> b:= StandardBasis( s ); StandardBasis( Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ) ) gap> b.vectors; [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] gap> StandardBasis( s, [ [ 0, 1, 1 ] * Z(2) ] ); StandardBasis( Submodule( nat, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ] ] ), [ [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ Z(2)^0, 0*Z(2), Z(2)^0 ] ] ) | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsEquivalent for Row Modules} 'IsEquivalent( , )' Let and be modules acted on by rings $R_1$ and $R_2$, respectively, such that mapping the generators of $R_1$ to the generators of $R_2$ defines a ring homomorphism. Furthermore let at least one of , be irreducible. Then 'IsEquivalent( , )' returns 'true' if the actions on and are equivalent, and 'false' otherwise. | gap> rand:= RandomInvertableMat( 3, GF(2) );; gap> b:= UnitalAlgebra( GF(2), List( a.generators, x -> x^rand ) );; gap> m:= NaturalModule( b );; gap> IsEquivalent( nat / FixedSubmodule( nat ), > m / FixedSubmodule( m ) ); true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsIrreducible for Row Modules} 'IsIrreducible( )' returns 'true' if the (quotient of a) row module is irreducible, and 'false' otherwise. | gap> IsIrreducible( nat ); false gap> IsIrreducible( nat / FixedSubmodule( nat ) ); true | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{FixedSubmodule} 'FixedSubmodule( )' returns the submodule of fixed points in the module under the action of the generators of '.ring'. | gap> fix:= FixedSubmodule( nat ); Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ) gap> Dimension( fix ); 1 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Module Homomorphisms}% \index{OperationHomomorphism for Modules}% \index{OperationModule}% Let $M_1$ and $M_2$ be modules acted on by the rings $R_1$ and $R_2$ (via exponentiation), and $\varphi$ a ring homomorphism from $R_1$ to $R_2$. Any linear map $\psi = \psi_{\varphi}$ from $M_1$ to $M_2$ with the property that $(m^r)^{\psi} = (m^{\psi})^(r^{\varphi})$ is called a *module homomorphism*. At the moment only the following type of module homomorphism is available in {\GAP}. Suppose you have the module $M_1$ for the algebra $R_1$. Then you can construct the operation algebra $R_2'\:= Operation'( R_1, M_1 )$, and the module for $R_2$ isomorphic to $M_1$ as $M_2'\:= OperationModule'( R_2 )$. Then $'OperationHomomorphism'( M_1, M_2 )$ can be used to construct the module homomorphism from $M_1$ to $M_2$. | gap> s:= Submodule( nat, [ [ 1, 1, 0 ] *Z(2) ] );; s.name:= "s";; gap> op:= Operation( a, s ); op.name:="op";; UnitalAlgebra( GF(2), [ [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2)^0 ] ], [ [ Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0 ] ] ] ) gap> opmod:= OperationModule( op ); opmod.name:= "opmod";; Module( op, [ [ Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0 ] ] ) gap> modhom:= OperationHomomorphism( s, opmod ); OperationHomomorphism( s, opmod ) gap> b:= Basis( s ); SemiEchelonBasis( s, [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] ) | Images and preimages of elements under module homomorphisms are computed using 'Image' and 'PreImagesRepresentative', respectively. If $M_1$ is a row module this is done by using the knowledge of images of a basis, if $M_1$ is a (quotient of a) free module then the algebra homomorphism and images of the generators of $M_1$ are used. The computation of preimages requires in both cases the knowledge of representatives of preimages of a basis of $M_2$. | gap> im:= List( b.vectors, x -> Image( modhom, x ) ); [ [ Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0 ] ] gap> List( im, x -> PreImagesRepresentative( modhom, x ) ); [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ] ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Row Module Records} Module records contain at least the components 'isDomain' : \\ always 'true', 'isModule' : \\ always 'true', 'isVectorSpace' : \\ always 'true', since modules are vector spaces, 'ring' : \\ the ring acting on the module, 'field' : \\ the coefficients field, is the same as '.field' where is the 'ring' component of the module, 'operations' : \\ the operations record of the module. The following components are optional, but if they are not present then the corresponding function in the 'operations' record must know how to compute them. 'generators' : \\ a list of *module* generators (not necessarily of vector space generators), 'zero' : \\ the zero element of the module. 'basis' : \\ a vector space basis of the module (see also "Row Space Bases"), \vspace{5mm} *Factors of row modules* have the same components as quotients of row spaces (see "Quotient Space Records"), except that of course they have an appropriate 'operations' record. Additionally factors of row modules have the components 'isModule', 'isFactorModule' (both always 'true'). Parent modules also have the 'ring' component, which is the same ring as the ring component of numerator and denominator. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Module Homomorphism Records} Module homomorphism records have at least the following components. 'isGeneralMapping' : \\ 'true', 'isMapping' : \\ 'true', 'isHomomorphism': \\ 'true', 'domain' : \\ 'Mappings', 'source' : \\ the source of the homomorphism, a module $M_1$, 'range' : \\ the range of the homomorphism, a module $M_2$, 'preImage' : \\ the module $M_1$, 'basisImage' : \\ a vector space basis of the image of $M_1$, 'preimagesBasis' : \\ a list of preimages of the basis vectors in 'basisImage' 'operations' : \\ the operations record of the homomorphism. If the source is a (factor of a) free module then there are also the components 'genimages' : \\ a list of images of the generators of the source, 'alghom' : \\ the underlying algebra homomorphism from the ring acting on $M_1$ to the ring acting on $M_2$. If the source is a (factor of a) row module then there are also the components 'basisSource' : \\ a vector space basis of $M_1$, 'imagesBasis' : \\ a list of images of the basis vectors in 'basisSource'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "%F\\|%V\\|%E" %% fill-column: 73 %% fill-prefix: "%% " %% eval: (hide-body) %% End: %%