Permutation group elements

Permutation group elements

AUTHORS:

  • David Joyner (2006-02)
  • David Joyner (2006-03): word problem method and reorganization
  • Robert Bradshaw (2007-11): convert to Cython

EXAMPLES: 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=cube.gens()[0]
sage: B=cube.gens()[1]
sage: L=cube.gens()[2]
sage: R=cube.gens()[3]
sage: U=cube.gens()[4]
sage: D=cube.gens()[5]
sage: cube.order()
43252003274489856000
sage: F.order()
4

The interested user may wish to explore the following commands: move = cube.random_element() and time word_problem([F,B,L,R,U,D], move, False). This typically takes about 5 minutes (on a 2 Ghz machine) and outputs a word (‘solving’ the cube in the position move) with about 60 terms or so.

OTHER EXAMPLES: 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: sage.structure.element.MultiplicativeGroupElement

An element of a permutation group.

EXAMPLES:

sage: G = PermutationGroup(['(1,2,3)(4,5)'])
sage: 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
conjugacy_class()

Return the conjugacy class of self.

EXAMPLES:

sage: D = DihedralGroup(5)
sage: g = D((1,3,5,2,4))
sage: g.conjugacy_class()
Conjugacy class of (1,3,5,2,4) in Dihedral group of order 10 as a permutation group
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')]
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()

Returns 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])
<type 'int'>
sage: x = G([2,1]); x
(1,2)
sage: x.dict()
{1: 2, 2: 1, 3: 3, 4: 4}
domain()

Returns 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])
<type 'int'>
sage: x = G([2,1]); x
(1,2)
sage: x.domain()
[2, 1, 3, 4]

TESTS:

sage: S = SymmetricGroup(0)
sage: x = S.one(); x
()
sage: x.domain()
[]
has_descent(i, side='right', positive=False)

INPUT:

  • i: an element of the index set
  • side: “left” or “right” (default: “right”)
  • positive: a boolean (default: False)

Returns whether self has a left (resp. right) descent at position i. If positive is True, 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 position i if self(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()

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

Returns deg x 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]
orbit(n, sorted=True)

Returns 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']
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.order()
6

TESTS:

sage: prod(primes(150))
1492182350939279320058875736615841068547583863326864530410
sage: L = [tuple(range(sum(primes(p))+1, sum(primes(p))+1+p)) for p in primes(150)]
sage: PermutationGroupElement(L).order()
1492182350939279320058875736615841068547583863326864530410
sign()

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

G and H are permutation groups, g in G, H is a subgroup of G generated by a list (words) of elements of G. If g is in H, return the expression for g as a word in the elements of (words).

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” and “PreImagesRepresentative”.

EXAMPLE:

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.groups.perm_gps.permgroup_element.is_PermutationGroupElement(x)

Returns True if x is a PermutationGroupElement.

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)

Returns a PermutationGroupElement given the permutation group G and the permutation x 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)

Returns a PermutationGroupElement given the permutation group G, the permutation x in list notation, and the domain domain 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)
sage.groups.perm_gps.permgroup_element.standardize_generator(g, convert_dict=None)

Standardizes the input for permutation group elements to a list of tuples. This was factored out of the PermutationGroupElement.__init__ since PermutationGroup_generic.__init__ needs to do the same computation in order to compute the domain of a group when it’s not explicitly specified.

INPUT:

  • g - a list, tuple, string, GapElement, PermutationGroupElement, Permutation
  • convert_dict - (optional) a dictionary used to convert the points to a number compatible with GAP.

OUTPUT:

The permutation in as a list of cycles.

EXAMPLES:

sage: from sage.groups.perm_gps.permgroup_element import standardize_generator
sage: standardize_generator('(1,2)')
[(1, 2)]

sage: p = PermutationGroupElement([(1,2)])
sage: standardize_generator(p)
[(1, 2)]
sage: standardize_generator(p._gap_())
[(1, 2)]
sage: standardize_generator((1,2))
[(1, 2)]
sage: standardize_generator([(1,2)])
[(1, 2)]
sage: standardize_generator(Permutation([2,1,3]))
[(1, 2), (3,)]
sage: d = {'a': 1, 'b': 2}
sage: p = SymmetricGroup(['a', 'b']).gen(0); p
('a','b')
sage: standardize_generator(p, convert_dict=d)
[(1, 2)]
sage: standardize_generator(p._gap_(), convert_dict=d)
[(1, 2)]
sage: standardize_generator(('a','b'), convert_dict=d)
[(1, 2)]
sage: standardize_generator([('a','b')], convert_dict=d)
[(1, 2)]
sage.groups.perm_gps.permgroup_element.string_to_tuples(g)

EXAMPLES:

sage: from sage.groups.perm_gps.permgroup_element import string_to_tuples
sage: string_to_tuples('(1,2,3)')
[(1, 2, 3)]
sage: string_to_tuples('(1,2,3)(4,5)')
[(1, 2, 3), (4, 5)]
sage: string_to_tuples(' (1,2, 3) (4,5)')
[(1, 2, 3), (4, 5)]
sage: string_to_tuples('(1,2)(3)')
[(1, 2), (3,)]

Previous topic

“Named” Permutation groups (such as the symmetric group, S_n)

Next topic

Permutation group homomorphisms

This Page