Colored Permutations#

Todo

Much of the colored permutations (and element) class can be generalized to $$G \wr S_n$$

class sage.combinat.colored_permutations.ColoredPermutation(parent, colors, perm)[source]#

A colored permutation.

colors()[source]#

Return the colors of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: x = s1*s2*t
sage: x.colors()
[1, 0, 0]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> s1,s2,t = C.gens()
>>> x = s1*s2*t
>>> x.colors()
[1, 0, 0]
has_left_descent(i)[source]#

Return True if i is a left descent of self.

Let $$p = ((s_1, \ldots s_n), \sigma)$$ be a colored permutation. We say $$p$$ has a left $$n$$-descent if $$s_n > 0$$. If $$i < n$$, then we say $$p$$ has a left $$i$$-descent if either

• $$s_i \neq 0, s_{i+1} = 0$$ and $$\sigma_i < \sigma_{i+1}$$ or

• $$s_i = s_{i+1}$$ and $$\sigma_i > \sigma_{i+1}$$.

This notion of a left $$i$$-descent is done in order to recursively construct $$w(p) = \sigma_i w(\sigma_i^{-1} p)$$, where $$w(p)$$ denotes a reduced word of $$p$$.

EXAMPLES:

sage: C = ColoredPermutations(2, 4)
sage: s1,s2,s3,s4 = C.gens()
sage: x = s4*s1*s2*s3*s4
sage: [x.has_left_descent(i) for i in C.index_set()]
[True, False, False, True]

sage: C = ColoredPermutations(1, 5)
sage: s1,s2,s3,s4 = C.gens()
sage: x = s4*s1*s2*s3*s4
sage: [x.has_left_descent(i) for i in C.index_set()]
[True, False, False, True]

sage: C = ColoredPermutations(3, 3)
sage: x = C([[2,1,0],[3,1,2]])
sage: [x.has_left_descent(i) for i in C.index_set()]
[False, True, False]

sage: C = ColoredPermutations(4, 4)
sage: x = C([[2,1,0,1],[3,2,4,1]])
sage: [x.has_left_descent(i) for i in C.index_set()]
[False, True, False, True]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(2), Integer(4))
>>> s1,s2,s3,s4 = C.gens()
>>> x = s4*s1*s2*s3*s4
>>> [x.has_left_descent(i) for i in C.index_set()]
[True, False, False, True]

>>> C = ColoredPermutations(Integer(1), Integer(5))
>>> s1,s2,s3,s4 = C.gens()
>>> x = s4*s1*s2*s3*s4
>>> [x.has_left_descent(i) for i in C.index_set()]
[True, False, False, True]

>>> C = ColoredPermutations(Integer(3), Integer(3))
>>> x = C([[Integer(2),Integer(1),Integer(0)],[Integer(3),Integer(1),Integer(2)]])
>>> [x.has_left_descent(i) for i in C.index_set()]
[False, True, False]

>>> C = ColoredPermutations(Integer(4), Integer(4))
>>> x = C([[Integer(2),Integer(1),Integer(0),Integer(1)],[Integer(3),Integer(2),Integer(4),Integer(1)]])
>>> [x.has_left_descent(i) for i in C.index_set()]
[False, True, False, True]
length()[source]#

Return the length of self in generating reflections.

This is the minimal numbers of generating reflections needed to obtain self.

EXAMPLES:

sage: C = ColoredPermutations(3, 3)
sage: x = C([[2,1,0],[3,1,2]])
sage: x.length()
7

sage: C = ColoredPermutations(4, 4)
sage: x = C([[2,1,0,1],[3,2,4,1]])
sage: x.length()
12
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(3), Integer(3))
>>> x = C([[Integer(2),Integer(1),Integer(0)],[Integer(3),Integer(1),Integer(2)]])
>>> x.length()
7

>>> C = ColoredPermutations(Integer(4), Integer(4))
>>> x = C([[Integer(2),Integer(1),Integer(0),Integer(1)],[Integer(3),Integer(2),Integer(4),Integer(1)]])
>>> x.length()
12
one_line_form()[source]#

Return the one line form of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: x = s1*s2*t
sage: x
[[1, 0, 0], [3, 1, 2]]
sage: x.one_line_form()
[(1, 3), (0, 1), (0, 2)]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> s1,s2,t = C.gens()
>>> x = s1*s2*t
>>> x
[[1, 0, 0], [3, 1, 2]]
>>> x.one_line_form()
[(1, 3), (0, 1), (0, 2)]
permutation()[source]#

Return the permutation of self.

This is obtained by forgetting the colors.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: x = s1*s2*t
sage: x.permutation()
[3, 1, 2]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> s1,s2,t = C.gens()
>>> x = s1*s2*t
>>> x.permutation()
[3, 1, 2]
reduced_word()[source]#

Return a word in the simple reflections to obtain self.

EXAMPLES:

sage: C = ColoredPermutations(3, 3)
sage: x = C([[2,1,0],[3,1,2]])
sage: x.reduced_word()
[2, 1, 3, 2, 1, 3, 3]

sage: C = ColoredPermutations(4, 4)
sage: x = C([[2,1,0,1],[3,2,4,1]])
sage: x.reduced_word()
[2, 1, 4, 3, 2, 1, 4, 3, 2, 4, 4, 3]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(3), Integer(3))
>>> x = C([[Integer(2),Integer(1),Integer(0)],[Integer(3),Integer(1),Integer(2)]])
>>> x.reduced_word()
[2, 1, 3, 2, 1, 3, 3]

>>> C = ColoredPermutations(Integer(4), Integer(4))
>>> x = C([[Integer(2),Integer(1),Integer(0),Integer(1)],[Integer(3),Integer(2),Integer(4),Integer(1)]])
>>> x.reduced_word()
[2, 1, 4, 3, 2, 1, 4, 3, 2, 4, 4, 3]
to_matrix()[source]#

Return a matrix of self.

The colors are mapped to roots of unity.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: x = s1*s2*t*s2; x.one_line_form()
[(1, 2), (0, 1), (0, 3)]
sage: M = x.to_matrix(); M                                                  # needs sage.rings.number_field
[    0     1     0]
[zeta4     0     0]
[    0     0     1]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> s1,s2,t = C.gens()
>>> x = s1*s2*t*s2; x.one_line_form()
[(1, 2), (0, 1), (0, 3)]
>>> M = x.to_matrix(); M                                                  # needs sage.rings.number_field
[    0     1     0]
[zeta4     0     0]
[    0     0     1]

The matrix multiplication is in the opposite order:

sage: M == s2.to_matrix()*t.to_matrix()*s2.to_matrix()*s1.to_matrix()       # needs sage.rings.number_field
True
>>> from sage.all import *
>>> M == s2.to_matrix()*t.to_matrix()*s2.to_matrix()*s1.to_matrix()       # needs sage.rings.number_field
True
class sage.combinat.colored_permutations.ColoredPermutations(m, n)[source]#

Bases: ShephardToddFamilyGroup

The group of $$m$$-colored permutations on $$\{1, 2, \ldots, n\}$$.

Let $$S_n$$ be the symmetric group on $$n$$ letters and $$C_m$$ be the cyclic group of order $$m$$. The $$m$$-colored permutation group on $$n$$ letters is given by $$P_n^m = C_m \wr S_n$$. This is also the complex reflection group $$G(m, 1, n)$$.

We define our multiplication by

$((s_1, \ldots s_n), \sigma) \cdot ((t_1, \ldots, t_n), \tau) = ((s_1 t_{\sigma(1)}, \ldots, s_n t_{\sigma(n)}), \tau \sigma).$

EXAMPLES:

sage: C = ColoredPermutations(4, 3); C
4-colored permutations of size 3
sage: s1,s2,t = C.gens()
sage: (s1, s2, t)
([[0, 0, 0], [2, 1, 3]], [[0, 0, 0], [1, 3, 2]], [[0, 0, 1], [1, 2, 3]])
sage: s1*s2
[[0, 0, 0], [3, 1, 2]]
sage: s1*s2*s1 == s2*s1*s2
True
sage: t^4 == C.one()
True
sage: s2*t*s2
[[0, 1, 0], [1, 2, 3]]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3)); C
4-colored permutations of size 3
>>> s1,s2,t = C.gens()
>>> (s1, s2, t)
([[0, 0, 0], [2, 1, 3]], [[0, 0, 0], [1, 3, 2]], [[0, 0, 1], [1, 2, 3]])
>>> s1*s2
[[0, 0, 0], [3, 1, 2]]
>>> s1*s2*s1 == s2*s1*s2
True
>>> t**Integer(4) == C.one()
True
>>> s2*t*s2
[[0, 1, 0], [1, 2, 3]]

We can also create a colored permutation by passing an iterable consisting of tuples consisting of (color, element):

sage: x = C([(2,1), (3,3), (3,2)]); x
[[2, 3, 3], [1, 3, 2]]
>>> from sage.all import *
>>> x = C([(Integer(2),Integer(1)), (Integer(3),Integer(3)), (Integer(3),Integer(2))]); x
[[2, 3, 3], [1, 3, 2]]

or a list of colors and a permutation:

sage: C([[3,3,1], [1,3,2]])
[[3, 3, 1], [1, 3, 2]]
sage: C(([3,3,1], [1,3,2]))
[[3, 3, 1], [1, 3, 2]]
>>> from sage.all import *
>>> C([[Integer(3),Integer(3),Integer(1)], [Integer(1),Integer(3),Integer(2)]])
[[3, 3, 1], [1, 3, 2]]
>>> C(([Integer(3),Integer(3),Integer(1)], [Integer(1),Integer(3),Integer(2)]))
[[3, 3, 1], [1, 3, 2]]

There is also the natural lift from permutations:

sage: P = Permutations(3)
sage: C(P.an_element())
[[0, 0, 0], [3, 1, 2]]
>>> from sage.all import *
>>> P = Permutations(Integer(3))
>>> C(P.an_element())
[[0, 0, 0], [3, 1, 2]]

A colored permutation:

sage: C(C.an_element()) == C.an_element()
True
>>> from sage.all import *
>>> C(C.an_element()) == C.an_element()
True

REFERENCES:

class sage.combinat.colored_permutations.ShephardToddFamilyGroup(m, p, n)[source]#

Bases: UniqueRepresentation, Parent

The Shephard-Todd family complex reflection group $$G(m, p, n)$$ realized as a subgroup of colored permutations.

A general complex reflection group is a subgroup of $$GL(V)$$, where $$V$$ is a $$\CC$$ vector space, that is generated by reflections, diagonalizable matrices with at most one eigenvalue not equal to $$1$$. The group of colored permutations $$G(m, 1, n)$$ are the generalized permutation matrices whose entries are $$m$$-th roots of unity. For $$p | m$$, the group $$G(m, p, n)$$ is the index $$p$$ subgroup such that the product of the entries is a $$m/p$$-th root of unity.

By the (Chevalley-)Shephard-Todd classification of irreducible finite complex reflection groups, the groups $$G(m, p, n)$$ (with $$G(2, 2, 2)$$ being exceptionally reducible since it is the Klein four group) form the only infinite family with an additional 34 exceptional groups $$G_k$$, where $$4 \leq k \leq 37$$. To avoid ambiguities, we refer to $$G(m, p, n)$$ as the Shephard-Todd family complex reflection group.

INPUT:

• m – positive integer

• p – positive integer dividing m

• n – positive integer

REFERENCES:

EXAMPLES:

sage: groups.misc.ShephardToddFamily(6, 1, 4)
6-colored permutations of size 4
sage: groups.misc.ShephardToddFamily(6, 2, 4)
Complex reflection group G(6, 2, 4)
sage: groups.misc.ShephardToddFamily(6, 3, 4)
Complex reflection group G(6, 3, 4)
sage: groups.misc.ShephardToddFamily(6, 6, 4)
Complex reflection group G(6, 6, 4)
>>> from sage.all import *
>>> groups.misc.ShephardToddFamily(Integer(6), Integer(1), Integer(4))
6-colored permutations of size 4
>>> groups.misc.ShephardToddFamily(Integer(6), Integer(2), Integer(4))
Complex reflection group G(6, 2, 4)
>>> groups.misc.ShephardToddFamily(Integer(6), Integer(3), Integer(4))
Complex reflection group G(6, 3, 4)
>>> groups.misc.ShephardToddFamily(Integer(6), Integer(6), Integer(4))
Complex reflection group G(6, 6, 4)
Element[source]#

alias of ColoredPermutation

as_permutation_group()[source]#

Return the permutation group corresponding to self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.as_permutation_group()                                              # needs sage.groups
Complex reflection group G(4, 1, 3) as a permutation group
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.as_permutation_group()                                              # needs sage.groups
Complex reflection group G(4, 1, 3) as a permutation group
cardinality()[source]#

Return the cardinality of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.cardinality()
384
sage: C.cardinality() == 4**3 * factorial(3)
True
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.cardinality()
384
>>> C.cardinality() == Integer(4)**Integer(3) * factorial(Integer(3))
True
codegrees()[source]#

Return the codegrees of self.

Let $$G$$ be a complex reflection group. The codegrees $$d_1^* \leq d_2^* \leq \cdots \leq d_{\ell}^*$$ of $$G$$ can be defined by:

$\prod_{i=1}^{\ell} (q - d_i^* - 1) = \sum_{g \in G} \det(g) q^{\dim(V^g)},$

where $$V$$ is the natural complex vector space that $$G$$ acts on and $$\ell$$ is the rank().

If $$m = 1$$, then we are in the special case of the symmetric group and the codegrees are $$(n-2, n-3, \ldots 1, 0)$$. Otherwise the degrees are $$((n-1)m, (n-2)m, \ldots, m, 0)$$.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.codegrees()
(8, 4, 0)
sage: S = ColoredPermutations(1, 3)
sage: S.codegrees()
(1, 0)
sage: G = groups.misc.ShephardToddFamily(6, 2, 3)
sage: G.codegrees()
(12, 6, 0)
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.codegrees()
(8, 4, 0)
>>> S = ColoredPermutations(Integer(1), Integer(3))
>>> S.codegrees()
(1, 0)
>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(2), Integer(3))
>>> G.codegrees()
(12, 6, 0)
coxeter_matrix()[source]#

Return the Coxeter matrix of self.

When the group is imprimitive and not a Coxeter group, this returns None.

EXAMPLES:

sage: C = ColoredPermutations(3, 4)
sage: C.coxeter_matrix()                                                    # needs sage.modules
[1 3 2 2]
[3 1 3 2]
[2 3 1 4]
[2 2 4 1]

sage: C = ColoredPermutations(1, 4)
sage: C.coxeter_matrix()                                                    # needs sage.modules
[1 3 2]
[3 1 3]
[2 3 1]

sage: G = groups.misc.ShephardToddFamily(2, 2, 3)
sage: G.coxeter_matrix()
[1 3 3]
[3 1 2]
[3 2 1]

sage: G = groups.misc.ShephardToddFamily(2, 2, 2)
sage: G.coxeter_matrix()
[1 2]
[2 1]

sage: G = groups.misc.ShephardToddFamily(2, 2, 1)
sage: G.coxeter_matrix()
[1]

sage: G = groups.misc.ShephardToddFamily(5, 5, 1)
sage: G.coxeter_matrix()
[]

sage: G = groups.misc.ShephardToddFamily(4, 4, 2)
sage: G.coxeter_matrix()
[1 4]
[4 1]

sage: G = groups.misc.ShephardToddFamily(7, 7, 2)
sage: G.coxeter_matrix()
[1 7]
[7 1]

sage: G = groups.misc.ShephardToddFamily(6, 3, 1)
sage: G.coxeter_matrix() is None
True
sage: G = groups.misc.ShephardToddFamily(6, 3, 4)
sage: G.coxeter_matrix() is None
True
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(3), Integer(4))
>>> C.coxeter_matrix()                                                    # needs sage.modules
[1 3 2 2]
[3 1 3 2]
[2 3 1 4]
[2 2 4 1]

>>> C = ColoredPermutations(Integer(1), Integer(4))
>>> C.coxeter_matrix()                                                    # needs sage.modules
[1 3 2]
[3 1 3]
[2 3 1]

>>> G = groups.misc.ShephardToddFamily(Integer(2), Integer(2), Integer(3))
>>> G.coxeter_matrix()
[1 3 3]
[3 1 2]
[3 2 1]

>>> G = groups.misc.ShephardToddFamily(Integer(2), Integer(2), Integer(2))
>>> G.coxeter_matrix()
[1 2]
[2 1]

>>> G = groups.misc.ShephardToddFamily(Integer(2), Integer(2), Integer(1))
>>> G.coxeter_matrix()
[1]

>>> G = groups.misc.ShephardToddFamily(Integer(5), Integer(5), Integer(1))
>>> G.coxeter_matrix()
[]

>>> G = groups.misc.ShephardToddFamily(Integer(4), Integer(4), Integer(2))
>>> G.coxeter_matrix()
[1 4]
[4 1]

>>> G = groups.misc.ShephardToddFamily(Integer(7), Integer(7), Integer(2))
>>> G.coxeter_matrix()
[1 7]
[7 1]

>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(3), Integer(1))
>>> G.coxeter_matrix() is None
True
>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(3), Integer(4))
>>> G.coxeter_matrix() is None
True
degrees()[source]#

Return the degrees of self.

The degrees of a complex reflection group are the degrees of the fundamental invariants of the ring of polynomial invariants.

If $$m = 1$$, then we are in the special case of the symmetric group and the degrees are $$(2, 3, \ldots, n, n+1)$$. Otherwise the degrees are $$(m, 2m, \ldots, nm)$$.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.degrees()
(4, 8, 12)
sage: S = ColoredPermutations(1, 3)
sage: S.degrees()
(2, 3)
sage: G = groups.misc.ShephardToddFamily(6, 2, 3)
sage: G.degrees()
(6, 9, 12)
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.degrees()
(4, 8, 12)
>>> S = ColoredPermutations(Integer(1), Integer(3))
>>> S.degrees()
(2, 3)
>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(2), Integer(3))
>>> G.degrees()
(6, 9, 12)

We now check that the product of the degrees is equal to the cardinality of self:

sage: prod(C.degrees()) == C.cardinality()
True
sage: prod(S.degrees()) == S.cardinality()
True
sage: prod(G.degrees()) == G.cardinality()
True
>>> from sage.all import *
>>> prod(C.degrees()) == C.cardinality()
True
>>> prod(S.degrees()) == S.cardinality()
True
>>> prod(G.degrees()) == G.cardinality()
True
fixed_point_polynomial(q=None)[source]#

The fixed point polynomial of self.

The fixed point polynomial $$f_G$$ of a complex reflection group $$G$$ is counting the dimensions of fixed points subspaces:

$f_G(q) = \sum_{w \in W} q^{\dim V^w}.$

Furthermore, let $$d_1, d_2, \ldots, d_{\ell}$$ be the degrees of $$G$$, where $$\ell$$ is the rank(). Then the fixed point polynomial is given by

$f_G(q) = \prod_{i=1}^{\ell} (q + d_i - 1).$

INPUT:

• q – (default: the generator of ZZ['q']) the parameter $$q$$

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.fixed_point_polynomial()
q^3 + 21*q^2 + 131*q + 231

sage: S = ColoredPermutations(1, 3)
sage: S.fixed_point_polynomial()
q^2 + 3*q + 2
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.fixed_point_polynomial()
q^3 + 21*q^2 + 131*q + 231

>>> S = ColoredPermutations(Integer(1), Integer(3))
>>> S.fixed_point_polynomial()
q^2 + 3*q + 2
gens()[source]#

Return the generators of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.gens()
([[0, 0, 0], [2, 1, 3]],
[[0, 0, 0], [1, 3, 2]],
[[0, 0, 1], [1, 2, 3]])

sage: S = SignedPermutations(4)
sage: S.gens()
([2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3], [1, 2, 3, -4])
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.gens()
([[0, 0, 0], [2, 1, 3]],
[[0, 0, 0], [1, 3, 2]],
[[0, 0, 1], [1, 2, 3]])

>>> S = SignedPermutations(Integer(4))
>>> S.gens()
([2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3], [1, 2, 3, -4])
index_set()[source]#

Return the index set of self.

EXAMPLES:

sage: C = ColoredPermutations(3, 4)
sage: C.index_set()
(1, 2, 3, 4)

sage: C = ColoredPermutations(1, 4)
sage: C.index_set()
(1, 2, 3)

sage: G = groups.misc.ShephardToddFamily(6, 6, 4)
sage: G.index_set()
(1, 2, 3, 4)

sage: G = groups.misc.ShephardToddFamily(6, 2, 4)
sage: G.index_set()
(1, 2, 3, 4, 5)

sage: G = groups.misc.ShephardToddFamily(6, 6, 1)
sage: G.index_set()
()

sage: G = groups.misc.ShephardToddFamily(6, 2, 1)
sage: G.index_set()
(1,)
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(3), Integer(4))
>>> C.index_set()
(1, 2, 3, 4)

>>> C = ColoredPermutations(Integer(1), Integer(4))
>>> C.index_set()
(1, 2, 3)

>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(6), Integer(4))
>>> G.index_set()
(1, 2, 3, 4)

>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(2), Integer(4))
>>> G.index_set()
(1, 2, 3, 4, 5)

>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(6), Integer(1))
>>> G.index_set()
()

>>> G = groups.misc.ShephardToddFamily(Integer(6), Integer(2), Integer(1))
>>> G.index_set()
(1,)
is_well_generated()[source]#

Return if self is a well-generated complex reflection group.

A complex reflection group $$G$$ is well-generated if it is generated by $$\ell$$ reflections. Equivalently, $$G$$ is well-generated if $$d_i + d_i^* = d_{\ell}$$ for all $$1 \leq i \leq \ell$$.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.is_well_generated()
True
sage: C = ColoredPermutations(2, 8)
sage: C.is_well_generated()
True
sage: C = ColoredPermutations(1, 4)
sage: C.is_well_generated()
True
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.is_well_generated()
True
>>> C = ColoredPermutations(Integer(2), Integer(8))
>>> C.is_well_generated()
True
>>> C = ColoredPermutations(Integer(1), Integer(4))
>>> C.is_well_generated()
True
matrix_group()[source]#

Return the matrix group corresponding to self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.matrix_group()                                                      # needs sage.modules
Matrix group over Cyclotomic Field of order 4 and degree 2 with 3 generators (
[0 1 0]  [1 0 0]  [    1     0     0]
[1 0 0]  [0 0 1]  [    0     1     0]
[0 0 1], [0 1 0], [    0     0 zeta4]
)
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.matrix_group()                                                      # needs sage.modules
Matrix group over Cyclotomic Field of order 4 and degree 2 with 3 generators (
[0 1 0]  [1 0 0]  [    1     0     0]
[1 0 0]  [0 0 1]  [    0     1     0]
[0 0 1], [0 1 0], [    0     0 zeta4]
)
number_of_reflection_hyperplanes()[source]#

Return the number of reflection hyperplanes of self.

The number of reflection hyperplanes of a complex reflection group is equal to the sum of the codegrees plus the rank.

EXAMPLES:

sage: C = ColoredPermutations(1, 2)
sage: C.number_of_reflection_hyperplanes()
1
sage: C = ColoredPermutations(1, 3)
sage: C.number_of_reflection_hyperplanes()
3
sage: C = ColoredPermutations(4, 12)
sage: C.number_of_reflection_hyperplanes()
276
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(1), Integer(2))
>>> C.number_of_reflection_hyperplanes()
1
>>> C = ColoredPermutations(Integer(1), Integer(3))
>>> C.number_of_reflection_hyperplanes()
3
>>> C = ColoredPermutations(Integer(4), Integer(12))
>>> C.number_of_reflection_hyperplanes()
276
one()[source]#

Return the identity element of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.one()
[[0, 0, 0], [1, 2, 3]]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.one()
[[0, 0, 0], [1, 2, 3]]
order()[source]#

Return the cardinality of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.cardinality()
384
sage: C.cardinality() == 4**3 * factorial(3)
True
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.cardinality()
384
>>> C.cardinality() == Integer(4)**Integer(3) * factorial(Integer(3))
True
random_element()[source]#

Return an element of self at random.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s = C.random_element(); s  # random
[[0, 2, 1], [2, 1, 3]]
sage: s in C
True
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> s = C.random_element(); s  # random
[[0, 2, 1], [2, 1, 3]]
>>> s in C
True
rank()[source]#

Return the rank of self.

The rank of a complex reflection group is equal to the dimension of the complex vector space the group acts on.

EXAMPLES:

sage: C = ColoredPermutations(4, 12)
sage: C.rank()
12
sage: C = ColoredPermutations(7, 4)
sage: C.rank()
4
sage: C = ColoredPermutations(1, 4)
sage: C.rank()
3
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(12))
>>> C.rank()
12
>>> C = ColoredPermutations(Integer(7), Integer(4))
>>> C.rank()
4
>>> C = ColoredPermutations(Integer(1), Integer(4))
>>> C.rank()
3
simple_reflection(i)[source]#

Return the i-th simple reflection of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.gens()
([[0, 0, 0], [2, 1, 3]], [[0, 0, 0], [1, 3, 2]], [[0, 0, 1], [1, 2, 3]])
sage: C.simple_reflection(2)
[[0, 0, 0], [1, 3, 2]]
sage: C.simple_reflection(3)
[[0, 0, 1], [1, 2, 3]]

sage: S = SignedPermutations(4)
sage: S.simple_reflection(1)
[2, 1, 3, 4]
sage: S.simple_reflection(4)
[1, 2, 3, -4]

sage: G = groups.misc.ShephardToddFamily(4, 2, 3)
sage: list(G.simple_reflections())
[[[0, 0, 0], [2, 1, 3]],
[[0, 0, 0], [1, 3, 2]],
[[0, 1, 3], [1, 3, 2]],
[[0, 0, 2], [1, 2, 3]]]

sage: G = groups.misc.ShephardToddFamily(8, 4, 1)
sage: G.simple_reflections()
Finite family {1: [[4], [1]]}

sage: G = groups.misc.ShephardToddFamily(8, 8, 1)
sage: G.simple_reflections()
Finite family {}
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(4), Integer(3))
>>> C.gens()
([[0, 0, 0], [2, 1, 3]], [[0, 0, 0], [1, 3, 2]], [[0, 0, 1], [1, 2, 3]])
>>> C.simple_reflection(Integer(2))
[[0, 0, 0], [1, 3, 2]]
>>> C.simple_reflection(Integer(3))
[[0, 0, 1], [1, 2, 3]]

>>> S = SignedPermutations(Integer(4))
>>> S.simple_reflection(Integer(1))
[2, 1, 3, 4]
>>> S.simple_reflection(Integer(4))
[1, 2, 3, -4]

>>> G = groups.misc.ShephardToddFamily(Integer(4), Integer(2), Integer(3))
>>> list(G.simple_reflections())
[[[0, 0, 0], [2, 1, 3]],
[[0, 0, 0], [1, 3, 2]],
[[0, 1, 3], [1, 3, 2]],
[[0, 0, 2], [1, 2, 3]]]

>>> G = groups.misc.ShephardToddFamily(Integer(8), Integer(4), Integer(1))
>>> G.simple_reflections()
Finite family {1: [[4], [1]]}

>>> G = groups.misc.ShephardToddFamily(Integer(8), Integer(8), Integer(1))
>>> G.simple_reflections()
Finite family {}
class sage.combinat.colored_permutations.SignedPermutation(parent, colors, perm)[source]#

Bases: ColoredPermutation

A signed permutation.

cycle_type()[source]#

Return a pair of partitions of len(self) corresponding to the signed cycle type of self.

A cycle is a tuple $$C = (c_0, \ldots, c_{k-1})$$ with $$\pi(c_i) = c_{i+1}$$ for $$0 \leq i < k$$ and $$\pi(c_{k-1}) = c_0$$. If $$C$$ is a cycle, $$\overline{C} = (-c_0, \ldots, -c_{k-1})$$ is also a cycle. A cycle is negative, if $$C = \overline{C}$$ up to cyclic reordering. In this case, $$k$$ is necessarily even and the length of $$C$$ is $$k/2$$. A positive cycle is a pair $$C \overline{C}$$, its length is $$k$$.

Let $$\alpha$$ be the partition whose parts are the lengths of the positive cycles and let $$\beta$$ be the partition whose parts are the lengths of the negative cycles. Then $$(\alpha, \beta)$$ is the cycle type of $$\pi$$.

EXAMPLES:

sage: G = SignedPermutations(7)
sage: pi = G([2, -1, 4, -6, -5, -3, 7])
sage: pi.cycle_type()
([3, 1], [2, 1])

sage: G = SignedPermutations(5)
sage: all(pi.cycle_type().size() == 5 for pi in G)
True
sage: set(pi.cycle_type() for pi in G) == set(PartitionTuples(2, 5))
True
>>> from sage.all import *
>>> G = SignedPermutations(Integer(7))
>>> pi = G([Integer(2), -Integer(1), Integer(4), -Integer(6), -Integer(5), -Integer(3), Integer(7)])
>>> pi.cycle_type()
([3, 1], [2, 1])

>>> G = SignedPermutations(Integer(5))
>>> all(pi.cycle_type().size() == Integer(5) for pi in G)
True
>>> set(pi.cycle_type() for pi in G) == set(PartitionTuples(Integer(2), Integer(5)))
True
has_left_descent(i)[source]#

Return True if i is a left descent of self.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: s1,s2,s3,s4 = S.gens()
sage: x = s4*s1*s2*s3*s4
sage: [x.has_left_descent(i) for i in S.index_set()]
[True, False, False, True]
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> s1,s2,s3,s4 = S.gens()
>>> x = s4*s1*s2*s3*s4
>>> [x.has_left_descent(i) for i in S.index_set()]
[True, False, False, True]
order()[source]#

Return the multiplicative order of the signed permutation.

EXAMPLES:

sage: pi = SignedPermutations(7)([2,-1,4,-6,-5,-3,7])
sage: pi.to_cycles(singletons=False)
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5)]
sage: pi.order()
12
>>> from sage.all import *
>>> pi = SignedPermutations(Integer(7))([Integer(2),-Integer(1),Integer(4),-Integer(6),-Integer(5),-Integer(3),Integer(7)])
>>> pi.to_cycles(singletons=False)
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5)]
>>> pi.order()
12
to_cycles(singletons=True, use_min=True, negative_cycles=True)[source]#

Return the signed permutation self as a list of disjoint cycles.

The cycles are returned in the order of increasing smallest elements, and each cycle is returned as a tuple which starts with its smallest positive element.

INPUT:

• singletons – (default: True) whether to include singleton cycles or not

• use_min – (default: True) if False, the cycles are returned in the order of increasing largest (not smallest) elements, and each cycle starts with its largest element

• negative_cycles – (default: True) if False, for any two cycles $$C^{\pm} = \{\pm c_1, \ldots, \pm c_k\}$$ such that $$C^+ \neq C^-$$, this does not include the cycle $$C^-$$

Warning

The arugment negative_cycles does not refer to the usual definition of a negative cycle; see cycle_type().

EXAMPLES:

sage: pi = SignedPermutations(7)([2,-1,4,-6,-5,-3,7])
sage: pi.to_cycles()
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5), (7,), (-7,)]
sage: pi.to_cycles(singletons=False)
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5)]
sage: pi.to_cycles(negative_cycles=False)
[(1, 2, -1, -2), (3, 4, -6), (5, -5), (7,)]
sage: pi.to_cycles(singletons=False, negative_cycles=False)
[(1, 2, -1, -2), (3, 4, -6), (5, -5)]
sage: pi.to_cycles(use_min=False)
[(7,), (-7,), (6, -3, -4), (-6, 3, 4), (5, -5), (2, -1, -2, 1)]
sage: pi.to_cycles(singletons=False, use_min=False)
[(6, -3, -4), (-6, 3, 4), (5, -5), (2, -1, -2, 1)]
>>> from sage.all import *
>>> pi = SignedPermutations(Integer(7))([Integer(2),-Integer(1),Integer(4),-Integer(6),-Integer(5),-Integer(3),Integer(7)])
>>> pi.to_cycles()
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5), (7,), (-7,)]
>>> pi.to_cycles(singletons=False)
[(1, 2, -1, -2), (3, 4, -6), (-3, -4, 6), (5, -5)]
>>> pi.to_cycles(negative_cycles=False)
[(1, 2, -1, -2), (3, 4, -6), (5, -5), (7,)]
>>> pi.to_cycles(singletons=False, negative_cycles=False)
[(1, 2, -1, -2), (3, 4, -6), (5, -5)]
>>> pi.to_cycles(use_min=False)
[(7,), (-7,), (6, -3, -4), (-6, 3, 4), (5, -5), (2, -1, -2, 1)]
>>> pi.to_cycles(singletons=False, use_min=False)
[(6, -3, -4), (-6, 3, 4), (5, -5), (2, -1, -2, 1)]
to_matrix()[source]#

Return a matrix of self.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: s1,s2,s3,s4 = S.gens()
sage: x = s4*s1*s2*s3*s4
sage: M = x.to_matrix(); M                                                  # needs sage.modules
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0 -1]
[-1  0  0  0]
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> s1,s2,s3,s4 = S.gens()
>>> x = s4*s1*s2*s3*s4
>>> M = x.to_matrix(); M                                                  # needs sage.modules
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0 -1]
[-1  0  0  0]

The matrix multiplication is in the opposite order:

sage: m1,m2,m3,m4 = [g.to_matrix() for g in S.gens()]                       # needs sage.modules
sage: M == m4 * m3 * m2 * m1 * m4                                           # needs sage.modules
True
>>> from sage.all import *
>>> m1,m2,m3,m4 = [g.to_matrix() for g in S.gens()]                       # needs sage.modules
>>> M == m4 * m3 * m2 * m1 * m4                                           # needs sage.modules
True
class sage.combinat.colored_permutations.SignedPermutations(n)[source]#

Bases: ColoredPermutations

Group of signed permutations.

The group of signed permutations is also known as the hyperoctahedral group, the Coxeter group of type $$B_n$$, and the 2-colored permutation group. Thus it can be constructed as the wreath product $$S_2 \wr S_n$$.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: s1,s2,s3,s4 = S.group_generators()
sage: x = s4*s1*s2*s3*s4; x
[-4, 1, 2, -3]
sage: x^4 == S.one()
True
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> s1,s2,s3,s4 = S.group_generators()
>>> x = s4*s1*s2*s3*s4; x
[-4, 1, 2, -3]
>>> x**Integer(4) == S.one()
True

This is a finite Coxeter group of type $$B_n$$:

sage: S.canonical_representation()                                              # needs sage.modules
Finite Coxeter group over Number Field in a with defining polynomial x^2 - 2
with a = 1.414213562373095? with Coxeter matrix:
[1 3 2 2]
[3 1 3 2]
[2 3 1 4]
[2 2 4 1]
sage: S.long_element()
[-1, -2, -3, -4]
sage: S.long_element().reduced_word()
[1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 4, 3, 4]
>>> from sage.all import *
>>> S.canonical_representation()                                              # needs sage.modules
Finite Coxeter group over Number Field in a with defining polynomial x^2 - 2
with a = 1.414213562373095? with Coxeter matrix:
[1 3 2 2]
[3 1 3 2]
[2 3 1 4]
[2 2 4 1]
>>> S.long_element()
[-1, -2, -3, -4]
>>> S.long_element().reduced_word()
[1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 4, 3, 4]

We can also go between the 2-colored permutation group:

sage: C = ColoredPermutations(2, 3)
sage: S = SignedPermutations(3)
sage: S.an_element()
[-3, 1, 2]
sage: C(S.an_element())
[[1, 0, 0], [3, 1, 2]]
sage: S(C(S.an_element())) == S.an_element()
True
sage: S(C.an_element())
[-3, 1, 2]
>>> from sage.all import *
>>> C = ColoredPermutations(Integer(2), Integer(3))
>>> S = SignedPermutations(Integer(3))
>>> S.an_element()
[-3, 1, 2]
>>> C(S.an_element())
[[1, 0, 0], [3, 1, 2]]
>>> S(C(S.an_element())) == S.an_element()
True
>>> S(C.an_element())
[-3, 1, 2]

There is also the natural lift from permutations:

sage: P = Permutations(3)
sage: x = S(P.an_element()); x
[3, 1, 2]
sage: x.parent()
Signed permutations of 3
>>> from sage.all import *
>>> P = Permutations(Integer(3))
>>> x = S(P.an_element()); x
[3, 1, 2]
>>> x.parent()
Signed permutations of 3

REFERENCES:

Element[source]#

alias of SignedPermutation

conjugacy_class_representative(nu)[source]#

Return a permutation with (signed) cycle type nu.

EXAMPLES:

sage: G = SignedPermutations(4)
sage: for nu in PartitionTuples(2, 4):
....:     print(nu, G.conjugacy_class_representative(nu))
....:     assert nu == G.conjugacy_class_representative(nu).cycle_type(), nu
([4], []) [2, 3, 4, 1]
([3, 1], []) [2, 3, 1, 4]
([2, 2], []) [2, 1, 4, 3]
([2, 1, 1], []) [2, 1, 3, 4]
([1, 1, 1, 1], []) [1, 2, 3, 4]
([3], [1]) [2, 3, 1, -4]
([2, 1], [1]) [2, 1, 3, -4]
([1, 1, 1], [1]) [1, 2, 3, -4]
([2], [2]) [2, 1, 4, -3]
([2], [1, 1]) [2, 1, -3, -4]
([1, 1], [2]) [1, 2, 4, -3]
([1, 1], [1, 1]) [1, 2, -3, -4]
([1], [3]) [1, 3, 4, -2]
([1], [2, 1]) [1, 3, -2, -4]
([1], [1, 1, 1]) [1, -2, -3, -4]
([], [4]) [2, 3, 4, -1]
([], [3, 1]) [2, 3, -1, -4]
([], [2, 2]) [2, -1, 4, -3]
([], [2, 1, 1]) [2, -1, -3, -4]
([], [1, 1, 1, 1]) [-1, -2, -3, -4]
>>> from sage.all import *
>>> G = SignedPermutations(Integer(4))
>>> for nu in PartitionTuples(Integer(2), Integer(4)):
...     print(nu, G.conjugacy_class_representative(nu))
...     assert nu == G.conjugacy_class_representative(nu).cycle_type(), nu
([4], []) [2, 3, 4, 1]
([3, 1], []) [2, 3, 1, 4]
([2, 2], []) [2, 1, 4, 3]
([2, 1, 1], []) [2, 1, 3, 4]
([1, 1, 1, 1], []) [1, 2, 3, 4]
([3], [1]) [2, 3, 1, -4]
([2, 1], [1]) [2, 1, 3, -4]
([1, 1, 1], [1]) [1, 2, 3, -4]
([2], [2]) [2, 1, 4, -3]
([2], [1, 1]) [2, 1, -3, -4]
([1, 1], [2]) [1, 2, 4, -3]
([1, 1], [1, 1]) [1, 2, -3, -4]
([1], [3]) [1, 3, 4, -2]
([1], [2, 1]) [1, 3, -2, -4]
([1], [1, 1, 1]) [1, -2, -3, -4]
([], [4]) [2, 3, 4, -1]
([], [3, 1]) [2, 3, -1, -4]
([], [2, 2]) [2, -1, 4, -3]
([], [2, 1, 1]) [2, -1, -3, -4]
([], [1, 1, 1, 1]) [-1, -2, -3, -4]
long_element(index_set=None)[source]#

Return the longest element of self, or of the parabolic subgroup corresponding to the given index_set.

INPUT:

• index_set – (optional) a subset (as a list or iterable) of the nodes of the indexing set

EXAMPLES:

sage: S = SignedPermutations(4)
sage: S.long_element()
[-1, -2, -3, -4]
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> S.long_element()
[-1, -2, -3, -4]
one()[source]#

Return the identity element of self.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: S.one()
[1, 2, 3, 4]
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> S.one()
[1, 2, 3, 4]
random_element()[source]#

Return an element drawn uniformly at random.

EXAMPLES:

sage: C = SignedPermutations(7)
sage: s = C.random_element(); s # random
[7, 6, -4, -5, 2, 3, -1]
sage: s in C
True
>>> from sage.all import *
>>> C = SignedPermutations(Integer(7))
>>> s = C.random_element(); s # random
[7, 6, -4, -5, 2, 3, -1]
>>> s in C
True
simple_reflection(i)[source]#

Return the i-th simple reflection of self.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: S.simple_reflection(1)
[2, 1, 3, 4]
sage: S.simple_reflection(4)
[1, 2, 3, -4]
>>> from sage.all import *
>>> S = SignedPermutations(Integer(4))
>>> S.simple_reflection(Integer(1))
[2, 1, 3, 4]
>>> S.simple_reflection(Integer(4))
[1, 2, 3, -4]