41 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 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).

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";; 

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.

Subsections

  1. More about Modules
  2. Row Modules
  3. Free Modules
  4. Module
  5. Submodule
  6. AsModule
  7. AsSubmodule
  8. AsSpace for Modules
  9. IsModule
  10. IsFreeModule
  11. Operations for Row Modules
  12. Functions for Row Modules
  13. StandardBasis for Row Modules
  14. IsEquivalent for Row Modules
  15. IsIrreducible for Row Modules
  16. FixedSubmodule
  17. Module Homomorphisms
  18. Row Module Records
  19. Module Homomorphism Records

41.1 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.

41.2 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 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.

41.3 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.

A ^ n

returns a free module of dimension n for the algebra A.

    gap> a:= FreeAlgebra( Rationals, 2 );; a.name:= "a";;
    gap> a^2;
    Module( a, [ [ a.one, a.zero ], [ a.zero, a.one ] ] ) 

41.4 Module

Module( R, gens )
Module( R, gens, zero )
Module( R, gens, "basis" )

returns the module for the ring R that is generated by the elements in the list gens. If gens is empty then the zero element zero of the module must be entered.

If the third argument is the string "basis" then the generators gens 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 

41.5 Submodule

Submodule( M, gens )

returns the submodule of the parent of the module M that is generated by the elements in the list gens. If M is a factor module, gens 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 

41.6 AsModule

AsModule( M )

returns a module that is isomorphic to the module or submodule M.

    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 

41.7 AsSubmodule

AsSubmodule( M, U )

returns a submodule of the parent of M that is isomorphic to the module U which can be a parent module or a submodule with a different parent.

Note that the same ring must act on M and U.

    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 

41.8 AsSpace for Modules

AsSpace( M )

returns a (quotient of a) row space that is equal to the (quotient of a) row module M.

    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 ] ] 

41.9 IsModule

IsModule( obj )

returns true if obj, which may be an object of arbitrary type, is a module, and false otherwise.

    gap> IsModule( nat );
    true
    gap> IsModule( AsSpace( nat ) );
    false 

41.10 IsFreeModule

IsFreeModule( obj )

returns true if obj, which may be an object of arbitrary type, is a free module, and false otherwise.

    gap> IsFreeModule( nat );
    false
    gap> IsFreeModule( a^2 );
    true 

41.11 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

M1 = M2
M1 < M2

Equality and ordering of (quotients of) row modules are defined as equality 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

M1 + M2 :

returns the sum of the two modules M1 and M2, that is, the smallest module containing both M1 and M2. Note that the same ring must act on M1 and M2.

M1 / M2 :

returns the factor module of the module M1 by its submodule M2. Note that the same ring must act on M1 and M2.
    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 

Operations for Row Spaces.

41.12 Functions for Row Modules

As stated in Row Modules, row modules behave like row spaces with respect 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).

41.13 StandardBasis for Row Modules

StandardBasis( M )
StandardBasis( M, seedvectors )

returns the standard basis of the row module M with respect to the seed vectors in the list seedvectors. If no second argument is given the generators of M are taken.

The standard basis is defined as follows. Take the first seed vector v, apply the generators of the ring R acting on M 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 ] ] ) 

41.14 IsEquivalent for Row Modules

IsEquivalent( M1, M2 )

Let M1 and M2 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 M1, M2 be irreducible. Then IsEquivalent( M1, M2 ) returns true if the actions on M1 and M2 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 

41.15 IsIrreducible for Row Modules

IsIrreducible( M )

returns true if the (quotient of a) row module M is irreducible, and false otherwise.

    gap> IsIrreducible( nat );
    false
    gap> IsIrreducible( nat / FixedSubmodule( nat ) );
    true 

41.16 FixedSubmodule

FixedSubmodule( M )

returns the submodule of fixed points in the module M under the action of the generators of M.ring.

    gap> fix:= FixedSubmodule( nat );
    Submodule( nat, [ [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] )
    gap> Dimension( fix );
    1 

41.17 Module Homomorphisms

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 ] ] 

41.18 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 R.field where R 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),

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.

41.19 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.

Previous Up Next
Index

GAP 3.4.4
April 1997