This chapter describes the functions in Semigroups for dealing with matrix semigroups. This part of the manual and the functions described herein were written by Markus Pfeiffer.
A matrix semigroup for the purposes of this document is a subsemigroup of the full monoid of n × n matrices over a finite field F.
More general matrix semigroups are planned, but not implemented yet.
GAP provides a way to define matrices which are in the filter IsMatrix (Reference: IsMatrix). For technical reasons, the matrix semigroup functions in Semigroups rely on a custom wrapper for matrices IsMatrixOverFiniteField (7.2-1).
gap> x := Z(4) * [[1,0], [0,2]]; [ [ Z(2^2), 0*Z(2) ], [ 0*Z(2), 0*Z(2) ] ] gap> IsMatrix(x); true gap> IsMatrixOverFiniteField(x); false gap> y := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 2, x); <matrix over GF(2^2) of degree 2> gap> IsMatrix(y); false gap> IsMatrixOverFiniteField(y); true
In the following we will refer to matrices in IsMatrix (Reference: IsMatrix) by GAP library matrices and to matrices in IsMatrixOverFiniteField (7.2-1) by matrices over finite fields. We take precautions to hide this fact from the user of Semigroups and also provide conversion functions between the two representations.
Random matrix semigroups can be created by using the functions RandomMatrixSemigroup (2.1-6) or RandomMatrixMonoid (2.1-6). While this is convenient for testing and playing around, creating semigroups from matrices can be a bit more work. We provide a couple of convenience functions to streamline the process.
‣ IsMatrixSemigroup( S ) | ( property ) |
‣ IsMatrixMonoid( S ) | ( property ) |
Returns: true or false.
A matrix semigroup is simply a semigroup consisting of matrices over a finite field. An object in GAP is a matrix semigroup if it satisfies IsSemigroup (Reference: IsSemigroup) and IsMatrixOverFiniteFieldCollection (7.2-2).
A matrix monoid is simply a monoid consisting of matrices over a finite field. An object in GAP is a matrix monoid if it satisfies IsMonoid (Reference: IsMonoid) and IsMatrixOverFiniteFieldCollection (7.2-2).
Note that it is possible for a matrix semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy IsMatrixMonoid.
‣ MatrixSemigroup( list[, F] ) | ( function ) |
Returns: A matrix semigroup.
This is a helper function to create matrix semigroups from GAP matrices. The argument list is a homogeneous list of GAP matrices over a finite field, and the optional argument F is a finite field.
The specification of the field F can be necessary to prevent GAP from trying to find a smaller common field for the entries in list.
gap> S := MatrixSemigroup([Z(3) * [[1,0,0], [1,1,0], [0,1,0]], > Z(3) * [[0,0,0], [0,0,1], [0,1,0]]], GF(9)); <semigroup of 3x3 matrices over GF(3^2) with 2 generators> gap> S := MatrixSemigroup([Z(3) * [[1,0,0], [1,1,0], [0,1,0]], > Z(3) * [[0,0,0], [0,0,1], [0,1,0]]]); <semigroup of 3x3 matrices over GF(3) with 2 generators> gap> S := MatrixSemigroup([Z(4) * [[1,0,0], [1,1,0], [0,1,0]], > Z(4) * [[0,0,0], [0,0,1], [0,1,0]]]); <semigroup of 3x3 matrices over GF(2^2) with 2 generators>
In addition to the above, IsomorphismMatrixSemigroup (2.4-5) and AsMatrixSemigroup (2.4-1) can be used to create a matrix semigroup isomorphic to an already known semigroup.
The matrix functions in the Semigroups package use a wrapper object for matrices. In the following these objects are documented.
‣ IsMatrixOverFiniteField( obj ) | ( category ) |
Returns: true or false.
This category contains Semigroups matrix object wrapper. The introduction of this filter was necessary to get around GAP limitations with regards to matrices and associative objects.
The behaviour of this object type might be changed or removed completely from the package in the future.
gap> x := Z(4) * [[1,0], [0,2]]; [ [ Z(2^2), 0*Z(2) ], [ 0*Z(2), 0*Z(2) ] ] gap> IsMatrixOverFiniteField(x); false gap> y := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 2, x); <matrix over GF(2^2) of degree 2> gap> IsMatrixOverFiniteField(y); true
‣ IsMatrixOverFiniteFieldCollection( obj ) | ( category ) |
Returns: true or false.
Every collection of matrices in the category IsMatrixOverFiniteField (7.2-1) belongs to the category IsMatrixOverFiniteFieldCollection. For example, matrix semigroup belong to IsMatrixOverFiniteFieldCollection.
‣ NewMatrixOverFiniteField( filt, F, n, rows ) | ( operation ) |
Returns: a new matrix object.
Creates a new n-by-n matrix over the finite field F with constructing filter filt. The matrix itself is given by a list rows of rows. Currently the only possible value for filt is IsPlistMatrixOverFiniteFieldRep.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 2, > Z(4)*[[1,0],[0,1]]); <matrix over GF(2^2) of degree 2> gap> y := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 0, []); <matrix over GF(2^2) of degree 0>
‣ NewIdentityMatrixOverFiniteField( filt, F, n ) | ( operation ) |
‣ NewZeroMatrixOverFiniteField( filt, F, n ) | ( operation ) |
Creates a new n-by-n zero or identity matrix with entries in the finite field F.
gap> x := NewIdentityMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, > GF(4), 2); <matrix over GF(2^2) of degree 2> gap> y := NewZeroMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, > GF(4), 2); <matrix over GF(2^2) of degree 2>
‣ RowSpaceBasis( m ) | ( attribute ) |
‣ RowSpaceTransformation( m ) | ( attribute ) |
‣ RowSpaceTransformationInv( m ) | ( attribute ) |
To compute the value of any of the above attributes, a canonical basis for the row space of m is computed along with an invertible matrix RowSpaceTransformation such that m * RowSpaceTransformation(m) = RowSpaceBasis(m). RowSpaceTransformationInv(m) is the inverse of RowSpaceTransformation(m).
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4)^0*[[1,1,0], [0,1,1], [1,1,1]] ); <matrix over GF(2^2) of degree 3> gap> RowSpaceBasis(x); <rowbasis of rank 3 over GF(2^2)> gap> RowSpaceTransformation(x); [ [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ Z(2)^0, Z(2)^0, Z(2)^0 ], [ Z(2)^0, 0*Z(2), Z(2)^0 ] ]
‣ RowRank( m ) | ( attribute ) |
Returns: Length of a basis of the row space of m.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 3, > Z(5)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(5) of degree 3> gap> RowRank(x); 2
‣ RightInverse( m ) | ( attribute ) |
‣ LeftInverse( m ) | ( attribute ) |
Returns: A matrix over a finite field.
These attributes contain a semigroup left-inverse, and a semigroup right-inverse of the matrix m respectively.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(2^2) of degree 3> gap> LeftInverse(x); <matrix over GF(2^2) of degree 3> gap> Display(LeftInverse(x) * x); <matrix over GF(2^2) of degree 3 [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ] ]>
‣ DegreeOfMatrixOverFiniteField( m ) | ( attribute ) |
Returns: Number of rows and columns of the matrix m.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 3, > Z(5)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(5) of degree 3> gap> DegreeOfMatrixOverFiniteField(x); 3
‣ BaseDomain( m ) | ( attribute ) |
Returns: The domain in which entries of m lie.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 3, > Z(5)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(5) of degree 3> gap> BaseDomain(x); GF(5)
‣ TransposedMatImmutable( m ) | ( attribute ) |
Returns: An immutable matrix.
This attribute contains an immutable copy of m. Note that matrices are immutable per default.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 3, > Z(5)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(5) of degree 3> gap> TransposedMatImmutable(x); <matrix over GF(5) of degree 3>
‣ AsMatrix( m ) | ( operation ) |
Returns: A matrix.
Turns a matrix over a finite field into a GAP matrix.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 3, > Z(5)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(5) of degree 3> gap> AsMatrix(x); [ [ Z(5)^0, Z(5)^0, 0*Z(5) ], [ 0*Z(5), 0*Z(5), 0*Z(5) ], [ Z(5)^0, Z(5)^0, Z(5)^0 ] ]
‣ ConstructingFilter( m ) | ( operation ) |
Returns: A filter
Return the filter that was passed to NewMatrixOverFiniteField (7.2-3) when creating the matrix m. This is used to create new objects that lie in the same filter.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4)^0*[[1,1,0], [0,0,0], [1,1,1]] ); <matrix over GF(2^2) of degree 3> gap> ConstructingFilter(x); <Representation "IsPlistMatrixOverFiniteFieldRep">
For interfacing the semigroups code with GAPs library code for matrix groups, the Semigroups package implements matrix groups that delegate to the GAP library.
‣ IsMatrixOverFiniteFieldGroup( G ) | ( property ) |
Returns: true or false.
A matrix group is simply a group of invertible matrices over a finite field. An object in Semigroups is a matrix group if it satisfies IsGroup (Reference: IsGroup) and IsMatrixOverFiniteFieldCollection (7.2-2).
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]); <matrix over GF(2^2) of degree 3> gap> G := Group(x); <group of 3x3 matrices over GF(2^2) with 1 generator> gap> IsMatrixOverFiniteFieldGroup(G); true gap> G := Group(Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]); Group([ <an immutable 3x3 matrix over GF2> ]) gap> IsGroup(G); true gap> IsMatrixOverFiniteFieldGroup(G); false
‣ \^( G, mat ) | ( operation ) |
Returns: A matrix group over a finite field.
The arguments of this operation, G and mat, must be categories IsMatrixOverFiniteFieldGroup (7.3-1) and IsMatrixOverFiniteField (7.2-1). If G consists of d by d matrices over GF(q) and mat is a d by d matrix over GF(q), then G ^ mat returns the conjugate of G by mat inside GL(d, q).
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]] );; gap> y := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4) ^ 0 * [[1, 0, 0], [1, 0, 1], [1, 1, 1]] );; gap> G := Group(x); <group of 3x3 matrices over GF(2^2) with 1 generator> gap> G ^ y; <group of 3x3 matrices over GF(2^2) with 1 generator>
‣ IsomorphismMatrixGroup( G ) | ( attribute ) |
Returns: An isomorphism.
If G belongs to the category IsMatrixOverFiniteFieldGroup (7.3-1), then IsomorphismMatrixGroup returns an isomorphism from G into a group consisting of GAP library matrices.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]] );; gap> G := Group(x);; gap> iso := IsomorphismMatrixGroup(G);; gap> Source(iso); Range(iso); <group of 3x3 matrices over GF(2^2) with 1 generator> Group( [ [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ])
‣ AsMatrixGroup( G ) | ( attribute ) |
Returns: A group of GAP library matrices over a finite field.
Returns the image of the isomorphism returned by 7.3-3.
gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(4), 3, > Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]] );; gap> G := Group(x); <group of 3x3 matrices over GF(2^2) with 1 generator> gap> AsMatrixGroup(G); Group( [ [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ])
generated by GAPDoc2HTML