Descent Algebras¶
AUTHORS:
- Travis Scrimshaw (2013-07-28): Initial version
-
class
sage.combinat.descent_algebra.
DescentAlgebra
(R, n)¶ Bases:
sage.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
Solomon’s descent algebra.
The descent algebra
over a ring
is a subalgebra of the symmetric group algebra
. (The product in the latter algebra is defined by
for any two permutations
and
in
and every
. The algebra
inherits this product.)
There are three bases currently implemented for
:
- the standard basis
of (sums of) descent classes, indexed by subsets
of
,
- the subset basis
, indexed by compositions
of
,
- the idempotent basis
, indexed by compositions
of
, which is used to construct the mutually orthogonal idempotents of the symmetric group algebra.
The idempotent basis is only defined when
is a
-algebra.
We follow the notations and conventions in [GR1989], apart from the order of multiplication being different from the one used in that article. Schocker’s exposition [Schocker2004], in turn, uses the same order of multiplication as we are, but has different notations for the bases.
INPUT:
R
– the base ringn
– a nonnegative integer
REFERENCES:
[GR1989] (1, 2, 3, 4, 5) C. Reutenauer, A. M. Garsia. A decomposition of Solomon’s descent algebra. Adv. Math. 77 (1989). http://www.lacim.uqam.ca/~christo/Publi%C3%A9s/1989/Decomposition%20Solomon.pdf [Atkinson] M. D. Atkinson. Solomon’s descent algebra revisited. Bull. London Math. Soc. 24 (1992) 545-551. http://www.cs.otago.ac.nz/staffpriv/mike/Papers/Descent/DescAlgRevisited.pdf [MR-Desc] C. Malvenuto, C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, Journal of Algebra 177 (1995), no. 3, 967-982. http://www.lacim.uqam.ca/~christo/Publi%C3%A9s/1995/Duality.pdf [Schocker2004] (1, 2, 3) Manfred Schocker, The descent algebra of the symmetric group. Fields Inst. Comm. 40 (2004), pp. 145-161. http://www.mathematik.uni-bielefeld.de/~ringel/schocker-neu.ps EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: D = DA.D(); D Descent algebra of 4 over Rational Field in the standard basis sage: B = DA.B(); B Descent algebra of 4 over Rational Field in the subset basis sage: I = DA.I(); I Descent algebra of 4 over Rational Field in the idempotent basis sage: basis_B = B.basis() sage: elt = basis_B[Composition([1,2,1])] + 4*basis_B[Composition([1,3])]; elt B[1, 2, 1] + 4*B[1, 3] sage: D(elt) 5*D{} + 5*D{1} + D{1, 3} + D{3} sage: I(elt) 7/6*I[1, 1, 1, 1] + 2*I[1, 1, 2] + 3*I[1, 2, 1] + 4*I[1, 3]
As syntactic sugar, one can use the notation
D[i,...,l]
to construct elements of the basis; note that for the empty set one must useD[[]]
due to Python’s syntax:sage: D[[]] + D[2] + 2*D[1,2] D{} + 2*D{1, 2} + D{2}
The same syntax works for the other bases:
sage: I[1,2,1] + 3*I[4] + 2*I[3,1] I[1, 2, 1] + 2*I[3, 1] + 3*I[4]
TESTS:
We check that we can go back and forth between our bases:
sage: DA = DescentAlgebra(QQ, 4) sage: D = DA.D() sage: B = DA.B() sage: I = DA.I() sage: all(D(B(b)) == b for b in D.basis()) True sage: all(D(I(b)) == b for b in D.basis()) True sage: all(B(D(b)) == b for b in B.basis()) True sage: all(B(I(b)) == b for b in B.basis()) True sage: all(I(D(b)) == b for b in I.basis()) True sage: all(I(B(b)) == b for b in I.basis()) True
-
class
B
(alg, prefix='B')¶ Bases:
sage.combinat.free_module.CombinatorialFreeModule
,sage.misc.bindable_class.BindableClass
The subset basis of a descent algebra (indexed by compositions).
The subset basis
of
is formed by
where
is the
standard basis
. However it is more natural to index the subset basis by compositions ofunder the bijection
(where
), which is what Sage uses to index the basis.
The basis element
is denoted
in [Schocker2004].
By using compositions of
, the product
becomes a sum over the non-negative-integer matrices
with row sum
and column sum
. The summand corresponding to
is
, where
is the composition obtained by reading
row-by-row from left-to-right and top-to-bottom and removing all zeroes. This multiplication rule is commonly called “Solomon’s Mackey formula”.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: B = DA.B() sage: list(B.basis()) [B[1, 1, 1, 1], B[1, 1, 2], B[1, 2, 1], B[1, 3], B[2, 1, 1], B[2, 2], B[3, 1], B[4]]
-
one_basis
()¶ Return the identity element which is the composition
, as per
AlgebrasWithBasis.ParentMethods.one_basis
.EXAMPLES:
sage: DescentAlgebra(QQ, 4).B().one_basis() [4] sage: DescentAlgebra(QQ, 0).B().one_basis() [] sage: all( U * DescentAlgebra(QQ, 3).B().one() == U ....: for U in DescentAlgebra(QQ, 3).B().basis() ) True
-
product_on_basis
(p, q)¶ Return
, where
and
are compositions of
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: B = DA.B() sage: p = Composition([1,2,1]) sage: q = Composition([3,1]) sage: B.product_on_basis(p, q) B[1, 1, 1, 1] + 2*B[1, 2, 1]
-
to_D_basis
(p)¶ Return
as a linear combination of
-basis elements.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: B = DA.B() sage: D = DA.D() sage: map(D, B.basis()) # indirect doctest [D{} + D{1} + D{1, 2} + D{1, 2, 3} + D{1, 3} + D{2} + D{2, 3} + D{3}, D{} + D{1} + D{1, 2} + D{2}, D{} + D{1} + D{1, 3} + D{3}, D{} + D{1}, D{} + D{2} + D{2, 3} + D{3}, D{} + D{2}, D{} + D{3}, D{}]
TESTS:
Check to make sure the empty case is handled correctly:
sage: DA = DescentAlgebra(QQ, 0) sage: B = DA.B() sage: D = DA.D() sage: map(D, B.basis()) [D{}]
-
to_I_basis
(p)¶ Return
as a linear combination of
-basis elements.
This is done using the formula
where
is the refinement order and
is defined as follows: When
, we can write
as a concatenation
with each
being a composition of the
-th entry of
, and then we set
to be
, where
denotes the number of parts of any composition
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: B = DA.B() sage: I = DA.I() sage: map(I, B.basis()) # indirect doctest [I[1, 1, 1, 1], 1/2*I[1, 1, 1, 1] + I[1, 1, 2], 1/2*I[1, 1, 1, 1] + I[1, 2, 1], 1/6*I[1, 1, 1, 1] + 1/2*I[1, 1, 2] + 1/2*I[1, 2, 1] + I[1, 3], 1/2*I[1, 1, 1, 1] + I[2, 1, 1], 1/4*I[1, 1, 1, 1] + 1/2*I[1, 1, 2] + 1/2*I[2, 1, 1] + I[2, 2], 1/6*I[1, 1, 1, 1] + 1/2*I[1, 2, 1] + 1/2*I[2, 1, 1] + I[3, 1], 1/24*I[1, 1, 1, 1] + 1/6*I[1, 1, 2] + 1/6*I[1, 2, 1] + 1/2*I[1, 3] + 1/6*I[2, 1, 1] + 1/2*I[2, 2] + 1/2*I[3, 1] + I[4]]
-
to_nsym
(p)¶ Return
as an element in
, the non-commutative symmetric functions.
This maps
to
where
denotes the Complete basis of
.
EXAMPLES:
sage: B = DescentAlgebra(QQ, 4).B() sage: S = NonCommutativeSymmetricFunctions(QQ).Complete() sage: map(S, B.basis()) # indirect doctest [S[1, 1, 1, 1], S[1, 1, 2], S[1, 2, 1], S[1, 3], S[2, 1, 1], S[2, 2], S[3, 1], S[4]]
-
-
class
DescentAlgebra.
D
(alg, prefix='D')¶ Bases:
sage.combinat.free_module.CombinatorialFreeModule
,sage.misc.bindable_class.BindableClass
The standard basis of a descent algebra.
This basis is indexed by
, and the basis vector indexed by
is the sum of all permutations, taken in the symmetric group algebra
, whose descent set is
. We denote this basis vector by
.
Occasionally this basis appears in literature but indexed by compositions of
rather than subsets of
. The equivalence between these two indexings is owed to the bijection from the power set of
to the set of all compositions of
which sends every subset
of
(with
) to the composition
.
The basis element corresponding to a composition
(or to the subset of
) is denoted
in [Schocker2004].
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: D = DA.D() sage: list(D.basis()) [D{}, D{1}, D{2}, D{3}, D{1, 2}, D{1, 3}, D{2, 3}, D{1, 2, 3}] sage: DA = DescentAlgebra(QQ, 0) sage: D = DA.D() sage: list(D.basis()) [D{}]
-
one_basis
()¶ Return the identity element, as per
AlgebrasWithBasis.ParentMethods.one_basis
.EXAMPLES:
sage: DescentAlgebra(QQ, 4).D().one_basis() () sage: DescentAlgebra(QQ, 0).D().one_basis() () sage: all( U * DescentAlgebra(QQ, 3).D().one() == U ....: for U in DescentAlgebra(QQ, 3).D().basis() ) True
-
product_on_basis
(S, T)¶ Return
, where
and
are subsets of
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: D = DA.D() sage: D.product_on_basis((1, 3), (2,)) D{} + D{1} + D{1, 2} + 2*D{1, 2, 3} + D{1, 3} + D{2} + D{2, 3} + D{3}
-
to_B_basis
(S)¶ Return
as a linear combination of
-basis elements.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: D = DA.D() sage: B = DA.B() sage: map(B, D.basis()) # indirect doctest [B[4], B[1, 3] - B[4], B[2, 2] - B[4], B[3, 1] - B[4], B[1, 1, 2] - B[1, 3] - B[2, 2] + B[4], B[1, 2, 1] - B[1, 3] - B[3, 1] + B[4], B[2, 1, 1] - B[2, 2] - B[3, 1] + B[4], B[1, 1, 1, 1] - B[1, 1, 2] - B[1, 2, 1] + B[1, 3] - B[2, 1, 1] + B[2, 2] + B[3, 1] - B[4]]
-
to_symmetric_group_algebra_on_basis
(S)¶ Return
as a linear combination of basis elements in the symmetric group algebra.
EXAMPLES:
sage: D = DescentAlgebra(QQ, 4).D() sage: [D.to_symmetric_group_algebra_on_basis(tuple(b)) ....: for b in Subsets(3)] [[1, 2, 3, 4], [2, 1, 3, 4] + [3, 1, 2, 4] + [4, 1, 2, 3], [1, 3, 2, 4] + [1, 4, 2, 3] + [2, 3, 1, 4] + [2, 4, 1, 3] + [3, 4, 1, 2], [1, 2, 4, 3] + [1, 3, 4, 2] + [2, 3, 4, 1], [3, 2, 1, 4] + [4, 2, 1, 3] + [4, 3, 1, 2], [2, 1, 4, 3] + [3, 1, 4, 2] + [3, 2, 4, 1] + [4, 1, 3, 2] + [4, 2, 3, 1], [1, 4, 3, 2] + [2, 4, 3, 1] + [3, 4, 2, 1], [4, 3, 2, 1]]
-
-
class
DescentAlgebra.
I
(alg, prefix='I')¶ Bases:
sage.combinat.free_module.CombinatorialFreeModule
,sage.misc.bindable_class.BindableClass
The idempotent basis of a descent algebra.
The idempotent basis
is a basis for
whenever the ground ring is a
-algebra. One way to compute it is using the formula (Theorem 3.3 in [GR1989])
where
is the refinement order and
denotes the number of parts of any composition
, and where
is defined as follows: When
, we can write
as a concatenation
with each
being a composition of the
-th entry of
, and then we set
to be the product
.
Let
denote the partition obtained from a composition
by sorting. This basis is called the idempotent basis since for any
such that
, we have:
where
denotes
, and where
is the stabilizer of
in
. (This is part of Theorem 4.2 in [GR1989].)
It is also straightforward to compute the idempotents
for the symmetric group algebra by the formula (Theorem 3.2 in [GR1989]):
Note
The basis elements are not orthogonal idempotents.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: I = DA.I() sage: list(I.basis()) [I[1, 1, 1, 1], I[1, 1, 2], I[1, 2, 1], I[1, 3], I[2, 1, 1], I[2, 2], I[3, 1], I[4]]
-
idempotent
(la)¶ Return the idemponent corresponding to the partition
la
of.
EXAMPLES:
sage: I = DescentAlgebra(QQ, 4).I() sage: E = I.idempotent([3,1]); E 1/2*I[1, 3] + 1/2*I[3, 1] sage: E*E == E True sage: E2 = I.idempotent([2,1,1]); E2 1/6*I[1, 1, 2] + 1/6*I[1, 2, 1] + 1/6*I[2, 1, 1] sage: E2*E2 == E2 True sage: E*E2 == I.zero() True
-
one
()¶ Return the identity element, which is
, in the
basis.
EXAMPLES:
sage: DescentAlgebra(QQ, 4).I().one() 1/24*I[1, 1, 1, 1] + 1/6*I[1, 1, 2] + 1/6*I[1, 2, 1] + 1/2*I[1, 3] + 1/6*I[2, 1, 1] + 1/2*I[2, 2] + 1/2*I[3, 1] + I[4] sage: DescentAlgebra(QQ, 0).I().one() I[]
TESTS:
sage: all( U * DescentAlgebra(QQ, 3).I().one() == U ....: for U in DescentAlgebra(QQ, 3).I().basis() ) True
-
one_basis
()¶ The element
is not (generally) a basis vector in the
basis, thus this returns a
TypeError
.EXAMPLES:
sage: DescentAlgebra(QQ, 4).I().one_basis() Traceback (most recent call last): ... TypeError: 1 is not a basis element in the I basis.
-
product_on_basis
(p, q)¶ Return
, where
and
are compositions of
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: I = DA.I() sage: p = Composition([1,2,1]) sage: q = Composition([3,1]) sage: I.product_on_basis(p, q) 0 sage: I.product_on_basis(p, p) 2*I[1, 2, 1]
-
to_B_basis
(p)¶ Return
as a linear combination of
-basis elements.
This is computed using the formula (Theorem 3.3 in [GR1989])
where
is the refinement order and
denotes the number of parts of any composition
, and where
is defined as follows: When
, we can write
as a concatenation
with each
being a composition of the
-th entry of
, and then we set
to be
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: B = DA.B() sage: I = DA.I() sage: map(B, I.basis()) # indirect doctest [B[1, 1, 1, 1], -1/2*B[1, 1, 1, 1] + B[1, 1, 2], -1/2*B[1, 1, 1, 1] + B[1, 2, 1], 1/3*B[1, 1, 1, 1] - 1/2*B[1, 1, 2] - 1/2*B[1, 2, 1] + B[1, 3], -1/2*B[1, 1, 1, 1] + B[2, 1, 1], 1/4*B[1, 1, 1, 1] - 1/2*B[1, 1, 2] - 1/2*B[2, 1, 1] + B[2, 2], 1/3*B[1, 1, 1, 1] - 1/2*B[1, 2, 1] - 1/2*B[2, 1, 1] + B[3, 1], -1/4*B[1, 1, 1, 1] + 1/3*B[1, 1, 2] + 1/3*B[1, 2, 1] - 1/2*B[1, 3] + 1/3*B[2, 1, 1] - 1/2*B[2, 2] - 1/2*B[3, 1] + B[4]]
-
-
DescentAlgebra.
a_realization
()¶ Return a particular realization of
self
(the-basis).
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4) sage: DA.a_realization() Descent algebra of 4 over Rational Field in the subset basis
- the standard basis
-
class
sage.combinat.descent_algebra.
DescentAlgebraBases
(base)¶ Bases:
sage.categories.realizations.Category_realization_of_parent
The category of bases of a descent algebra.
-
class
ElementMethods
¶ -
to_symmetric_group_algebra
()¶ Return
self
in the symmetric group algebra.EXAMPLES:
sage: B = DescentAlgebra(QQ, 4).B() sage: B[1,3].to_symmetric_group_algebra() [1, 2, 3, 4] + [2, 1, 3, 4] + [3, 1, 2, 4] + [4, 1, 2, 3] sage: I = DescentAlgebra(QQ, 4).I() sage: elt = I(B[1,3]) sage: elt.to_symmetric_group_algebra() [1, 2, 3, 4] + [2, 1, 3, 4] + [3, 1, 2, 4] + [4, 1, 2, 3]
-
-
class
DescentAlgebraBases.
ParentMethods
¶ -
is_commutative
()¶ Return whether this descent algebra is commutative.
EXAMPLES:
sage: B = DescentAlgebra(QQ, 4).B() sage: B.is_commutative() False sage: B = DescentAlgebra(QQ, 1).B() sage: B.is_commutative() True
-
is_field
(proof=True)¶ Return whether this descent algebra is a field.
EXAMPLES:
sage: B = DescentAlgebra(QQ, 4).B() sage: B.is_field() False sage: B = DescentAlgebra(QQ, 1).B() sage: B.is_field() True
-
to_symmetric_group_algebra
()¶ Morphism from
self
to the symmetric group algebra.EXAMPLES:
sage: D = DescentAlgebra(QQ, 4).D() sage: D.to_symmetric_group_algebra(D[1,3]) [2, 1, 4, 3] + [3, 1, 4, 2] + [3, 2, 4, 1] + [4, 1, 3, 2] + [4, 2, 3, 1] sage: B = DescentAlgebra(QQ, 4).B() sage: B.to_symmetric_group_algebra(B[1,2,1]) [1, 2, 3, 4] + [1, 2, 4, 3] + [1, 3, 4, 2] + [2, 1, 3, 4] + [2, 1, 4, 3] + [2, 3, 4, 1] + [3, 1, 2, 4] + [3, 1, 4, 2] + [3, 2, 4, 1] + [4, 1, 2, 3] + [4, 1, 3, 2] + [4, 2, 3, 1]
-
to_symmetric_group_algebra_on_basis
(S)¶ Return the basis element index by
S
as a linear combination of basis elements in the symmetric group algebra.EXAMPLES:
sage: B = DescentAlgebra(QQ, 3).B() sage: [B.to_symmetric_group_algebra_on_basis(c) ....: for c in Compositions(3)] [[1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1], [1, 2, 3] + [2, 1, 3] + [3, 1, 2], [1, 2, 3] + [1, 3, 2] + [2, 3, 1], [1, 2, 3]] sage: I = DescentAlgebra(QQ, 3).I() sage: [I.to_symmetric_group_algebra_on_basis(c) ....: for c in Compositions(3)] [[1, 2, 3] + [1, 3, 2] + [2, 1, 3] + [2, 3, 1] + [3, 1, 2] + [3, 2, 1], 1/2*[1, 2, 3] - 1/2*[1, 3, 2] + 1/2*[2, 1, 3] - 1/2*[2, 3, 1] + 1/2*[3, 1, 2] - 1/2*[3, 2, 1], 1/2*[1, 2, 3] + 1/2*[1, 3, 2] - 1/2*[2, 1, 3] + 1/2*[2, 3, 1] - 1/2*[3, 1, 2] - 1/2*[3, 2, 1], 1/3*[1, 2, 3] - 1/6*[1, 3, 2] - 1/6*[2, 1, 3] - 1/6*[2, 3, 1] - 1/6*[3, 1, 2] + 1/3*[3, 2, 1]]
-
-
DescentAlgebraBases.
super_categories
()¶ The super categories of
self
.EXAMPLES:
sage: from sage.combinat.descent_algebra import DescentAlgebraBases sage: DA = DescentAlgebra(QQ, 4) sage: bases = DescentAlgebraBases(DA) sage: bases.super_categories() [Category of finite dimensional algebras with basis over Rational Field, Category of realizations of Descent algebra of 4 over Rational Field]
-
class