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
ifi
is a left descent ofself
.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
ifi
is a left descent ofself
.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: