Differences

This shows you the differences between two versions of the page.

Link to this comparison view

documentation:guide:permutations_and_permutation_groups [2015/11/21 12:33] (current)
Line 1: Line 1:
 +====== Permutations and permutation groups ======
 +<​html>​
 +<div class="​text-right"​ style="​font-size:​ 15px; ">
 +</​html>​
 +Next topic: [[documentation:​guide:​programming_with_redberry]]
 +<​html>​
 +<span class="​glyphicon glyphicon-arrow-right"></​span>​
 +</​div>​
 +</​html>​
 +
 +----
 +
 +====Permutations====
 +
 +Permutations play a very important role in tensor algebra. For example, [[Symmetries of tensors|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. [[documentation:​ref:​Symmetrize]] transformation or [[mappings of indices]] are uses algorithms with  permutation groups). ​
 +
 +A single [[documentation:​ref:​Permutation]] in Redberry can be inputted using ''​.p''​ property both in cycle and one-line notation:
 +<sxh groovy; gutter: false>
 +//​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
 +</​sxh>​
 +[[documentation:​ref:​Permutation]] can represent both permutational symmetry and antisymmetry. In order to convert symmetry to antisymmetry and vice versa, one can use minus:
 +<sxh groovy; gutter: false>
 +//symmetry
 +def sym = [[0, 2, 5], [6, 7]].p
 +//​antisymmetry
 +def asym = -sym
 +</​sxh>​
 +
 +One can use [[documentation:​ref:​Permutation]] to permute a list of objects via ''​%%>>​%%''​ operator:
 +<sxh groovy; gutter: true>
 +def p = [[0, 1], [2, 3]].p
 +println p >> [10, 9, 8, 7]
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > [9, 10, 7, 8]
 +</​sxh>​
 +<sxh groovy; gutter: true; first-line: 3>
 +println p >> ['​a',​ '​b',​ '​c',​ '​d',​ '​e'​]
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > [b, a, d, c, e]
 +</​sxh>​
 +
 +In order to make a composition of permutations one can simply use multiplication:​
 +<sxh groovy; gutter: true>
 +def perm1 = [[0, 5, 4], [1, 3]].p
 +def perm2 = [[0, 1], [2, 3]].p
 +println perm1*perm2
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > +[[0, 5, 4, 1, 2, 3]]
 +</​sxh>​
 +<sxh groovy; gutter: true; first-line: 4>
 +println perm2*perm1
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > +[[0, 3, 2, 1, 5, 4]]
 +</​sxh>​
 +The result of applying composition ''​perm1*perm2''​ is equivalent to applying ''​perm2''​ then ''​perm1'':​
 +<sxh groovy; gutter: true; first-line: 5>
 +def list = ['​a',​ '​b',​ '​c',​ '​d',​ '​e',​ '​f'​]
 +assert (perm1 * perm2) >> list == perm1 >> (perm2 >> list)
 +assert (perm2 * perm1) >> list == perm2 >> (perm1 >> list)
 +</​sxh>​
 +
 +See [[documentation:​ref:​Permutation]] for further details.
 +====Permutation groups====
 +In order to [[Symmetries of tensors|specify symmetries of tensors]] one should specify a generating set of permutations. Redberry uses generating set to create a [[documentation:​ref:​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 [[documentation:​ref:​PermutationGroup]] directly, one can do:
 +<sxh groovy; gutter: true>
 +def gen1 = [[1, 4, 5], [3, 6]].p
 +def gen2 = -[[2, 3], [1, 5]].p
 +def group = Group(gen1, gen2)
 +</​sxh>​
 +Giving a [[documentation:​ref:​PermutationGroup]],​ one can e.g. check its order (i.e. number of all elements in group) or enumerate all its element:
 +<sxh groovy; gutter: true; first-line: 4>
 +//print number of all group elements
 +println group.order()
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > 36
 +</​sxh>​
 +<sxh groovy; gutter: true; first-line: 6>
 +//enumerate all elements
 +def all = []
 +for (def perm in group)
 +    all << perm
 +//find all antisymmetries
 +def assyms = group.findAll { perm -> perm.antisymmetry() }
 +println assyms
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > [-[[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]]]
 +</​sxh>​
 +
 +
 +[[documentation:​ref:​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
 +<sxh groovy; gutter: true; first-line: 13>
 +def perm1 = [[1, 2, 5]].p
 +println group.membershipTest(perm1)
 +</​sxh>​
 +<sxh plain; gutter: false>
 +   > false
 +</​sxh>​
 +<sxh groovy; gutter: true; first-line: 15>
 +def perm2 = [[1, 4, 5]].p
 +println group.membershipTest(perm2)
 +</​sxh> ​
 +<sxh plain; gutter: false>
 +   > true
 +</​sxh>​
 +To find a subgroup that stabilizes a set of points (i.e. map set on itself "as a whole"​) one can do:
 +<sxh groovy; gutter: true; first-line: 17>
 +println group.setwiseStabilizer(1,​ 3, 5)
 +</​sxh> ​
 +<sxh plain; gutter: false>
 +   > Group( +[[2, 6]], -[[1, 5]] )
 +</​sxh>​
 +
 +See [[documentation:​ref:​PermutationGroup]] ​ for further details.
 +
 +====See also====
 +  * Related guides: [[documentation:​guide:​symmetries_of_tensors]]
 +  * Related reference material: [[documentation:​ref:​permutation]],​ [[documentation:​ref:​permutationgroup]]