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)

Bases: sage.structure.element.MultiplicativeGroupElement

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

Return the inverse of self.

EXAMPLES:

sage: C = ColoredPermutations(4, 3)
sage: s1,s2,t = C.gens()
sage: ~t
[[0, 0, 3], [1, 2, 3]]
sage: all(x * ~x == C.one() for x in C.gens())
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
sage.combinat.colored_permutations.ColoredPermutations

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 either a list 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]]

There is also the natural lift from permutations:

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

REFERENCES:

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

Bases: sage.combinat.colored_permutations.ColoredPermutation

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

Return the inverse of self.

EXAMPLES:

sage: S = SignedPermutations(4)
sage: s1,s2,s3,s4 = S.gens()
sage: x = s4*s1*s2*s3*s4
sage: ~x
[2, 3, -4, -1]
sage: x * ~x == S.one()
True
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
sage.combinat.colored_permutations.SignedPermutations

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