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

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()

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])])
...
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()
...
NotImplementedError: Matrix group over Complex Field with 53 bits of precision not implemented.
sage: G = SL(0, QQ)
...
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

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)¶

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

sage: GL(2,ZZ).list()
...
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_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

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()
[2 1 1 1]
[1 0 2 1]
[0 1 1 0]
[1 0 0 1]

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()
[1 3]
[0 3]
sage: G.random_element()
[2 2]
[1 0]
sage: G.random_element()
[4 0]
[1 4]

class sage.groups.matrix_gps.matrix_group.MatrixGroup_generic¶: Bases: sage.groups.group.Group

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])
...
ValueError: each generator must be an invertible matrix but one is not:
[1 0]
[0 0]

as_permutation_group(method=None)¶

This returns 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. The “method=smaller” option tries return an isomorphic group of lower degree.

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: G.as_permutation_group()     
Permutation Group with generators [(2,3,5,11,20,38,14,26,43,66)(4,8,16,29,47,63,48,74,56,86)(6,13,24,41,22,27,45,69,98,67)(9,19,35,58,88,94,70,100,84,104)(17,32,52,36,60,75,108,133,101,128)(30,50,77,110,117,106,61,92,123,89)(33,55,83,81,72,103,115,137,112,119)(53,80), (2,4,9,20)(3,6,14,27)(8,17,33,56)(11,22,16,30)(13,19,36,61)(29,48,75,103)(32,53,81,92)(38,63,94,66)(43,67,74,106)(45,70,101,50)(47,72,104,128)(55,84,117,137)(58,89,83,115)(60,86,119,88)(77,108,80,112), (1,2)(3,7)(4,10)(5,12)(6,15)(8,18)(9,21)(11,23)(13,25)(14,28)(16,31)(17,34)(19,37)(20,39)(22,40)(24,42)(26,44)(27,46)(29,49)(30,51)(32,54)(33,57)(35,59)(36,62)(38,64)(41,65)(43,68)(45,71)(47,73)(48,76)(50,78)(52,79)(53,82)(55,85)(56,87)(58,90)(60,91)(61,93)(63,95)(66,96)(67,97)(69,99)(70,102)(72,105)(74,107)(75,109)(77,111)(80,113)(81,114)(83,116)(84,118)(86,120)(88,121)(89,122)(92,124)(94,125)(98,126)(100,127)(101,129)(103,130)(104,131)(106,132)(108,134)(110,135)(112,136)(115,138)(117,139)(119,140)(123,141)(128,142)(133,143)(137,144)]
sage: set_random_seed(3); current_randstate().set_seed_gap()  
sage: G.as_permutation_group(method="smaller") 
Permutation Group with generators [(1,2)(3,7,13,25,45,5,10,19,35,60)(8,16,30,41,69,11,22,40,31,54)(14,28,49,80,91,20,38,64,93,78)(17,33,57,26,48,23,43,72,36,63)(46,61)(52,73,55,76,94,67,58,70,89,81), (1,3,8,17)(2,5,11,23)(7,14)(10,20)(13,26,49,81)(16,31,55,72)(19,36,64,94)(22,41,70,57)(25,46,76,93)(28,38)(30,52,63,91)(33,58)(35,61,89,80)(40,67,48,78)(43,73)(45,69)(54,60), (1,4)(2,6)(3,9)(5,12)(7,15)(8,18)(10,21)(11,24)(13,27)(14,29)(16,32)(17,34)(19,37)(20,39)(22,42)(23,44)(25,47)(26,50)(28,51)(30,53)(31,56)(33,59)(35,62)(36,65)(38,66)(40,68)(41,71)(43,74)(45,75)(46,77)(48,79)(49,82)(52,83)(54,84)(55,85)(57,86)(58,87)(60,88)(61,90)(63,92)(64,95)(67,96)(69,97)(70,98)(72,99)(73,100)(76,101)(78,102)(80,103)(81,104)(89,105)(91,106)(93,107)(94,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()  ## takes a long time (several mins)
[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()
[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(method=None)¶

Returns a list of triples consisting of [base field, dimension, irreducibility], for each of the Meataxe composition factors modules. The method=”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(method=’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

Matrix Groups¶

Previous topic

Next topic

This Page

Navigation

Matrix Groups¶

Previous topic

Next topic

This Page

Quick search

Navigation