ApCoCoA-1:Symmetric groups: Difference between revisions

From ApCoCoAWiki
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 ...
 
F lorenz (talk | contribs)
No edit summary
Line 1: Line 1:
=== <div id="Symmetric_groups">[[:ApCoCoA:Symbolic data#Symmetric_groups|Symmetric groups]]</div> ===
=== <div id="Symmetric_groups">[[:ApCoCoA:Symbolic data#Symmetric_groups|Symmetric groups]]</div> ===
==== Description ====
==== Description ====
The elements of the symmetric group S_n are all permutations of a finite set of n symbols. The group operation can be
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:
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>
   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 ====  
==== Reference ====  
Kerber, Adalbert (1971), Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240 240, Berlin, New York
Cameron, Peter J., Permutation Groups, London Mathematical Society Student Texts 45, Cambridge University Press, 1999
 
Cameron, Peter J. (1999), Permutation Groups, London Mathematical Society Student Texts 45


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

Revision as of 06:56, 10 September 2013

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);