Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Colored Permutations
.. TODO::
Much of the colored permutations (and element) class can be generalized to `G \wr S_n` """
""" A colored permutation. """ """ Initialize ``self``.
TESTS::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: TestSuite(s1*s2*t).run() """
r""" TESTS::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: hash(s1), hash(s2), hash(t) (2666658751600856334, 3639282354432100950, 3639281107336048003) # 64-bit (-1973744370, 88459862, -1467077245) # 32-bit """
""" Return a string representation of ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: s1*s2*t [[1, 0, 0], [3, 1, 2]] """
r""" Return a latex representation of ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: latex(s1*s2*t) [3_{1}, 1_{0}, 2_{0}] """ for i, x in enumerate(self._perm))
""" Multiply ``self`` and ``other``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: s1*s2*s1 == s2*s1*s2 True """ for i, val in enumerate(self._perm))
""" 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 """ tuple([-self._colors[i - 1] for i in ip]), # -1 for indexing ip)
""" Check equality.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: s1*s2*s1 == s2*s1*s2 True sage: t^4 == C.one() True sage: s1*s2 == s2*s1 False """ and self._colors == other._colors and self._perm == other._perm)
""" Check inequality.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: s1*s2*s1 != s2*s1*s2 False sage: s1*s2 != s2*s1 True """
""" Iterate over ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: s1,s2,t = C.gens() sage: x = s1*s2*t sage: list(x) [(1, 3), (0, 1), (0, 2)] """
""" 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)] """
""" 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] """
""" 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] """
""" 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 """
""" Return ``True`` if ``i`` is a left descent of ``self``.
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] """
raise ValueError("descents are undefined")
# TODO: Parts of this should be put in the category of complex # reflection groups r""" 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
.. MATH::
((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:
- :wikipedia:`Generalized_symmetric_group` - :wikipedia:`Complex_reflection_group` """ """ Initialize ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: TestSuite(C).run() sage: C = ColoredPermutations(2, 3) sage: TestSuite(C).run() sage: C = ColoredPermutations(1, 3) sage: TestSuite(C).run() """ raise ValueError("m must be a positive integer")
else:
""" Return a string representation of ``self``.
EXAMPLES::
sage: ColoredPermutations(4, 3) 4-colored permutations of size 3 """
def index_set(self): """ 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)
TESTS::
sage: S = SignedPermutations(4) sage: S.index_set() (1, 2, 3, 4) """
""" 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]
TESTS::
sage: S = SignedPermutations(4) sage: S.coxeter_matrix() [1 3 2 2] [3 1 3 2] [2 3 1 4] [2 2 4 1] """
def one(self): """ Return the identity element of ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: C.one() [[0, 0, 0], [1, 2, 3]] """ self._P.identity())
r""" 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] """ raise ValueError("i must be in the index set")
def gens(self): """ 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]) """
""" 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] ) """
""" Construct an element of ``self`` from ``x``.
INPUT:
Either a list of pairs (color, element) or a pair of lists (colors, elements).
TESTS::
sage: C = ColoredPermutations(4, 3) sage: x = C([(2,1), (3,3), (3,2)]); x [[2, 3, 3], [1, 3, 2]] sage: x == C([[2,3,3], [1,3,2]]) True """ raise ValueError("input must be pairs (color, element)")
raise ValueError("input must be a pair of a list of colors and a permutation")
""" Return a coerce map from ``C`` if it exists and ``None`` otherwise.
EXAMPLES::
sage: C = ColoredPermutations(2, 3) sage: S = SignedPermutations(3) sage: C.has_coerce_map_from(S) True
sage: C = ColoredPermutations(4, 3) sage: C.has_coerce_map_from(S) False sage: S = SignedPermutations(4) sage: C.has_coerce_map_from(S) False
sage: P = Permutations(3) sage: C.has_coerce_map_from(P) True sage: P = Permutations(4) sage: C.has_coerce_map_from(P) False """ [P._C.zero() if v == 1 else P._C.one() for v in x._colors], x._perm)
""" Iterate over ``self``.
EXAMPLES::
sage: C = ColoredPermutations(2, 2) sage: [x for x in C] [[[0, 0], [1, 2]], [[0, 1], [1, 2]], [[1, 0], [1, 2]], [[1, 1], [1, 2]], [[0, 0], [2, 1]], [[0, 1], [2, 1]], [[1, 0], [2, 1]], [[1, 1], [2, 1]]] """
""" Return the cardinality of ``self``.
EXAMPLES::
sage: C = ColoredPermutations(4, 3) sage: C.cardinality() 384 sage: C.cardinality() == 4**3 * factorial(3) True """
""" 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 """
""" 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 """ # For the usual symmetric group (self._m=1) we need to start at 2
r""" 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:
.. MATH::
\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 :meth:`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)
TESTS:
We check the polynomial identity::
sage: R.<q> = ZZ[] sage: C = ColoredPermutations(3, 2) sage: f = prod(q - ds - 1 for ds in C.codegrees()) sage: d = lambda x: sum(1 for e in x.to_matrix().eigenvalues() if e == 1) sage: g = sum(det(x.to_matrix()) * q**d(x) for x in C) sage: f == g True """ # Special case for the usual symmetric group
""" 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 """
r""" 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:
.. MATH::
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 :meth:`rank`. Then the fixed point polynomial is given by
.. MATH::
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
TESTS:
We check the against the degrees and codegrees::
sage: R.<q> = ZZ[] sage: C = ColoredPermutations(4, 3) sage: C.fixed_point_polynomial(q) == prod(q + d - 1 for d in C.degrees()) True """
""" 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 """
##################################################################### ## Signed permutations
""" A signed permutation. """ """ Return a string representation of ``self``.
EXAMPLES::
sage: S = SignedPermutations(4) sage: s1,s2,s3,s4 = S.gens() sage: s4*s1*s2*s3*s4 [-4, 1, 2, -3] """
""" Multiply ``self`` and ``other``.
EXAMPLES::
sage: S = SignedPermutations(4) sage: s1,s2,s3,s4 = S.gens() sage: x = s4*s1*s2*s3*s4; x [-4, 1, 2, -3] sage: x * x [3, -4, 1, -2]
::
sage: s1*s2*s1 == s1*s2*s1 True sage: s3*s4*s3*s4 == s4*s3*s4*s3 True """ for i, val in enumerate(self._perm))
""" 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 """ tuple([self._colors[i - 1] for i in ip]), # -1 for indexing ip)
""" Iterate over ``self``.
EXAMPLES::
sage: S = SignedPermutations(4) sage: s1,s2,s3,s4 = S.gens() sage: x = s4*s1*s2*s3*s4 sage: [a for a in x] [-4, 1, 2, -3] """
""" 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 """
""" 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] """
r""" 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() [-4, -3, -2, -1] sage: S.long_element().reduced_word() [4, 3, 4, 2, 3, 4, 1, 2, 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:
- :wikipedia:`Hyperoctahedral_group` """ """ Initialize ``self``.
EXAMPLES::
sage: S = SignedPermutations(4) sage: TestSuite(S).run() """
""" Return a string representation of ``self``.
EXAMPLES::
sage: SignedPermutations(4) Signed permutations of 4 """
def one(self): """ Return the identity element of ``self``.
EXAMPLES::
sage: S = SignedPermutations(4) sage: S.one() [1, 2, 3, 4] """ self._P.identity())
r""" 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] """ raise ValueError("i must be in the index set")
""" Construct an element of ``self`` from ``x``.
TESTS::
sage: S = SignedPermutations(3) sage: x = S([(+1,1), (-1,3), (-1,2)]); x [1, -3, -2] sage: x == S([[+1,-1,-1], [1,3,2]]) True sage: x == S([1, -3, -2]) True """ raise ValueError("input must be pairs (sign, element)") raise ValueError("the sign must be +1 or -1")
else:
raise ValueError("input must be a pair of a list of signs and a permutation") raise ValueError("the sign must be +1 or -1")
""" Iterate over ``self``.
EXAMPLES::
sage: S = SignedPermutations(2) sage: [x for x in S] [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]] """
""" Return a coerce map from ``C`` if it exists and ``None`` otherwise.
EXAMPLES::
sage: C = ColoredPermutations(2, 3) sage: S = SignedPermutations(3) sage: S.has_coerce_map_from(C) True
sage: C = ColoredPermutations(4, 3) sage: S.has_coerce_map_from(C) False
sage: P = Permutations(3) sage: C.has_coerce_map_from(P) True sage: P = Permutations(4) sage: C.has_coerce_map_from(P) False """ [1 if v == 0 else -1 for v in x._colors], x._perm)
""" 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() [-4, -3, -2, -1] """ return super(SignedPermutations, self).long_element()
# TODO: Make this a subgroup #class EvenSignedPermutations(SignedPermutations): # """ # Group of even signed permutations. # """ # def _repr_(self): # """ # Return a string representation of ``self``. # """ # return "Even signed permutations of {}".format(self._n) # # def __iter__(self): # """ # Iterate over ``self``. # """ # for s in SignedPermutations.__iter__(self): # total = 0 # for pm in s._colors: # if pm == -1: # total += 1 # # if total % 2 == 0: # yield s |