Symmetric Group Algebra#
- sage.combinat.symmetric_group_algebra.HeckeAlgebraSymmetricGroupT(R, n, q=None)#
Return the Hecke algebra of the symmetric group \(S_n\) on the T-basis with quantum parameter
q
over the ring \(R\).If \(R\) is a commutative ring and \(q\) is an invertible element of \(R\), and if \(n\) is a nonnegative integer, then the Hecke algebra of the symmetric group \(S_n\) over \(R\) with quantum parameter \(q\) is defined as the algebra generated by the generators \(T_1, T_2, \ldots, T_{n-1}\) with relations
\[T_i T_{i+1} T_i = T_{i+1} T_i T_{i+1}\]for all \(i < n-1\) (“braid relations”),
\[T_i T_j = T_j T_i\]for all \(i\) and \(j\) such that \(| i-j | > 1\) (“locality relations”), and
\[T_i^2 = q + (q-1) T_i\]for all \(i\) (the “quadratic relations”, also known in the form \((T_i + 1) (T_i - q) = 0\)). (This is only one of several existing definitions in literature, not all of which are fully equivalent. We are following the conventions of [Go1993].) For any permutation \(w \in S_n\), we can define an element \(T_w\) of this Hecke algebra by setting \(T_w = T_{i_1} T_{i_2} \cdots T_{i_k}\), where \(w = s_{i_1} s_{i_2} \cdots s_{i_k}\) is a reduced word for \(w\) (with \(s_i\) meaning the transposition \((i, i+1)\), and the product of permutations being evaluated by first applying \(s_{i_k}\), then \(s_{i_{k-1}}\), etc.). This element is independent of the choice of the reduced decomposition, and can be computed in Sage by calling
H[w]
whereH
is the Hecke algebra andw
is the permutation.The Hecke algebra of the symmetric group \(S_n\) with quantum parameter \(q\) over \(R\) can be seen as a deformation of the group algebra \(R S_n\); indeed, it becomes \(R S_n\) when \(q = 1\).
Warning
The multiplication on the Hecke algebra of the symmetric group does not follow the global option
mult
of thePermutations
class (seeoptions()
). It is always as defined above. It does not match the default option (mult=l2r
) of the symmetric group algebra!EXAMPLES:
sage: HeckeAlgebraSymmetricGroupT(QQ, 3) Hecke algebra of the symmetric group of order 3 on the T basis over Univariate Polynomial Ring in q over Rational Field
sage: HeckeAlgebraSymmetricGroupT(QQ, 3, 2) Hecke algebra of the symmetric group of order 3 with q=2 on the T basis over Rational Field
The multiplication on the Hecke algebra follows a different convention than the one on the symmetric group algebra does by default:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ, 3) sage: H3([1,3,2]) * H3([2,1,3]) T[3, 1, 2] sage: S3 = SymmetricGroupAlgebra(QQ, 3) sage: S3([1,3,2]) * S3([2,1,3]) [2, 3, 1] sage: TestSuite(H3).run()
- class sage.combinat.symmetric_group_algebra.HeckeAlgebraSymmetricGroup_generic(R, n, q=None)#
Bases:
sage.combinat.free_module.CombinatorialFreeModule
- one_basis()#
Return the identity permutation.
EXAMPLES:
sage: HeckeAlgebraSymmetricGroupT(QQ, 3).one() # indirect doctest T[1, 2, 3]
- q()#
Return the variable or parameter \(q\).
EXAMPLES:
sage: HeckeAlgebraSymmetricGroupT(QQ, 3).q() q sage: HeckeAlgebraSymmetricGroupT(QQ, 3, 2).q() 2
- class sage.combinat.symmetric_group_algebra.HeckeAlgebraSymmetricGroup_t(R, n, q=None)#
Bases:
sage.combinat.symmetric_group_algebra.HeckeAlgebraSymmetricGroup_generic
- algebra_generators()#
Return the generators of the algebra.
EXAMPLES:
sage: HeckeAlgebraSymmetricGroupT(QQ,3).algebra_generators() [T[2, 1, 3], T[1, 3, 2]]
- jucys_murphy(k)#
Return the Jucys-Murphy element \(J_k\) of the Hecke algebra.
These Jucys-Murphy elements are defined by
\[J_k = (T_{k-1} T_{k-2} \cdots T_1) (T_1 T_2 \cdots T_{k-1}).\]More explicitly,
\[J_k = q^{k-1} + \sum_{l=1}^{k-1} (q^l - q^{l-1}) T_{(l, k)}.\]For generic \(q\), the \(J_k\) generate a maximal commutative sub-algebra of the Hecke algebra.
Warning
The specialization \(q = 1\) does not map these elements \(J_k\) to the Young-Jucys-Murphy elements of the group algebra \(R S_n\). (Instead, it maps the “reduced” Jucys-Murphy elements \((J_k - q^{k-1}) / (q - 1)\) to the Young-Jucys-Murphy elements of \(R S_n\).)
EXAMPLES:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ,3) sage: j2 = H3.jucys_murphy(2); j2 q*T[1, 2, 3] + (q-1)*T[2, 1, 3] sage: j3 = H3.jucys_murphy(3); j3 q^2*T[1, 2, 3] + (q^2-q)*T[1, 3, 2] + (q-1)*T[3, 2, 1] sage: j2*j3 == j3*j2 True sage: j0 = H3.jucys_murphy(1); j0 == H3.one() True sage: H3.jucys_murphy(0) Traceback (most recent call last): ... ValueError: k (= 0) must be between 1 and n (= 3)
- product_on_basis(perm1, perm2)#
EXAMPLES:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ, 3, 1) sage: a = H3([2,1,3])+2*H3([1,2,3])-H3([3,2,1]) sage: a^2 #indirect doctest 6*T[1, 2, 3] + 4*T[2, 1, 3] - T[2, 3, 1] - T[3, 1, 2] - 4*T[3, 2, 1]
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = QS3([2,1,3])+2*QS3([1,2,3])-QS3([3,2,1]) sage: a^2 6*[1, 2, 3] + 4*[2, 1, 3] - [2, 3, 1] - [3, 1, 2] - 4*[3, 2, 1]
- t(i)#
Return the element \(T_i\) of the Hecke algebra
self
.EXAMPLES:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ,3) sage: H3.t(1) T[2, 1, 3] sage: H3.t(2) T[1, 3, 2] sage: H3.t(0) Traceback (most recent call last): ... ValueError: i (= 0) must be between 1 and n-1 (= 2)
- t_action(a, i)#
Return the product \(T_i \cdot a\).
EXAMPLES:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ, 3) sage: a = H3([2,1,3])+2*H3([1,2,3]) sage: H3.t_action(a, 1) q*T[1, 2, 3] + (q+1)*T[2, 1, 3] sage: H3.t(1)*a q*T[1, 2, 3] + (q+1)*T[2, 1, 3]
- t_action_on_basis(perm, i)#
Return the product \(T_i \cdot T_{perm}\), where
perm
is a permutation in the symmetric group \(S_n\).EXAMPLES:
sage: H3 = HeckeAlgebraSymmetricGroupT(QQ, 3) sage: H3.t_action_on_basis(Permutation([2,1,3]), 1) q*T[1, 2, 3] + (q-1)*T[2, 1, 3] sage: H3.t_action_on_basis(Permutation([1,2,3]), 1) T[2, 1, 3] sage: H3 = HeckeAlgebraSymmetricGroupT(QQ, 3, 1) sage: H3.t_action_on_basis(Permutation([2,1,3]), 1) T[1, 2, 3] sage: H3.t_action_on_basis(Permutation([1,3,2]), 2) T[1, 2, 3]
- sage.combinat.symmetric_group_algebra.SymmetricGroupAlgebra(R, W, category=None)#
Return the symmetric group algebra of order
W
over the ringR
.INPUT:
W
– a symmetric group; alternatively an integer \(n\) can be provided, as shorthand forPermutations(n)
.R
– a base ringcategory
– a category (default: the category ofW
)
This supports several implementations of the symmetric group. At this point this has been tested with
W=Permutations(n)
andW=SymmetricGroup(n)
.Warning
Some features are failing in the latter case, in particular if the domain of the symmetric group is not \(1,\ldots,n\).
Note
The brave can also try setting
W=WeylGroup(['A',n-1])
, but little support for this currently exists.EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3); QS3 Symmetric group algebra of order 3 over Rational Field sage: QS3(1) [1, 2, 3] sage: QS3(2) 2*[1, 2, 3] sage: basis = [QS3(p) for p in Permutations(3)] sage: a = sum(basis); a [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: a^2 6*[1, 2, 3] + 6*[1, 3, 2] + 6*[2, 1, 3] + 6*[2, 3, 1] + 6*[3, 1, 2] + 6*[3, 2, 1] sage: a^2 == 6*a True sage: b = QS3([3, 1, 2]) sage: b [3, 1, 2] sage: b*a [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: b*a == a True
We now construct the symmetric group algebra by providing explicitly the underlying group:
sage: SGA = SymmetricGroupAlgebra(QQ, Permutations(4)); SGA Symmetric group algebra of order 4 over Rational Field sage: SGA.group() Standard permutations of 4 sage: SGA.an_element() [1, 2, 3, 4] + 2*[1, 2, 4, 3] + 3*[1, 3, 2, 4] + [4, 1, 2, 3] sage: SGA = SymmetricGroupAlgebra(QQ, SymmetricGroup(4)); SGA Symmetric group algebra of order 4 over Rational Field sage: SGA.group() Symmetric group of order 4! as a permutation group sage: SGA.an_element() () + (2,3,4) + 2*(1,3)(2,4) + 3*(1,4)(2,3) sage: SGA = SymmetricGroupAlgebra(QQ, WeylGroup(["A",3], prefix='s')); SGA Symmetric group algebra of order 4 over Rational Field sage: SGA.group() Weyl Group of type ['A', 3] (as a matrix group acting on the ambient space) sage: SGA.an_element() s1*s2*s3 + 3*s3*s2 + 2*s3 + 1
The preferred way to construct the symmetric group algebra is to go through the usual
algebra
method:sage: SGA = Permutations(3).algebra(QQ); SGA Symmetric group algebra of order 3 over Rational Field sage: SGA.group() Standard permutations of 3 sage: SGA = SymmetricGroup(3).algebra(QQ); SGA Symmetric group algebra of order 3 over Rational Field sage: SGA.group() Symmetric group of order 3! as a permutation group
The canonical embedding from the symmetric group algebra of order \(n\) to the symmetric group algebra of order \(p > n\) is available as a coercion:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: QS4.coerce_map_from(QS3) Generic morphism: From: Symmetric group algebra of order 3 over Rational Field To: Symmetric group algebra of order 4 over Rational Field sage: x3 = QS3([3,1,2]) + 2 * QS3([2,3,1]); x3 2*[2, 3, 1] + [3, 1, 2] sage: QS4(x3) 2*[2, 3, 1, 4] + [3, 1, 2, 4]
This allows for mixed expressions:
sage: x4 = 3*QS4([3, 1, 4, 2]) sage: x3 + x4 2*[2, 3, 1, 4] + [3, 1, 2, 4] + 3*[3, 1, 4, 2] sage: QS0 = SymmetricGroupAlgebra(QQ, 0) sage: QS1 = SymmetricGroupAlgebra(QQ, 1) sage: x0 = QS0([]) sage: x1 = QS1([1]) sage: x0 * x1 [1] sage: x3 - (2*x0 + x1) - x4 -3*[1, 2, 3, 4] + 2*[2, 3, 1, 4] + [3, 1, 2, 4] - 3*[3, 1, 4, 2]
Caveat: to achieve this, constructing
SymmetricGroupAlgebra(QQ, 10)
currently triggers the construction of all symmetric group algebras of smaller order. Is this a feature we really want to have?Warning
The semantics of multiplication in symmetric group algebras with index set
Permutations(n)
is determined by the order in which permutations are multiplied, which currently defaults to “in such a way that multiplication is associative with permutations acting on integers from the right”, but can be changed to the opposite order at runtime by setting the global variablePermutations.options['mult']
(seesage.combinat.permutation.Permutations.options()
). On the other hand, the semantics of multiplication in symmetric group algebras with index setSymmetricGroup(n)
does not depend on this global variable. (This has the awkward consequence that the coercions between these two sorts of symmetric group algebras do not respect multiplication when this global variable is set to'r2l'
.) In view of this, it is recommended that code not rely on the usual multiplication function, but rather use the methodsleft_action_product()
andright_action_product()
for multiplying permutations (these methods don’t depend on the setting). See trac ticket #14885 for more information.We conclude by constructing the algebra of the symmetric group as a monoid algebra:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3, category=Monoids()) sage: QS3.category() Category of finite dimensional cellular monoid algebras over Rational Field sage: TestSuite(QS3).run(skip=['_test_construction'])
- class sage.combinat.symmetric_group_algebra.SymmetricGroupAlgebra_n(R, W, category)#
Bases:
sage.algebras.group_algebra.GroupAlgebra_class
- algebra_generators()#
Return generators of this group algebra (as algebra) as a list of permutations.
The generators used for the group algebra of \(S_n\) are the transposition \((2, 1)\) and the \(n\)-cycle \((1, 2, \ldots, n)\), unless \(n \leq 1\) (in which case no generators are needed).
EXAMPLES:
sage: SymmetricGroupAlgebra(ZZ,5).algebra_generators() Family ([2, 1, 3, 4, 5], [2, 3, 4, 5, 1]) sage: SymmetricGroupAlgebra(QQ,0).algebra_generators() Family () sage: SymmetricGroupAlgebra(QQ,1).algebra_generators() Family ()
- antipode(x)#
Return the image of the element
x
ofself
under the antipode of the Hopf algebraself
(where the comultiplication is the usual one on a group algebra).Explicitly, this is obtained by replacing each permutation \(\sigma\) by \(\sigma^{-1}\) in
x
while keeping all coefficients as they are.EXAMPLES:
sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: QS4.antipode(2 * QS4([1, 3, 4, 2]) - 1/2 * QS4([1, 4, 2, 3])) -1/2*[1, 3, 4, 2] + 2*[1, 4, 2, 3] sage: all( QS4.antipode(QS4(p)) == QS4(p.inverse()) ....: for p in Permutations(4) ) True sage: ZS3 = SymmetricGroupAlgebra(ZZ, 3) sage: ZS3.antipode(ZS3.zero()) 0 sage: ZS3.antipode(-ZS3(Permutation([2, 3, 1]))) -[3, 1, 2]
- binary_unshuffle_sum(k)#
Return the \(k\)-th binary unshuffle sum in the group algebra
self
.The \(k\)-th binary unshuffle sum in the symmetric group algebra \(R S_n\) over a ring \(R\) is defined as the sum of all permutations \(\sigma \in S_n\) satisfying \(\sigma(1) < \sigma(2) < \cdots < \sigma(k)\) and \(\sigma(k+1) < \sigma(k+2) < \cdots < \sigma(n)\).
This element has the property that, if it is denoted by \(t_k\), and if the \(k\)-th semi-RSW element (see
semi_rsw_element()
) is denoted by \(s_k\), then \(s_k S(t_k)\) and \(t_k S(s_k)\) both equal the \(k\)-th Reiner-Saliola-Welker shuffling element of \(R S_n\) (seersw_shuffling_element()
).The \(k\)-th binary unshuffle sum is the image of the complete non-commutative symmetric function \(S^{(k, n-k)}\) in the ring of non-commutative symmetric functions under the canonical projection on the symmetric group algebra (through the descent algebra).
EXAMPLES:
The binary unshuffle sums on \(\QQ S_3\):
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS3.binary_unshuffle_sum(0) [1, 2, 3] sage: QS3.binary_unshuffle_sum(1) [1, 2, 3] + [2, 1, 3] + [3, 1, 2] sage: QS3.binary_unshuffle_sum(2) [1, 2, 3] + [1, 3, 2] + [2, 3, 1] sage: QS3.binary_unshuffle_sum(3) [1, 2, 3] sage: QS3.binary_unshuffle_sum(4) 0
Let us check the relation with the \(k\)-th Reiner-Saliola-Welker shuffling element stated in the docstring:
sage: def test_rsw(n): ....: ZSn = SymmetricGroupAlgebra(ZZ, n) ....: for k in range(1, n): ....: a = ZSn.semi_rsw_element(k) ....: b = ZSn.binary_unshuffle_sum(k) ....: c = ZSn.left_action_product(a, ZSn.antipode(b)) ....: d = ZSn.left_action_product(b, ZSn.antipode(a)) ....: e = ZSn.rsw_shuffling_element(k) ....: if c != e or d != e: ....: return False ....: return True sage: test_rsw(3) True sage: test_rsw(4) # long time True sage: test_rsw(5) # long time True
Let us also check the statement about the complete non-commutative symmetric function:
sage: def test_rsw_ncsf(n): ....: ZSn = SymmetricGroupAlgebra(ZZ, n) ....: NSym = NonCommutativeSymmetricFunctions(ZZ) ....: S = NSym.S() ....: for k in range(1, n): ....: a = S(Composition([k, n-k])).to_symmetric_group_algebra() ....: if a != ZSn.binary_unshuffle_sum(k): ....: return False ....: return True sage: test_rsw_ncsf(3) True sage: test_rsw_ncsf(4) True sage: test_rsw_ncsf(5) # long time True
- canonical_embedding(other)#
Return the canonical coercion of
self
into a symmetric group algebraother
.INPUT:
other
– a symmetric group algebra with order \(p\) satisfying \(p \geq n\), where \(n\) is the order ofself
, over a ground ring into which the ground ring ofself
coerces.
EXAMPLES:
sage: QS2 = SymmetricGroupAlgebra(QQ, 2) sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: phi = QS2.canonical_embedding(QS4); phi Generic morphism: From: Symmetric group algebra of order 2 over Rational Field To: Symmetric group algebra of order 4 over Rational Field sage: x = QS2([2,1]) + 2 * QS2([1,2]) sage: phi(x) 2*[1, 2, 3, 4] + [2, 1, 3, 4] sage: loads(dumps(phi)) Generic morphism: From: Symmetric group algebra of order 2 over Rational Field To: Symmetric group algebra of order 4 over Rational Field sage: ZS2 = SymmetricGroupAlgebra(ZZ, 2) sage: phi = ZS2.canonical_embedding(QS4); phi Generic morphism: From: Symmetric group algebra of order 2 over Integer Ring To: Symmetric group algebra of order 4 over Rational Field sage: phi = ZS2.canonical_embedding(QS2); phi Generic morphism: From: Symmetric group algebra of order 2 over Integer Ring To: Symmetric group algebra of order 2 over Rational Field sage: QS4.canonical_embedding(QS2) Traceback (most recent call last): ... ValueError: There is no canonical embedding from Symmetric group algebra of order 2 over Rational Field to Symmetric group algebra of order 4 over Rational Field sage: QS4g = SymmetricGroup(4).algebra(QQ) sage: QS4.canonical_embedding(QS4g)(QS4([1,3,2,4])) (2,3) sage: QS4g.canonical_embedding(QS4)(QS4g((2,3))) [1, 3, 2, 4] sage: ZS2.canonical_embedding(QS4g)(ZS2([2,1])) (1,2) sage: ZS2g = SymmetricGroup(2).algebra(ZZ) sage: ZS2g.canonical_embedding(QS4)(ZS2g((1,2))) [2, 1, 3, 4]
- cell_module(la, **kwds)#
Return the cell module indexed by
la
.EXAMPLES:
sage: S = SymmetricGroupAlgebra(QQ, 3) sage: M = S.cell_module(Partition([2,1])); M Cell module indexed by [2, 1] of Cellular basis of Symmetric group algebra of order 3 over Rational Field
We check that the input
la
is standardized:sage: N = S.cell_module([2,1]) sage: M is N True
- cell_module_indices(la)#
Return the indices of the cell module of
self
indexed byla
.This is the finite set \(M(\lambda)\).
EXAMPLES:
sage: S = SymmetricGroupAlgebra(QQ, 4) sage: S.cell_module_indices([3,1]) Standard tableaux of shape [3, 1]
- cell_poset()#
Return the cell poset of
self
.EXAMPLES:
sage: S = SymmetricGroupAlgebra(QQ, 4) sage: S.cell_poset() Finite poset containing 5 elements
- central_orthogonal_idempotent(la, block=True)#
Return the central idempotent for the symmetric group of order \(n\) corresponding to the indecomposable block to which the partition
la
is associated.If
self.base_ring()
contains \(\QQ\), this corresponds to the classical central idempotent corresponding to the irreducible representation indexed byla
.Alternatively, if
self.base_ring()
has characteristic \(p > 0\), then Theorem 2.8 in [Mur1983] provides thatla
is associated to an idempotent \(f_\mu\), where \(\mu\) is the \(p\)-core ofla
. This \(f_\mu\) is a sum of classical idempotents,\[f_\mu = \sum_{c(\lambda)=\mu} e_\lambda,\]where the sum ranges over the partitions \(\lambda\) of \(n\) with \(p\)-core equal to \(\mu\).
INPUT:
la
– a partition ofself.n
or aself.base_ring().characteristic()
-core of such a partitionblock
– boolean (default:True
); whenFalse
, this returns the classical idempotent associated tola
(defined over \(\QQ\))
OUTPUT:
If
block=False
and the corresponding coefficients are not defined overself.base_ring()
, then returnNone
. Otherwise return an element ofself
.EXAMPLES:
Asking for block idempotents in any characteristic, by passing a partition of
self.n
:sage: S0 = SymmetricGroup(4).algebra(QQ) sage: S2 = SymmetricGroup(4).algebra(GF(2)) sage: S3 = SymmetricGroup(4).algebra(GF(3)) sage: S0.central_orthogonal_idempotent([2,1,1]) 3/8*() - 1/8*(3,4) - 1/8*(2,3) - 1/8*(2,4) - 1/8*(1,2) - 1/8*(1,2)(3,4) + 1/8*(1,2,3,4) + 1/8*(1,2,4,3) + 1/8*(1,3,4,2) - 1/8*(1,3) - 1/8*(1,3)(2,4) + 1/8*(1,3,2,4) + 1/8*(1,4,3,2) - 1/8*(1,4) + 1/8*(1,4,2,3) - 1/8*(1,4)(2,3) sage: S2.central_orthogonal_idempotent([2,1,1]) () sage: idem = S3.central_orthogonal_idempotent([4]); idem () + (1,2)(3,4) + (1,3)(2,4) + (1,4)(2,3) sage: idem == S3.central_orthogonal_idempotent([1,1,1,1]) True sage: S3.central_orthogonal_idempotent([2,2]) () + (1,2)(3,4) + (1,3)(2,4) + (1,4)(2,3)
Asking for block idempotents in any characteristic, by passing \(p\)-cores:
sage: S0.central_orthogonal_idempotent([1,1]) Traceback (most recent call last): ... ValueError: [1, 1] is not a partition of integer 4 sage: S2.central_orthogonal_idempotent([]) () sage: S2.central_orthogonal_idempotent([1]) Traceback (most recent call last): ... ValueError: the 2-core of [1] is not a 2-core of a partition of 4 sage: S3.central_orthogonal_idempotent([1]) () + (1,2)(3,4) + (1,3)(2,4) + (1,4)(2,3) sage: S3.central_orthogonal_idempotent([7]) () + (1,2)(3,4) + (1,3)(2,4) + (1,4)(2,3)
Asking for classical idempotents:
sage: S3.central_orthogonal_idempotent([2,2], block=False) is None True sage: S3.central_orthogonal_idempotent([2,1,1], block=False) (3,4) + (2,3) + (2,4) + (1,2) + (1,2)(3,4) + 2*(1,2,3,4) + 2*(1,2,4,3) + 2*(1,3,4,2) + (1,3) + (1,3)(2,4) + 2*(1,3,2,4) + 2*(1,4,3,2) + (1,4) + 2*(1,4,2,3) + (1,4)(2,3)
- central_orthogonal_idempotents()#
Return a maximal list of central orthogonal idempotents for
self
.This method does not require that
self
be semisimple, relying on Nakayama’s Conjecture wheneverself.base_ring()
has positive characteristic.EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: a = QS3.central_orthogonal_idempotents() sage: a[0] # [3] 1/6*[1, 2, 3] + 1/6*[1, 3, 2] + 1/6*[2, 1, 3] + 1/6*[2, 3, 1] + 1/6*[3, 1, 2] + 1/6*[3, 2, 1] sage: a[1] # [2, 1] 2/3*[1, 2, 3] - 1/3*[2, 3, 1] - 1/3*[3, 1, 2]
See also
- dft(form='seminormal', mult='l2r')#
Return the discrete Fourier transform for
self
.INPUT:
mult
– string (default: \(l2r\)). If set to \(r2l\), this causes the method to use the antipodes (antipode()
) of the seminormal basis instead of the seminormal basis.
EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS3.dft() [ 1 1 1 1 1 1] [ 1 1/2 -1 -1/2 -1/2 1/2] [ 0 3/4 0 3/4 -3/4 -3/4] [ 0 1 0 -1 1 -1] [ 1 -1/2 1 -1/2 -1/2 -1/2] [ 1 -1 -1 1 1 -1]
- epsilon_ik(itab, ktab, star=0, mult='l2r')#
Return the seminormal basis element of
self
corresponding to the pair of tableauxitab
andktab
(or restrictions of these tableaux, if the optional variablestar
is set).INPUT:
itab
,ktab
– two standard tableaux of size \(n\).star
– integer (default: \(0\)).mult
– string (default: \(l2r\)). If set to \(r2l\), this causes the method to return the antipode (antipode()
) of \(\epsilon(I, K)\) instead of \(\epsilon(I, K)\) itself.
OUTPUT:
The element \(\epsilon(I, K)\), where \(I\) and \(K\) are the tableaux obtained by removing all entries higher than \(n - \mathrm{star}\) from
itab
andktab
, respectively. Here, we are using the notations fromseminormal_basis()
.EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = QS3.epsilon_ik([[1,2,3]], [[1,2,3]]); a 1/6*[1, 2, 3] + 1/6*[1, 3, 2] + 1/6*[2, 1, 3] + 1/6*[2, 3, 1] + 1/6*[3, 1, 2] + 1/6*[3, 2, 1] sage: QS3.dft()*vector(a) (1, 0, 0, 0, 0, 0) sage: a = QS3.epsilon_ik([[1,2],[3]], [[1,2],[3]]); a 1/3*[1, 2, 3] - 1/6*[1, 3, 2] + 1/3*[2, 1, 3] - 1/6*[2, 3, 1] - 1/6*[3, 1, 2] - 1/6*[3, 2, 1] sage: QS3.dft()*vector(a) (0, 0, 0, 0, 1, 0)
Let us take some properties of the seminormal basis listed in the docstring of
seminormal_basis()
, and verify them on the situation of \(S_3\).First, check the formula
\[\epsilon(T) = \frac{1}{\kappa_{\mathrm{sh}(T)}} \epsilon(\overline{T}) e(T) \epsilon(\overline{T}).\]In fact:
sage: from sage.combinat.symmetric_group_algebra import e sage: def test_sn1(n): ....: QSn = SymmetricGroupAlgebra(QQ, n) ....: QSn1 = SymmetricGroupAlgebra(QQ, n - 1) ....: for T in StandardTableaux(n): ....: TT = T.restrict(n-1) ....: eTT = QSn1.epsilon_ik(TT, TT) ....: eT = QSn.epsilon_ik(T, T) ....: kT = prod(T.shape().hooks()) ....: if kT * eT != eTT * e(T) * eTT: ....: return False ....: return True sage: test_sn1(3) True sage: test_sn1(4) # long time True
Next, we check the identity
\[\epsilon(T, S) = \frac{1}{\kappa_{\mathrm{sh}(T)}} \epsilon(\overline S) \pi_{T, S} e(T) \epsilon(\overline T)\]which we used to define \(\epsilon(T, S)\). In fact:
sage: from sage.combinat.symmetric_group_algebra import e sage: def test_sn2(n): ....: QSn = SymmetricGroupAlgebra(QQ, n) ....: mul = QSn.left_action_product ....: QSn1 = SymmetricGroupAlgebra(QQ, n - 1) ....: for lam in Partitions(n): ....: k = prod(lam.hooks()) ....: for T in StandardTableaux(lam): ....: for S in StandardTableaux(lam): ....: TT = T.restrict(n-1) ....: SS = S.restrict(n-1) ....: eTT = QSn1.epsilon_ik(TT, TT) ....: eSS = QSn1.epsilon_ik(SS, SS) ....: eTS = QSn.epsilon_ik(T, S) ....: piTS = [0] * n ....: for (i, j) in T.cells(): ....: piTS[T[i][j] - 1] = S[i][j] ....: piTS = QSn(Permutation(piTS)) ....: if k * eTS != mul(mul(eSS, piTS), mul(e(T), eTT)): ....: return False ....: return True sage: test_sn2(3) True sage: test_sn2(4) # long time True
Let us finally check the identity
\[\epsilon(T, S) \epsilon(U, V) = \delta_{T, V} \epsilon(U, S)\]In fact:
sage: def test_sn3(lam): ....: n = lam.size() ....: QSn = SymmetricGroupAlgebra(QQ, n) ....: mul = QSn.left_action_product ....: for T in StandardTableaux(lam): ....: for S in StandardTableaux(lam): ....: for U in StandardTableaux(lam): ....: for V in StandardTableaux(lam): ....: lhs = mul(QSn.epsilon_ik(T, S), QSn.epsilon_ik(U, V)) ....: if T == V: ....: rhs = QSn.epsilon_ik(U, S) ....: else: ....: rhs = QSn.zero() ....: if rhs != lhs: ....: return False ....: return True sage: all( test_sn3(lam) for lam in Partitions(3) ) True sage: all( test_sn3(lam) for lam in Partitions(4) ) # long time True
- jucys_murphy(k)#
Return the Jucys-Murphy element \(J_k\) (also known as a Young-Jucys-Murphy element) for the symmetric group algebra
self
.The Jucys-Murphy element \(J_k\) in the symmetric group algebra \(R S_n\) is defined for every \(k \in \{ 1, 2, \ldots, n \}\) by
\[J_k = (1, k) + (2, k) + \cdots + (k-1, k) \in R S_n,\]where the addends are transpositions in \(S_n\) (regarded as elements of \(R S_n\)). We note that there is not a dependence on \(n\), so it is often suppressed in the notation.
EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS3.jucys_murphy(1) 0 sage: QS3.jucys_murphy(2) [2, 1, 3] sage: QS3.jucys_murphy(3) [1, 3, 2] + [3, 2, 1] sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: j3 = QS4.jucys_murphy(3); j3 [1, 3, 2, 4] + [3, 2, 1, 4] sage: j4 = QS4.jucys_murphy(4); j4 [1, 2, 4, 3] + [1, 4, 3, 2] + [4, 2, 3, 1] sage: j3*j4 == j4*j3 True sage: QS5 = SymmetricGroupAlgebra(QQ, 5) sage: QS5.jucys_murphy(4) [1, 2, 4, 3, 5] + [1, 4, 3, 2, 5] + [4, 2, 3, 1, 5]
- left_action_product(left, right)#
Return the product of two elements
left
andright
ofself
, where multiplication is defined in such a way that for two permutations \(p\) and \(q\), the product \(pq\) is the permutation obtained by first applying \(q\) and then applying \(p\). This definition of multiplication is tailored to make multiplication of permutations associative with their action on numbers if permutations are to act on numbers from the left.EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: p1 = Permutation([2, 1, 3]) sage: p2 = Permutation([3, 1, 2]) sage: QS3.left_action_product(QS3(p1), QS3(p2)) [3, 2, 1] sage: x = QS3([1, 2, 3]) - 2*QS3([1, 3, 2]) sage: y = 1/2 * QS3([3, 1, 2]) + 3*QS3([1, 2, 3]) sage: QS3.left_action_product(x, y) 3*[1, 2, 3] - 6*[1, 3, 2] - [2, 1, 3] + 1/2*[3, 1, 2] sage: QS3.left_action_product(0, x) 0
The method coerces its input into the algebra
self
:sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: QS4.left_action_product(QS3([1, 2, 3]), QS3([2, 1, 3])) [2, 1, 3, 4] sage: QS4.left_action_product(1, Permutation([4, 1, 2, 3])) [4, 1, 2, 3]
Warning
Note that coercion presently works from permutations of
n
into then
-th symmetric group algebra, and also from all smaller symmetric group algebras into then
-th symmetric group algebra, but not from permutations of integers smaller thann
into then
-th symmetric group algebra.
- monomial_from_smaller_permutation(permutation)#
Convert
permutation
into a permutation, possibly extending it to the appropriate size, and return the corresponding basis element ofself
.EXAMPLES:
sage: QS5 = SymmetricGroupAlgebra(QQ, 5) sage: QS5.monomial_from_smaller_permutation([]) [1, 2, 3, 4, 5] sage: QS5.monomial_from_smaller_permutation(Permutation([3,1,2])) [3, 1, 2, 4, 5] sage: QS5.monomial_from_smaller_permutation([5,3,4,1,2]) [5, 3, 4, 1, 2] sage: QS5.monomial_from_smaller_permutation(SymmetricGroup(2)((1,2))) [2, 1, 3, 4, 5] sage: QS5g = SymmetricGroup(5).algebra(QQ) sage: QS5g.monomial_from_smaller_permutation([2,1]) (1,2)
- retract_direct_product(f, m)#
Return the direct-product retract of the element \(f \in R S_n\) to \(R S_m\), where \(m \leq n\) (and where \(R S_n\) is
self
).If \(m\) is a nonnegative integer less or equal to \(n\), then the direct-product retract from \(S_n\) to \(S_m\) is defined as an \(R\)-linear map \(S_n \to S_m\) which sends every permutation \(p \in S_n\) to
\[\begin{split}\begin{cases} \mbox{dret}(p) &\mbox{if } \mbox{dret}(p)\mbox{ is defined;} \\ 0 & \mbox{otherwise} \end{cases}.\end{split}\]Here \(\mbox{dret}(p)\) denotes the direct-product retract of the permutation \(p\) to \(S_m\), which is defined in
retract_direct_product()
.EXAMPLES:
sage: SGA3 = SymmetricGroupAlgebra(QQ, 3) sage: SGA3.retract_direct_product(2*SGA3([1,2,3]) - 4*SGA3([2,1,3]) + 7*SGA3([1,3,2]), 2) 2*[1, 2] - 4*[2, 1] sage: SGA3.retract_direct_product(2*SGA3([1,3,2]) - 5*SGA3([2,3,1]), 2) 0 sage: SGA5 = SymmetricGroupAlgebra(QQ, 5) sage: SGA5.retract_direct_product(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 4) 11*[3, 2, 1, 4] sage: SGA5.retract_direct_product(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 3) -6*[1, 3, 2] + 11*[3, 2, 1] sage: SGA5.retract_direct_product(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 2) 0 sage: SGA5.retract_direct_product(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 1) 2*[1] sage: SGA5.retract_direct_product(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 3) 8*[1, 2, 3] - 6*[1, 3, 2] sage: SGA5.retract_direct_product(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 1) 2*[1] sage: SGA5.retract_direct_product(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 0) 2*[]
See also
- retract_okounkov_vershik(f, m)#
Return the Okounkov-Vershik retract of the element \(f \in R S_n\) to \(R S_m\), where \(m \leq n\) (and where \(R S_n\) is
self
).If \(m\) is a nonnegative integer less or equal to \(n\), then the Okounkov-Vershik retract from \(S_n\) to \(S_m\) is defined as an \(R\)-linear map \(S_n \to S_m\) which sends every permutation \(p \in S_n\) to the Okounkov-Vershik retract of the permutation \(p\) to \(S_m\), which is defined in
retract_okounkov_vershik()
.EXAMPLES:
sage: SGA3 = SymmetricGroupAlgebra(QQ, 3) sage: SGA3.retract_okounkov_vershik(2*SGA3([1,2,3]) - 4*SGA3([2,1,3]) + 7*SGA3([1,3,2]), 2) 9*[1, 2] - 4*[2, 1] sage: SGA3.retract_okounkov_vershik(2*SGA3([1,3,2]) - 5*SGA3([2,3,1]), 2) 2*[1, 2] - 5*[2, 1] sage: SGA5 = SymmetricGroupAlgebra(QQ, 5) sage: SGA5.retract_okounkov_vershik(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 4) -6*[1, 3, 2, 4] + 8*[1, 4, 2, 3] + 11*[3, 2, 1, 4] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 3) 2*[1, 3, 2] + 11*[3, 2, 1] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 2) 13*[1, 2] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 1) 13*[1] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 3) 8*[1, 2, 3] - 6*[1, 3, 2] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 1) 2*[1] sage: SGA5.retract_okounkov_vershik(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 0) 2*[]
See also
- retract_plain(f, m)#
Return the plain retract of the element \(f \in R S_n\) to \(R S_m\), where \(m \leq n\) (and where \(R S_n\) is
self
).If \(m\) is a nonnegative integer less or equal to \(n\), then the plain retract from \(S_n\) to \(S_m\) is defined as an \(R\)-linear map \(S_n \to S_m\) which sends every permutation \(p \in S_n\) to
\[\begin{split}\begin{cases} \mbox{pret}(p) &\mbox{if } \mbox{pret}(p)\mbox{ is defined;} \\ 0 & \mbox{otherwise} \end{cases}.\end{split}\]Here \(\mbox{pret}(p)\) denotes the plain retract of the permutation \(p\) to \(S_m\), which is defined in
retract_plain()
.EXAMPLES:
sage: SGA3 = SymmetricGroupAlgebra(QQ, 3) sage: SGA3.retract_plain(2*SGA3([1,2,3]) - 4*SGA3([2,1,3]) + 7*SGA3([1,3,2]), 2) 2*[1, 2] - 4*[2, 1] sage: SGA3.retract_plain(2*SGA3([1,3,2]) - 5*SGA3([2,3,1]), 2) 0 sage: SGA5 = SymmetricGroupAlgebra(QQ, 5) sage: SGA5.retract_plain(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 4) 11*[3, 2, 1, 4] sage: SGA5.retract_plain(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 3) 11*[3, 2, 1] sage: SGA5.retract_plain(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 2) 0 sage: SGA5.retract_plain(8*SGA5([1,4,2,5,3]) - 6*SGA5([1,3,2,5,4]) + 11*SGA5([3,2,1,4,5]), 1) 0 sage: SGA5.retract_plain(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 3) 8*[1, 2, 3] - 6*[1, 3, 2] sage: SGA5.retract_plain(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 1) 8*[1] sage: SGA5.retract_plain(8*SGA5([1,2,3,4,5]) - 6*SGA5([1,3,2,4,5]), 0) 8*[]
- right_action_product(left, right)#
Return the product of two elements
left
andright
ofself
, where multiplication is defined in such a way that for two permutations \(p\) and \(q\), the product \(pq\) is the permutation obtained by first applying \(p\) and then applying \(q\). This definition of multiplication is tailored to make multiplication of permutations associative with their action on numbers if permutations are to act on numbers from the right.EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: p1 = Permutation([2, 1, 3]) sage: p2 = Permutation([3, 1, 2]) sage: QS3.right_action_product(QS3(p1), QS3(p2)) [1, 3, 2] sage: x = QS3([1, 2, 3]) - 2*QS3([1, 3, 2]) sage: y = 1/2 * QS3([3, 1, 2]) + 3*QS3([1, 2, 3]) sage: QS3.right_action_product(x, y) 3*[1, 2, 3] - 6*[1, 3, 2] + 1/2*[3, 1, 2] - [3, 2, 1] sage: QS3.right_action_product(0, x) 0
The method coerces its input into the algebra
self
:sage: QS4 = SymmetricGroupAlgebra(QQ, 4) sage: QS4.right_action_product(QS3([1, 2, 3]), QS3([2, 1, 3])) [2, 1, 3, 4] sage: QS4.right_action_product(1, Permutation([4, 1, 2, 3])) [4, 1, 2, 3]
Warning
Note that coercion presently works from permutations of
n
into then
-th symmetric group algebra, and also from all smaller symmetric group algebras into then
-th symmetric group algebra, but not from permutations of integers smaller thann
into then
-th symmetric group algebra.
- rsw_shuffling_element(k)#
Return the \(k\)-th Reiner-Saliola-Welker shuffling element in the group algebra
self
.The \(k\)-th Reiner-Saliola-Welker shuffling element in the symmetric group algebra \(R S_n\) over a ring \(R\) is defined as the sum \(\sum_{\sigma \in S_n} \mathrm{noninv}_k(\sigma) \cdot \sigma\), where for every permutation \(\sigma\), the number \(\mathrm{noninv}_k(\sigma)\) is the number of all \(k\)-noninversions of \(\sigma\) (that is, the number of all \(k\)-element subsets of \(\{ 1, 2, \ldots, n \}\) on which \(\sigma\) restricts to a strictly increasing map). See
sage.combinat.permutation.number_of_noninversions()
for the \(\mathrm{noninv}\) map.This element is more or less the operator \(\nu_{k, 1^{n-k}}\) introduced in [RSW2011]; more precisely, \(\nu_{k, 1^{n-k}}\) is the left multiplication by this element.
It is a nontrivial theorem (Theorem 1.1 in [RSW2011]) that the operators \(\nu_{k, 1^{n-k}}\) (for fixed \(n\) and varying \(k\)) pairwise commute. It is a conjecture (Conjecture 1.2 in [RSW2011]) that all their eigenvalues are integers (which, in light of their commutativity and easily established symmetry, yields that they can be simultaneously diagonalized over \(\QQ\) with only integer eigenvalues).
EXAMPLES:
The Reiner-Saliola-Welker shuffling elements on \(\QQ S_3\):
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS3.rsw_shuffling_element(0) [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: QS3.rsw_shuffling_element(1) 3*[1, 2, 3] + 3*[1, 3, 2] + 3*[2, 1, 3] + 3*[2, 3, 1] + 3*[3, 1, 2] + 3*[3, 2, 1] sage: QS3.rsw_shuffling_element(2) 3*[1, 2, 3] + 2*[1, 3, 2] + 2*[2, 1, 3] + [2, 3, 1] + [3, 1, 2] sage: QS3.rsw_shuffling_element(3) [1, 2, 3] sage: QS3.rsw_shuffling_element(4) 0
Checking the commutativity of Reiner-Saliola-Welker shuffling elements (we leave out the ones for which it is trivial):
sage: def test_rsw_comm(n): ....: QSn = SymmetricGroupAlgebra(QQ, n) ....: rsws = [QSn.rsw_shuffling_element(k) for k in range(2, n)] ....: return all( all( rsws[i] * rsws[j] == rsws[j] * rsws[i] ....: for j in range(i) ) ....: for i in range(len(rsws)) ) sage: test_rsw_comm(3) True sage: test_rsw_comm(4) True sage: test_rsw_comm(5) # long time True
Note
For large
k
(relative ton
), it might be faster to callQSn.left_action_product(QSn.semi_rsw_element(k), QSn.antipode(binary_unshuffle_sum(k)))
thanQSn.rsw_shuffling_element(n)
.See also
- semi_rsw_element(k)#
Return the \(k\)-th semi-RSW element in the group algebra
self
.The \(k\)-th semi-RSW element in the symmetric group algebra \(R S_n\) over a ring \(R\) is defined as the sum of all permutations \(\sigma \in S_n\) satisfying \(\sigma(1) < \sigma(2) < \cdots < \sigma(k)\).
This element has the property that, if it is denoted by \(s_k\), then \(s_k S(s_k)\) is \((n-k)!\) times the \(k\)-th Reiner-Saliola-Welker shuffling element of \(R S_n\) (see
rsw_shuffling_element()
). Here, \(S\) denotes the antipode of the group algebra \(R S_n\).The \(k\)-th semi-RSW element is the image of the complete non-commutative symmetric function \(S^{(k, 1^{n-k})}\) in the ring of non-commutative symmetric functions under the canonical projection on the symmetric group algebra (through the descent algebra).
EXAMPLES:
The semi-RSW elements on \(\QQ S_3\):
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: QS3.semi_rsw_element(0) [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: QS3.semi_rsw_element(1) [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: QS3.semi_rsw_element(2) [1, 2, 3] + [1, 3, 2] + [2, 3, 1] sage: QS3.semi_rsw_element(3) [1, 2, 3] sage: QS3.semi_rsw_element(4) 0
Let us check the relation with the \(k\)-th Reiner-Saliola-Welker shuffling element stated in the docstring:
sage: def test_rsw(n): ....: ZSn = SymmetricGroupAlgebra(ZZ, n) ....: for k in range(1, n): ....: a = ZSn.semi_rsw_element(k) ....: b = ZSn.left_action_product(a, ZSn.antipode(a)) ....: if factorial(n-k) * ZSn.rsw_shuffling_element(k) != b: ....: return False ....: return True sage: test_rsw(3) True sage: test_rsw(4) True sage: test_rsw(5) # long time True
Let us also check the statement about the complete non-commutative symmetric function:
sage: def test_rsw_ncsf(n): ....: ZSn = SymmetricGroupAlgebra(ZZ, n) ....: NSym = NonCommutativeSymmetricFunctions(ZZ) ....: S = NSym.S() ....: for k in range(1, n): ....: a = S(Composition([k] + [1]*(n-k))).to_symmetric_group_algebra() ....: if a != ZSn.semi_rsw_element(k): ....: return False ....: return True sage: test_rsw_ncsf(3) True sage: test_rsw_ncsf(4) True sage: test_rsw_ncsf(5) # long time True
- seminormal_basis(mult='l2r')#
Return a list of the seminormal basis elements of
self
.The seminormal basis of a symmetric group algebra is defined as follows:
Let \(n\) be a nonnegative integer. Let \(R\) be a \(\QQ\)-algebra. In the following, we will use the “left action” convention for multiplying permutations. This means that for all permutations \(p\) and \(q\) in \(S_n\), the product \(pq\) is defined in such a way that \((pq)(i) = p(q(i))\) for each \(i \in \{ 1, 2, \ldots, n \}\) (this is the same convention as in
left_action_product()
, but not the default semantics of the \(*\) operator on permutations in Sage). Thus, for instance, \(s_2 s_1\) is the permutation obtained by first transposing \(1\) with \(2\) and then transposing \(2\) with \(3\) (where \(s_i = (i, i+1)\)).For every partition \(\lambda\) of \(n\), let
\[\kappa_{\lambda} = \frac{n!}{f^{\lambda}}\]where \(f^{\lambda}\) is the number of standard Young tableaux of shape \(\lambda\). Note that \(\kappa_{\lambda}\) is an integer, namely the product of all hook lengths of \(\lambda\) (by the hook length formula). In Sage, this integer can be computed by using
sage.combinat.symmetric_group_algebra.kappa()
.Let \(T\) be a standard tableau of size \(n\).
Let \(a(T)\) denote the formal sum (in \(R S_n\)) of all permutations in \(S_n\) which stabilize the rows of \(T\) (as sets), i. e., which map each entry \(i\) of \(T\) to an entry in the same row as \(i\). (See
sage.combinat.symmetric_group_algebra.a()
for an implementation of this.)Let \(b(T)\) denote the signed formal sum (in \(R S_n\)) of all permutations in \(S_n\) which stabilize the columns of \(T\) (as sets). Here, “signed” means that each permutation is multiplied with its sign. (This is implemented in
sage.combinat.symmetric_group_algebra.b()
.)Define an element \(e(T)\) of \(R S_n\) to be \(a(T) b(T)\). (This is implemented in
sage.combinat.symmetric_group_algebra.e()
for \(R = \QQ\).)Let \(\mathrm{sh}(T)\) denote the shape of \(T\). (See
shape()
.)Let \(\overline{T}\) denote the standard tableau of size \(n-1\) obtained by removing the letter \(n\) (along with its cell) from \(T\) (if \(n \geq 1\)).
Now, we define an element \(\epsilon(T)\) of \(R S_n\). We define it by induction on the size \(n\) of \(T\), so we set \(\epsilon(\emptyset) = 1\) and only need to define \(\epsilon(T)\) for \(n \geq 1\), assuming that \(\epsilon(\overline{T})\) is already defined. We do this by setting
\[\epsilon(T) = \frac{1}{\kappa_{\mathrm{sh}(T)}} \epsilon(\overline{T}) e(T) \epsilon(\overline{T}).\]This element \(\epsilon(T)\) is implemented as
sage.combinat.symmetric_group_algebra.epsilon()
for \(R = \QQ\), but it is also a particular case of the elements \(\epsilon(T, S)\) defined below.Now let \(S\) be a further tableau of the same shape as \(T\) (possibly equal to \(T\)). Let \(\pi_{T, S}\) denote the permutation in \(S_n\) such that applying this permutation to the entries of \(T\) yields the tableau \(S\). Define an element \(\epsilon(T, S)\) of \(R S_n\) by
\[\epsilon(T, S) = \frac{1}{\kappa_{\mathrm{sh}(T)}} \epsilon(\overline S) \pi_{T, S} e(T) \epsilon(\overline T) = \frac{1}{\kappa_{\mathrm{sh}(T)}} \epsilon(\overline S) a(S) \pi_{T, S} b(T) \epsilon(\overline T).\]This element \(\epsilon(T, S)\) is called Young’s seminormal unit corresponding to the bitableau `(T, S)`, and is the return value of
epsilon_ik()
applied toT
andS
. Note that \(\epsilon(T, T) = \epsilon(T)\).If we let \(\lambda\) run through all partitions of \(n\), and \((T, S)\) run through all pairs of tableaux of shape \(\lambda\), then the elements \(\epsilon(T, S)\) form a basis of \(R S_n\). This basis is called Young’s seminormal basis and has the properties that
\[\epsilon(T, S) \epsilon(U, V) = \delta_{T, V} \epsilon(U, S)\](where \(\delta\) stands for the Kronecker delta).
Warning
Because of our convention, we are multiplying our elements in reverse of those given in some papers, for example [Ram1997]. Using the other convention of multiplying permutations, we would instead have \(\epsilon(U, V) \epsilon(T, S) = \delta_{T, V} \epsilon(U, S)\).
In other words, Young’s seminormal basis consists of the matrix units in a (particular) Artin-Wedderburn decomposition of \(R S_n\) into a direct product of matrix algebras over \(\QQ\).
The output of
seminormal_basis()
is a list of all elements of the seminormal basis ofself
.INPUT:
mult
– string (default:'l2r'
). If set to'r2l'
, this causes the method to return the list of the antipodes (antipode()
) of all \(\epsilon(T, S)\) instead of the \(\epsilon(T, S)\) themselves.
EXAMPLES:
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: QS3.seminormal_basis() [1/6*[1, 2, 3] + 1/6*[1, 3, 2] + 1/6*[2, 1, 3] + 1/6*[2, 3, 1] + 1/6*[3, 1, 2] + 1/6*[3, 2, 1], 1/3*[1, 2, 3] + 1/6*[1, 3, 2] - 1/3*[2, 1, 3] - 1/6*[2, 3, 1] - 1/6*[3, 1, 2] + 1/6*[3, 2, 1], 1/3*[1, 3, 2] + 1/3*[2, 3, 1] - 1/3*[3, 1, 2] - 1/3*[3, 2, 1], 1/4*[1, 3, 2] - 1/4*[2, 3, 1] + 1/4*[3, 1, 2] - 1/4*[3, 2, 1], 1/3*[1, 2, 3] - 1/6*[1, 3, 2] + 1/3*[2, 1, 3] - 1/6*[2, 3, 1] - 1/6*[3, 1, 2] - 1/6*[3, 2, 1], 1/6*[1, 2, 3] - 1/6*[1, 3, 2] - 1/6*[2, 1, 3] + 1/6*[2, 3, 1] + 1/6*[3, 1, 2] - 1/6*[3, 2, 1]]
- sage.combinat.symmetric_group_algebra.a(tableau, star=0, base_ring=Rational Field)#
The row projection operator corresponding to the Young tableau
tableau
(which is supposed to contain every integer from \(1\) to its size precisely once, but may and may not be standard).This is the sum (in the group algebra of the relevant symmetric group over \(\QQ\)) of all the permutations which preserve the rows of
tableau
. It is called \(a_{\text{tableau}}\) in [EGHLSVY], Section 4.2.INPUT:
tableau
– Young tableau which contains every integer from \(1\) to its size precisely once.star
– nonnegative integer (default: \(0\)). When this optional variable is set, the method computes not the row projection operator oftableau
, but the row projection operator of the restriction oftableau
to the entries1, 2, ..., tableau.size() - star
instead.base_ring
– commutative ring (default:QQ
). When this optional variable is set, the row projection operator is computed over a user-determined base ring instead of \(\QQ\). (Note that symmetric group algebras currently don’t preserve coercion, so e. g. a symmetric group algebra over \(\ZZ\) does not coerce into the corresponding one over \(\QQ\); so convert manually or choose your base rings wisely!)
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import a sage: a([[1,2]]) [1, 2] + [2, 1] sage: a([[1],[2]]) [1, 2] sage: a([]) [] sage: a([[1, 5], [2, 3], [4]]) [1, 2, 3, 4, 5] + [1, 3, 2, 4, 5] + [5, 2, 3, 4, 1] + [5, 3, 2, 4, 1] sage: a([[1,4], [2,3]], base_ring=ZZ) [1, 2, 3, 4] + [1, 3, 2, 4] + [4, 2, 3, 1] + [4, 3, 2, 1]
- sage.combinat.symmetric_group_algebra.b(tableau, star=0, base_ring=Rational Field)#
The column projection operator corresponding to the Young tableau
tableau
(which is supposed to contain every integer from \(1\) to its size precisely once, but may and may not be standard).This is the signed sum (in the group algebra of the relevant symmetric group over \(\QQ\)) of all the permutations which preserve the column of
tableau
(where the signs are the usual signs of the permutations). It is called \(b_{\text{tableau}}\) in [EGHLSVY], Section 4.2.INPUT:
tableau
– Young tableau which contains every integer from \(1\) to its size precisely once.star
– nonnegative integer (default: \(0\)). When this optional variable is set, the method computes not the column projection operator oftableau
, but the column projection operator of the restriction oftableau
to the entries1, 2, ..., tableau.size() - star
instead.base_ring
– commutative ring (default:QQ
). When this optional variable is set, the column projection operator is computed over a user-determined base ring instead of \(\QQ\). (Note that symmetric group algebras currently don’t preserve coercion, so e. g. a symmetric group algebra over \(\ZZ\) does not coerce into the corresponding one over \(\QQ\); so convert manually or choose your base rings wisely!)
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import b sage: b([[1,2]]) [1, 2] sage: b([[1],[2]]) [1, 2] - [2, 1] sage: b([]) [] sage: b([[1, 2, 4], [5, 3]]) [1, 2, 3, 4, 5] - [1, 3, 2, 4, 5] - [5, 2, 3, 4, 1] + [5, 3, 2, 4, 1] sage: b([[1, 4], [2, 3]], base_ring=ZZ) [1, 2, 3, 4] - [1, 2, 4, 3] - [2, 1, 3, 4] + [2, 1, 4, 3] sage: b([[1, 4], [2, 3]], base_ring=Integers(5)) [1, 2, 3, 4] + 4*[1, 2, 4, 3] + 4*[2, 1, 3, 4] + [2, 1, 4, 3]
With the
l2r
setting for multiplication, the unnormalized Young symmetrizere(tableau)
should be the productb(tableau) * a(tableau)
for everytableau
. Let us check this on the standard tableaux of size 5:sage: from sage.combinat.symmetric_group_algebra import a, b, e sage: all( e(t) == b(t) * a(t) for t in StandardTableaux(5) ) True
- sage.combinat.symmetric_group_algebra.e(tableau, star=0)#
The unnormalized Young projection operator corresponding to the Young tableau
tableau
(which is supposed to contain every integer from \(1\) to its size precisely once, but may and may not be standard).If \(n\) is a nonnegative integer, and \(T\) is a Young tableau containing every integer from \(1\) to \(n\) exactly once, then the unnormalized Young projection operator \(e(T)\) is defined by
\[e(T) = a(T) b(T) \in \QQ S_n,\]where \(a(T) \in \QQ S_n\) is the sum of all permutations in \(S_n\) which fix the rows of \(T\) (as sets), and \(b(T) \in \QQ S_n\) is the signed sum of all permutations in \(S_n\) which fix the columns of \(T\) (as sets). Here, “signed” means that each permutation is multiplied with its sign; and the product on the group \(S_n\) is defined in such a way that \((pq)(i) = p(q(i))\) for any permutations \(p\) and \(q\) and any \(1 \leq i \leq n\).
Note that the definition of \(e(T)\) is not uniform across literature. Others define it as \(b(T) a(T)\) instead, or include certain scalar factors (we do not, whence “unnormalized”).
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import e sage: e([[1,2]]) [1, 2] + [2, 1] sage: e([[1],[2]]) [1, 2] - [2, 1] sage: e([]) []
There are differing conventions for the order of the symmetrizers and antisymmetrizers. This example illustrates our conventions:
sage: e([[1,2],[3]]) [1, 2, 3] + [2, 1, 3] - [3, 1, 2] - [3, 2, 1]
To obtain the product \(b(T) a(T)\), one has to take the antipode of this:
sage: QS3 = parent(e([[1,2],[3]])) sage: QS3.antipode(e([[1,2],[3]])) [1, 2, 3] + [2, 1, 3] - [2, 3, 1] - [3, 2, 1]
See also
- sage.combinat.symmetric_group_algebra.e_hat(tab, star=0)#
The Young projection operator corresponding to the Young tableau
tab
(which is supposed to contain every integer from \(1\) to its size precisely once, but may and may not be standard). This is an idempotent in the rational group algebra.If \(n\) is a nonnegative integer, and \(T\) is a Young tableau containing every integer from \(1\) to \(n\) exactly once, then the Young projection operator \(\widehat{e}(T)\) is defined by
\[\widehat{e}(T) = \frac{1}{\kappa_\lambda} a(T) b(T) \in \QQ S_n,\]where \(\lambda\) is the shape of \(T\), where \(\kappa_\lambda\) is \(n!\) divided by the number of standard tableaux of shape \(\lambda\), where \(a(T) \in \QQ S_n\) is the sum of all permutations in \(S_n\) which fix the rows of \(T\) (as sets), and where \(b(T) \in \QQ S_n\) is the signed sum of all permutations in \(S_n\) which fix the columns of \(T\) (as sets). Here, “signed” means that each permutation is multiplied with its sign; and the product on the group \(S_n\) is defined in such a way that \((pq)(i) = p(q(i))\) for any permutations \(p\) and \(q\) and any \(1 \leq i \leq n\).
Note that the definition of \(\widehat{e}(T)\) is not uniform across literature. Others define it as \(\frac{1}{\kappa_\lambda} b(T) a(T)\) instead.
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import e_hat sage: e_hat([[1,2,3]]) 1/6*[1, 2, 3] + 1/6*[1, 3, 2] + 1/6*[2, 1, 3] + 1/6*[2, 3, 1] + 1/6*[3, 1, 2] + 1/6*[3, 2, 1] sage: e_hat([[1],[2]]) 1/2*[1, 2] - 1/2*[2, 1]
There are differing conventions for the order of the symmetrizers and antisymmetrizers. This example illustrates our conventions:
sage: e_hat([[1,2],[3]]) 1/3*[1, 2, 3] + 1/3*[2, 1, 3] - 1/3*[3, 1, 2] - 1/3*[3, 2, 1]
See also
- sage.combinat.symmetric_group_algebra.e_ik(itab, ktab, star=0)#
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import e_ik sage: e_ik([[1,2,3]], [[1,2,3]]) [1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1] sage: e_ik([[1,2,3]], [[1,2,3]], star=1) [1, 2] + [2, 1]
- sage.combinat.symmetric_group_algebra.epsilon(tab, star=0)#
The \((T, T)\)-th element of the seminormal basis of the group algebra \(\QQ[S_n]\), where \(T\) is the tableau
tab
(with itsstar
highest entries removed if the optional variablestar
is set).See the docstring of
seminormal_basis()
for the notation used herein.EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import epsilon sage: epsilon([[1,2]]) 1/2*[1, 2] + 1/2*[2, 1] sage: epsilon([[1],[2]]) 1/2*[1, 2] - 1/2*[2, 1]
- sage.combinat.symmetric_group_algebra.epsilon_ik(itab, ktab, star=0)#
Return the seminormal basis element of the symmetric group algebra \(\QQ S_n\) corresponding to the pair of tableaux
itab
andktab
(or restrictions of these tableaux, if the optional variablestar
is set).INPUT:
itab
,ktab
– two standard tableaux of same size.star
– integer (default: \(0\)).
OUTPUT:
The element \(\epsilon(I, K) \in \QQ S_n\), where \(I\) and \(K\) are the tableaux obtained by removing all entries higher than \(n - \mathrm{star}\) from
itab
andktab
, respectively (where \(n\) is the size ofitab
andktab
). Here, we are using the notations fromseminormal_basis()
.EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import epsilon_ik sage: epsilon_ik([[1,2],[3]], [[1,3],[2]]) 1/4*[1, 3, 2] - 1/4*[2, 3, 1] + 1/4*[3, 1, 2] - 1/4*[3, 2, 1] sage: epsilon_ik([[1,2],[3]], [[1,3],[2]], star=1) Traceback (most recent call last): ... ValueError: the two tableaux must be of the same shape
- sage.combinat.symmetric_group_algebra.kappa(alpha)#
Return \(\kappa_\alpha\), which is \(n!\) divided by the number of standard tableaux of shape \(\alpha\) (where \(\alpha\) is a partition of \(n\)).
INPUT:
alpha
– integer partition (can be encoded as a list).
OUTPUT:
The factorial of the size of
alpha
, divided by the number of standard tableaux of shapealpha
. Equivalently, the product of all hook lengths ofalpha
.EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import kappa sage: kappa(Partition([2,1])) 3 sage: kappa([2,1]) 3
- sage.combinat.symmetric_group_algebra.pi_ik(itab, ktab)#
Return the permutation \(p\) which sends every entry of the tableau
itab
to the respective entry of the tableauktab
, as an element of the corresponding symmetric group algebra.This assumes that
itab
andktab
are tableaux (possibly given just as lists of lists) of the same shape.EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import pi_ik sage: pi_ik([[1,3],[2]], [[1,2],[3]]) [1, 3, 2]
- sage.combinat.symmetric_group_algebra.seminormal_test(n)#
Run a variety of tests to verify that the construction of the seminormal basis works as desired. The numbers appearing are results in James and Kerber’s ‘Representation Theory of the Symmetric Group’ [JK1981].
EXAMPLES:
sage: from sage.combinat.symmetric_group_algebra import seminormal_test sage: seminormal_test(3) True