AUTHORS:
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
.
There are three bases currently implemented for :
We follow the notations and conventions in [GR1989]. In order to use
the idempotent basis, we require to be a
-algebra.
INPUT:
REFERENCES:
[GR1989] | (1, 2, 3) 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 |
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]
There is the following syntatic sugar for calling elements of a basis, note that for the empty set one must use D[[]] due to python’s syntax:
sage: D[[]] + D[2] + 2*D[1,2]
D{} + 2*D{1, 2} + D{2}
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
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
of
under the bijection
,
which is what Sage uses to index the basis.
By using compositions of , the product
becomes a
sum over the non-negative-integer matrices
with column sum
and row 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]]
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
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]
Return as a linear combination of
-basis elements.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4)
sage: B = DA.B()
sage: D = DA.D()
sage: for b in B.basis(): D(b) # 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: for b in B.basis(): D(b)
D{}
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: for b in B.basis(): I(b) # 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]
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: for b in B.basis(): S(b) # 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]
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
.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4)
sage: D = DA.D()
sage: list(D.basis())
[D{}, D{1}, D{2}, D{1, 2}, D{3}, D{1, 3}, D{2, 3}, D{1, 2, 3}]
sage: DA = DescentAlgebra(QQ, 0)
sage: D = DA.D()
sage: list(D.basis())
[D{}]
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
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}
Return as a linear combination of
-basis elements.
EXAMPLES:
sage: DA = DescentAlgebra(QQ, 4)
sage: D = DA.D()
sage: B = DA.B()
sage: for b in D.basis(): B(b) # indirect doctest
B[4]
B[1, 3] - B[4]
B[2, 2] - B[4]
B[1, 1, 2] - B[1, 3] - B[2, 2] + B[4]
B[3, 1] - 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]
Return as a linear combination of basis elements in the
symmetric group algebra.
EXAMPLES:
sage: D = DescentAlgebra(QQ, 4).D()
sage: for b in Subsets(3): D.to_symmetric_group_algebra_on_basis(tuple(b))
[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]
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
.
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
.
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]]
Return the idemponent corresponding to the partition la.
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
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
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.
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]
Return as a linear combination of
-basis elements.
This is computed using the formula (Theorem 3.4 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: for b in I.basis(): B(b) # 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]
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
Bases: sage.categories.realizations.Category_realization_of_parent
The category of bases of a descent 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]
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
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
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]
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: for c in Compositions(3): B.to_symmetric_group_algebra_on_basis(c)
[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: for c in Compositions(3): I.to_symmetric_group_algebra_on_basis(c)
[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]
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]