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

A colored permutation.

colors()#

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]

has_left_descent(i)#

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]

length()#

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

one_line_form()#

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

permutation()#

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]

reduced_word()#

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]

to_matrix()#

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
[    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()
True

class sage.combinat.colored_permutations.ColoredPermutations(m, n)#

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]]


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]]


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]]


There is also the natural lift from permutations:

sage: P = Permutations(3)
sage: C(P.an_element())
[[0, 0, 0], [3, 1, 2]]


A colored permutation:

sage: C(C.an_element()) == C.an_element()
True


REFERENCES:

Element#

alias of ColoredPermutation

as_permutation_group()#

Return the permutation group corresponding to self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.as_permutation_group()
Complex reflection group G(4, 1, 3) as a permutation group

cardinality()#

Return the cardinality of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.cardinality()
384
sage: C.cardinality() == 4**3 * factorial(3)
True

codegrees()#

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)

coxeter_matrix()#

Return the Coxeter matrix of self.

EXAMPLES:

sage: C = ColoredPermutations(3, 4)
sage: C.coxeter_matrix()
[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()
[1 3 2]
[3 1 3]
[2 3 1]

degrees()#

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)


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

fixed_point_polynomial(q=None)#

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

gens()#

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

index_set()#

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)

is_well_generated()#

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

matrix_group()#

Return the matrix group corresponding to self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.matrix_group()
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()#

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

one()#

Return the identity element of self.

EXAMPLES:

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

order()#

Return the cardinality of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: C.cardinality()
384
sage: C.cardinality() == 4**3 * factorial(3)
True

rank()#

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

simple_reflection(i)#

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]

class sage.combinat.colored_permutations.SignedPermutation(parent, colors, perm)#

A signed permutation.

has_left_descent(i)#

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]

order()#

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), (5, -5)]
sage: pi.order()
12

to_cycles(singletons=True, use_min=True, negative_singletons=True)#

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. We do not include the corresponding negative cycles.

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

EXAMPLES:

sage: pi = SignedPermutations(7)([2,-1,4,-6,-5,-3,7])
sage: pi.to_cycles()
[(1, 2, -1, -2), (3, 4, -6), (5, -5), (7,)]
sage: pi.to_cycles(singletons=False)
[(1, 2, -1, -2), (3, 4, -6), (5, -5)]
sage: pi.to_cycles(use_min=False)
[(7,), (6, -3, -4), (5, -5), (2, -1, -2, 1)]
sage: pi.to_cycles(singletons=False, use_min=False)
[(6, -3, -4), (5, -5), (2, -1, -2, 1)]

to_matrix()#

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
[ 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()]
sage: M == m4 * m3 * m2 * m1 * m4
True

class sage.combinat.colored_permutations.SignedPermutations(n)#

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


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

sage: S.canonical_representation()
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]


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]


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


REFERENCES:

Element#

alias of SignedPermutation

long_element(index_set=None)#

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]

one()#

Return the identity element of self.

EXAMPLES:

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

simple_reflection(i)#

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]