Module: sage.combinat.combinatorial_algebra
Combinatorial Algebras
A combinatorial algebra is an algebra whose basis elements are indexed by a combinatorial class. Some examples of combinatorial algebras are the symmetric group algebra of order n (indexed by permutations of size n) and the algebra of symmetric functions (indexed by integer partitions).
The CombinatorialAlgebra base class makes it easy to define and work with new combinatorial algebras in Sage. For example, the following code constructs an algebra which models the power-sum symmetric functions.
sage: class PowerSums(CombinatorialAlgebra): ... def __init__(self, R): ... self._combinatorial_class = Partitions() ... self._one = Partition([]) ... self._name = 'Power-sum symmetric functions' ... self._prefix = 'p' ... CombinatorialAlgebra.__init__(self, R) ... def _multiply_basis(self, a, b): ... l = list(a)+list(b) ... l.sort(reverse=True) ... return Partition(l) ...
sage: ps = PowerSums(QQ); ps Power-sum symmetric functions over Rational Field sage: ps([2,1])^2 p[2, 2, 1, 1] sage: ps([2,1])+2*ps([1,1,1]) 2*p[1, 1, 1] + p[2, 1] sage: ps(2) 2*p[]
The important things to define are ._combinatorial_class which specifies the combinatorial class that indexes the basis elements, ._one which specifies the identity element in the algebra, ._name which specifies the name of the algebra, ._prefix which is the string put in front of each basis element, and finally a _multiply or _multiply basis method that defines the multiplication in the algebra.
Class: CombinatorialAlgebra
self, R, [element_class=None]) |
TESTS:
sage: s = SFASchur(QQ) sage: s == loads(dumps(s)) True
Functions: basis,
combinatorial_class,
dimension,
get_order,
multiply,
prefix,
set_order
self) |
Returns a list of the basis elements of self.
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: QS3.basis() [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
self) |
Returns the combinatorial class that indexes the basis elements.
sage: s = SFASchur(QQ) sage: s.combinatorial_class() Partitions
self) |
Returns the dimension of the combinatorial algebra (which is given by the number of elements in the associated combinatorial class).
sage: s = SFASchur(QQ) sage: s.dimension() +Infinity
self) |
Returns the order of the elements in the basis.
sage: QS2 = SymmetricGroupAlgebra(QQ,2) sage: QS2.get_order() [[1, 2], [2, 1]]
self, left, right) |
Returns left*right where left and right are elements of self. multiply() uses either _multiply or _multiply basis to carry out the actual multiplication.
sage: s = SFASchur(QQ) sage: a = s([2]) sage: s.multiply(a,a) s[2, 2] + s[3, 1] + s[4]
self) |
Returns the prefix used when displaying elements of self.
sage: X = SchubertPolynomialRing(QQ) sage: X.prefix() 'X'
self, order) |
Sets the order of the elements of the combinatorial class.
If .set_order() has not been called, then the ordering is the one used in the generation of the elements of self's associated combinatorial class.
sage: QS2 = SymmetricGroupAlgebra(QQ,2) sage: b = QS2.basis() sage: b.reverse() sage: QS2.set_order(b) sage: QS2.get_order() [[2, 1], [1, 2]]
Special Functions: __call__,
__cmp__,
__init__,
__repr__,
_an_element_impl,
_apply_module_endomorphism,
_apply_module_morphism,
_coerce_impl,
_from_dict
self, x) |
Coerce x into self.
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: QS3(2) 2*[1, 2, 3] sage: QS3([2,3,1]) [2, 3, 1]
self, other) |
sage: XQ = SchubertPolynomialRing(QQ) sage: XZ = SchubertPolynomialRing(ZZ) sage: XQ == XZ #indirect doctest False sage: XQ == XQ True
self) |
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: print QS3.__repr__() Symmetric group algebra of order 3 over Rational Field
self) |
Returns an element of self, namely the unit element.
sage: s = SFASchur(QQ) sage: s._an_element_impl() s[] sage: _.parent() is s True
self, a, f) |
This takes in a function from the basis elements to the elements of self and applies it linearly to a. Note that _apply_module_endomorphism does not require multiplication on self to be defined.
sage: s = SFASchur(QQ) sage: f = lambda part: 2*s(part.conjugate()) sage: s._apply_module_endomorphism( s([2,1]) + s([1,1,1]), f) 2*s[2, 1] + 2*s[3]
self, x, f) |
Returns the image of x under the module morphism defined by extending f by linearity.
Input:
sage: s = SFASchur(QQ) sage: a = s([3]) + s([2,1]) + s([1,1,1]) sage: b = 2*a sage: f = lambda part: len(part) sage: s._apply_module_morphism(a, f) #1+2+3 6 sage: s._apply_module_morphism(b, f) #2*(1+2+3) 12
self, x) |
sage: s = SFASchur(QQ) sage: s._coerce_impl(2) 2*s[]
self, d, [coerce=False]) |
Given a monomial coefficient dictionary d, return the element of self with the dictionary.
sage: e = SFAElementary(QQ) sage: s = SFASchur(QQ) sage: a = e([2,1]) + e([1,1,1]); a e[1, 1, 1] + e[2, 1] sage: s._from_dict(a.monomial_coefficients()) s[1, 1, 1] + s[2, 1]
sage: part = Partition([2,1]) sage: d = {part:1} sage: a = s._from_dict(d,coerce=True); a s[2, 1] sage: a.coefficient(part).parent() Rational Field
Class: CombinatorialAlgebraElement
self, A, x) |
Create a combinatorial algebra element x. This should never be called directly, but only through the parent combinatorial algebra's __call__ method.
TESTS:
sage: s = SFASchur(QQ) sage: a = s._element_class(s, {Partition([2,1]):QQ(2)}); a 2*s[2, 1] sage: a == loads(dumps(a)) True
Functions: coefficient,
coefficients,
is_zero,
length,
map_basis,
map_coefficients,
map_mc,
monomial_coefficients,
monomials,
support,
to_matrix,
to_vector
self, m) |
sage: s = SFASchur(QQ) sage: z = s([4]) - 2*s([2,1]) + s([1,1,1]) + s([1]) sage: z.coefficient([4]) 1 sage: z.coefficient([2,1]) -2
self) |
Returns a list of the coefficents appearing on the basiselements in self.
sage: s = SFASchur(QQ) sage: z = s([4]) + s([2,1]) + s([1,1,1]) + s([1]) sage: z.coefficients() [1, 1, 1, 1]
self) |
Returns True if and only self == 0.
sage: s = SFASchur(QQ) sage: s([2,1]).is_zero() False sage: s(0).is_zero() True sage: (s([2,1]) - s([2,1])).is_zero() True
self) |
Returns the number of basis elements of self with nonzero coefficients.
sage: s = SFASchur(QQ) sage: z = s([4]) + s([2,1]) + s([1,1,1]) + s([1]) sage: z.length() 4
self, f) |
Returns a new element of self.parent() obtained by applying the function f to all of the combinatorial objects indexing the basis elements.
sage: s = SFASchur(QQ) sage: a = s([2,1])+2*s([3,2]) sage: a.map_basis(lambda x: x.conjugate()) s[2, 1] + 2*s[2, 2, 1]
self, f) |
Returns a new element of self.parent() obtained by applying the function f to all of the coefficients of self.
sage: s = SFASchur(QQ) sage: a = s([2,1])+2*s([3,2]) sage: a.map_coefficients(lambda x: x*2) 2*s[2, 1] + 4*s[3, 2]
self, f) |
Returns a new element of self.parent() obtained by applying the function f to a monomial coefficient (m,c) pair. f returns a (new_m, new_c) pair.
sage: s = SFASchur(QQ) sage: f = lambda m,c: (m.conjugate(), 2*c) sage: a = s([2,1]) + s([1,1,1]) sage: a.map_mc(f) 2*s[2, 1] + 2*s[3]
self) |
Return the internal dictionary which has the combinatorial objects indexing the basis as keys and their corresponding coefficients as values.
sage: s = SFASchur(QQ) sage: a = s([2,1])+2*s([3,2]) sage: d = a.monomial_coefficients() sage: type(d) <type 'dict'> sage: d[ Partition([2,1]) ] 1 sage: d[ Partition([3,2]) ] 2
self) |
Returns a list of the combinatorial objects indexing the basis elements of self which non-zero coefficients.
sage: s = SFASchur(QQ) sage: z = s([4]) + s([2,1]) + s([1,1,1]) + s([1]) sage: z.monomials() [[1], [1, 1, 1], [2, 1], [4]]
self) |
Returns a pair [mons, cffs] of lists of the monomials of self (mons) and their respective coefficients (cffs).
sage: s = SFASchur(QQ) sage: z = s([4]) + s([2,1]) + s([1,1,1]) + s([1]) sage: z.support() [[[1], [1, 1, 1], [2, 1], [4]], [1, 1, 1, 1]]
self) |
Returns a matrix version of self obtained by the action of self on the left. If new_BR is specified, then the matrix will be over new_BR.
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = QS3([2,1,3]) sage: a._matrix_() # indirect doctest [0 0 1 0 0 0] [0 0 0 0 1 0] [1 0 0 0 0 0] [0 0 0 0 0 1] [0 1 0 0 0 0] [0 0 0 1 0 0] sage: a._matrix_(RDF) [0.0 0.0 1.0 0.0 0.0 0.0] [0.0 0.0 0.0 0.0 1.0 0.0] [1.0 0.0 0.0 0.0 0.0 0.0] [0.0 0.0 0.0 0.0 0.0 1.0] [0.0 1.0 0.0 0.0 0.0 0.0] [0.0 0.0 0.0 1.0 0.0 0.0]
self) |
Returns a vector version of self.
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = 2*QS3([1,2,3])+4*QS3([3,2,1]) sage: a.to_vector() (2, 0, 0, 0, 0, 4)
Special Functions: __cmp__,
__contains__,
__init__,
__invert__,
__iter__,
__len__,
__pow__,
__repr__,
_add_,
_coefficient_fast,
_div_,
_latex_,
_matrix_,
_mul_,
_neg_,
_sub_,
_vector_
left, right) |
The ordering is the one on the underlying sorted list of (monomial,coefficients) pairs.
sage: s = SFASchur(QQ) sage: a = s([2,1]) sage: b = s([1,1,1]) sage: cmp(a,b) #indirect doctest 1
self, x) |
Returns whether or not a combinatorial object x indexing a basis element is in the support of self.
sage: s = SFASchur(QQ) sage: a = s([2,1]) + s([3]) sage: Partition([2,1]) in a True sage: Partition([1,1,1]) in a False
self) |
sage: s = SFASchur(QQ) sage: ~s(2) 1/2*s[] sage: ~s([2,1]) Traceback (most recent call last): ... ValueError: cannot invert self (= s[2, 1])
self) |
sage: s = SFASchur(QQ) sage: a = s([2,1]) + s([3]) sage: [i for i in sorted(a)] [([2, 1], 1), ([3], 1)]
self) |
Returns the number of basis elements of self with nonzero coefficients.
sage: s = SFASchur(QQ) sage: z = s([4]) + s([2,1]) + s([1,1,1]) + s([1]) sage: len(z) 4
self, n) |
Returns self to the
power.
sage: s = SFASchur(QQ) sage: s([2])^2 s[2, 2] + s[3, 1] + s[4]
TESTS:
sage: s = SFASchur(QQ) sage: z = s([2,1]) sage: z s[2, 1] sage: z^2 s[2, 2, 1, 1] + s[2, 2, 2] + s[3, 1, 1, 1] + 2*s[3, 2, 1] + s[3, 3] + s[4, 1, 1] + s[4, 2]
sage: e = SFAElementary(QQ) sage: y = e([1]) sage: y^2 e[1, 1] sage: y^4 e[1, 1, 1, 1]
self) |
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: a = 2 + QS3([2,1,3]) sage: print a.__repr__() 2*[1, 2, 3] + [2, 1, 3]
self, y) |
sage: s = SFASchur(QQ) sage: s([2,1]) + s([5,4]) # indirect doctest s[2, 1] + s[5, 4] sage: a = s([2,1]) + 0 sage: len(a.monomial_coefficients()) 1
self, m, [default=None]) |
Returns the coefficient of m in self, where m is key in self._monomial_coefficients.
sage: p = Partition([2,1]) sage: s = SFASchur(QQ) sage: a = s([2,1]) sage: a._coefficient_fast([2,1]) Traceback (most recent call last): ... TypeError: list objects are unhashable sage: a._coefficient_fast(p) 1 sage: a._coefficient_fast(p, 2) 1
self, y) |
sage: s = SFASchur(QQ) sage: a = s([2]) sage: a._div_(s(2)) 1/2*s[2] sage: a._div_(a) Traceback (most recent call last): ... ValueError: cannot invert self (= s[2])
self) |
sage: QS3 = SymmetricGroupAlgebra(QQ,3) sage: a = 2 + QS3([2,1,3]) sage: latex(a) #indirect doctest 2[1,2,3] + [2,1,3]
self, [new_BR=None]) |
Returns a matrix version of self obtained by the action of self on the left. If new_BR is specified, then the matrix will be over new_BR.
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = QS3([2,1,3]) sage: a._matrix_() [0 0 1 0 0 0] [0 0 0 0 1 0] [1 0 0 0 0 0] [0 0 0 0 0 1] [0 1 0 0 0 0] [0 0 0 1 0 0] sage: a._matrix_(RDF) [0.0 0.0 1.0 0.0 0.0 0.0] [0.0 0.0 0.0 0.0 1.0 0.0] [1.0 0.0 0.0 0.0 0.0 0.0] [0.0 0.0 0.0 0.0 0.0 1.0] [0.0 1.0 0.0 0.0 0.0 0.0] [0.0 0.0 0.0 1.0 0.0 0.0]
self, y) |
sage: s = SFASchur(QQ) sage: a = s([2]) sage: a._mul_(a) #indirect doctest s[2, 2] + s[3, 1] + s[4]
self) |
sage: s = SFASchur(QQ) sage: -s([2,1]) # indirect doctest -s[2, 1]
self, y) |
sage: s = SFASchur(QQ) sage: s([2,1]) - s([5,4]) # indirect doctest s[2, 1] - s[5, 4]
self, [new_BR=None]) |
Returns a vector version of self. If new_BR is specified, then in returns a vector over new_BR.
sage: QS3 = SymmetricGroupAlgebra(QQ, 3) sage: a = 2*QS3([1,2,3])+4*QS3([3,2,1]) sage: a._vector_() (2, 0, 0, 0, 0, 4) sage: vector(a) (2, 0, 0, 0, 0, 4) sage: a._vector_(RDF) (2.0, 0.0, 0.0, 0.0, 0.0, 4.0)