9. Canonical representative of a double coset

In this and the next section we shall use tensor terminology: the points will be either indices or slots, with the convention that the permutation g acts on slots and its images are indices. That is, 3^g = 7 will now be read "the third slot contains the seventh index".

When including dummy indices in a tensor there are two different kinds of symmetries: apart from those coming from the intrinsic symmetries of the tensor slots (the group S), we have more symmetries due to exchange of names of dummy indices and to the exchange of up/down indices of a pair when a metric is present (we shall call D the group of those new symmetries). Now we need to work with the double coset S.g.D, and again we need to find a canonical representative. It is important to note that this code is prepared to work only with a special type of group D: that needed to canonicalize tensors, and that the S group acts from the left of g while the D group acts from the right of g.
The most general situation we need to handle for the D group is the following:
    - We can have dummies coming from several different vbundles. The D symmetries cannot mix them and so the D group can be reduced as a direct product of smaller groups. Therefore the strong generating sets can be easily constructed independently and then joined together.
    - Inside each vbundle there are two types of "dummies": pair-dummies, each pair having a S_2 or A_2 group or nothing, and then repeated indices, each type of repeated index having a S_n symmetry group, with n being the number of times that a given index is repeated. All pair-dummies in a vbundle can be exchanged. Therefore the D symmetry group for a vbundle is also the product of symmetric and pair-symmetric groups. (Note: sometimes I call "drummies" the combined type of dummies and "repes").
This is an important simplification because we do not need to worry about what is happenning to the generating set of the D group, but only to its base. That is, given the base of the D group we know how to construct an adequate generating set. This is done using the concepts of DummySet and RepeatedSet.

Suppose a tensor with 12 indices where there are 5 pairs of dummies of the same vbundle TM. We encode the situation in a DummySet expression. The first pair {7,11} means that the seventh index in the canonical configuration is an up-index paired with the eleventh index (which is hence a down-index). The number 0 at the end means that there is no metric:

In[287]:=

In[288]:=

Out[288]=

We include a symmetric metric with a 1 at the end (-1 would give an antisymmetric metric):

In[289]:=

In[290]:=

Out[290]=

In[291]:=

In[292]:=

Out[292]=

Now suppose this configuration, where the free indices 2 and 3 are at the third and fifth slots. The canonicalization process (assuming no additional symmetry in the tensor) exchanges the pair {4,5} and changes the pair {10,6} with the pair {8,9}. The pair {11,7} is also exchanged. Compare the timing of the "brute-force" method and that of Portugal's algorithm.

In[293]:=

In[294]:=

In[295]:=

Out[295]=

The base for sorting of permutations is taken from the SGS of group S. If the base does not include all positions of dummies, then it is expanded to cover them all, sorting the missing dummies.

In[296]:=

Out[296]=

The external C code would be even faster.

DummySet                    Head for a set of dummy indices
RepeatedSet                    Head for a set of repeated indices
SGSOfDummySet                Compute SGS for the group associated to a set of dummy indices
DoubleCosetRepresentative    Compute a canonical representative of a double coset

Canonicalization of dummy and repeated indices.

Created by Mathematica  (May 16, 2008)