Difference between revisions of "ApCoCoA-1:Symmetric groups"
From ApCoCoAWiki
(New page: === <div id="Symmetric_groups">Symmetric groups</div> === ==== Description ==== The elements of the symmetric group S_n are all permutations of ...) |
StrohmeierB (talk | contribs) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | === <div id="Symmetric_groups">[[:ApCoCoA:Symbolic data#Symmetric_groups|Symmetric | + | === <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 ==== | ||
| − | + | Cameron, Peter J., Permutation Groups, London Mathematical Society Student Texts 45, Cambridge University Press, 1999 | |
| − | |||
| − | Cameron, Peter J. | ||
==== Computation ==== | ==== Computation ==== | ||
/*Use the ApCoCoA package ncpoly.*/ | /*Use the ApCoCoA package ncpoly.*/ | ||
| − | // Number of | + | // 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 | + | // 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 | + | // 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 | + | // 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; | |
EndDefine; | EndDefine; | ||
Relations:=CreateRelationsSymmetric(); | 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> | ||
Latest revision as of 20:58, 22 April 2014
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>
