Module: sage.groups.perm_gps.permgroup
A permutation group is a finite group G whose elements are permutations
of a given finite set X (i.e., bijections X -> X) and whose group operation is
the composition of permutations. The number of elements of
is called the
degree of G.
In SAGE a permutation is represented as either a string that defines a permutation using disjoint cycle notation, or a list of tuples, which represent disjoint cycles.
(a,...,b)(c,...,d)...(e,...,f) <--> [(a,...,b), (c,...,d),..., (e,...,f)] () = identity <--> []
You can construct the following permutation groups:
- SymmetricGroup,
of ordr
- AlternatingGroup,
or order
- DihedralGroup,
of order
- CyclicPermutationGroup,
of order
- TransitiveGroup,
transitive group of degree
from the GAP tables of transitive groups (requires
the "optional" package database_gap)
- PGL(n,q), projective general linear group of
matrices over
the finite field GF(q)
- PSL(n,q), projective special linear group of
matrices over
the finite field GF(q)
- PSp(2n,q), projective symplectic linear group of
matrices over
the finite field GF(q)
- PSU(n,q), projective special unitary group of
matrices having
coefficients in the finite field
JOKE: Q: What's hot, chunky, and acts on a polygon? A: Dihedral soup. Renteln, P. and Dundes, A. "Foolproof: A Sampling of Mathematical Folk Humor." Notices Amer. Math. Soc. 52, 24-34, 2005.
Author Log:
REFERENCES: Cameron, P., Permutation Groups. New York: Cambridge University Press, 1999. Wielandt, H., Finite Permutation Groups. New York: Academic Press, 1964. Dixon, J. and Mortimer, B., Permutation Groups, Springer-Verlag, Berlin/New York, 1996.
TODO: Implement PGU over GF(q) as a permutation group.
Module-level Functions
x, [from_group=True], [check=False]) |
Return the permutation group associated to
(typically a list
of generators).
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G Permutation Group with generators [(1,2,3)(4,5), (3,4)]
We can also make permutation groups from PARI groups:
sage: H = pari('x^4 - 2*x^3 - 2*x + 1').polgalois() sage: G = PariGroup(H, 4); G PARI group [8, -1, 3, "D(4)"] of degree 4 sage: H = PermutationGroup(G); H # requires optional database_gap Transitive group number 3 of degree 4 sage: H.gens() # requires optional database_gap ((1,2,3,4), (1,3))
There is an underlying gap object that implements each permutation group.
sage: G = PermutationGroup([[(1,2,3,4)]]) sage: G._gap_() Group([ (1,2,3,4) ]) sage: gap(G) Group([ (1,2,3,4) ]) sage: gap(G) is G._gap_() True sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G._gap_().DerivedSeries() # output somewhat random [ Group([ (1,2,3)(4,5), (3,4) ]), Group([ (1,5)(3,4), (1,5)(2,4), (1,4,5) ]) ]
x) |
Put a permutation in Gap format, as a string.
Class: AlternatingGroup
self, n) |
INPUT: n -- integer $n \geq 1$
sage: G = AlternatingGroup(8) sage: G.order() 20160 sage: G Alternating group of order 8!/2 as a permutation group sage: loads(G.dumps()) == G True
Special Functions: _repr_
Class: CyclicPermutationGroup
sage: C = CyclicPermutationGroup(10) sage: C.is_abelian() True
self, n) |
INPUT: n -- a positive integer
sage: G = CyclicPermutationGroup(8) sage: G.order() 8 sage: G Cyclic group of order 8 as a permutation group sage: loads(G.dumps()) == G True
Functions: is_abelian,
is_commutative
Special Functions: _repr_
Class: DihedralGroup
self, n) |
INPUT: n -- a positive integer OUTPUT: -- the dihedral group of order 2*n, as a permutation group
sage: G = DihedralGroup(6) sage: G.order() 12 sage: G = DihedralGroup(5) sage: G.order() 10 sage: G Dihedral group of order 10 as a permutation group sage: loads(G.dumps()) == G True
Special Functions: _repr_
Class: PermutationGroup_generic
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G Permutation Group with generators [(1,2,3)(4,5), (3,4)] sage: G.center() Permutation Group with generators [()] sage: G.group_id() # requires optional database_gap [120, 34] sage: n = G.order(); n 120 sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: loads(G.dumps()) == G True
self, gens, [from_group=True], [check=False]) |
Functions: center,
character_table,
conjugacy_classes_representatives,
degree,
derived_series,
direct_product,
gen,
gens,
group_id,
has_element,
id,
identity,
is_abelian,
is_commutative,
largest_moved_point,
list,
order,
random,
smallest_moved_point
self) |
Return the subgroup of elements of that commute with every element of this group.
sage: G = PermutationGroup([[(1,2,3,4)]]) sage: G.center() Permutation Group with generators [(1,2,3,4)] sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]]) sage: G.center() Permutation Group with generators [()]
self) |
Returns the matrix of values of the irreducible characters of
a permutation group
at the conjugacy classes of
. The
columns represent the the conjugacy classes of
and the
rows represent the different irreducible characters in the
ordering given by GAP.
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]]) sage: G.order() 12 sage: G.character_table() [ 1 1 1 1] [ 1 1 -zeta3 - 1 zeta3] [ 1 1 zeta3 -zeta3 - 1] [ 3 -1 0 0] sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]]) sage: CT = gap(G).CharacterTable() sage: print gap.eval("Display(%s)"%CT.name()) CT1 2 2 2 . . 3 1 . 1 1 1a 2a 3a 3b 2P 1a 1a 3b 3a 3P 1a 2a 1a 1a X.1 1 1 1 1 X.2 1 1 A /A X.3 1 1 /A A X.4 3 -1 . . A = E(3)^2 = (-1-ER(-3))/2 = -1-b3
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]]) sage: G.order() 8 sage: G.character_table() [ 1 1 1 1 1] [ 1 -1 -1 1 1] [ 1 -1 1 -1 1] [ 1 1 -1 -1 1] [ 2 0 0 0 -2] sage: CT = gap(G).CharacterTable() sage: print gap.eval("Display(%s)"%CT.name()) CT2 2 3 2 2 2 3 1a 2a 2b 4a 2c 2P 1a 1a 1a 2c 1a 3P 1a 2a 2b 4a 2c X.1 1 1 1 1 1 X.2 1 -1 -1 1 1 X.3 1 -1 1 -1 1 X.4 1 1 -1 -1 1 X.5 2 . . . -2
sage: SymmetricGroup(2).character_table() [ 1 -1] [ 1 1] sage: SymmetricGroup(3).character_table() [ 1 -1 1] [ 2 0 -1] [ 1 1 1] sage: SymmetricGroup(5).character_table() [ 1 -1 1 1 -1 -1 1] [ 4 -2 0 1 1 0 -1] [ 5 -1 1 -1 -1 1 0] [ 6 0 -2 0 0 0 1] [ 5 1 1 -1 1 -1 0] [ 4 2 0 1 -1 0 -1] [ 1 1 1 1 1 1 1] sage: list(AlternatingGroup(6).character_table()) [(1, 1, 1, 1, 1, 1, 1), (5, 1, -1, 2, -1, 0, 0), (5, 1, 2, -1, -1, 0, 0), (8, 0, -1, -1, 0, zeta5^3 + zeta5^2 + 1, -zeta5^3 - zeta5^2), (8, 0, -1, -1, 0, -zeta5^3 - zeta5^2, zeta5^3 + zeta5^2 + 1), (9, 1, 0, 0, 1, -1, -1), (10, -2, 1, 1, 0, 0, 0)]
Suppose that you have a class function
on
and you
know the values
on the conjugacy class
elements in
conjugacy_classes_representatives(G)
=
. Since the irreducible characters
of
form an
-basis of the space
of all class functions (
a ``sufficiently large''
cyclotomic field), such a class function is a linear
combination of these basis elements,
. To find the coefficients
, you simply solve
the linear system
character_table_values(G)
*
,
where
=
character_table_values(G)
.
Author: David Joyner and William Stein (2006-01-04)
self) |
Returns a complete list of representatives of conjugacy classes in a permutation group G. The ordering is that given by GAP.
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]]) sage: cl = G.conjugacy_classes_representatives(); cl [(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3)(2,4)] sage: cl[3] in G True
sage: G = SymmetricGroup(5) sage: G.conjugacy_classes_representatives () [(), (1,2), (1,2)(3,4), (1,2,3), (1,2,3)(4,5), (1,2,3,4), (1,2,3,4,5)]
Author: David Joyner and William Stein (2006-01-04)
self) |
Synonym for largest_moved_point().
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G.degree() 5
self) |
Return the derived series of this group as a list of permutation groups.
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G.derived_series() # somewhat random output [Permutation Group with generators [(1,2,3)(4,5), (3,4)], Permutation Group with generators [(1,5)(3,4), (1,5)(2,4), (2,4)(3,5)]]
self, other, [maps=True]) |
Wraps GAP's DirectProduct, Embedding, and Projection.
SAGE calls GAP's DirectProduct, which chooses an efficient representation for the direct product. The direct product of permutation groups will be a permutation group again. For a direct product D, the GAP operation Embedding(D,i) returns the homomorphism embedding the i-th factor into D. The GAP operation Projection(D,i) gives the projection of D onto the i-th factor.
INPUT: self, other -- permutation groups This method returns a 5-tuple - a permutation groups and 4 morphisms. OUTPUT: D -- a direct product of the inputs, returned as a permutation group as well iota1 -- an embedding of self into D iota2 -- an embedding of other into D pr1 -- the projection of D onto self (giving a splitting 1 -> other -> D ->> self -> 1) pr2 -- the projection of D onto other (giving a splitting 1 -> self -> D ->> other -> 1)
sage: G = CyclicPermutationGroup(4) sage: D = G.direct_product(G,False) sage: D Permutation Group with generators [(1,2,3,4), (5,6,7,8)] sage: D,iota1,iota2,pr1,pr2 = G.direct_product(G) sage: D; iota1; iota2; pr1; pr2 Permutation Group with generators [(1,2,3,4), (5,6,7,8)] Homomorphism : Cyclic group of order 4 as a permutation group --> Permutation Group with generators [(1,2,3,4), (5,6,7,8)] Homomorphism : Cyclic group of order 4 as a permutation group --> Permutation Group with generators [(1,2,3,4), (5,6,7,8)] Homomorphism : Permutation Group with generators [(1,2,3,4), (5,6,7,8)] --> Cyclic group of order 4 as a permutation group Homomorphism : Permutation Group with generators [(1,2,3,4), (5,6,7,8)] --> Cyclic group of order 4 as a permutation group
sage: g=D([(1,3),(2,4)]); g (1,3)(2,4) sage: d=D([(1,4,3,2),(5,7),(6,8)]); d (1,4,3,2)(5,7)(6,8) sage: iota1(g); iota2(g); pr1(d); pr2(d) (1,3)(2,4) (5,7)(6,8) (1,4,3,2) (1,3)(2,4)
self) |
Return tuple of generators of this group. These need not be minimal, as they are the generators used in defining this group.
sage: G = PermutationGroup([[(1,2,3)], [(1,2)]]) sage: G.gens() ((1,2,3), (1,2))
Note that the generators need not be minimal.
sage: G = PermutationGroup([[(1,2)], [(1,2)]]) sage: G.gens() ((1,2), (1,2))
sage: G = PermutationGroup([[(1,2,3,4), (5,6)], [(1,2)]]) sage: g = G.gens() sage: g[0] (1,2,3,4)(5,6) sage: g[1] (1,2)
self) |
Return the ID code of this group, which is a list of two integers. Requires "optional" database_gap-4.4.x package.
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]]) sage: G.group_id() # requires optional database_gap-4.4.6 package [12, 4]
self, item) |
Returns boolean value of "item in self" - however *ignores* parentage.
sage: G = CyclicPermutationGroup(4) sage: gens = G.gens() sage: H = DihedralGroup(4) sage: g = G([(1,2,3,4)]); g (1,2,3,4) sage: G.has_element(g) True sage: h = H([(1,2),(3,4)]); h (1,2)(3,4) sage: G.has_element(h) False
self) |
Same as self.group_id()
self) |
Return the identity element of this group.
sage: G = PermutationGroup([[(1,2,3),(4,5)]]) sage: e = G.identity() sage: e () sage: g = G.gen(0) sage: g*e (1,2,3)(4,5) sage: e*g (1,2,3)(4,5)
self) |
Return True if this group is abelian.
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)']) sage: G.is_abelian() False sage: G = PermutationGroup(['(1,2,3)(4,5)']) sage: G.is_abelian() True
self) |
Return True if this group is commutative.
sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)']) sage: G.is_commutative() False sage: G = PermutationGroup(['(1,2,3)(4,5)']) sage: G.is_commutative() True
self) |
Return the largest point moved by a permutation in this group.
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]]) sage: G.largest_moved_point() 4 sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]]) sage: G.largest_moved_point() 10
self) |
Return list of all elements of this group.
sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]]) sage: G.list() [(), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3)]
self) |
Return the number of elements of this group.
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]]) sage: G.order() 12
self) |
Return a random element of this group.
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]]) sage: G.random() ## random output (1, 3)(4, 5)
self) |
Return the smallest point moved by a permutation in this group.
sage: G = PermutationGroup([[(3,4)], [(2,3,4)]]) sage: G.smallest_moved_point() 2 sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]]) sage: G.smallest_moved_point() 1
Special Functions: __call__,
__cmp__,
__contains__,
__iter__,
_gap_init_,
_latex_,
_magma_init_,
_repr_
self, x) |
Coerce x into this permutation group.
sage: G = PermutationGroup([(1,2,3,4)]) sage: G([(1,3), (2,4)]) (1,3)(2,4) sage: G(G.0^3) (1,4,3,2) sage: G(1) () sage: G((1,4,3,2)) (1,4,3,2) sage: G([(1,2)]) Traceback (most recent call last): ... TypeError: permutation (1,2) not in Permutation Group with generators [(1,2,3,4)]
self, right) |
Compare self and right.
The ordering is whatever it is in Gap.
sage: G1 = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]]) sage: G2 = PermutationGroup([[(1,2,3),(4,5)]]) sage: G1 > G2 True sage: G1 < G2 False
self, item) |
Returns boolean value of "item in self"
self) |
Return an iterator over the elements of this group.
sage: G = PermutationGroup([[(1,2,3)], [(1,2)]]) sage: [a for a in G] [(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
Class: PermutationGroup_subgroup
self, ambient, gens, [from_group=True], [check=False]) |
sage: G = CyclicPermutationGroup(4) sage: gens = G.gens() sage: H = DihedralGroup(4) sage: PermutationGroup_subgroup(H,list(gens)) Subgroup of Dihedral group of order 8 as a permutation group generated by [(1,2,3,4)] sage: K=PermutationGroup_subgroup(H,list(gens)) sage: K.list() [(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)] sage: K.ambient_group() Dihedral group of order 8 as a permutation group sage: K.gens() [(1,2,3,4)]
Functions: ambient_group,
gens
self) |
Return the ambient group related to self.
self) |
Return the generators for this subgroup.
Special Functions: __cmp__,
_latex_,
_repr_
self, other) |
Compare self and other. If self and other are in a common ambient group, then self <= other precisely if self is contained in other.
sage: G = CyclicPermutationGroup(4) sage: gens = G.gens() sage: H = DihedralGroup(4) sage: PermutationGroup_subgroup(H,list(gens)) Subgroup of Dihedral group of order 8 as a permutation group generated by [(1,2,3,4)] sage: K=PermutationGroup_subgroup(H,list(gens)) sage: G<K False sage: G>K False
self) |
Return latex representation of this group.
Class: PGL
self, n, q) |
INPUT: n -- positive integer; the degree q -- prime power; the size of the ground field OUTPUT: PGL(n,q)
sage: G = PGL(2,3); G Permutation Group with generators [(3,4), (1,2,4)] sage: print G The projective general linear group of degree 2 over Finite Field of size 3 sage: G.base_ring() Finite Field of size 3 sage: G.order() 24
Functions: base_ring
Special Functions: __str__
Class: PSL
self, n, q) |
INPUT: n -- positive integer; the degree q -- prime power; the size of the ground field OUTPUT: PSL(n,q)
sage: G = PSL(2,3); G Permutation Group with generators [(2,3,4), (1,2)(3,4)] sage: G.order() 12 sage: G.base_ring() Finite Field of size 3 sage: print G The projective special linear group of degree 2 over Finite Field of size 3
Functions: base_ring
Special Functions: __str__
Class: PSP
self, n, q) |
INPUT: n -- positive integer; the degree q -- prime power; the size of the ground field OUTPUT: PSp(n,q)
sage: G = PSp(2,3); G Permutation Group with generators [(2,3,4), (1,2)(3,4)] sage: G.order() 12 sage: G = PSp(4,3); G Permutation Group with generators [(3,4)(6,7)(9,10)(12,13)(17,20)(18,21)(19,22)(23,32)(24,33)(25,34)(26,38)(2 7, 39)(28,40)(29,35)(30,36)(31,37), (1,5,14,17,27,22,19,36,3)(2,6,32)(4,7,23,20,37,13,16,26,40)(8,24,29,30,39,1 0, 33,11,34)(9,15,35)(12,25,38)(21,28,31)] sage: G.order() 25920 sage: print G The projective symplectic linear group of degree 4 over Finite Field of size 3 sage: G.base_ring() Finite Field of size 3
Functions: base_ring
Special Functions: __str__
Class: PSp
self, n, q) |
INPUT: n -- positive integer; the degree q -- prime power; the size of the ground field OUTPUT: PSp(n,q)
sage: G = PSp(2,3); G Permutation Group with generators [(2,3,4), (1,2)(3,4)] sage: G.order() 12 sage: G = PSp(4,3); G Permutation Group with generators [(3,4)(6,7)(9,10)(12,13)(17,20)(18,21)(19,22)(23,32)(24,33)(25,34)(26,38)(2 7, 39)(28,40)(29,35)(30,36)(31,37), (1,5,14,17,27,22,19,36,3)(2,6,32)(4,7,23,20,37,13,16,26,40)(8,24,29,30,39,1 0, 33,11,34)(9,15,35)(12,25,38)(21,28,31)] sage: G.order() 25920 sage: print G The projective symplectic linear group of degree 4 over Finite Field of size 3 sage: G.base_ring() Finite Field of size 3
Functions: base_ring
Special Functions: __str__
Class: PSU
self, n, q) |
INPUT: n -- positive integer; the degree q -- prime power; the size of the ground field OUTPUT: PSU(n,q)
sage: PSU(2,3) Permutation Group with generators [(2,9,6)(3,8,10)(4,7,5), (1,2)(5,10)(6,9)(7,8)] sage: print PSU(2,3) The projective special unitary group of degree 2 over Finite Field of size 3 (matrix representation has coefficients in Finite Field in a of size 3^2)
Functions: base_ring,
field_of_definition
Special Functions: __str__
Class: SymmetricGroup
self, n) |
INPUT: n -- a positive integer
sage: G = SymmetricGroup(8) sage: G.order() 40320 sage: G Symmetric group of order 8! as a permutation group sage: G.degree() 8
sage: S8 = SymmetricGroup(8) sage: loads(dumps(S8)) == S8 True
Special Functions: _repr_
Class: TransitiveGroup
self, d, n) |
INPUT: d -- positive integer; the degree n -- positive integer; the number OUTPUT: the n-th transitive group of degree d
sage: G = TransitiveGroup(1,1); G Transitive group number 1 of degree 1 sage: G = TransitiveGroup(5, 2); G # requires optional database_gap Transitive group number 2 of degree 5 sage: G.gens() # requires optional database_gap ((1,2,3,4,5), (1,4)(2,3))
sage: loads(G.dumps()) == G # requires optional database_gap True
Special Functions: _repr_
See About this document... for information on suggesting changes.