ApCoCoA-1:Symmetric groups

From ApCoCoAWiki
Revision as of 17:04, 11 March 2014 by StrohmeierB (talk | contribs)

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

Cameron, Peter J., Permutation Groups, London Mathematical Society Student Texts 45, Cambridge University Press, 1999

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 relations (a_i)^2 = 1
   For Index1 := 1 To MEMORY.N-1 Do 
     Append(Relations,[[a[Index1]^2],[1]]);
   EndFor;
   
   // add the relations 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 relations (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);

Example in Symbolic Data Format

 <FREEALGEBRA createdAt="2014-03-11" createdBy="strohmeier">
 	<vars>a1,a2,a3,a4</vars>
 	<basis>
 	<ncpoly>a1^2-1</ncpoly>
 	<ncpoly>a2^2-1</ncpoly>
 	<ncpoly>a3^2-1</ncpoly>
 	<ncpoly>a4^2-1</ncpoly>
 	<ncpoly>a1*a3-a3*a1</ncpoly>
 	<ncpoly>a1*a4-a4*a1</ncpoly>
 	<ncpoly>a2*a4-a4*a2</ncpoly>
 	<ncpoly>(a1*a2)^3-1</ncpoly>
 	<ncpoly>(a2*a3)^3-1</ncpoly>
 	<ncpoly>(a3*a4)^3-1</ncpoly>
 	</basis>
 	<Comment>Symmetric_group_5</Comment>
 </FREEALGEBRA>