# Generic code for bases¶

This is a collection of code that is shared by bases of noncommutative symmetric functions and quasisymmetric functions.

AUTHORS:

• Jason Bandlow
• Franco Saliola
• Chris Berg
class sage.combinat.ncsf_qsym.generic_basis_code.AlgebraMorphism(domain, on_generators, position=0, codomain=None, category=None, anti=False)

A class for algebra morphism defined on a free algebra from the image of the generators

class sage.combinat.ncsf_qsym.generic_basis_code.BasesOfQSymOrNCSF(parent_with_realization)

TESTS:

sage: from sage.categories.realizations import Category_realization_of_parent
sage: A = Sets().WithRealizations().example(); A
The subset algebra of {1, 2, 3} over Rational Field
sage: C = A.Realizations(); C
Category of realizations of The subset algebra of {1, 2, 3} over Rational Field
sage: isinstance(C, Category_realization_of_parent)
True
sage: C.parent_with_realization
The subset algebra of {1, 2, 3} over Rational Field
sage: TestSuite(C).run(skip=["_test_category_over_bases"])


Todo

Fix the failing test by making C a singleton category. This will require some fiddling with the assertion in Category_singleton.__classcall__()

class ElementMethods
degree()

The maximum of the degrees of the homogeneous summands.

EXAMPLES:

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: (x, y) = (S[2], S[3])
sage: x.degree()
2
sage: (x^3 + 4*y^2).degree()
6
sage: ((1 + x)^3).degree()
6

sage: F = QuasiSymmetricFunctions(QQ).F()
sage: (x, y) = (F[2], F[3])
sage: x.degree()
2
sage: (x^3 + 4*y^2).degree()
6
sage: ((1 + x)^3).degree()
6


TESTS:

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: S.zero().degree()
Traceback (most recent call last):
...
ValueError: The zero element does not have a well-defined degree.
sage: F = QuasiSymmetricFunctions(QQ).F()
sage: F.zero().degree()
Traceback (most recent call last):
...
ValueError: The zero element does not have a well-defined degree.

degree_negation()

Return the image of self under the degree negation automorphism of the parent of self.

The degree negation is the automorphism which scales every homogeneous element of degree $$k$$ by $$(-1)^k$$ (for all $$k$$).

Calling degree_negation(self) is equivalent to calling self.parent().degree_negation(self).

EXAMPLES:

sage: NSym = NonCommutativeSymmetricFunctions(ZZ)
sage: S = NSym.S()
sage: f = 2*S[2,1] + 4*S[1,1] - 5*S[1,2] - 3*S[[]]
sage: f.degree_negation()
-3*S[] + 4*S[1, 1] + 5*S[1, 2] - 2*S[2, 1]

sage: QSym = QuasiSymmetricFunctions(QQ)
sage: dI = QSym.dualImmaculate()
sage: f = -3*dI[2,1] + 4*dI[2] + 2*dI[1]
sage: f.degree_negation()
-2*dI[1] + 4*dI[2] + 3*dI[2, 1]


TESTS:

The zero element behaves well:

sage: a = S.zero().degree_negation(); a
0
sage: parent(a)
Non-Commutative Symmetric Functions over the Integer Ring in the Complete basis


Todo

Generalize this to all graded vector spaces?

duality_pairing(y)

The duality pairing between elements of $$NSym$$ and elements of $$QSym$$.

The complete basis is dual to the monomial basis with respect to this pairing.

INPUT:

• y – an element of the dual Hopf algebra of self

OUTPUT:

• The result of pairing self with y.

EXAMPLES:

sage: R = NonCommutativeSymmetricFunctions(QQ).Ribbon()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: R[1,1,2].duality_pairing(F[1,1,2])
1
sage: R[1,2,1].duality_pairing(F[1,1,2])
0

sage: L = NonCommutativeSymmetricFunctions(QQ).Elementary()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: L[1,2].duality_pairing(F[1,2])
0
sage: L[1,1,1].duality_pairing(F[1,2])
1

skew_by(y, side='left')

The operation which is dual to multiplication by y, where y is an element of the dual space of self.

This is calculated through the coproduct of self and the expansion of y in the dual basis.

INPUT:

• y – an element of the dual Hopf algebra of self
• side – (Default=’left’) Either ‘left’ or ‘right’

OUTPUT:

• The result of skewing self by y, on the side side

EXAMPLES:

Skewing an element of NCSF by an element of QSym:

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: R([2,2,2]).skew_by(F[1,1])
R[1, 1, 2] + R[1, 2, 1] + R[1, 3] + R[2, 1, 1] + 2*R[2, 2] + R[3, 1] + R[4]
sage: R([2,2,2]).skew_by(F[2])
R[1, 1, 2] + R[1, 2, 1] + R[1, 3] + R[2, 1, 1] + 3*R[2, 2] + R[3, 1] + R[4]


Skewing an element of QSym by an element of NCSF:

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: R = NonCommutativeSymmetricFunctions(QQ).R()
sage: F = QuasiSymmetricFunctions(QQ).F()
sage: F[3,2].skew_by(R[1,1])
0
sage: F[3,2].skew_by(R[1,1], side='right')
0
sage: F[3,2].skew_by(S[1,1,1], side='right')
F[2]
sage: F[3,2].skew_by(S[1,2], side='right')
F[2]
sage: F[3,2].skew_by(S[2,1], side='right')
0
sage: F[3,2].skew_by(S[1,1,1])
F[2]
sage: F[3,2].skew_by(S[1,1])
F[1, 2]
sage: F[3,2].skew_by(S[1])
F[2, 2]

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: R = NonCommutativeSymmetricFunctions(QQ).R()
sage: M = QuasiSymmetricFunctions(QQ).M()
sage: M[3,2].skew_by(S[2])
0
sage: M[3,2].skew_by(S[2], side='right')
M[3]
sage: M[3,2].skew_by(S[3])
M[2]
sage: M[3,2].skew_by(S[3], side='right')
0

class BasesOfQSymOrNCSF.ParentMethods
alternating_sum_of_fatter_compositions(composition)

Return the alternating sum of fatter compositions in a basis of the non-commutative symmetric functions.

INPUT:

• composition – a composition

OUTPUT:

• The alternating sum of the compositions fatter than composition, in the basis self. The alternation is upon the length of the compositions, and is normalized so that composition has coefficient $$1$$.

EXAMPLES:

sage: NCSF=NonCommutativeSymmetricFunctions(QQ)
sage: elementary = NCSF.elementary()
sage: elementary.alternating_sum_of_fatter_compositions(Composition([2,2,1]))
L[2, 2, 1] - L[2, 3] - L[4, 1] + L[5]
sage: elementary.alternating_sum_of_fatter_compositions(Composition([1,2]))
L[1, 2] - L[3]


TESTS:

sage: complete = NonCommutativeSymmetricFunctions(ZZ).complete()
sage: I = Composition([1,1])
sage: x = complete.alternating_sum_of_fatter_compositions(I)
sage: [c.parent() for c in x.coefficients()]
[Integer Ring, Integer Ring]

alternating_sum_of_finer_compositions(composition, conjugate=False)

Return the alternating sum of finer compositions in a basis of the non-commutative symmetric functions.

INPUT:

• composition – a composition
• conjugate – (default: False) a boolean

OUTPUT:

• The alternating sum of the compositions finer than composition, in the basis self. The alternation is upon the length of the compositions, and is normalized so that composition has coefficient $$1$$. If the variable conjugate is set to True, then the conjugate of composition is used instead of composition.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: elementary = NCSF.elementary()
sage: elementary.alternating_sum_of_finer_compositions(Composition([2,2,1]))
L[1, 1, 1, 1, 1] - L[1, 1, 2, 1] - L[2, 1, 1, 1] + L[2, 2, 1]
sage: elementary.alternating_sum_of_finer_compositions(Composition([1,2]))
-L[1, 1, 1] + L[1, 2]


TESTS:

sage: complete = NonCommutativeSymmetricFunctions(ZZ).complete()
sage: I = Composition([2])
sage: x = complete.alternating_sum_of_finer_compositions(I)
sage: [c.parent() for c in x.coefficients()]
[Integer Ring, Integer Ring]

counit_on_basis(I)

The counit is defined by sending all elements of positive degree to zero.

EXAMPLES:

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: S.counit_on_basis([1,3])
0
sage: M = QuasiSymmetricFunctions(QQ).M()
sage: M.counit_on_basis([1,3])
0


TESTS:

sage: S.counit_on_basis([])
1
sage: S.counit_on_basis(Composition([]))
1
sage: M.counit_on_basis([])
1
sage: M.counit_on_basis(Composition([]))
1

degree_negation(element)

Return the image of element under the degree negation automorphism of self.

The degree negation is the automorphism which scales every homogeneous element of degree $$k$$ by $$(-1)^k$$ (for all $$k$$).

INPUT:

• element – element of self

EXAMPLES:

sage: NSym = NonCommutativeSymmetricFunctions(ZZ)
sage: S = NSym.S()
sage: f = 2*S[2,1] + 4*S[1,1] - 5*S[1,2] - 3*S[[]]
sage: S.degree_negation(f)
-3*S[] + 4*S[1, 1] + 5*S[1, 2] - 2*S[2, 1]

sage: QSym = QuasiSymmetricFunctions(QQ)
sage: dI = QSym.dualImmaculate()
sage: f = -3*dI[2,1] + 4*dI[2] + 2*dI[1]
sage: dI.degree_negation(f)
-2*dI[1] + 4*dI[2] + 3*dI[2, 1]


TESTS:

Using degree_negation() on an element of a different basis works correctly:

sage: NSym = NonCommutativeSymmetricFunctions(QQ)
sage: S = NSym.S()
sage: Phi = NSym.Phi()
sage: S.degree_negation(Phi[2])
-S[1, 1] + 2*S[2]
sage: S.degree_negation(Phi[3])
-S[1, 1, 1] + 3/2*S[1, 2] + 3/2*S[2, 1] - 3*S[3]
sage: Phi.degree_negation(S[3])
-1/6*Phi[1, 1, 1] - 1/4*Phi[1, 2] - 1/4*Phi[2, 1] - 1/3*Phi[3]


The zero element behaves well:

sage: a = Phi.degree_negation(S.zero()); a
0
sage: parent(a)
Non-Commutative Symmetric Functions over the Rational Field in the Phi basis


Todo

Generalize this to all graded vector spaces?

degree_on_basis(I)

Return the degree of the basis element indexed by $$I$$.

INPUT:

• I – a composition

OUTPUT:

• The degree of the non-commutative symmetric function basis element of self indexed by I. By definition, this is the size of the composition I.

EXAMPLES:

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: R.degree_on_basis(Composition([2,3]))
5
sage: M = QuasiSymmetricFunctions(QQ).Monomial()
sage: M.degree_on_basis(Composition([3,2]))
5
sage: M.degree_on_basis(Composition([]))
0

duality_pairing(x, y)

The duality pairing between elements of $$NSym$$ and elements of $$QSym$$.

This is a default implementation that uses self.realizations_of().a_realization() and its dual basis.

INPUT:

• x – an element of self
• y – an element in the dual basis of self

OUTPUT:

• The result of pairing the function x from self with the function y from the dual basis of self

EXAMPLES:

sage: R = NonCommutativeSymmetricFunctions(QQ).Ribbon()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: R.duality_pairing(R[1,1,2], F[1,1,2])
1
sage: R.duality_pairing(R[1,2,1], F[1,1,2])
0
sage: F.duality_pairing(F[1,2,1], R[1,1,2])
0

sage: S = NonCommutativeSymmetricFunctions(QQ).Complete()
sage: M = QuasiSymmetricFunctions(QQ).Monomial()
sage: S.duality_pairing(S[1,1,2], M[1,1,2])
1
sage: S.duality_pairing(S[1,2,1], M[1,1,2])
0
sage: M.duality_pairing(M[1,1,2], S[1,1,2])
1
sage: M.duality_pairing(M[1,2,1], S[1,1,2])
0

sage: S = NonCommutativeSymmetricFunctions(QQ).Complete()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: S.duality_pairing(S[1,2], F[1,1,1])
0
sage: S.duality_pairing(S[1,1,1,1], F[4])
1


TESTS:

The result has the right parent even if the sum is empty:

sage: x = S.duality_pairing(S.zero(), F.zero()); x
0
sage: parent(x)
Rational Field

duality_pairing_by_coercion(x, y)

The duality pairing between elements of NSym and elements of QSym.

This is a default implementation that uses self.realizations_of().a_realization() and its dual basis.

INPUT:

• x – an element of self
• y – an element in the dual basis of self

OUTPUT:

• The result of pairing the function x from self with the function y from the dual basis of self

EXAMPLES:

sage: L = NonCommutativeSymmetricFunctions(QQ).Elementary()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: L.duality_pairing_by_coercion(L[1,2], F[1,2])
0
sage: F.duality_pairing_by_coercion(F[1,2], L[1,2])
0
sage: L.duality_pairing_by_coercion(L[1,1,1], F[1,2])
1
sage: F.duality_pairing_by_coercion(F[1,2], L[1,1,1])
1


TESTS:

The result has the right parent even if the sum is empty:

sage: x = F.duality_pairing_by_coercion(F.zero(), L.zero()); x
0
sage: parent(x)
Rational Field

duality_pairing_matrix(basis, degree)

The matrix of scalar products between elements of NSym and elements of QSym.

INPUT:

• basis – A basis of the dual Hopf algebra
• degree – a non-negative integer

OUTPUT:

• The matrix of scalar products between the basis self and the basis basis in the dual Hopf algebra in degree degree.

EXAMPLES:

The ribbon basis of NCSF is dual to the fundamental basis of QSym:

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: R.duality_pairing_matrix(F, 3)
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
sage: F.duality_pairing_matrix(R, 3)
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]


The complete basis of NCSF is dual to the monomial basis of QSym:

sage: S = NonCommutativeSymmetricFunctions(QQ).complete()
sage: M = QuasiSymmetricFunctions(QQ).Monomial()
sage: S.duality_pairing_matrix(M, 3)
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
sage: M.duality_pairing_matrix(S, 3)
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]


The matrix between the ribbon basis of NCSF and the monomial basis of QSym:

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: M = QuasiSymmetricFunctions(QQ).Monomial()
sage: R.duality_pairing_matrix(M, 3)
[ 1 -1 -1  1]
[ 0  1  0 -1]
[ 0  0  1 -1]
[ 0  0  0  1]
sage: M.duality_pairing_matrix(R, 3)
[ 1  0  0  0]
[-1  1  0  0]
[-1  0  1  0]
[ 1 -1 -1  1]


The matrix between the complete basis of NCSF and the fundamental basis of QSym:

sage: S = NonCommutativeSymmetricFunctions(QQ).complete()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: S.duality_pairing_matrix(F, 3)
[1 1 1 1]
[0 1 0 1]
[0 0 1 1]
[0 0 0 1]


A base case test:

sage: R.duality_pairing_matrix(M,0)
[1]

one_basis()

Return the empty composition.

OUTPUT

• The empty composition.

EXAMPLES:

sage: L=NonCommutativeSymmetricFunctions(QQ).L()
sage: parent(L)
<class 'sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions.Elementary_with_category'>
sage: parent(L).one_basis()
[]

skew(x, y, side='left')

Return a function x in self skewed by a function y in the Hopf dual of self.

INPUT:

• x – a non-commutative or quasi-symmetric function; it is an element of self
• y – a quasi-symmetric or non-commutative symmetric function; it is an element of the dual algebra of self
• side – (default: 'left') either 'left' or 'right'

OUTPUT:

• The result of skewing the element x by the Hopf algebra element y (either from the left or from the right, as determined by side), written in the basis self.

EXAMPLES:

sage: S = NonCommutativeSymmetricFunctions(QQ).complete()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: S.skew(S[2,2,2], F[1,1])
S[1, 1, 2] + S[1, 2, 1] + S[2, 1, 1]
sage: S.skew(S[2,2,2], F[2])
S[1, 1, 2] + S[1, 2, 1] + S[2, 1, 1] + 3*S[2, 2]

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: F = QuasiSymmetricFunctions(QQ).Fundamental()
sage: R.skew(R[2,2,2], F[1,1])
R[1, 1, 2] + R[1, 2, 1] + R[1, 3] + R[2, 1, 1] + 2*R[2, 2] + R[3, 1] + R[4]
sage: R.skew(R[2,2,2], F[2])
R[1, 1, 2] + R[1, 2, 1] + R[1, 3] + R[2, 1, 1] + 3*R[2, 2] + R[3, 1] + R[4]

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: R = NonCommutativeSymmetricFunctions(QQ).R()
sage: M = QuasiSymmetricFunctions(QQ).M()
sage: M.skew(M[3,2], S[2])
0
sage: M.skew(M[3,2], S[2], side='right')
M[3]
sage: M.skew(M[3,2], S[3])
M[2]
sage: M.skew(M[3,2], S[3], side='right')
0


TESTS:

sage: R = NonCommutativeSymmetricFunctions(QQ).R()
sage: R.skew([2,1], [1])
Traceback (most recent call last):
...
AssertionError: x must be an element of Non-Commutative Symmetric Functions over the Rational Field
sage: R([2,1]).skew_by([1])
Traceback (most recent call last):
...
AssertionError: y must be an element of Quasisymmetric functions over the Rational Field
sage: F = QuasiSymmetricFunctions(QQ).F()
sage: F([2,1]).skew_by([1])
Traceback (most recent call last):
...
AssertionError: y must be an element of Non-Commutative Symmetric Functions over the Rational Field

sum_of_fatter_compositions(composition)

Return the sum of all fatter compositions.

INPUT:

• composition – a composition

OUTPUT:

• the sum of all basis elements which are indexed by compositions fatter (coarser?) than composition.

EXAMPLES:

sage: L=NonCommutativeSymmetricFunctions(QQ).L()
sage: L.sum_of_fatter_compositions(Composition([2,1]))
L[2, 1] + L[3]
sage: R=NonCommutativeSymmetricFunctions(QQ).R()
sage: R.sum_of_fatter_compositions(Composition([1,3]))
R[1, 3] + R[4]

sum_of_finer_compositions(composition)

Return the sum of all finer compositions.

INPUT:

• composition – a composition

OUTPUT:

• The sum of all basis self elements which are indexed by compositions finer than composition.

EXAMPLES:

sage: L=NonCommutativeSymmetricFunctions(QQ).L()
sage: L.sum_of_finer_compositions(Composition([2,1]))
L[1, 1, 1] + L[2, 1]
sage: R=NonCommutativeSymmetricFunctions(QQ).R()
sage: R.sum_of_finer_compositions(Composition([1,3]))
R[1, 1, 1, 1] + R[1, 1, 2] + R[1, 2, 1] + R[1, 3]

sum_of_partition_rearrangements(par)

Return the sum of all basis elements indexed by compositions which can be sorted to obtain a given partition.

INPUT:

• par – a partition

OUTPUT:

• The sum of all self basis elements indexed by compositions which are permutations of par (without multiplicity).

EXAMPLES:

sage: NCSF=NonCommutativeSymmetricFunctions(QQ)
sage: elementary = NCSF.elementary()
sage: elementary.sum_of_partition_rearrangements(Partition([2,2,1]))
L[1, 2, 2] + L[2, 1, 2] + L[2, 2, 1]
sage: elementary.sum_of_partition_rearrangements(Partition([3,2,1]))
L[1, 2, 3] + L[1, 3, 2] + L[2, 1, 3] + L[2, 3, 1] + L[3, 1, 2] + L[3, 2, 1]
sage: elementary.sum_of_partition_rearrangements(Partition([]))
L[]

BasesOfQSymOrNCSF.super_categories()

TESTS:

sage: from sage.combinat.ncsf_qsym.generic_basis_code import BasesOfQSymOrNCSF
sage: QSym = QuasiSymmetricFunctions(QQ)
sage: BasesOfQSymOrNCSF(QSym).super_categories()
[Category of realizations of Quasisymmetric functions over the Rational Field,
Category of graded hopf algebras with basis over Rational Field,
Join of Category of realizations of hopf algebras over Rational Field and
Category of graded algebras over Rational Field]


Constructs the class of modules with internal product. This is used to give an internal product structure to the non-commutative symmetric functions.

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.generic_basis_code import GradedModulesWithInternalProduct
sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: R = N.ribbon()
True

class ElementMethods
internal_product(other)

Return the internal product of two non-commutative symmetric functions.

The internal product on the algebra of non-commutative symmetric functions is adjoint to the internal coproduct on the algebra of quasisymmetric functions with respect to the duality pairing between these two algebras. This means, explicitly, that any two non-commutative symmetric functions $$f$$ and $$g$$ and any quasi-symmetric function $$h$$ satisfy

$\langle f * g, h \rangle = \sum_i \left\langle f, h^{\prime}_i \right\rangle \left\langle g, h^{\prime\prime}_i \right\rangle,$

where we write $$\Delta^{\times}(h)$$ as $$\sum_i h^{\prime}_i \otimes h^{\prime\prime}_i$$. Here, $$f * g$$ denotes the internal product of the non-commutative symmetric functions $$f$$ and $$g$$.

If $$f$$ and $$g$$ are two homogeneous elements of $$NSym$$ having distinct degrees, then the internal product $$f * g$$ is zero.

Explicit formulas can be given for internal products of elements of the complete and the Psi bases. First, the formula for the Complete basis ([NCSF1] Proposition 5.1): If $$I$$ and $$J$$ are two compositions of lengths $$p$$ and $$q$$, respectively, then the corresponding Complete homogeneous non-commutative symmetric functions $$S^I$$ and $$S^J$$ have internal product

$S^I * S^J = \sum S^{\operatorname*{comp}M},$

where the sum ranges over all $$p \times q$$-matrices $$M \in \NN^{p \times q}$$ (with nonnegative integers as entries) whose row sum vector is $$I$$ (that is, the sum of the entries of the $$r$$-th row is the $$r$$-th part of $$I$$ for all $$r$$) and whose column sum vector is $$J$$ (that is, the sum of all entries of the $$s$$-th row is the $$s$$-th part of $$J$$ for all $$s$$). Here, for any $$M \in \NN^{p \times q}$$, we denote by $$\operatorname*{comp}M$$ the composition obtained by reading the entries of the matrix $$M$$ in the usual order (row by row, proceeding left to right in each row, traversing the rows from top to bottom).

The formula on the Psi basis ([NCSF2] Lemma 3.10) is more complicated. Let $$I$$ and $$J$$ be two compositions of lengths $$p$$ and $$q$$, respectively, having the same size $$|I| = |J|$$. We denote by $$\Psi^K$$ the element of the Psi basis corresponding to any composition $$K$$.

• If $$p > q$$, then $$\Psi^I * \Psi^J$$ is plainly $$0$$.
• Assume that $$p = q$$. Let $$\widetilde{\delta}_{I, J}$$ denote the integer $$1$$ if the compositions $$I$$ and $$J$$ are permutations of each other, and the integer $$0$$ otherwise. For every positive integer $$i$$, let $$m_i$$ denote the number of parts of $$I$$ equal to $$i$$. Then, $$\Psi^I * \Psi^J$$ equals $$\widetilde{\delta}_{I, J} \prod_{i>0} i^{m_i} m_i! \Psi^I$$.
• Now assume that $$p < q$$. Write the composition $$I$$ as $$I = (i_1, i_2, \ldots, i_p)$$. For every nonempty composition $$K = (k_1, k_2, \ldots, k_s)$$, denote by $$\Gamma_K$$ the non-commutative symmetric function $$k_1 [\ldots [[\Psi_{k_1}, \Psi_{k_2}], \Psi_{k_3}], \ldots \Psi_{k_s}]$$. For any subset $$A$$ of $$\{ 1, 2, \ldots, q \}$$, let $$J_A$$ be the composition obtained from $$J$$ by removing the $$r$$-th parts for all $$r \notin A$$ (while keeping the $$r$$-th parts for all $$r \in A$$ in order). Then, $$\Psi^I * \Psi^J$$ equals the sum of $$\Gamma_{J_{K_1}} \Gamma_{J_{K_2}} \cdots \Gamma_{J_{K_p}}$$ over all ordered set partitions $$(K_1, K_2, \ldots, K_p)$$ of $$\{ 1, 2, \ldots, q \}$$ into $$p$$ parts such that each $$1 \leq k \leq p$$ satisfies $$\left\lvert J_{K_k} \right\rvert = i_k$$. (See OrderedSetPartition() for the meaning of “ordered set partition”.)

Aliases for internal_product() are itensor() and kronecker_product().

INPUT:

• other – another non-commutative symmetric function

OUTPUT:

• The result of taking the internal product of self with other.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: x = S.an_element(); x
2*S[] + 2*S[1] + 3*S[1, 1]
sage: x.internal_product(S[2])
3*S[1, 1]
sage: x.internal_product(S[1])
2*S[1]
sage: S[1,2].internal_product(S[1,2])
S[1, 1, 1] + S[1, 2]


Let us check the duality between the inner product and the inner coproduct in degree $$4$$:

sage: M = QuasiSymmetricFunctions(FiniteField(29)).M()
sage: S = NonCommutativeSymmetricFunctions(FiniteField(29)).S()
sage: def tensor_incopr(f, g, h):  # computes \sum_i \left< f, h'_i \right> \left< g, h''_i \right>
....:     result = h.base_ring().zero()
....:     h_parent = h.parent()
....:     for partition_pair, coeff in h.internal_coproduct().monomial_coefficients().items():
....:         result += coeff * f.duality_pairing(h_parent[partition_pair[0]]) * g.duality_pairing(h_parent[partition_pair[1]])
....:     return result
sage: def testall(n):
....:     return all( all( all( tensor_incopr(S[u], S[v], M[w]) == (S[u].itensor(S[v])).duality_pairing(M[w])
....:                           for w in Compositions(n) )
....:                      for v in Compositions(n) )
....:                 for u in Compositions(n) )
sage: testall(2)
True
sage: testall(3)  # long time
True
sage: testall(4)  # long time
True


The internal product on the algebra of non-commutative symmetric functions commutes with the canonical commutative projection on the symmetric functions:

sage: S = NonCommutativeSymmetricFunctions(ZZ).S()
sage: e = SymmetricFunctions(ZZ).e()
sage: def int_pr_of_S_in_e(I, J):
....:     return (S[I].internal_product(S[J])).to_symmetric_function()
sage: all( all( int_pr_of_S_in_e(I, J)
....:           == S[I].to_symmetric_function().internal_product(S[J].to_symmetric_function())
....:           for I in Compositions(3) )
....:      for J in Compositions(3) )
True

itensor(other)

Return the internal product of two non-commutative symmetric functions.

The internal product on the algebra of non-commutative symmetric functions is adjoint to the internal coproduct on the algebra of quasisymmetric functions with respect to the duality pairing between these two algebras. This means, explicitly, that any two non-commutative symmetric functions $$f$$ and $$g$$ and any quasi-symmetric function $$h$$ satisfy

$\langle f * g, h \rangle = \sum_i \left\langle f, h^{\prime}_i \right\rangle \left\langle g, h^{\prime\prime}_i \right\rangle,$

where we write $$\Delta^{\times}(h)$$ as $$\sum_i h^{\prime}_i \otimes h^{\prime\prime}_i$$. Here, $$f * g$$ denotes the internal product of the non-commutative symmetric functions $$f$$ and $$g$$.

If $$f$$ and $$g$$ are two homogeneous elements of $$NSym$$ having distinct degrees, then the internal product $$f * g$$ is zero.

Explicit formulas can be given for internal products of elements of the complete and the Psi bases. First, the formula for the Complete basis ([NCSF1] Proposition 5.1): If $$I$$ and $$J$$ are two compositions of lengths $$p$$ and $$q$$, respectively, then the corresponding Complete homogeneous non-commutative symmetric functions $$S^I$$ and $$S^J$$ have internal product

$S^I * S^J = \sum S^{\operatorname*{comp}M},$

where the sum ranges over all $$p \times q$$-matrices $$M \in \NN^{p \times q}$$ (with nonnegative integers as entries) whose row sum vector is $$I$$ (that is, the sum of the entries of the $$r$$-th row is the $$r$$-th part of $$I$$ for all $$r$$) and whose column sum vector is $$J$$ (that is, the sum of all entries of the $$s$$-th row is the $$s$$-th part of $$J$$ for all $$s$$). Here, for any $$M \in \NN^{p \times q}$$, we denote by $$\operatorname*{comp}M$$ the composition obtained by reading the entries of the matrix $$M$$ in the usual order (row by row, proceeding left to right in each row, traversing the rows from top to bottom).

The formula on the Psi basis ([NCSF2] Lemma 3.10) is more complicated. Let $$I$$ and $$J$$ be two compositions of lengths $$p$$ and $$q$$, respectively, having the same size $$|I| = |J|$$. We denote by $$\Psi^K$$ the element of the Psi basis corresponding to any composition $$K$$.

• If $$p > q$$, then $$\Psi^I * \Psi^J$$ is plainly $$0$$.
• Assume that $$p = q$$. Let $$\widetilde{\delta}_{I, J}$$ denote the integer $$1$$ if the compositions $$I$$ and $$J$$ are permutations of each other, and the integer $$0$$ otherwise. For every positive integer $$i$$, let $$m_i$$ denote the number of parts of $$I$$ equal to $$i$$. Then, $$\Psi^I * \Psi^J$$ equals $$\widetilde{\delta}_{I, J} \prod_{i>0} i^{m_i} m_i! \Psi^I$$.
• Now assume that $$p < q$$. Write the composition $$I$$ as $$I = (i_1, i_2, \ldots, i_p)$$. For every nonempty composition $$K = (k_1, k_2, \ldots, k_s)$$, denote by $$\Gamma_K$$ the non-commutative symmetric function $$k_1 [\ldots [[\Psi_{k_1}, \Psi_{k_2}], \Psi_{k_3}], \ldots \Psi_{k_s}]$$. For any subset $$A$$ of $$\{ 1, 2, \ldots, q \}$$, let $$J_A$$ be the composition obtained from $$J$$ by removing the $$r$$-th parts for all $$r \notin A$$ (while keeping the $$r$$-th parts for all $$r \in A$$ in order). Then, $$\Psi^I * \Psi^J$$ equals the sum of $$\Gamma_{J_{K_1}} \Gamma_{J_{K_2}} \cdots \Gamma_{J_{K_p}}$$ over all ordered set partitions $$(K_1, K_2, \ldots, K_p)$$ of $$\{ 1, 2, \ldots, q \}$$ into $$p$$ parts such that each $$1 \leq k \leq p$$ satisfies $$\left\lvert J_{K_k} \right\rvert = i_k$$. (See OrderedSetPartition() for the meaning of “ordered set partition”.)

Aliases for internal_product() are itensor() and kronecker_product().

INPUT:

• other – another non-commutative symmetric function

OUTPUT:

• The result of taking the internal product of self with other.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: x = S.an_element(); x
2*S[] + 2*S[1] + 3*S[1, 1]
sage: x.internal_product(S[2])
3*S[1, 1]
sage: x.internal_product(S[1])
2*S[1]
sage: S[1,2].internal_product(S[1,2])
S[1, 1, 1] + S[1, 2]


Let us check the duality between the inner product and the inner coproduct in degree $$4$$:

sage: M = QuasiSymmetricFunctions(FiniteField(29)).M()
sage: S = NonCommutativeSymmetricFunctions(FiniteField(29)).S()
sage: def tensor_incopr(f, g, h):  # computes \sum_i \left< f, h'_i \right> \left< g, h''_i \right>
....:     result = h.base_ring().zero()
....:     h_parent = h.parent()
....:     for partition_pair, coeff in h.internal_coproduct().monomial_coefficients().items():
....:         result += coeff * f.duality_pairing(h_parent[partition_pair[0]]) * g.duality_pairing(h_parent[partition_pair[1]])
....:     return result
sage: def testall(n):
....:     return all( all( all( tensor_incopr(S[u], S[v], M[w]) == (S[u].itensor(S[v])).duality_pairing(M[w])
....:                           for w in Compositions(n) )
....:                      for v in Compositions(n) )
....:                 for u in Compositions(n) )
sage: testall(2)
True
sage: testall(3)  # long time
True
sage: testall(4)  # long time
True


The internal product on the algebra of non-commutative symmetric functions commutes with the canonical commutative projection on the symmetric functions:

sage: S = NonCommutativeSymmetricFunctions(ZZ).S()
sage: e = SymmetricFunctions(ZZ).e()
sage: def int_pr_of_S_in_e(I, J):
....:     return (S[I].internal_product(S[J])).to_symmetric_function()
sage: all( all( int_pr_of_S_in_e(I, J)
....:           == S[I].to_symmetric_function().internal_product(S[J].to_symmetric_function())
....:           for I in Compositions(3) )
....:      for J in Compositions(3) )
True

kronecker_product(other)

Return the internal product of two non-commutative symmetric functions.

The internal product on the algebra of non-commutative symmetric functions is adjoint to the internal coproduct on the algebra of quasisymmetric functions with respect to the duality pairing between these two algebras. This means, explicitly, that any two non-commutative symmetric functions $$f$$ and $$g$$ and any quasi-symmetric function $$h$$ satisfy

$\langle f * g, h \rangle = \sum_i \left\langle f, h^{\prime}_i \right\rangle \left\langle g, h^{\prime\prime}_i \right\rangle,$

where we write $$\Delta^{\times}(h)$$ as $$\sum_i h^{\prime}_i \otimes h^{\prime\prime}_i$$. Here, $$f * g$$ denotes the internal product of the non-commutative symmetric functions $$f$$ and $$g$$.

If $$f$$ and $$g$$ are two homogeneous elements of $$NSym$$ having distinct degrees, then the internal product $$f * g$$ is zero.

Explicit formulas can be given for internal products of elements of the complete and the Psi bases. First, the formula for the Complete basis ([NCSF1] Proposition 5.1): If $$I$$ and $$J$$ are two compositions of lengths $$p$$ and $$q$$, respectively, then the corresponding Complete homogeneous non-commutative symmetric functions $$S^I$$ and $$S^J$$ have internal product

$S^I * S^J = \sum S^{\operatorname*{comp}M},$

where the sum ranges over all $$p \times q$$-matrices $$M \in \NN^{p \times q}$$ (with nonnegative integers as entries) whose row sum vector is $$I$$ (that is, the sum of the entries of the $$r$$-th row is the $$r$$-th part of $$I$$ for all $$r$$) and whose column sum vector is $$J$$ (that is, the sum of all entries of the $$s$$-th row is the $$s$$-th part of $$J$$ for all $$s$$). Here, for any $$M \in \NN^{p \times q}$$, we denote by $$\operatorname*{comp}M$$ the composition obtained by reading the entries of the matrix $$M$$ in the usual order (row by row, proceeding left to right in each row, traversing the rows from top to bottom).

The formula on the Psi basis ([NCSF2] Lemma 3.10) is more complicated. Let $$I$$ and $$J$$ be two compositions of lengths $$p$$ and $$q$$, respectively, having the same size $$|I| = |J|$$. We denote by $$\Psi^K$$ the element of the Psi basis corresponding to any composition $$K$$.

• If $$p > q$$, then $$\Psi^I * \Psi^J$$ is plainly $$0$$.
• Assume that $$p = q$$. Let $$\widetilde{\delta}_{I, J}$$ denote the integer $$1$$ if the compositions $$I$$ and $$J$$ are permutations of each other, and the integer $$0$$ otherwise. For every positive integer $$i$$, let $$m_i$$ denote the number of parts of $$I$$ equal to $$i$$. Then, $$\Psi^I * \Psi^J$$ equals $$\widetilde{\delta}_{I, J} \prod_{i>0} i^{m_i} m_i! \Psi^I$$.
• Now assume that $$p < q$$. Write the composition $$I$$ as $$I = (i_1, i_2, \ldots, i_p)$$. For every nonempty composition $$K = (k_1, k_2, \ldots, k_s)$$, denote by $$\Gamma_K$$ the non-commutative symmetric function $$k_1 [\ldots [[\Psi_{k_1}, \Psi_{k_2}], \Psi_{k_3}], \ldots \Psi_{k_s}]$$. For any subset $$A$$ of $$\{ 1, 2, \ldots, q \}$$, let $$J_A$$ be the composition obtained from $$J$$ by removing the $$r$$-th parts for all $$r \notin A$$ (while keeping the $$r$$-th parts for all $$r \in A$$ in order). Then, $$\Psi^I * \Psi^J$$ equals the sum of $$\Gamma_{J_{K_1}} \Gamma_{J_{K_2}} \cdots \Gamma_{J_{K_p}}$$ over all ordered set partitions $$(K_1, K_2, \ldots, K_p)$$ of $$\{ 1, 2, \ldots, q \}$$ into $$p$$ parts such that each $$1 \leq k \leq p$$ satisfies $$\left\lvert J_{K_k} \right\rvert = i_k$$. (See OrderedSetPartition() for the meaning of “ordered set partition”.)

Aliases for internal_product() are itensor() and kronecker_product().

INPUT:

• other – another non-commutative symmetric function

OUTPUT:

• The result of taking the internal product of self with other.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: x = S.an_element(); x
2*S[] + 2*S[1] + 3*S[1, 1]
sage: x.internal_product(S[2])
3*S[1, 1]
sage: x.internal_product(S[1])
2*S[1]
sage: S[1,2].internal_product(S[1,2])
S[1, 1, 1] + S[1, 2]


Let us check the duality between the inner product and the inner coproduct in degree $$4$$:

sage: M = QuasiSymmetricFunctions(FiniteField(29)).M()
sage: S = NonCommutativeSymmetricFunctions(FiniteField(29)).S()
sage: def tensor_incopr(f, g, h):  # computes \sum_i \left< f, h'_i \right> \left< g, h''_i \right>
....:     result = h.base_ring().zero()
....:     h_parent = h.parent()
....:     for partition_pair, coeff in h.internal_coproduct().monomial_coefficients().items():
....:         result += coeff * f.duality_pairing(h_parent[partition_pair[0]]) * g.duality_pairing(h_parent[partition_pair[1]])
....:     return result
sage: def testall(n):
....:     return all( all( all( tensor_incopr(S[u], S[v], M[w]) == (S[u].itensor(S[v])).duality_pairing(M[w])
....:                           for w in Compositions(n) )
....:                      for v in Compositions(n) )
....:                 for u in Compositions(n) )
sage: testall(2)
True
sage: testall(3)  # long time
True
sage: testall(4)  # long time
True


The internal product on the algebra of non-commutative symmetric functions commutes with the canonical commutative projection on the symmetric functions:

sage: S = NonCommutativeSymmetricFunctions(ZZ).S()
sage: e = SymmetricFunctions(ZZ).e()
sage: def int_pr_of_S_in_e(I, J):
....:     return (S[I].internal_product(S[J])).to_symmetric_function()
sage: all( all( int_pr_of_S_in_e(I, J)
....:           == S[I].to_symmetric_function().internal_product(S[J].to_symmetric_function())
....:           for I in Compositions(3) )
....:      for J in Compositions(3) )
True

internal_product()

Internal product as an endomorphism of self.

This is constructed by extending the method internal_product_on_basis() bilinearly, if available, or using the method internal_product_by_coercion().

OUTPUT:

• The internal product map of the algebra the non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: S.internal_product
Generic endomorphism of Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: S.internal_product(S[2,2], S[1,2,1])
2*S[1, 1, 1, 1] + S[1, 1, 2] + S[2, 1, 1]
sage: S.internal_product(S[2,2], S[1,2])
0

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: R = N.ribbon()
sage: R.internal_product
<bound method ....internal_product_by_coercion ...>
sage: R.internal_product_by_coercion(R[1, 1], R[1,1])
R[2]
sage: R.internal_product(R[2,2], R[1,2])
0


Todo

Despite the __repr__, this is NOT an endomorphism!

internal_product_on_basis(I, J)

The internal product of the two basis elements indexed by I and J (optional)

INPUT:

• I, J – compositions indexing two elements of the basis of self

Returns the internal product of the corresponding basis elements. If this method is implemented, the internal product is defined from it by linearity.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: S.internal_product_on_basis([2,2], [1,2,1])
2*S[1, 1, 1, 1] + S[1, 1, 2] + S[2, 1, 1]
sage: S.internal_product_on_basis([2,2], [2,1])
0

itensor()

Internal product as an endomorphism of self.

This is constructed by extending the method internal_product_on_basis() bilinearly, if available, or using the method internal_product_by_coercion().

OUTPUT:

• The internal product map of the algebra the non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: S.internal_product
Generic endomorphism of Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: S.internal_product(S[2,2], S[1,2,1])
2*S[1, 1, 1, 1] + S[1, 1, 2] + S[2, 1, 1]
sage: S.internal_product(S[2,2], S[1,2])
0

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: R = N.ribbon()
sage: R.internal_product
<bound method ....internal_product_by_coercion ...>
sage: R.internal_product_by_coercion(R[1, 1], R[1,1])
R[2]
sage: R.internal_product(R[2,2], R[1,2])
0


Todo

Despite the __repr__, this is NOT an endomorphism!

kronecker_product()

Internal product as an endomorphism of self.

This is constructed by extending the method internal_product_on_basis() bilinearly, if available, or using the method internal_product_by_coercion().

OUTPUT:

• The internal product map of the algebra the non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: S.internal_product
Generic endomorphism of Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: S.internal_product(S[2,2], S[1,2,1])
2*S[1, 1, 1, 1] + S[1, 1, 2] + S[2, 1, 1]
sage: S.internal_product(S[2,2], S[1,2])
0

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: R = N.ribbon()
sage: R.internal_product
<bound method ....internal_product_by_coercion ...>
sage: R.internal_product_by_coercion(R[1, 1], R[1,1])
R[2]
sage: R.internal_product(R[2,2], R[1,2])
0


Todo

Despite the __repr__, this is NOT an endomorphism!

TESTS:

sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
...       _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()

class ParentMethods
internal_product_by_coercion(left, right)

Internal product of left and right.

This is a default implementation that computes the internal product in the realization specified by self.realization_of().a_realization().

INPUT:

• left – an element of the non-commutative symmetric functions
• right – an element of the non-commutative symmetric functions

OUTPUT:

• The internal product of left and right.

EXAMPLES:

sage: S=NonCommutativeSymmetricFunctions(QQ).S()
sage: S.internal_product_by_coercion(S[2,1], S[3])
S[2, 1]
sage: S.internal_product_by_coercion(S[2,1], S[4])
0


EXAMPLES:

sage: from sage.combinat.ncsf_qsym.generic_basis_code import GradedModulesWithInternalProduct