Finitely Generated Matrix Groups

This class is designed for computing with matrix groups defined by a 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]  [0 2]  [0 2]  [0 1]  [2 0]
[0 1], [2 1], [2 2], [1 1], [1 2], [2 0], [0 2]
)

The finitely generated matrix groups can also be constructed as subgroups of matrix groups:

sage: SL2Z = SL(2,ZZ)
sage: S, T = SL2Z.gens()
sage: SL2Z.subgroup([T^2])
Matrix group over Integer Ring with 1 generators (
[1 2]
[0 1]
)

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.
  • Volker Braun (2013-1) port to new Parent, libGAP.
class sage.groups.matrix_gps.finitely_generated.FinitelyGeneratedMatrixGroup_gap(degree, base_ring, libgap_group, ambient=None, category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_gap

Matrix group generated by a finite number of matrices.

EXAMPLES:

sage: m1 = matrix(GF(11), [[1,2],[3,4]])
sage: m2 = matrix(GF(11), [[1,3],[10,0]])
sage: G = MatrixGroup(m1, m2);  G
Matrix group over Finite Field of size 11 with 2 generators (
[1 2]  [ 1  3]
[3 4], [10  0]
)
sage: type(G)
<class 'sage.groups.matrix_gps.finitely_generated.FinitelyGeneratedMatrixGroup_gap_with_category'>
sage: TestSuite(G).run()
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.

invariant_generators()

Return invariant ring generators.

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.

ALGORITHM:

Wraps Singular’s invariant_algebra_reynolds and invariant_ring in finvar.lib.

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
  • B. Sturmfels, “Algorithms in invariant theory”, Springer-Verlag, 1993.
  • S. King, “Minimal Generating Sets of non-modular invariant rings of finite groups”, Arxiv math/0703035.
module_composition_factors(algorithm=None)

Return 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/ref/chap69.html

class sage.groups.matrix_gps.finitely_generated.FinitelyGeneratedMatrixGroup_generic(degree, base_ring, generator_matrices, category=None)

Bases: sage.groups.matrix_gps.matrix_group.MatrixGroup_generic

Matrix group generated by a finite number of matrices.

EXAMPLES:

sage: m1 = matrix(SR, [[1,2],[3,4]])
sage: m2 = matrix(SR, [[1,3],[-1,0]])
sage: G = MatrixGroup(m1, m2)
sage: TestSuite(G).run()
sage: type(G)
<class 'sage.groups.matrix_gps.finitely_generated.FinitelyGeneratedMatrixGroup_generic_with_category'>

sage: from sage.groups.matrix_gps.finitely_generated import             ....:     FinitelyGeneratedMatrixGroup_generic
sage: G = FinitelyGeneratedMatrixGroup_generic(2, QQ, [matrix(QQ,[[1,2],[3,4]])])
sage: G.gens()
(
[1 2]
[3 4]
)
gen(i)

Return the \(i\)-th generator

OUTPUT:

The \(i\)-th generator of the group.

EXAMPLES:

sage: H = GL(2, GF(3))
sage: h1, h2 = H([[1,0],[2,1]]), H([[1,1],[0,1]])
sage: G = H.subgroup([h1, h2])
sage: G.gen(0)
[1 0]
[2 1]
sage: G.gen(0).matrix() == h1.matrix()
True
gens()

Return the generators of the matrix group.

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

Return the number of generators

OUTPUT:

An integer. The number of generators.

EXAMPLES:

sage: H = GL(2, GF(3))
sage: h1, h2 = H([[1,0],[2,1]]), H([[1,1],[0,1]])
sage: G = H.subgroup([h1, h2])
sage: G.ngens()
2
sage.groups.matrix_gps.finitely_generated.MatrixGroup(*gens, **kwds)

Return the matrix group with given generators.

INPUT:

  • *gens – matrices, or a single list/tuple/iterable of matrices, or a matrix group.
  • check – boolean keyword argument (optional, default: True). Whether to check that each matrix is invertible.

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]  [1 1]
[4 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]  [1 1]  [2 0]
[6 1], [0 1], [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

sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: MatrixGroup([MS.0])
Traceback (most recent call last):
...
ValueError: each generator must be an invertible matrix
sage: MatrixGroup([MS.0], check=False)  # works formally but is mathematical nonsense
Matrix group over Finite Field of size 5 with 1 generators (
[1 0]
[0 0]
)

Some groups are not supported, or do not have much functionality implemented:

sage: G = SL(0, QQ)
Traceback (most recent call last):
...
ValueError: the degree must be at least 1

sage: SL2C = SL(2, CC);  SL2C
Special Linear Group of degree 2 over Complex Field with 53 bits of precision
sage: SL2C.gens()
Traceback (most recent call last):
...
AttributeError: 'LinearMatrixGroup_generic_with_category' object has no attribute 'gens'
sage.groups.matrix_gps.finitely_generated.QuaternionMatrixGroupGF3()

The quaternion group as a set of \(2\times 2\) matrices over \(GF(3)\).

OUTPUT:

A matrix group consisting of \(2\times 2\) matrices with elements from the finite field of order 3. The group is the quaternion group, the nonabelian group of order 8 that is not isomorphic to the group of symmetries of a square (the dihedral group \(D_4\)).

Note

This group is most easily available via groups.matrix.QuaternionGF3().

EXAMPLES:

The generators are the matrix representations of the elements commonly called \(I\) and \(J\), while \(K\) is the product of \(I\) and \(J\).

sage: from sage.groups.matrix_gps.finitely_generated import QuaternionMatrixGroupGF3
sage: Q = QuaternionMatrixGroupGF3()
sage: Q.order()
8
sage: aye = Q.gens()[0]; aye
[1 1]
[1 2]
sage: jay = Q.gens()[1]; jay
[2 1]
[1 1]
sage: kay = aye*jay; kay
[0 2]
[1 0]

TESTS:

sage: groups.matrix.QuaternionGF3()
Matrix group over Finite Field of size 3 with 2 generators (
[1 1]  [2 1]
[1 2], [1 1]
)

sage: Q = QuaternionMatrixGroupGF3()
sage: QP = Q.as_permutation_group()
sage: QP.is_isomorphic(QuaternionGroup())
True
sage: H = DihedralGroup(4)
sage: H.order()
8
sage: QP.is_abelian(), H.is_abelian()
(False, False)
sage: QP.is_isomorphic(H)
False
sage.groups.matrix_gps.finitely_generated.normalize_square_matrices(matrices)

Find a common space for all matrices.

OUTPUT:

A list of matrices, all elements of the same matrix space.

EXAMPLES:

sage: from sage.groups.matrix_gps.finitely_generated import normalize_square_matrices
sage: m1 = [[1,2],[3,4]]
sage: m2 = [2, 3, 4, 5]
sage: m3 = matrix(QQ, [[1/2,1/3],[1/4,1/5]])
sage: m4 = MatrixGroup(m3).gen(0)
sage: normalize_square_matrices([m1, m2, m3, m4])
[
[1 2]  [2 3]  [1/2 1/3]  [1/2 1/3]
[3 4], [4 5], [1/4 1/5], [1/4 1/5]
]

Previous topic

Matrix Group Elements

Next topic

Homomorphisms Between Matrix Groups

This Page