1. Defining new combinatorial algebras

1.1. Combinatorial algebras on a given basis

We now turn to the central feature of the MuPAD-Combinat package: the ability to easily implement new combinatorial algebras. We start by the free associative algebra over the rational numbers generated by non commutative letters . Its basis is indexed by words, and the product of two basis elements is obtained by concatenating the corresponding words:

We will explain the bits of this definition in a minute after a few examples of use. Let us define two elements of the free algebra:

The B just stands for the name of the basis. We can compute linear combinations and products of x and y:

Here is a more complicated expression:

Note how the 3 in the expression is automatically converted into an element of the domain; declaring that FreeAlgebra was an algebra (with a unit) automatically defined the natural embedding of the coefficient ring into it.

We turn to the explanation of the implementation of FreeAlgebra above. The line

states that we are defining a new domain called FreeAlgebra (a new class in the usual object oriented terminology).

lets FreeAlgebra inherit its implementation from the free module over the rationals (Dom::Rational) with basis indexed by words (combinat::words).

states that FreeAlgebra is actually an algebra with a distinguished basis; this allows one, in particular, to define the multiplication by linearity on the basis.

defines that the unit of FreeAlgebra is the empty word (dom refers to the domain being defined, and dom::term is a constructor that takes an element of the basis, and returns it as an element of the domain). Finally,

states that two elements of the basis are multiplied by concatenating them, and making an element of the domain with the result (@ denotes the composition of functions). That's it.

Let us define the free commutative algebra on the letters :

       Note that we cheated a little bit: we declared that the basis of FreeCommutativeAlgebra consisted of words, whereas it really consists of words up to permutation of its letters: B([a,b]) and B([b,a]) represent the same element of the algebra. A careful implementation should define the combinatorial class of words up to permutation, and use it as the basis of FreeCommutativeAlgebra.

To enforce the uniqueness of the representation, we straighten the words in the basis by sorting them. This is the job of the straightenBasis constructor.

The product of two words is then defined by concatenating them and straightening the result:

If efficiency was at a premium, instead of sorting the concatenation of the two lists, we could have used the MuPAD function listlib::merge which merges sorted lists.

Note that two elements of FreeCommutativeAlgebra and of FreeAlgebra may happen to be printed out the same way:

and even share the exact same internal representation:

However, they are not equal, because they are not in the same domain:

So, even if they share the same name of basis, there is no risk of confusion; for example we are not allowed to multiply them together:

Of course, this is still confusing for the user. He or she may always customize the basis names (as many other things) at any time should he or she wish to do so:

   Here, T stands for “Tensor algebra”, while S stands for “Symmetric algebra”. The hold is there for safety, in case one of the identifiers T or S is assigned a value.

We can define the natural evaluation morphism from FreeAlgebra to FreeCommutativeAlgebra by linearity on the words; a word itself is simply sorted, and converted into an element of FreeCommutativeAlgebra:  

Let us apply this morphism to the sum of two words which only differ by a permutation:

The evaluation morphism is actually quite canonical, so it can make sense to declare it as a conversion to the system. This can be achieved with the operators::overloaded::declareConversion function:

Here, the conversion has been declared as implicit. If an expression mixes elements of FreeAlgebra and FreeCommutativeAlgebra, the former are automatically converted into FreeCommutativeAlgebra:

Of course, such a feature is questionable. Depending on the context, it can prove very practical, or on the contrary dangerous. The user is the only judge, and she or he can restrict the scope of this conversion by using the Explicit option. In this case, the conversion will only be applied if requested explicitly by convert or by new:

Typically, for symmetric functions, we only provided explicit conversions to construct symmetric functions from partitions because those conversions are not canonical at all: the Schur function s[3,2,1] obtained by converting the partition [3,2,1] has nothing to do with the elementary function e[3,2,1]. We refer to the design notes and to the documentation of the operators::overloaded library for details on the mechanism we use for defining automatic conversions and overloaded operators and functions. Note that it is not (yet) completely possible to declare new conversions as above when the target domain of the conversion is one of the predefined domains of the MuPAD library.

1.2. Combinatorial algebras with several representations

As usual, for shortening the notations, we export the library combinat:

To continue our exploration, we implement variations on the two previous domains, where we assume that the algebra generators are indexed by 1,2,.... The basis elements of the free algebra and of the free commutative algebra are now respectively indexed by compositions and partitions.

Let us analyze the differences with our previous implementation of the free algebras. First, we chose an indexed notation for the basis elements, as this notation is more compact and quite conventional in other systems. This is the purpose of the line exprTerm := dom::exprTermIndex: the method exprTerm of the domain is called to convert a term into an expression, as well as to print a term if there is no printTerm method; dom::exprTermIndex is a possible implementation of exprTerm, inherited from the category, which gives indexed notations. The other difference is that, following the usual convention, the integers in the partitions are sorted decreasingly. Here, this is suboptimally achieved by reverting the list after sorting it in the SF::straightenBasis method.

A disadvantage of this implementation of SF is that elements with many repetitions are not represented compactly:

One might prefer to use another basis for SF, where the element above would be represented as the first generator to the power . This can be done via the usual exponent notation for partitions. The basis of the algebra now consists of integer vectors. The product of two elements is simply obtained by adding up the vectors part by part, which can conveniently be implemented using the zipMuPAD function.

Let us do some computations:

This notation could be confusing, so we override it:

   As is, the elements of this algebra are not uniquely represented. For example, the first generator of the algebra can be represented by any of [1], [1,0], [1,0,0], ...:

We leave it up as an exercise for the reader to fix this bug by implementing a straightenBasis method which strips out the trailing zeroes of the basis elements.

Of course, SF and SFExp really represent the same algebra; only the internal data representation changes. So, we provide as conversions the reciprocal isomorphisms obtained by extending by linearity the bijections combinat::partitions::fromExp and combinat::partitions::toExp:

Here is a simple conversion:

Let us check on an example that the conversions are indeed morphisms:

We can write expressions that mix elements of both domains, and let the system find a way to convert them appropriately:

A priori, the representation of the result cannot be predicted; it depends on how the overloading mechanism chooses to resolve the conversions. If the user prefers one of the representations, she or he can take over the control at any level of the expression by forcing proper conversions:

The implicit conversions are automatically applied transitively. As a consequence, we have without further work a conversion from NCSF to SF:

Another consequence is that, when there are different representations for an algebra (say the symmetric functions expressed on any of the p, e, m, h, or s basis), it is sufficient a priori to implement conversions to be able to get all the possible conversions. In practice, we usually implement conversions, so that no conversion takes more than two steps. Of course it is still possible to implement some extra direct conversions for improved efficiency; when there are several ways to convert an element from one domain to another, the system always uses one of the shortest ones.

As usual, for shortening the notations, we export the library combinat:

As a more advanced example, we demonstrate some computations in the so-called -shuffle algebra. This algebra has the sets of words for basis. The product is defined recursively by

TODO: Math "import_TeX("\epsilon \shuffle w = w \shuffle \epsilon  = w")"

TODO: Math "ua * import_TeX("\shuffle vb := (ua \shuffle v) b + q^{|vb|} (u \shuffle vb) a")" .

where TODO: Math "import_TeX("\epsilon")" is the empty word, are words, letters and denotes the length of the word .

Note: in a free module, the entry dom::basisIndices contains the combinatorial class that indexes the basis of the module, and the function mapterms(elts, f, ...) applies f on each term of the element elts of the module. Thus, if elts writes , the call

returns the MuPAD representation of .

Let us declare this algebra over the field of expressions:

and try some computations:

Obviously, this is a non commutative algebra. One can use any object as letter:

Moreover, the automatic conversion from the base field allows one to write complicated expression such as:

Finally note that this implementation is not very efficient. In particular, at each stage of the recursion in the expression:

the system has to solve the overloading, i.e., to decide the meaning of + and *. It is better to decide this once and for all, i.e., to replace + by dom::plus2, and * by dom::multcoeffs.    The emerging expression is less readable, but its processing is considerably faster:

Moreover, a non-recursive implementation of the -shuffle is likely to be more efficient.