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
- class sage.combinat.colored_permutations.ColoredPermutations(m, n)¶
Bases:
sage.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
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:
- 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 ofZZ['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 ofself
.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)¶
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
- class sage.combinat.colored_permutations.SignedPermutations(n)¶
Bases:
sage.combinat.colored_permutations.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
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 givenindex_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 ofself
.EXAMPLES:
sage: S = SignedPermutations(4) sage: S.simple_reflection(1) [2, 1, 3, 4] sage: S.simple_reflection(4) [1, 2, 3, -4]