Permutations and permutation groups

Next topic: Programming with Redberry

Permutations

Permutations play a very important role in tensor algebra. For example, symmetries of tensors are specified in terms of permutations of indices. Besides, permutations and permutation groups are used in many routines and algorithms with tensors (e.g. Symmetrize transformation or Mappings of indices are uses algorithms with permutation groups).

A single Permutation in Redberry can be inputted using .p property both in cycle and one-line notation: 

//permutation in one-line notation
def p1 = [0, 2, 5, 6, 7, 1, 3, 4].p
//same permutation in cycle notation
def p2 = [[1, 2, 5], [4, 7], [3, 6]].p
assert p1 == p2
Permutation can represent both permutational symmetry and antisymmetry. In order to convert symmetry to antisymmetry and vice versa, one can use minus: 
//symmetry
def sym = [[0, 2, 5], [6, 7]].p
//antisymmetry
def asym = -sym

One can use Permutation to permute a list of objects via >> operator: 

def p = [[0, 1], [2, 3]].p
println p >> [10, 9, 8, 7]

   > [9, 10, 7, 8]

println p >> ['a', 'b', 'c', 'd', 'e']

   > [b, a, d, c, e]

In order to make a composition of permutations one can simply use multiplication: 

def perm1 = [[0, 5, 4], [1, 3]].p
def perm2 = [[0, 1], [2, 3]].p
println perm1*perm2

   > +[[0, 5, 4, 1, 2, 3]]

println perm2*perm1

   > +[[0, 3, 2, 1, 5, 4]]
The result of applying composition perm1*perm2 is equivalent to applying perm2 then perm1: 
def list = ['a', 'b', 'c', 'd', 'e', 'f']
assert (perm1 * perm2) >> list == perm1 >> (perm2 >> list)
assert (perm2 * perm1) >> list == perm2 >> (perm1 >> list)

See Permutation for further details.

Permutation groups

In order to specify symmetries of tensors one should specify a generating set of permutations. Redberry uses generating set to create a PermutationGroup which is used in all further routines. Redberry can handle permutation groups with degree in the range of a few thousand, hence working with groups with more than $10^{1000}$ elements.

In order to create PermutationGroup directly, one can do: 

def gen1 = [[1, 4, 5], [3, 6]].p
def gen2 = -[[2, 3], [1, 5]].p
def group = Group(gen1, gen2)
Giving a PermutationGroup, one can e.g. check its order (i.e. number of all elements in group) or enumerate all its element: 
//print number of all group elements
println group.order()

   > 36

//enumerate all elements
def all = []
for (def perm in group)
    all << perm
//find all antisymmetries
def assyms = group.findAll { perm -> perm.antisymmetry() }
println assyms

   > [-[[4,5]], -[[3,6],[4,5]], -[[2,3],[4,5]], -[[2,6,3],[4,5]], -[[2,6],[4,5]],
          -[[2,3,6],[4,5]], -[[1,4],[3,6]], -[[1,4]], -[[1,4],[2,3,6]], -[[1,4],[2,6]],
          -[[1,4],[2,6,3]], -[[1,4],[2,3]], -[[1,5],[2,3]], -[[1,5],[2,6,3]], -[[1,5]],
          -[[1,5],[3,6]], -[[1,5],[2,3,6]], -[[1,5],[2,6]]]

PermutationGroup provides a wide range of specialized methods including membership testing, coset enumeration, searching for centralizers, stabilizers, etc. For example, to check whether some permutation belongs to a group one can do 

def perm1 = [[1, 2, 5]].p
println group.membershipTest(perm1)

   > false

def perm2 = [[1, 4, 5]].p
println group.membershipTest(perm2)

   > true
To find a subgroup that stabilizes a set of points (i.e. map set on itself “as a whole”) one can do: 
println group.setwiseStabilizer(1, 3, 5)

   > Group( +[[2, 6]], -[[1, 5]] )

See PermutationGroup for further details.

See also