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:
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]
- 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 # 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
- class sage.combinat.colored_permutations.ColoredPermutations(m, n)#
Bases:
Parent
,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 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() # needs sage.groups 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() # 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]
- 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() # 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()#
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
- random_element()#
Return an element drawn uniformly 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
- 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:
ColoredPermutation
A signed permutation.
- cycle_type()#
Return a pair of partitions of
len(self)
corresponding to the signed cycle type ofself
.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
- 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]
- 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), (-3, -4, 6), (5, -5)] sage: pi.order() 12
- to_cycles(singletons=True, use_min=True, negative_cycles=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.
INPUT:
singletons
– (default:True
) whether to include singleton cycles or notuse_min
– (default:True
) ifFalse
, the cycles are returned in the order of increasing largest (not smallest) elements, and each cycle starts with its largest elementnegative_cycles
– (default:True
) ifFalse
, 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; seecycle_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)]
- 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 # 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
- class sage.combinat.colored_permutations.SignedPermutations(n)#
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
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]
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
- conjugacy_class_representative(nu)#
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]
- 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]
- random_element()#
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
- 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]