The meaning of canonicalization. Tensor indices and slots

Before describing the algorithms for "canonicalization" of a permutation we want to introduce what we mean by it. Given some equivalence relation which decomposes a group of permutations into disjoint classes we want to identify uniquely a representative per class. That representative will be called the "canonical representative" of the class, and the process of finding the representative of the class of a given permutation perm will be referred to as the "canonicalization" of perm. The main criterium for canonicalization is that the identity permutation must always be the representative of its class; the secondary criterium will choose the permutation which is "closest" to the identity. This will be done by defining a total ordering among the permutations of the group and choosing the smallest permutation of the class. There are many ways to define that ordering, with the only restriction that the identity must be always the first one in any set containing it. As you can imagine, we will choose an ordering based on the base of an SGS describing the full group.

The special role of the identity poses a small but important problem, because the identity is its own inverse. So, given a sorted set of permutations, are their inverses automatically sorted with respect to the same ordering? The answer is no, and therefore we must always know whether we are sorting the permutations themselves or their inverses. Here we shall follow the convention in the papers by R. Portugal et al, which are the main source for the algorithms implemented here.

In relation to tensors, this amounts to the following: for example, given the collection of sorted indices a,b,c,d,... (renamed as 1,2,3,4,...) Renato says that permutation Cycles[{1,3,2,4}] represents the tensor T^{cdba} (at first slot we find third index; at third slot we find second index; etc.). The opposite view would represent that tensor with the inverse permutation Cycles[{1,4,2,3}] (the first index goes to the fourth slot; the fourth index goes to the second slot; etc).

Created by Mathematica (May 16, 2008) |