72.3 Examples of Vector Enumeration

We consider those of the examples given in chapter 8 of the VE manual that can be used in GAP.

8.1 The natural permutation representation of S_3

The symmetric group S_3 is also the dihedral group D_6, and so is presented by two involutions with product of order 3. Taking the permutation action on the cosets of the cyclic group generated by one of the involutions we obtain the following presentation.

```    gap> a:= FreeAlgebra( Rationals, 2 );;
gap> a:= a / [ a.1^2 - a.one, a.2^2 - a.one,
>              (a.1*a.2)^3 - a.one ];
UnitalAlgebra( Rationals, [ a.1, a.2 ] )
gap> a.name:= "a";; ```
We choose as module `q` the quotient of the regular module for `a` by the submodule generated by `a.1 - 1`, and compute the action of `a` on `q`.

```    gap> m:= a^1;;
gap> q:= m / [ [ a.1 - a.one ] ];
Module( a, [ [ a.one ] ] ) / [ [ -1*a.one+a.1 ] ]
gap> op:= Operation( a, q );
UnitalAlgebra( Rationals,
[ [ [ 1, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ] ],
[ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ] ] )
gap> op.name:= "op";; ```

8.2 A Quotient of a Permutation Representation

The permutation representation constructed in example 8.1 fixes the all-ones vector (as do all permutation representations). This is the image of the module element `[ a.one + a.2 + a.2*a.1 ]` in the corresponding module for the algebra `op`.

```    gap> ophom:= OperationHomomorphism( a, op );;
gap> opmod:= OperationModule( op );
Module( op, [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ] )
gap> modhom:= OperationHomomorphism( q, opmod );;
gap> pre:= PreImagesRepresentative( modhom, [ 1, 1, 1 ] );;
gap> pre:= pre.representative;
[ a.one+a.2+a.2*a.1 ] ```

We could have computed such a preimage also by computing a matrix that maps the image of the submodule generator of `q` to the all-ones vector, and applying a preimage to the submodule generator. Of course the we do not necessarily get the same representatives.

```    gap> images:= List( Generators( q ), x -> Image( modhom, x ) );
[ [ 1, 0, 0 ] ]
gap> rep:= RepresentativeOperation( op, images[1], [ 1, 1, 1 ] );
[ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]
gap> PreImagesRepresentative( ophom, rep );
a.one+a.1*a.2+a.2*a.1 ```
Now we factor out the fixed submodule by enlarging the denominator of the module `q`. (Note that we could also compute the action of the matrix algebra if we were only interested in the 2-dimensional representation.)

Accordingly we can write down the following presentation for the quotient module.

```    gap> q:= m / [ [ a.1 - a.one ], pre ];;
gap> op:= Operation( a, q );
UnitalAlgebra( Rationals,
[ [ [ 1, 0 ], [ -1, -1 ] ], [ [ 0, 1 ], [ 1, 0 ] ] ] ) ```

8.3 A Non-cyclic Module

If we take the direct product of two copies of the permutation representation constructed in example 8.1, we can identify the fixed vectors in the two copies in the following presentation.

```    gap> m:= a^2;;
gap> q:= m / [ [ a.zero, a.1 - a.one ], [ a.1 - a.one, a.zero ],
>              [ a.one+a.2+a.2*a.1, -a.one-a.2-a.2*a.1 ] ];
Module( a, [ [ a.one, a.zero ], [ a.zero, a.one ] ] ) /
[ [ a.zero, -1*a.one+a.1 ], [ -1*a.one+a.1, a.zero ],
[ a.one+a.2+a.2*a.1, -1*a.one+-1*a.2+-1*a.2*a.1 ] ] ```
We compute the matrix representation.

```    gap> op:= Operation( a, q );
UnitalAlgebra( Rationals,
[ [ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ],
[ 0, 0, 1, 0, 0 ], [ 1, -1, 1, 1, -1 ] ],
[ [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0 ], [ 0, 1, 0, 0, 0 ] ] ] ) ```
In this case it is interesting to look at the images of the module generators and pre-images of the basis vectors. Note that these preimages are elements of a factor module, corresponding elements of the free module are again found as representatives.

```    gap> ophom:= OperationHomomorphism( a, op );;
gap> opmod:= OperationModule( op );;
gap> opmod.name:= "opmod";;
gap> modhom:= OperationHomomorphism( q, opmod );;
gap> List( Generators( q ), x -> Image( modhom, x ) );
[ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ] ]
gap> basis:= Basis( opmod );
CanonicalBasis( opmod )
gap> preim:= List( basis.vectors, x ->
>               PreImagesRepresentative( modhom, x ) );;
gap> preim:= List( preim, Representative );
[ [ a.one, a.zero ], [ a.zero, a.one ], [ a.2, a.zero ],
[ a.2*a.1, a.zero ], [ a.zero, a.2 ] ] ```

8.4 A Monoid Representation

The Coxeter monoid of type B_2 has a transformation representation on four points. This can be constructed as a matrix representation over GF(3), from the following presentation.

```    gap> a:= FreeAlgebra( GF(3), 2 );;
gap> a:= a / [ a.1^2 - a.1, a.2^2 - a.2,
> (a.1*a.2)^2 - (a.2*a.1)^2 ];;
gap> q:= a^1 / [ [ a.1 - a.one ] ];;
gap> op:= Operation( a, q );
UnitalAlgebra( GF(3),
[ [ [ Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0,
0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ],
[ [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
[ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ],
[ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ] ] ) ```

8.7 A Quotient of a Polynomial Ring

The quotient of a polynomial ring by the ideal generated by some polynomials will be finite-dimensional just when the polynomials have finitely many common roots in the algebraic closure of the ground ring. For example, three polynomials in three variables give us the following presentation for the quotient of their ideal.

Define `a` to be the polynomial algebra on three variables.

```    gap> a:= FreeAlgebra( Rationals, 3 );;
gap> a:= a / [ a.1 * a.2 - a.2 * a.1,
>              a.1 * a.3 - a.3 * a.1,
>              a.2 * a.3 - a.3 * a.2 ];; ```
Define the quotient module by the polynomials `A+B+C`, `AB+BC+CA`, `ABC-1`.

```    gap> q:= a^1 / [ [ a.1+a.2+a.3 ],
>                [ a.1*a.2+a.2*a.3+a.3*a.1 ],
>                [ a.1*a.2*a.3-a.one ]        ];; ```
Compute the representation.

```    gap> op:= Operation( a, q );
UnitalAlgebra( Rationals,
[ [ [ 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0 ],
[ -1, 0, 0, 0, 0, -1 ], [ 0, 0, 1, 0, 0, 0 ],
[ 1, 0, 0, 0, 0, 0 ], [ 0, -1, 0, -1, 0, 0 ] ],
[ [ 0, 0, 0, 1, 0, 0 ], [ 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1 ],
[ 0, 0, -1, 0, -1, 0 ], [ -1, 0, 0, 0, 0, -1 ],
[ 0, 1, 0, 0, 0, 0 ] ],
[ [ 0, -1, 0, -1, 0, 0 ], [ 0, 0, -1, 0, -1, 0 ],
[ 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 1, 0, 0 ] ] ] ) ```
Previous Up Top Next
Index

GAP 3.4.4
April 1997