Descent Algebras¶

AUTHORS:

Travis Scrimshaw (2013-07-28): Initial version

class sage.combinat.descent_algebra.DescentAlgebra(R, n)[source]¶

Bases: UniqueRepresentation, Parent

Solomon’s descent algebra.

The descent algebra $Σ_{n}$ over a ring $R$ is a subalgebra of the symmetric group algebra $R S_{n}$ . (The product in the latter algebra is defined by $(p q) (i) = q (p (i))$ for any two permutations $p$ and $q$ in $S_{n}$ and every $i \in {1, 2, \dots, n}$ . The algebra $Σ_{n}$ inherits this product.)

There are three bases currently implemented for $Σ_{n}$ :

the standard basis $D_{S}$ of (sums of) descent classes, indexed by subsets $S$ of ${1, 2, \dots, n - 1}$ ,
the subset basis $B_{p}$ , indexed by compositions $p$ of $n$ ,
the idempotent basis $I_{p}$ , indexed by compositions $p$ of $n$ , which is used to construct the mutually orthogonal idempotents of the symmetric group algebra.

The idempotent basis is only defined when $R$ is a $Q$ -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 [Sch2004], in turn, uses the same order of multiplication as we are, but has different notations for the bases.

INPUT:

R – the base ring
n – nonnegative integer

REFERENCES:

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> D = DA.D(); D
Descent algebra of 4 over Rational Field in the standard basis
>>> B = DA.B(); B
Descent algebra of 4 over Rational Field in the subset basis
>>> I = DA.I(); I
Descent algebra of 4 over Rational Field in the idempotent basis
>>> basis_B = B.basis()
>>> elt = basis_B[Composition([Integer(1),Integer(2),Integer(1)])] + Integer(4)*basis_B[Composition([Integer(1),Integer(3)])]; elt
B[1, 2, 1] + 4*B[1, 3]
>>> D(elt)
5*D{} + 5*D{1} + D{1, 3} + D{3}
>>> I(elt)
7/6*I[1, 1, 1, 1] + 2*I[1, 1, 2] + 3*I[1, 2, 1] + 4*I[1, 3]

Sage Live

DA = DescentAlgebra(QQ, 4)
D = DA.D(); D
B = DA.B(); B
I = DA.I(); I
basis_B = B.basis()
elt = basis_B[Composition([1,2,1])] + 4*basis_B[Composition([1,3])]; elt
D(elt)
I(elt)

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 use D[[]] due to Python’s syntax:

Sage

sage: D[[]] + D[2] + 2*D[1,2]
D{} + 2*D{1, 2} + D{2}

Python

>>> from sage.all import *
>>> D[[]] + D[Integer(2)] + Integer(2)*D[Integer(1),Integer(2)]
D{} + 2*D{1, 2} + D{2}

Sage Live

D[[]] + D[2] + 2*D[1,2]

The same syntax works for the other bases:

Sage

sage: I[1,2,1] + 3*I[4] + 2*I[3,1]
I[1, 2, 1] + 2*I[3, 1] + 3*I[4]

Python

>>> from sage.all import *
>>> I[Integer(1),Integer(2),Integer(1)] + Integer(3)*I[Integer(4)] + Integer(2)*I[Integer(3),Integer(1)]
I[1, 2, 1] + 2*I[3, 1] + 3*I[4]

Sage Live

I[1,2,1] + 3*I[4] + 2*I[3,1]

class B(alg, prefix='B')[source]¶

Bases: CombinatorialFreeModule, BindableClass

The subset basis of a descent algebra (indexed by compositions).

The subset basis $(B_{S})_{S \subseteq {1, 2, \dots, n - 1}}$ of $Σ_{n}$ is formed by

B_{S} = \sum_{T \subseteq S} D_{T},

where $(D_{S})_{S \subseteq {1, 2, \dots, n - 1}}$ is the standard basis. However it is more natural to index the subset basis by compositions of $n$ under the bijection ${i_{1}, i_{2}, \dots, i_{k}} \mapsto (i_{1}, i_{2} - i_{1}, i_{3} - i_{2}, \dots, i_{k} - i_{k - 1}, n - i_{k})$ (where $i_{1} < i_{2} < \dots < i_{k}$ ), which is what Sage uses to index the basis.

The basis element $B_{p}$ is denoted $Ξ^{p}$ in [Sch2004].

By using compositions of $n$ , the product $B_{p} B_{q}$ becomes a sum over the nonnegative-integer matrices $M$ with row sum $p$ and column sum $q$ . The summand corresponding to $M$ is $B_{c}$ , where $c$ is the composition obtained by reading $M$ 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

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]]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> B = DA.B()
>>> 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]]

Sage Live

DA = DescentAlgebra(QQ, 4)
B = DA.B()
list(B.basis())

one_basis()[source]¶

Return the identity element which is the composition $[n]$ , as per AlgebrasWithBasis.ParentMethods.one_basis.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> DescentAlgebra(QQ, Integer(4)).B().one_basis()
[4]
>>> DescentAlgebra(QQ, Integer(0)).B().one_basis()
[]

>>> all( U * DescentAlgebra(QQ, Integer(3)).B().one() == U
...      for U in DescentAlgebra(QQ, Integer(3)).B().basis() )
True

Sage Live

DescentAlgebra(QQ, 4).B().one_basis()
DescentAlgebra(QQ, 0).B().one_basis()
all( U * DescentAlgebra(QQ, 3).B().one() == U
     for U in DescentAlgebra(QQ, 3).B().basis() )

product_on_basis(p, q)[source]¶

Return $B_{p} B_{q}$ , where $p$ and $q$ are compositions of $n$ .

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> B = DA.B()
>>> p = Composition([Integer(1),Integer(2),Integer(1)])
>>> q = Composition([Integer(3),Integer(1)])
>>> B.product_on_basis(p, q)
B[1, 1, 1, 1] + 2*B[1, 2, 1]

Sage Live

DA = DescentAlgebra(QQ, 4)
B = DA.B()
p = Composition([1,2,1])
q = Composition([3,1])
B.product_on_basis(p, q)

to_D_basis(p)[source]¶

Return $B_{p}$ as a linear combination of $D$ -basis elements.

EXAMPLES:

Sage

sage: DA = DescentAlgebra(QQ, 4)
sage: B = DA.B()
sage: D = DA.D()
sage: list(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{}]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> B = DA.B()
>>> D = DA.D()
>>> list(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{}]

Sage Live

DA = DescentAlgebra(QQ, 4)
B = DA.B()
D = DA.D()
list(map(D, B.basis()))  # indirect doctest

to_I_basis(p)[source]¶

Return $B_{p}$ as a linear combination of $I$ -basis elements.

This is done using the formula

B_{p} = \sum_{q \leq p} \frac{1}{k! (q, p)} I_{q},

where $\leq$ is the refinement order and $k! (q, p)$ is defined as follows: When $q \leq p$ , we can write $q$ as a concatenation $q_{(1)} q_{(2)} \dots q_{(k)}$ with each $q_{(i)}$ being a composition of the $i$ -th entry of $p$ , and then we set $k! (q, p)$ to be $l (q_{(1)})! l (q_{(2)})! \dots l (q_{(k)})!$ , where $l (r)$ denotes the number of parts of any composition $r$ .

EXAMPLES:

Sage

sage: DA = DescentAlgebra(QQ, 4)
sage: B = DA.B()
sage: I = DA.I()
sage: list(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]]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> B = DA.B()
>>> I = DA.I()
>>> list(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]]

Sage Live

DA = DescentAlgebra(QQ, 4)
B = DA.B()
I = DA.I()
list(map(I, B.basis()))  # indirect doctest

to_nsym(p)[source]¶

Return $B_{p}$ as an element in $N S y m$ , the non-commutative symmetric functions.

This maps $B_{p}$ to $S_{p}$ where $S$ denotes the Complete basis of $N S y m$ .

EXAMPLES:

Sage

sage: B = DescentAlgebra(QQ, 4).B()
sage: S = NonCommutativeSymmetricFunctions(QQ).Complete()
sage: list(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]]

Python

>>> from sage.all import *
>>> B = DescentAlgebra(QQ, Integer(4)).B()
>>> S = NonCommutativeSymmetricFunctions(QQ).Complete()
>>> list(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]]

Sage Live

B = DescentAlgebra(QQ, 4).B()
S = NonCommutativeSymmetricFunctions(QQ).Complete()
list(map(S, B.basis()))  # indirect doctest

class D(alg, prefix='D')[source]¶

Bases: CombinatorialFreeModule, BindableClass

The standard basis of a descent algebra.

This basis is indexed by $S \subseteq {1, 2, \dots, n - 1}$ , and the basis vector indexed by $S$ is the sum of all permutations, taken in the symmetric group algebra $R S_{n}$ , whose descent set is $S$ . We denote this basis vector by $D_{S}$ .

Occasionally this basis appears in literature but indexed by compositions of $n$ rather than subsets of ${1, 2, \dots, n - 1}$ . The equivalence between these two indexings is owed to the bijection from the power set of ${1, 2, \dots, n - 1}$ to the set of all compositions of $n$ which sends every subset ${i_{1}, i_{2}, \dots, i_{k}}$ of ${1, 2, \dots, n - 1}$ (with $i_{1} < i_{2} < \dots < i_{k}$ ) to the composition $(i_{1}, i_{2} - i_{1}, \dots, i_{k} - i_{k - 1}, n - i_{k})$ .

The basis element corresponding to a composition $p$ (or to the subset of ${1, 2, \dots, n - 1}$ ) is denoted $Δ^{p}$ in [Sch2004].

EXAMPLES:

Sage

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{}]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> D = DA.D()
>>> list(D.basis())
[D{}, D{1}, D{2}, D{3}, D{1, 2}, D{1, 3}, D{2, 3}, D{1, 2, 3}]

>>> DA = DescentAlgebra(QQ, Integer(0))
>>> D = DA.D()
>>> list(D.basis())
[D{}]

Sage Live

DA = DescentAlgebra(QQ, 4)
D = DA.D()
list(D.basis())
DA = DescentAlgebra(QQ, 0)
D = DA.D()
list(D.basis())

one_basis()[source]¶

Return the identity element, as per AlgebrasWithBasis.ParentMethods.one_basis.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> DescentAlgebra(QQ, Integer(4)).D().one_basis()
()
>>> DescentAlgebra(QQ, Integer(0)).D().one_basis()
()

>>> all( U * DescentAlgebra(QQ, Integer(3)).D().one() == U
...      for U in DescentAlgebra(QQ, Integer(3)).D().basis() )
True

Sage Live

DescentAlgebra(QQ, 4).D().one_basis()
DescentAlgebra(QQ, 0).D().one_basis()
all( U * DescentAlgebra(QQ, 3).D().one() == U
     for U in DescentAlgebra(QQ, 3).D().basis() )

product_on_basis(S, T)[source]¶

Return $D_{S} D_{T}$ , where $S$ and $T$ are subsets of $[n - 1]$ .

EXAMPLES:

Sage

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}

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> D = DA.D()
>>> D.product_on_basis((Integer(1), Integer(3)), (Integer(2),))
D{} + D{1} + D{1, 2} + 2*D{1, 2, 3} + D{1, 3} + D{2} + D{2, 3} + D{3}

Sage Live

DA = DescentAlgebra(QQ, 4)
D = DA.D()
D.product_on_basis((1, 3), (2,))

to_B_basis(S)[source]¶

Return $D_{S}$ as a linear combination of $B_{p}$ -basis elements.

EXAMPLES:

Sage

sage: DA = DescentAlgebra(QQ, 4)
sage: D = DA.D()
sage: B = DA.B()
sage: list(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]]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> D = DA.D()
>>> B = DA.B()
>>> list(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]]

Sage Live

DA = DescentAlgebra(QQ, 4)
D = DA.D()
B = DA.B()
list(map(B, D.basis()))  # indirect doctest

to_symmetric_group_algebra_on_basis(S)[source]¶

Return $D_{S}$ as a linear combination of basis elements in the symmetric group algebra.

EXAMPLES:

Sage

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]]

Python

>>> from sage.all import *
>>> D = DescentAlgebra(QQ, Integer(4)).D()
>>> [D.to_symmetric_group_algebra_on_basis(tuple(b))
...  for b in Subsets(Integer(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]]

Sage Live

D = DescentAlgebra(QQ, 4).D()
[D.to_symmetric_group_algebra_on_basis(tuple(b))
 for b in Subsets(3)]

class I(alg, prefix='I')[source]¶

Bases: CombinatorialFreeModule, BindableClass

The idempotent basis of a descent algebra.

The idempotent basis $(I_{p})_{p ⊨ n}$ is a basis for $Σ_{n}$ whenever the ground ring is a $Q$ -algebra. One way to compute it is using the formula (Theorem 3.3 in [GR1989])

I_{p} = \sum_{q \leq p} \frac{(- 1)^{l (q) - l (p)}}{k (q, p)} B_{q},

where $\leq$ is the refinement order and $l (r)$ denotes the number of parts of any composition $r$ , and where $k (q, p)$ is defined as follows: When $q \leq p$ , we can write $q$ as a concatenation $q_{(1)} q_{(2)} \dots q_{(k)}$ with each $q_{(i)}$ being a composition of the $i$ -th entry of $p$ , and then we set $k (q, p)$ to be the product $l (q_{(1)}) l (q_{(2)}) \dots l (q_{(k)})$ .

Let $λ (p)$ denote the partition obtained from a composition $p$ by sorting. This basis is called the idempotent basis since for any $q$ such that $λ (p) = λ (q)$ , we have:

I_{p} I_{q} = s (λ) I_{p}

where $λ$ denotes $λ (p) = λ (q)$ , and where $s (λ)$ is the stabilizer of $λ$ in $S_{n}$ . (This is part of Theorem 4.2 in [GR1989].)

It is also straightforward to compute the idempotents $E_{λ}$ for the symmetric group algebra by the formula (Theorem 3.2 in [GR1989]):

E_{λ} = \frac{1}{k!} \sum_{λ (p) = λ} I_{p} .

Note

The basis elements are not orthogonal idempotents.

EXAMPLES:

Sage

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]]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> I = DA.I()
>>> 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]]

Sage Live

DA = DescentAlgebra(QQ, 4)
I = DA.I()
list(I.basis())

idempotent(la)[source]¶

Return the idempotent corresponding to the partition la of $n$ .

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> I = DescentAlgebra(QQ, Integer(4)).I()
>>> E = I.idempotent([Integer(3),Integer(1)]); E
1/2*I[1, 3] + 1/2*I[3, 1]
>>> E*E == E
True
>>> E2 = I.idempotent([Integer(2),Integer(1),Integer(1)]); E2
1/6*I[1, 1, 2] + 1/6*I[1, 2, 1] + 1/6*I[2, 1, 1]
>>> E2*E2 == E2
True
>>> E*E2 == I.zero()
True

Sage Live

I = DescentAlgebra(QQ, 4).I()
E = I.idempotent([3,1]); E
E*E == E
E2 = I.idempotent([2,1,1]); E2
E2*E2 == E2
E*E2 == I.zero()

one()[source]¶

Return the identity element, which is $B_{[n]}$ , in the $I$ basis.

EXAMPLES:

Sage

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[]

Python

>>> from sage.all import *
>>> DescentAlgebra(QQ, Integer(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]
>>> DescentAlgebra(QQ, Integer(0)).I().one()
I[]

Sage Live

DescentAlgebra(QQ, 4).I().one()
DescentAlgebra(QQ, 0).I().one()

one_basis()[source]¶

The element $1$ is not (generally) a basis vector in the $I$ basis, thus this raises a TypeError.

EXAMPLES:

Sage

sage: DescentAlgebra(QQ, 4).I().one_basis()
Traceback (most recent call last):
...
TypeError: 1 is not a basis element in the I basis

Python

>>> from sage.all import *
>>> DescentAlgebra(QQ, Integer(4)).I().one_basis()
Traceback (most recent call last):
...
TypeError: 1 is not a basis element in the I basis

Sage Live

DescentAlgebra(QQ, 4).I().one_basis()

product_on_basis(p, q)[source]¶

Return $I_{p} I_{q}$ , where $p$ and $q$ are compositions of $n$ .

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> I = DA.I()
>>> p = Composition([Integer(1),Integer(2),Integer(1)])
>>> q = Composition([Integer(3),Integer(1)])
>>> I.product_on_basis(p, q)
0
>>> I.product_on_basis(p, p)
2*I[1, 2, 1]

Sage Live

DA = DescentAlgebra(QQ, 4)
I = DA.I()
p = Composition([1,2,1])
q = Composition([3,1])
I.product_on_basis(p, q)
I.product_on_basis(p, p)

to_B_basis(p)[source]¶

Return $I_{p}$ as a linear combination of $B$ -basis elements.

This is computed using the formula (Theorem 3.3 in [GR1989])

I_{p} = \sum_{q \leq p} \frac{(- 1)^{l (q) - l (p)}}{k (q, p)} B_{q},

EXAMPLES:

Sage

sage: DA = DescentAlgebra(QQ, 4)
sage: B = DA.B()
sage: I = DA.I()
sage: list(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]]

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> B = DA.B()
>>> I = DA.I()
>>> list(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]]

Sage Live

DA = DescentAlgebra(QQ, 4)
B = DA.B()
I = DA.I()
list(map(B, I.basis()))  # indirect doctest

a_realization()[source]¶

Return a particular realization of self (the $B$ -basis).

EXAMPLES:

Sage

sage: DA = DescentAlgebra(QQ, 4)
sage: DA.a_realization()
Descent algebra of 4 over Rational Field in the subset basis

Python

>>> from sage.all import *
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> DA.a_realization()
Descent algebra of 4 over Rational Field in the subset basis

Sage Live

DA = DescentAlgebra(QQ, 4)
DA.a_realization()

idempotent[source]¶: alias of I

standard[source]¶: alias of D

subset[source]¶: alias of B

class sage.combinat.descent_algebra.DescentAlgebraBases(base)[source]¶

Bases: Category_realization_of_parent

The category of bases of a descent algebra.

class ElementMethods[source]¶

Bases: object

to_symmetric_group_algebra()[source]¶

Return self in the symmetric group algebra.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> B = DescentAlgebra(QQ, Integer(4)).B()
>>> B[Integer(1),Integer(3)].to_symmetric_group_algebra()
[1, 2, 3, 4] + [2, 1, 3, 4] + [3, 1, 2, 4] + [4, 1, 2, 3]
>>> I = DescentAlgebra(QQ, Integer(4)).I()
>>> elt = I(B[Integer(1),Integer(3)])
>>> elt.to_symmetric_group_algebra()
[1, 2, 3, 4] + [2, 1, 3, 4] + [3, 1, 2, 4] + [4, 1, 2, 3]

Sage Live

B = DescentAlgebra(QQ, 4).B()
B[1,3].to_symmetric_group_algebra()
I = DescentAlgebra(QQ, 4).I()
elt = I(B[1,3])
elt.to_symmetric_group_algebra()

class ParentMethods[source]¶

Bases: object

to_symmetric_group_algebra()[source]¶

Morphism from self to the symmetric group algebra.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> D = DescentAlgebra(QQ, Integer(4)).D()
>>> D.to_symmetric_group_algebra(D[Integer(1),Integer(3)])
[2, 1, 4, 3] + [3, 1, 4, 2] + [3, 2, 4, 1] + [4, 1, 3, 2] + [4, 2, 3, 1]
>>> B = DescentAlgebra(QQ, Integer(4)).B()
>>> B.to_symmetric_group_algebra(B[Integer(1),Integer(2),Integer(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]

Sage Live

D = DescentAlgebra(QQ, 4).D()
D.to_symmetric_group_algebra(D[1,3])
B = DescentAlgebra(QQ, 4).B()
B.to_symmetric_group_algebra(B[1,2,1])

to_symmetric_group_algebra_on_basis(S)[source]¶

Return the basis element index by S as a linear combination of basis elements in the symmetric group algebra.

EXAMPLES:

Sage

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]]

Python

>>> from sage.all import *
>>> B = DescentAlgebra(QQ, Integer(3)).B()
>>> [B.to_symmetric_group_algebra_on_basis(c)
...  for c in Compositions(Integer(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]]
>>> I = DescentAlgebra(QQ, Integer(3)).I()
>>> [I.to_symmetric_group_algebra_on_basis(c)
...  for c in Compositions(Integer(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]]

Sage Live

B = DescentAlgebra(QQ, 3).B()
[B.to_symmetric_group_algebra_on_basis(c)
 for c in Compositions(3)]
I = DescentAlgebra(QQ, 3).I()
[I.to_symmetric_group_algebra_on_basis(c)
 for c in Compositions(3)]

super_categories()[source]¶

The super categories of self.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> from sage.combinat.descent_algebra import DescentAlgebraBases
>>> DA = DescentAlgebra(QQ, Integer(4))
>>> bases = DescentAlgebraBases(DA)
>>> bases.super_categories()
[Category of finite dimensional algebras with basis over Rational Field,
 Category of realizations of Descent algebra of 4 over Rational Field]

Sage Live

from sage.combinat.descent_algebra import DescentAlgebraBases
DA = DescentAlgebra(QQ, 4)
bases = DescentAlgebraBases(DA)
bases.super_categories()