The MuPAD-Combinat Handbook

We start with an example of algebra with several bases. Let

be a finite set, and consider the free module

over the subsets of

. It is endowed with an algebra structure by extending the intersection operation by linearity. Implementing this algebra in MuPAD requires some helper tools; we put them inside a dummy domain called SubsetsSpaceTools to avoid polluting the global name space:

We now implement the module

with elements expanded on the fundamental basis denoted by

. There are two parameters: the set S and, as usual, the coefficient ring Ring. Note the use of combinat::subClass to define the combinatorial class of the subsets of S:

domain SubsetsSpaceTools::Fundamental(S, Ring)

category Cat::AlgebraWithBasis(Ring);

inherits Dom::FreeModule(Ring,

combinat::subClass(combinat::subsets,

Parameters = S));

info_str := "The subset space on the fundamental basis";

basisName := hold(F);

mult2Basis :=

proc(s1: dom::basisIndices, s2: dom::basisIndices)

begin

dom::term(s1 intersect s2);

end_proc;

end_domain:

Let us just recall that, in a free module, the entry dom::basisIndices contains the combinatorial class that indexes the bases of the module. Here, this is a shortcut for the combinatorial class:

The module

has two other bases

and

that we describe below. We just declare them to MuPAD, without implementing the product:

domain SubsetsSpaceTools::In(S, Ring)

category Cat::AlgebraWithBasis(Ring);

inherits Dom::FreeModule(Ring,

combinat::subClass(combinat::subsets,

Parameters = S));

info_str := "The subset space on the 'In' basis";

basisName := hold(In);

end_domain:

domain SubsetsSpaceTools::Out(S, Ring)

category Cat::AlgebraWithBasis(Ring);

inherits Dom::FreeModule(Ring,

combinat::subClass(combinat::subsets,

Parameters = S));

info_str := "The subset space on the 'Out' basis";

basisName := hold(Out);

end_domain:

The module

is endowed with a scalar product which makes the fundamental basis

orthonormal. The

basis is then defined by the rule

and the

basis is the dual basis of

with respect to the scalar product. This information is sufficient to define mathematically all the bases change in between

, and

by transposing and inverting matrices. The implementation follows the same compact line:

domain SubsetsSpace(S : DOM_SET,

Ring = Dom::Rational : DOM_DOMAIN)

category Cat::ModuleWithSeveralBases(Ring);

inherits Dom::BaseDomain;

info_str := "The subsets space on various bases";

Fundamental := SubsetsSpaceTools::Fundamental(S, Ring);

F := dom::Fundamental; // a shortcut

In := SubsetsSpaceTools::In(S, Ring);

Out := SubsetsSpaceTools::Out(S, Ring);

// When possible, define automatically basis changes by

// transposition or inversion of matrices.

autoDefineBasisChanges := TRUE;

basisChangesBasis := table(

(dom::In, dom::F) =

proc(set : dom::In::basisIndices) : dom::F

local xSet;

begin

dom::F::plus(dom::F::term(xSet) $

xSet in combinat::subsets::list(set));

end_proc);

dual := dom; // The dual of this space.

// The pairs of dual bases.

// The pair [dom::Out, dom::In] will be automatically declared.

dualBasesPairs := {[dom::F, dom::F], [dom::In, dom::Out]};

end_domain:

The crucial line of the preceding code is the declaration of SubsetsSpace as a Cat::ModuleWithSeveralBases. This category provides helper tools for implementing modules which are represented on several modules. We just need to supply the basis changes from In to F (see basisChangesBasis) and to declare which bases are in duality (see dual and basisChangesBasis). The system then provides default implementations for the scalar products and the other changes of bases (see autoDefineBasisChanges), and provides the standard free module entries testtype and coeffRing together with the set of bases bases.

We define the free module spanned by the subsets of

and build some of its elements:

The required matrix inversions are computed only once and remembered, so that later basis changes are considerably faster, at some memory cost.

Finally we check that algebra products and scalar products are handled correctly:

Products of Out elements are actually computed and returned in the F basis. As usual, an explicit conversion can be used to force the result back in the Out basis: