10. Canonical permutation

Finally, we give an algorithm that canonicalize simultaneously the free and the dummy/repeated indices. The algorithm always canonicalizes first the free indices and then the dummy/repeated indices.

Portugal's example in paper II. Suppose a tensor with 12 indices whose index-configuration is described by the following permutation:

In[297]:=

perm = Cycles[{1, 12, 11, 4, 5, 6, 8, 9, 10, 7, 3}] ;

In[298]:=

TranslatePerm[perm, Images]

Out[298]=

Images[{12, 2, 1, 5, 6, 8, 3, 9, 10, 7, 4, 11}]

The symmetries of the tensor are described by this GS:

In[299]:=

1) Canonical configuration assuming that all indices are free (empty DummySet/RepeatedSet expressions):

In[300]:=

CanonicalPerm[perm, 12, GS, Range[12], {}, TimeVerbose→True, MathLink→False]

SGS for group of order 1024 computed in 0.660042 secs.

Free algorithm applied in 0.016001 secs.

Out[300]=

Cycles[{2, 5, 3}, {4, 12, 10, 11, 7, 6, 9}]

In[301]:=

TranslatePerm[%, Images]

Out[301]=

Images[{1, 5, 2, 12, 3, 9, 6, 8, 4, 11, 7, 10}]

In[302]:=

CanonicalPerm[perm, 12, GS, Range[12], {}, MathLink→True]

Out[302]=

Images[{1, 5, 2, 12, 3, 9, 6, 8, 4, 11, 7, 10}]

Let us check that this is the smallest permutation in the right coset S.g. We work in Images notation because only then the sorting process is apparent:

In[303]:=

Length[groupS = Dimino[TranslatePerm[GS, {Images, 12}]]]

Out[303]=

1024

In[304]:=

Change at i=2 to  -Images[{2, 12, 1, 5, 6, 8, 3, 9, 10, 7, 4, 11}]

Change at i=18 to Images[{2, 12, 1, 5, 6, 8, 3, 9, 7, 10, 4, 11}]

Change at i=65 to Images[{1, 5, 12, 2, 6, 8, 3, 9, 10, 7, 4, 11}]

Change at i=67 to  -Images[{1, 5, 2, 12, 6, 8, 3, 9, 10, 7, 4, 11}]

Change at i=83 to Images[{1, 5, 2, 12, 6, 8, 3, 9, 7, 10, 4, 11}]

Change at i=195 to  -Images[{1, 5, 2, 12, 3, 9, 6, 8, 10, 7, 4, 11}]

Change at i=211 to Images[{1, 5, 2, 12, 3, 9, 6, 8, 7, 10, 4, 11}]

Change at i=451 to  -Images[{1, 5, 2, 12, 3, 9, 6, 8, 4, 11, 10, 7}]

Change at i=483 to Images[{1, 5, 2, 12, 3, 9, 6, 8, 4, 11, 7, 10}]

Out[304]=

{0.208013 Second, Images[{1, 5, 2, 12, 3, 9, 6, 8, 4, 11, 7, 10}]}

2) Now suppose that indices 1,2 (in the canonical list) are free while the others are contracted as given by the list of pairs or slots {{3,4},{5,6},{7,8},{9,10},{11,12}}. The canonical configuration is (note that this is the result quoted by Portugal et al.):

In[305]:=

CanonicalPerm[perm, 12, GS, {1, 2}, {DummySet[M, {{3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}}, 1]}, TimeVerbose→True, MathLink→False]

SGS for group of order 1024 computed in 0.656041 secs.

Free algorithm applied in 0.008001 secs.

Dummy algorithm applied in 0.128008 secs.

Out[305]=

-Cycles[{2, 3}, {4, 5}, {6, 7, 9}, {8, 11}]

In[306]:=

TranslatePerm[%, {Images, 12}]

Out[306]=

-Images[{1, 3, 2, 5, 4, 7, 9, 11, 6, 10, 8, 12}]

In[307]:=

CanonicalPerm[perm, 12, GS, {1, 2}, {DummySet[M, {{3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}}, 1]}, MathLink→True]

Out[307]=

-Images[{1, 3, 2, 5, 4, 7, 9, 11, 6, 10, 8, 12}]

Note that this permutation is smaller than the one obtained using only the right coset S.g. This is obvious because the double coset S.g.D contains the right coset S.g. Again, we check that this is the right answer by brute force. We construct the SGS of the group D and search for the least of the permutations of the double coset S.g.D. Do not evaluate the Module below because it takes very long (the cell has been made nonevaluatable):

In[308]:=

SGSD = TranslatePerm[SGSOfDummySet[DummySet[M, {{3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}}, 1]], {Images, 12}]

Out[308]=

In[309]:=

Length[groupD = Dimino[SGSD[[2]]]]

Out[309]=

3840

In[310]:=

3) With OrderedBase→False we can get a different result, because we are sorting indices with a different base:

In[311]:=

CanonicalPerm[perm, 12, GS, {1, 2}, {DummySet[M, {{3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}}, 1]}, OrderedBase→False, TimeVerbose→True, MathLink→False]

SGS for group of order 1024 computed in 0.400025 secs.

Free algorithm applied in 0.004001 secs.

Dummy algorithm applied in 0.616038 secs.

Out[311]=

-Cycles[{2, 3}, {4, 6, 10, 8, 12}]

In[312]:=

TranslatePerm[%, {Images, 12}]

Out[312]=

-Images[{1, 3, 2, 6, 5, 10, 7, 12, 9, 8, 11, 4}]

In[313]:=

CanonicalPerm[perm, 12, GS, {1, 2}, {DummySet[M, {{3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}}, 1]}, OrderedBase→False, MathLink→True]

Out[313]=

-Images[{1, 3, 2, 6, 5, 10, 7, 12, 9, 8, 11, 4}]

That result can also be interpreted in terms of an ordering of permutations with respect to a particular base. In this case the dummy indices are sorted differently (again, this cell has been made nonevaluatable):

In[314]:=

CanonicalPerm                Compute a canonical representative given the free and dummy indices of an object
TimeVerbose                    Timings information
xPermVerbose                Detailed information of the internal processes
OrderedBase                    Fill missing points in base with sorted points

Index canonicalization


Created by Mathematica  (May 16, 2008) Valid XHTML 1.1!