In this section, we describe functions developed by Celler and Leedham-Green (see [4] for details) to recognise constructively classical groups in their natural representation over finite fields.
ConstructivelyRecogniseClassical( G, "linear" )
computes both a standard generating set for a matrix group G which
contains the special linear group and expressions for the new
generators in terms of G.generators
. This generating set will allow
you to write an element of G as a word in the given generating set of
G.
The algorithm is of polynomial complexity in the dimension and field size. However, it is a Las Vegas algorithm, i.e. there is a chance that the algorithm fails to complete in the expected time. It will run indefinitely if G does not contain the special linear group.
The following functions can be applied to the record sl
returned.
SizeFlag( sl )
returns the size of G.
Rewrite( sl, elm )
returns an expression such that Value( Rewrite( sl, elm ),
G.generators )
is equal to the element elm.
Example
gap> m1 := [ [ 0*Z(17), Z(17), Z(17)^10, Z(17)^12, Z(17)^2 ], [ Z(17)^13, Z(17)^10, Z(17)^15, Z(17)^8, Z(17)^0 ], [ Z(17)^10, Z(17)^6, Z(17)^9, Z(17)^8, Z(17)^10 ], [ Z(17)^13, Z(17)^5, Z(17)^0, Z(17)^12, Z(17)^5 ], [ Z(17)^14, Z(17)^13, Z(17)^5, Z(17)^10, Z(17)^0 ] ];; gap> m2 := [ [ 0*Z(17), Z(17)^10, Z(17)^2, 0*Z(17), Z(17)^10 ], [ 0*Z(17), Z(17)^6, Z(17)^0, Z(17)^4, Z(17)^15 ], [ Z(17)^7, Z(17)^6, Z(17)^10, Z(17), Z(17)^2 ], [ Z(17)^3, Z(17)^10, Z(17)^5, Z(17)^4, Z(17)^6 ], [ Z(17)^0, Z(17)^8, Z(17)^0, Z(17)^5, Z(17) ] ];; gap> G := Group( m1, m2 );; gap> sl := ConstructivelyRecogniseClassical( G, "linear" );; gap> SizeFlag(sl); 338200968038818404584356577280 gap> w := Rewrite( sl, m1^m2 );; gap> Value( w, [m1,m2] ) = m1^m2; true
The algorithm is described in [4].
GAP 3.4.4