ApCoCoA-1:Symmetric groups

From ApCoCoAWiki
Revision as of 06:49, 10 September 2013 by F lorenz (talk | contribs) (New page: === <div id="Symmetric_groups">Symmetric groups</div> === ==== Description ==== The elements of the symmetric group S_n are all permutations of ...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Description

The elements of the symmetric group S_n are all permutations of a finite set of n symbols. The group operation can be seen as a bijective function from the set of symbols to itself. The order of the group is n! since there are n! different permutations. An efficient finite group representation is given by:

 S_n = <a_{1},..,a_{n-1} | a_{i}^2 = 1, a_{i}a_{j} = a_{j}a_{i} for j != i +/- 1, (a_{i}a_{i+1})^3 = 1>

Reference

Kerber, Adalbert (1971), Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240 240, Berlin, New York

Cameron, Peter J. (1999), Permutation Groups, London Mathematical Society Student Texts 45

Computation

 /*Use the ApCoCoA package ncpoly.*/
 
 // Number of Symmetric group
 MEMORY.N:=5;
 
 Use ZZ/(2)[a[1..(MEMORY.N-1)]];
 NC.SetOrdering("LLEX");
 Define CreateRelationsSymmetric()
   Relations:=[];
   // add the relation (a_i)^2 = 1
   For Index1 := 1 To MEMORY.N-1 Do 
     Append(Relations,[[a[Index1]^2],[1]]);
   EndFor;
 
   // add the relation a_{i}a_{j} = a_{j}a_{i} for j != i +/- 1
   For Index2 := 1 To MEMORY.N-1 Do
     For Index3 := Index2 + 2 To MEMORY.N-1 Do
       Append(Relations,[[a[Index2],a[Index3]],[a[Index3],a[Index2]]]);
     EndFor;
   EndFor;
 
   // add the relation (a_{i}a_{i+1})^3 = 1
   For Index4 := 1 To MEMORY.N-2 Do
     Append(Relations,[[a[Index4],a[Index4+1],a[Index4],a[Index4+1],a[Index4],a[Index4+1]],[1]]);
   EndFor;
   Return Relations;
 EndDefine;
 
 Relations:=CreateRelationsSymmetric();
 GB:=NC.GB(Relations);