Permutation group elements#
AUTHORS:
David Joyner (2006-02)
David Joyner (2006-03): word problem method and reorganization
Robert Bradshaw (2007-11): convert to Cython
Sebastian Oehms (2018-11): Added
gap()
as synonym to_gap_()
(compatibility to libgap framework, see github issue #26750)Sebastian Oehms (2019-02): Implemented
gap()
properly (github issue #27234)
There are several ways to define a permutation group element:
Define a permutation group \(G\), then use
G.gens()
and multiplication*
to construct elements.Define a permutation group \(G\), then use, e.g.,
G([(1,2),(3,4,5)])
to construct an element of the group. You could also useG('(1,2)(3,4,5)')
Use, e.g.,
PermutationGroupElement([(1,2),(3,4,5)])
orPermutationGroupElement('(1,2)(3,4,5)')
to make a permutation group element with parent \(S_5\).
EXAMPLES:
We illustrate construction of permutation using several different methods.
First we construct elements by multiplying together generators for a group:
sage: G = PermutationGroup(['(1,2)(3,4)', '(3,4,5,6)'], canonicalize=False)
sage: s = G.gens()
sage: s[0]
(1,2)(3,4)
sage: s[1]
(3,4,5,6)
sage: s[0]*s[1]
(1,2)(3,5,6)
sage: (s[0]*s[1]).parent()
Permutation Group with generators [(1,2)(3,4), (3,4,5,6)]
Next we illustrate creation of a permutation using coercion into an already-created group:
sage: g = G([(1,2),(3,5,6)])
sage: g
(1,2)(3,5,6)
sage: g.parent()
Permutation Group with generators [(1,2)(3,4), (3,4,5,6)]
sage: g == s[0]*s[1]
True
We can also use a string or one-line notation to specify the permutation:
sage: h = G('(1,2)(3,5,6)')
sage: i = G([2,1,5,4,6,3])
sage: g == h == i
True
The Rubik’s cube group:
sage: f = [(17,19,24,22),(18,21,23,20),( 6,25,43,16),( 7,28,42,13),( 8,30,41,11)]
sage: b = [(33,35,40,38),(34,37,39,36),( 3, 9,46,32),( 2,12,47,29),( 1,14,48,27)]
sage: l = [( 9,11,16,14),(10,13,15,12),( 1,17,41,40),( 4,20,44,37),( 6,22,46,35)]
sage: r = [(25,27,32,30),(26,29,31,28),( 3,38,43,19),( 5,36,45,21),( 8,33,48,24)]
sage: u = [( 1, 3, 8, 6),( 2, 5, 7, 4),( 9,33,25,17),(10,34,26,18),(11,35,27,19)]
sage: d = [(41,43,48,46),(42,45,47,44),(14,22,30,38),(15,23,31,39),(16,24,32,40)]
sage: cube = PermutationGroup([f, b, l, r, u, d])
sage: F, B, L, R, U, D = cube.gens()
sage: cube.order()
43252003274489856000
sage: F.order()
4
We create element of a permutation group of large degree:
sage: G = SymmetricGroup(30)
sage: s = G(srange(30,0,-1)); s
(1,30)(2,29)(3,28)(4,27)(5,26)(6,25)(7,24)(8,23)(9,22)(10,21)(11,20)(12,19)(13,18)(14,17)(15,16)
- class sage.groups.perm_gps.permgroup_element.PermutationGroupElement#
Bases:
MultiplicativeGroupElement
An element of a permutation group.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)']); G Permutation Group with generators [(1,2,3)(4,5)] sage: g = G.random_element() sage: g in G True sage: g = G.gen(0); g (1,2,3)(4,5) sage: print(g) (1,2,3)(4,5) sage: g*g (1,3,2) sage: g**(-1) (1,3,2)(4,5) sage: g**2 (1,3,2) sage: G = PermutationGroup([(1,2,3)]) sage: g = G.gen(0); g (1,2,3) sage: g.order() 3
This example illustrates how permutations act on multivariate polynomials.
sage: R = PolynomialRing(RationalField(), 5, ["x","y","z","u","v"]) sage: x, y, z, u, v = R.gens() sage: f = x**2 - y**2 + 3*z**2 sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)']) sage: sigma = G.gen(0) sage: f * sigma 3*x^2 + y^2 - z^2
- cycle_string(singletons=False)#
Return string representation of this permutation.
EXAMPLES:
sage: g = PermutationGroupElement([(1,2,3),(4,5)]) sage: g.cycle_string() '(1,2,3)(4,5)' sage: g = PermutationGroupElement([3,2,1]) sage: g.cycle_string(singletons=True) '(1,3)(2)'
- cycle_tuples(singletons=False)#
Return
self
as a list of disjoint cycles, represented as tuples rather than permutation group elements.INPUT:
singletons
– boolean (default:False
) whether or not consider the cycle that correspond to fixed point
EXAMPLES:
sage: p = PermutationGroupElement('(2,6)(4,5,1)') sage: p.cycle_tuples() [(1, 4, 5), (2, 6)] sage: p.cycle_tuples(singletons=True) [(1, 4, 5), (2, 6), (3,)]
EXAMPLES:
sage: S = SymmetricGroup(4) sage: S.gen(0).cycle_tuples() [(1, 2, 3, 4)]
sage: S = SymmetricGroup(['a','b','c','d']) sage: S.gen(0).cycle_tuples() [('a', 'b', 'c', 'd')] sage: S([('a', 'b'), ('c', 'd')]).cycle_tuples() [('a', 'b'), ('c', 'd')]
- cycle_type(singletons=True, as_list=False)#
Return the partition that gives the cycle type of
self
as an element of its parent.INPUT:
g
– an element of the permutation groupself.parent()
singletons
–True
orFalse
depending on whether or not trivial cycles should be counted (default:True
)as_list
–True
orFalse
depending on whether the cycle type should be returned as alist
or as aPartition
(default:False
)
OUTPUT:
A
Partition
, orlist
ifis_list
isTrue
, giving the cycle type ofself
If speed is a concern, then
as_list=True
should be used.EXAMPLES:
sage: # needs sage.combinat sage: G = DihedralGroup(3) sage: [g.cycle_type() for g in G] [[1, 1, 1], [3], [3], [2, 1], [2, 1], [2, 1]] sage: PermutationGroupElement('(1,2,3)(4,5)(6,7,8)').cycle_type() [3, 3, 2] sage: G = SymmetricGroup(3); G('(1,2)').cycle_type() [2, 1] sage: G = SymmetricGroup(4); G('(1,2)').cycle_type() [2, 1, 1] sage: G = SymmetricGroup(4); G('(1,2)').cycle_type(singletons=False) [2] sage: G = SymmetricGroup(4); G('(1,2)').cycle_type(as_list=False) [2, 1, 1]
- cycles()#
Return
self
as a list of disjoint cycles.EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5,6,7)']) sage: g = G.0 sage: g.cycles() [(1,2,3), (4,5,6,7)] sage: a, b = g.cycles() sage: a(1), b(1) (2, 1)
- dict()#
Return a dictionary associating each element of the domain with its image.
EXAMPLES:
sage: G = SymmetricGroup(4) sage: g = G((1,2,3,4)); g (1,2,3,4) sage: v = g.dict(); v {1: 2, 2: 3, 3: 4, 4: 1} sage: type(v[1]) <... 'int'> sage: x = G([2,1]); x (1,2) sage: x.dict() {1: 2, 2: 1, 3: 3, 4: 4}
- domain()#
Return the domain of
self
.EXAMPLES:
sage: G = SymmetricGroup(4) sage: x = G([2,1,4,3]); x (1,2)(3,4) sage: v = x.domain(); v [2, 1, 4, 3] sage: type(v[0]) <... 'int'> sage: x = G([2,1]); x (1,2) sage: x.domain() [2, 1, 3, 4]
- gap()#
Return
self
as a libgap element.EXAMPLES:
sage: S = SymmetricGroup(4) sage: p = S('(2,4)') sage: p_libgap = libgap(p) sage: p_libgap.Order() 2 sage: S(p_libgap) == p True sage: # needs sage.rings.finite_rings sage: P = PGU(8,2) sage: p, q = P.gens() sage: p_libgap = p.gap()
- has_descent(i, side='right', positive=False)#
INPUT:
i
– an element of the index setside
–"left"
or"right"
(default:"right"
)positive
– a boolean (default:False
)
Returns whether
self
has a left (resp. right) descent at positioni
. Ifpositive
isTrue
, then test for a non descent instead.Beware that, since permutations are acting on the right, the meaning of descents is the reverse of the usual convention. Hence,
self
has a left descent at positioni
ifself(i) > self(i+1)
.EXAMPLES:
sage: S = SymmetricGroup([1,2,3]) sage: S.one().has_descent(1) False sage: S.one().has_descent(2) False sage: s = S.simple_reflections() sage: x = s[1]*s[2] sage: x.has_descent(1, side="right") False sage: x.has_descent(2, side="right") True sage: x.has_descent(1, side="left") True sage: x.has_descent(2, side="left") False sage: S._test_has_descent()
The symmetric group acting on a set not of the form \((1,\dots,n)\) is also supported:
sage: S = SymmetricGroup([2,4,1]) sage: s = S.simple_reflections() sage: x = s[2]*s[4] sage: x.has_descent(4) True sage: S._test_has_descent()
- inverse()#
Return the inverse permutation.
OUTPUT:
For an element of a permutation group, this method returns the inverse element, which is both the inverse function and the inverse as an element of a group.
EXAMPLES:
sage: s = PermutationGroupElement("(1,2,3)(4,5)") sage: s.inverse() (1,3,2)(4,5) sage: A = AlternatingGroup(4) sage: t = A("(1,2,3)") sage: t.inverse() (1,3,2)
There are several ways (syntactically) to get an inverse of a permutation group element.
sage: s = PermutationGroupElement("(1,2,3,4)(6,7,8)") sage: s.inverse() == s^-1 True sage: s.inverse() == ~s True
- matrix()#
Return a deg \(\times\) deg permutation matrix associated to the permutation
self
.EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)']) sage: g = G.gen(0) sage: g.matrix() [0 1 0 0 0] [0 0 1 0 0] [1 0 0 0 0] [0 0 0 0 1] [0 0 0 1 0]
- multiplicative_order()#
Return the order of this group element, which is the smallest positive integer \(n\) for which \(g^n = 1\).
EXAMPLES:
sage: s = PermutationGroupElement('(1,2)(3,5,6)') sage: s.multiplicative_order() 6
order()
is just an alias formultiplicative_order()
:sage: s.order() 6
- orbit(n, sorted=True)#
Return the orbit of the integer \(n\) under this group element, as a sorted list.
EXAMPLES:
sage: G = PermutationGroup(['(1,2,3)(4,5)']) sage: g = G.gen(0) sage: g.orbit(4) [4, 5] sage: g.orbit(3) [1, 2, 3] sage: g.orbit(10) [10]
sage: s = SymmetricGroup(['a', 'b']).gen(0); s ('a','b') sage: s.orbit('a') ['a', 'b']
- sign()#
Return the sign of
self
, which is \((-1)^{s}\), where \(s\) is the number of swaps.EXAMPLES:
sage: s = PermutationGroupElement('(1,2)(3,5,6)') sage: s.sign() -1
ALGORITHM: Only even cycles contribute to the sign, thus
\[sign(sigma) = (-1)^{\sum_c len(c)-1}\]where the sum is over cycles in self.
- tuple()#
Return tuple of images of the domain under
self
.EXAMPLES:
sage: G = SymmetricGroup(5) sage: s = G([2,1,5,3,4]) sage: s.tuple() (2, 1, 5, 3, 4) sage: S = SymmetricGroup(['a', 'b']) sage: S.gen().tuple() ('b', 'a')
- word_problem(words, display=True, as_list=False)#
Try to solve the word problem for
self
.INPUT:
words
– a list of elements of the ambient group, generating a subgroupdisplay
– boolean (defaultTrue
) whether to display additional informationas_list
– boolean (defaultFalse
) whether to return the result as a list of pairs (generator, exponent)
OUTPUT:
a pair of strings, both representing the same word
or
a list of pairs representing the word, each pair being (generator as a string, exponent as an integer)
Let \(G\) be the ambient permutation group, containing the given element \(g\). Let \(H\) be the subgroup of \(G\) generated by the list
words
of elements of \(G\). If \(g\) is in \(H\), this function returns an expression for \(g\) as a word in the elements ofwords
and their inverses.This function does not solve the word problem in Sage. Rather it pushes it over to GAP, which has optimized algorithms for the word problem. Essentially, this function is a wrapper for the GAP functions
EpimorphismFromFreeGroup
andPreImagesRepresentative
.EXAMPLES:
sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]], canonicalize=False) sage: g1, g2 = G.gens() sage: h = g1^2*g2*g1 sage: h.word_problem([g1,g2], False) ('x1^2*x2^-1*x1', '(1,2,3)(4,5)^2*(3,4)^-1*(1,2,3)(4,5)') sage: h.word_problem([g1,g2]) x1^2*x2^-1*x1 [['(1,2,3)(4,5)', 2], ['(3,4)', -1], ['(1,2,3)(4,5)', 1]] ('x1^2*x2^-1*x1', '(1,2,3)(4,5)^2*(3,4)^-1*(1,2,3)(4,5)') sage: h.word_problem([g1,g2], False, as_list=True) [['(1,2,3)(4,5)', 2], ['(3,4)', -1], ['(1,2,3)(4,5)', 1]]
- class sage.groups.perm_gps.permgroup_element.SymmetricGroupElement#
Bases:
PermutationGroupElement
An element of the symmetric group.
- absolute_length()#
Return the absolute length of
self
.The absolute length is the size minus the number of its disjoint cycles. Alternatively, it is the length of the shortest expression of the element as a product of reflections.
See also
absolute_le()
EXAMPLES:
sage: S = SymmetricGroup(3) sage: [x.absolute_length() for x in S] # needs sage.combinat [0, 2, 2, 1, 1, 1]
- has_left_descent(i)#
Return whether \(i\) is a left descent of
self
.EXAMPLES:
sage: W = SymmetricGroup(4) sage: w = W.from_reduced_word([1,3,2,1]) sage: [i for i in W.index_set() if w.has_left_descent(i)] [1, 3]
- sage.groups.perm_gps.permgroup_element.is_PermutationGroupElement(x)#
Return
True
ifx
is aPermutationGroupElement
.EXAMPLES:
sage: p = PermutationGroupElement([(1,2),(3,4,5)]) sage: from sage.groups.perm_gps.permgroup_element import is_PermutationGroupElement sage: is_PermutationGroupElement(p) True
- sage.groups.perm_gps.permgroup_element.make_permgroup_element(G, x)#
Return a
PermutationGroupElement
given the permutation groupG
and the permutationx
in list notation.This is function is used when unpickling old (pre-domain) versions of permutation groups and their elements. This now does a bit of processing and calls
make_permgroup_element_v2()
which is used in unpickling the current PermutationGroupElements.EXAMPLES:
sage: from sage.groups.perm_gps.permgroup_element import make_permgroup_element sage: S = SymmetricGroup(3) sage: make_permgroup_element(S, [1,3,2]) (2,3)
- sage.groups.perm_gps.permgroup_element.make_permgroup_element_v2(G, x, domain)#
Return a
PermutationGroupElement
given the permutation groupG
, the permutationx
in list notation, and the domaindomain
of the permutation group.This is function is used when unpickling permutation groups and their elements.
EXAMPLES:
sage: from sage.groups.perm_gps.permgroup_element import make_permgroup_element_v2 sage: S = SymmetricGroup(3) sage: make_permgroup_element_v2(S, [1,3,2], S.domain()) (2,3)