Matrix Groups

AUTHORS:

  • William Stein: initial version
  • David Joyner (2006-03-15): degree, base_ring, _contains_, list, random, order methods; examples
  • William Stein (2006-12): rewrite
  • David Joyner (2007-12): Added invariant_generators (with Martin Albrecht and Simon King)
  • David Joyner (2008-08): Added module_composition_factors (interface to GAP’s MeatAxe implementation) and as_permutation_group (returns isomorphic PermutationGroup).
  • Simon King (2010-05): Improve invariant_generators by using GAP for the construction of the Reynolds operator in Singular.

This class is designed for computing with matrix groups defined by a (relatively small) finite set of generating matrices.

EXAMPLES:

sage: F = GF(3)
sage: gens = [matrix(F,2, [1,0, -1,1]), matrix(F, 2, [1,1,0,1])]
sage: G = MatrixGroup(gens)
sage: G.conjugacy_class_representatives()
[
[1 0]
[0 1],
[0 1]
[2 1],
[0 1]
[2 2],
[0 2]
[1 1],
[0 2]
[1 2],
[0 1]
[2 0],
[2 0]
[0 2]
]    

Loading, saving, ... works:

sage: G = GL(2,5); G
General Linear Group of degree 2 over Finite Field of size 5
sage: TestSuite(G).run()

sage: g = G.1; g
[4 1]
[4 0]
sage: TestSuite(g).run()

We test that #9437 is fixed:

sage: len(list(SL(2, Zmod(4))))
48
sage.groups.matrix_gps.matrix_group.MatrixGroup(gens)

Return the matrix group with given generators.

INPUT:

  • gens - list of matrices in a matrix space or matrix group

EXAMPLES:

sage: F = GF(5)
sage: gens = [matrix(F,2,[1,2, -1, 1]), matrix(F,2, [1,1, 0,1])]
sage: G = MatrixGroup(gens); G
Matrix group over Finite Field of size 5 with 2 generators: 
[[[1, 2], [4, 1]], [[1, 1], [0, 1]]]

In the second example, the generators are a matrix over \ZZ, a matrix over a finite field, and the integer 2. Sage determines that they both canonically map to matrices over the finite field, so creates that matrix group there.

sage: gens = [matrix(2,[1,2, -1, 1]), matrix(GF(7), 2, [1,1, 0,1]), 2]
sage: G = MatrixGroup(gens); G
Matrix group over Finite Field of size 7 with 3 generators: 
[[[1, 2], [6, 1]], [[1, 1], [0, 1]], [[2, 0], [0, 2]]]

Each generator must be invertible:

sage: G = MatrixGroup([matrix(ZZ,2,[1,2,3,4])])
Traceback (most recent call last):
...
ValueError: each generator must be an invertible matrix but one is not:
[1 2]
[3 4]

Some groups aren’t supported:

sage: SL(2, CC).gens()
Traceback (most recent call last):
...
NotImplementedError: Matrix group over Complex Field with 53 bits of precision not implemented.
sage: G = SL(0, QQ)
Traceback (most recent call last):
...
ValueError: The degree must be at least 1
class sage.groups.matrix_gps.matrix_group.MatrixGroup_gap(n, R, var='a', category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_generic

INPUT:

  • n - the degree
  • R - the base ring
  • var - variable used to define field of definition of actual matrices in this group.
Element

alias of MatrixGroupElement

as_matrix_group()

Return this group, but as a general matrix group, i.e., throw away the extra structure of general unitary group.

EXAMPLES:

sage: G = SU(4,GF(5))
sage: G.as_matrix_group()
Matrix group over Finite Field in a of size 5^2 with 2 generators:
[[[a, 0, 0, 0], 
  [0, 2*a + 3, 0, 0], 
  [0, 0, 4*a + 1, 0], 
  [0, 0, 0, 3*a]], 
 [[1, 0, 4*a + 3, 0], 
  [1, 0, 0, 0], 
  [0, 2*a + 4, 0, 1], 
  [0, 3*a + 1, 0, 0]]]
sage: G = GO(3,GF(5))
sage: G.as_matrix_group()
Matrix group over Finite Field of size 5 with 2 generators:
[[[2, 0, 0], [0, 3, 0], [0, 0, 1]], [[0, 1, 0], [1, 4, 4], [0, 2, 1]]]
base_field()

Return the base ring of this matrix group.

EXAMPLES:

sage: GL(2,GF(3)).base_ring()
Finite Field of size 3
sage: G = SU(3,GF(5))
sage: G.base_ring()
Finite Field of size 5
sage: G.field_of_definition()
Finite Field in a of size 5^2
base_ring()

Return the base ring of this matrix group.

EXAMPLES:

sage: GL(2,GF(3)).base_ring()
Finite Field of size 3
sage: G = SU(3,GF(5))
sage: G.base_ring()
Finite Field of size 5
sage: G.field_of_definition()
Finite Field in a of size 5^2
cardinality()

Implements EnumeratedSets.ParentMethods.cardinality().

EXAMPLES:

sage: G = Sp(4,GF(3))
sage: G.cardinality()
51840
sage: G = SL(4,GF(3))
sage: G.cardinality()
12130560
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
sage: G = MatrixGroup(gens)
sage: G.cardinality()
480
sage: G = MatrixGroup([matrix(ZZ,2,[1,1,0,1])])
sage: G.cardinality()
+Infinity
degree()

Return the degree of this matrix group.

EXAMPLES:

sage: SU(5,5).degree()
5
field_of_definition(var='a')

Return a field that contains all the matrices in this matrix group.

EXAMPLES:

sage: G = SU(3,GF(5))
sage: G.base_ring()
Finite Field of size 5
sage: G.field_of_definition()
Finite Field in a of size 5^2
sage: G = GO(4,GF(7),1)
sage: G.field_of_definition()
Finite Field of size 7
sage: G.base_ring()
Finite Field of size 7
gen(n)

Return the n-th generator.

EXAMPLES:

sage: G = GU(4,GF(5), var='beta')
sage: G.gen(0)     
[  beta      0      0      0]
[     0      1      0      0]
[     0      0      1      0]
[     0      0      0 3*beta]
gens()

Return generators for this matrix group.

EXAMPLES:

sage: G = GO(3,GF(5))
sage: G.gens()
[
[2 0 0]
[0 3 0]
[0 0 1],
[0 1 0]
[1 4 4]
[0 2 1]
]
hom(x)

x.__init__(...) initializes x; see help(type(x)) for signature

irreducible_characters()

Returns the list of irreducible characters of the group.

EXAMPLES:

sage: G = GL(2,2)
sage: G.irreducible_characters()
[Character of General Linear Group of degree 2 over Finite Field of size 2,
 Character of General Linear Group of degree 2 over Finite Field of size 2,
 Character of General Linear Group of degree 2 over Finite Field of size 2]
is_abelian()

Return True if this group is an abelian group.

Note: The result is cached, since it tends to get called rather often (e.g. by word_problem) and it’s very slow to use the Gap interface every time.

EXAMPLES:

sage: SL(1, 17).is_abelian()
True
sage: SL(2, 17).is_abelian()
False
is_finite()

Return True if this matrix group is finite.

EXAMPLES:

sage: G = GL(2,GF(3))
sage: G.is_finite()
True
sage: SL(2,ZZ).is_finite()
False
list()

Return list of all elements of this group.

Always returns a new list, so it is safe to change the returned list.

EXAMPLES:

sage: F = GF(3)
sage: gens = [matrix(F,2, [1,0, -1,1]), matrix(F, 2, [1,1,0,1])]
sage: G = MatrixGroup(gens)
sage: G.cardinality()
24
sage: v = G.list()
sage: len(v)
24
sage: v[:2]
[[0 1]
[2 0], [0 1]
[2 1]]            
sage: G.list()[0] in G
True

An example over a ring (see trac 5241):

sage: M1 = matrix(ZZ,2,[[-1,0],[0,1]]) 
sage: M2 = matrix(ZZ,2,[[1,0],[0,-1]]) 
sage: M3 = matrix(ZZ,2,[[-1,0],[0,-1]]) 
sage: MG = MatrixGroup([M1, M2, M3]) 
sage: MG.list() 
[[-1  0] 
[ 0 -1], [-1  0] 
[ 0  1], [ 1  0] 
[ 0 -1], [1 0] 
[0 1]] 
sage: MG.list()[1] 
[-1  0] 
[ 0  1] 
sage: MG.list()[1].parent() 
Matrix group over Integer Ring with 3 generators: 
[[[-1, 0], [0, 1]], [[1, 0], [0, -1]], [[-1, 0], [0, -1]]] 

An example over a field (see trac 10515):

sage: gens = [matrix(QQ,2,[1,0,0,1])]
sage: MatrixGroup(gens).list()
[[1 0]
[0 1]]

Another example over a ring (see trac 9437):

sage: len(SL(2, Zmod(4)).list())
48

An error is raised if the group is not finite:

sage: GL(2,ZZ).list()
Traceback (most recent call last):
...
ValueError: group must be finite
matrix_space()

Return the matrix space corresponding to this matrix group.

This is a matrix space over the field of definition of this matrix group.

EXAMPLES:

sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS(1), MS([1,2,3,4])])
sage: G.matrix_space()
Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5
ngens()

Return the number of generators of this linear group.

EXAMPLES:

sage: G = GO(3,GF(5))
sage: G.ngens()
2
order()

Backward compatibility alias for cardinality().

Might be deprecated in the future.

EXAMPLES:

sage: G = Sp(4,GF(3))
sage: G.order()
51840
class sage.groups.matrix_gps.matrix_group.MatrixGroup_gap_finite_field(n, R, var='a', category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_gap

Python class for matrix groups over a finite field.

cardinality()

EXAMPLES:

sage: G = Sp(4,GF(3))
sage: G.cardinality()
51840
sage: G = SL(4,GF(3))
sage: G.cardinality()
12130560
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
sage: G = MatrixGroup(gens)
sage: G.cardinality()
480
sage: G = MatrixGroup([matrix(ZZ,2,[1,1,0,1])])
sage: G.cardinality()
+Infinity
center()

Return the center of this linear group as a matrix group.

EXAMPLES:

sage: G = SU(3,GF(2))
sage: G.center()
Matrix group over Finite Field in a of size 2^2 with 1 generators: 
 [[[a, 0, 0], [0, a, 0], [0, 0, a]]]
sage: GL(2,GF(3)).center()
Matrix group over Finite Field of size 3 with 1 generators: 
 [[[2, 0], [0, 2]]]
sage: GL(3,GF(3)).center()
Matrix group over Finite Field of size 3 with 1 generators: 
 [[[2, 0, 0], [0, 2, 0], [0, 0, 2]]]
sage: GU(3,GF(2)).center()
Matrix group over Finite Field in a of size 2^2 with 1 generators: 
 [[[a + 1, 0, 0], [0, a + 1, 0], [0, 0, a + 1]]]
sage: A=Matrix(FiniteField(5), [[2,0,0], [0,3,0], [0,0,1]])
sage: B=Matrix(FiniteField(5), [[1,0,0], [0,1,0], [0,1,1]])
sage: MatrixGroup([A,B]).center()
Matrix group over Finite Field of size 5 with 1 generators: 
 [[[1, 0, 0], [0, 1, 0], [0, 0, 1]]]
conjugacy_class(g)

Return the conjugacy class of g inside of self.

INPUT:

  • g – an element of self

OUTPUT:

The conjugacy class of g in the group self. If self is the group denoted by G, this method computes the set \{x^{-1}gx\ \vert\ x\in G\}.

EXAMPLES:

sage: G = SL(3, GF(3))
sage: g = G.gens()[0]
sage: G.conjugacy_class(g)
Conjugacy class of [1 1 0]
[0 1 0]
[0 0 1] in Special Linear Group of degree 3 over Finite Field of size 3
conjugacy_class_representatives()

Return a set of representatives for each of the conjugacy classes of the group.

EXAMPLES:

sage: G = SU(3,GF(2))
sage: len(G.conjugacy_class_representatives())
16
sage: len(GL(2,GF(3)).conjugacy_class_representatives())
8
sage: len(GU(2,GF(5)).conjugacy_class_representatives())
36
conjugacy_classes()

Return a list with all the conjugacy classes of self.

EXAMPLES:

sage: G = SL(2, GF(2))
sage: G.conjugacy_classes()
[Conjugacy class of [1 0]
[0 1] in Special Linear Group of degree 2 over Finite Field of size 2, Conjugacy class of [0 1]
[1 0] in Special Linear Group of degree 2 over Finite Field of size 2, Conjugacy class of [0 1]
[1 1] in Special Linear Group of degree 2 over Finite Field of size 2]
random()

Deprecated. Use self.random_element() instead.

random_element()

Return a random element of this group.

EXAMPLES:

sage: G = Sp(4,GF(3))
sage: G.random_element()  # random
[2 1 1 1]
[1 0 2 1]
[0 1 1 0]
[1 0 0 1]
sage: G.random_element() in G
True
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[0,1]])]
sage: G = MatrixGroup(gens)
sage: G.random_element()  # random
[1 3]
[0 3]
sage: G.random_element() in G
True
class sage.groups.matrix_gps.matrix_group.MatrixGroup_generic

Bases: sage.groups.old.Group

TESTS:

   sage: from sage.groups.old import Group
   sage: G = Group()
   sage: G.category()
   Category of groups
   sage: G = Group(category = Groups()) # todo: do the same test with some subcategory of Groups when there will exist one
   sage: G.category()
   Category of groups
   sage: G = Group(category = CommutativeAdditiveGroups())
   Traceback (most recent call last):
   ...
   AssertionError: Category of commutative additive groups is not a subcategory of Category of groups

Check for #8119::

   sage: G = SymmetricGroup(2)
   sage: h = hash(G)
   sage: G.rename('S2')
   sage: h == hash(G)
   True
class sage.groups.matrix_gps.matrix_group.MatrixGroup_gens(gensG, category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_gap

EXAMPLES:

A ValueError is raised if one of the generators is not invertible.

sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS.0])
Traceback (most recent call last):
...
ValueError: each generator must be an invertible matrix but one is not:
[1 0]
[0 0]
as_permutation_group(algorithm=None)

Return a permutation group representation for the group.

In most cases occurring in practice, this is a permutation group of minimal degree (the degree begin determined from orbits under the group action). When these orbits are hard to compute, the procedure can be time-consuming and the degree may not be minimal.

INPUT:

  • algorithmNone or 'smaller'. In the latter case, try harder to find a permutation representation of small degree.

OUTPUT:

A permutation group isomorphic to self. The algorithm='smaller' option tries to return an isomorphic group of low degree, but is not guaranteed to find the smallest one.

EXAMPLES:

sage: MS = MatrixSpace(GF(2), 5, 5)
sage: A = MS([[0,0,0,0,1],[0,0,0,1,0],[0,0,1,0,0],[0,1,0,0,0],[1,0,0,0,0]])
sage: G = MatrixGroup([A])
sage: G.as_permutation_group()
Permutation Group with generators [(1,2)]
sage: MS = MatrixSpace( GF(7), 12, 12)
sage: GG = gap("ImfMatrixGroup( 12, 3 )")
sage: GG.GeneratorsOfGroup().Length()
3
sage: g1 = MS(eval(str(GG.GeneratorsOfGroup()[1]).replace("\n","")))
sage: g2 = MS(eval(str(GG.GeneratorsOfGroup()[2]).replace("\n","")))
sage: g3 = MS(eval(str(GG.GeneratorsOfGroup()[3]).replace("\n","")))
sage: G = MatrixGroup([g1, g2, g3])
sage: G.cardinality()
21499084800
sage: set_random_seed(0); current_randstate().set_seed_gap()  
sage: P = G.as_permutation_group()
sage: P.cardinality()
21499084800
sage: P.degree()  # random output
144
sage: set_random_seed(3); current_randstate().set_seed_gap()  
sage: Psmaller = G.as_permutation_group(algorithm="smaller") 
sage: Psmaller.cardinality()
21499084800
sage: Psmaller.degree()  # random output
108

In this case, the “smaller” option returned an isomorphic group of lower degree. The above example used GAP’s library of irreducible maximal finite (“imf”) integer matrix groups to construct the MatrixGroup G over GF(7). The section “Irreducible Maximal Finite Integral Matrix Groups” in the GAP reference manual has more details.

gens()

EXAMPLES:

sage: F = GF(3); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
sage: G = MatrixGroup(gens)
sage: gens[0] in G
True
sage: gens = G.gens()
sage: gens[0] in G
True
sage: gens = [MS([[1,0],[0,1]]),MS([[1,1],[0,1]])]
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS(1), MS([1,2,3,4])])
sage: G
Matrix group over Finite Field of size 5 with 2 generators:
 [[[1, 0], [0, 1]], [[1, 2], [3, 4]]]
sage: G.gens()
[[1 0]
[0 1], [1 2]
[3 4]]
invariant_generators()

Wraps Singular’s invariant_algebra_reynolds and invariant_ring in finvar.lib, with help from Simon King and Martin Albrecht. Computes generators for the polynomial ring F[x_1,\ldots,x_n]^G, where G in GL(n,F) is a finite matrix group.

In the “good characteristic” case the polynomials returned form a minimal generating set for the algebra of G-invariant polynomials. In the “bad” case, the polynomials returned are primary and secondary invariants, forming a not necessarily minimal generating set for the algebra of G-invariant polynomials.

EXAMPLES:

sage: F = GF(7); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[0,1],[-1,0]]),MS([[1,1],[2,3]])]
sage: G = MatrixGroup(gens)
sage: G.invariant_generators()
[x1^7*x2 - x1*x2^7, x1^12 - 2*x1^9*x2^3 - x1^6*x2^6 + 2*x1^3*x2^9 + x2^12, x1^18 + 2*x1^15*x2^3 + 3*x1^12*x2^6 + 3*x1^6*x2^12 - 2*x1^3*x2^15 + x2^18]
sage: q = 4; a = 2
sage: MS = MatrixSpace(QQ, 2, 2)
sage: gen1 = [[1/a,(q-1)/a],[1/a, -1/a]]; gen2 = [[1,0],[0,-1]]; gen3 = [[-1,0],[0,1]]
sage: G = MatrixGroup([MS(gen1),MS(gen2),MS(gen3)])
sage: G.cardinality()
12
sage: G.invariant_generators()
[x1^2 + 3*x2^2, x1^6 + 15*x1^4*x2^2 + 15*x1^2*x2^4 + 33*x2^6]
sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[1,2],[-1,1]]),MS([[1,1],[-1,1]])]
sage: G = MatrixGroup(gens)
sage: G.invariant_generators()  # long time (67s on sage.math, 2012)
[x1^20 + x1^16*x2^4 + x1^12*x2^8 + x1^8*x2^12 + x1^4*x2^16 + x2^20, x1^20*x2^4 + x1^16*x2^8 + x1^12*x2^12 + x1^8*x2^16 + x1^4*x2^20]
sage: F=CyclotomicField(8)
sage: z=F.gen()
sage: a=z+1/z
sage: b=z^2
sage: MS=MatrixSpace(F,2,2)
sage: g1=MS([[1/a,1/a],[1/a,-1/a]])
sage: g2=MS([[1,0],[0,b]])
sage: g3=MS([[b,0],[0,1]])
sage: G=MatrixGroup([g1,g2,g3])
sage: G.invariant_generators()  # long time (12s on sage.math, 2011)
[x1^8 + 14*x1^4*x2^4 + x2^8,
 x1^24 + 10626/1025*x1^20*x2^4 + 735471/1025*x1^16*x2^8 + 2704156/1025*x1^12*x2^12 + 735471/1025*x1^8*x2^16 + 10626/1025*x1^4*x2^20 + x2^24]

AUTHORS:

  • David Joyner, Simon King and Martin Albrecht.

REFERENCES:

  • Singular reference manual
    1. Sturmfels, “Algorithms in invariant theory”, Springer-Verlag, 1993.
  • S. King, “Minimal Generating Sets of non-modular invariant rings of finite groups”, arXiv:math.AC/0703035
module_composition_factors(algorithm=None)

Returns a list of triples consisting of [base field, dimension, irreducibility], for each of the Meataxe composition factors modules. The algorithm=”verbose” option returns more information, but in Meataxe notation.

EXAMPLES:

sage: F=GF(3);MS=MatrixSpace(F,4,4)
sage: M=MS(0)
sage: M[0,1]=1;M[1,2]=1;M[2,3]=1;M[3,0]=1
sage: G = MatrixGroup([M])
sage: G.module_composition_factors()
[(Finite Field of size 3, 1, True),
 (Finite Field of size 3, 1, True),
 (Finite Field of size 3, 2, True)]
sage: F = GF(7); MS = MatrixSpace(F,2,2)
sage: gens = [MS([[0,1],[-1,0]]),MS([[1,1],[2,3]])]
sage: G = MatrixGroup(gens)
sage: G.module_composition_factors()
[(Finite Field of size 7, 2, True)]

Type “G.module_composition_factors(algorithm=’verbose’)” to get a more verbose version.

For more on MeatAxe notation, see http://www.gap-system.org/Manuals/doc/htm/ref/CHAP067.htm

class sage.groups.matrix_gps.matrix_group.MatrixGroup_gens_finite_field(gensG, category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_gens, sage.groups.matrix_gps.matrix_group.MatrixGroup_gap_finite_field

sage.groups.matrix_gps.matrix_group.is_MatrixGroup(x)

EXAMPLES:

sage: from sage.groups.matrix_gps.matrix_group import is_MatrixGroup
sage: is_MatrixGroup(MatrixSpace(QQ,3))
False
sage: is_MatrixGroup(Mat(QQ,3))
False
sage: is_MatrixGroup(GL(2,ZZ))
True
sage: is_MatrixGroup(MatrixGroup([matrix(2,[1,1,0,1])]))
True

Previous topic

Rubik’s cube group functions

Next topic

Matrix Group Elements

This Page