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
. (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 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:
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]
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
(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]]
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: 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{}]
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]]
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]]
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{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: map(B, D.basis()) # 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: [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]]
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]]
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
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.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]]
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: [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]]
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]