Group Theory Algorithms

Coset Representatives	Setwise Stabilizer
Centralizer

This tutorial introduces some basic algorithms for computing with finite permutation groups, other than those introduced in "Permutation Groups".

Coset Representatives

A subgroup

of a group

partitions the list of elements of

into disjoint subsets, called cosets of

, such that

is one of them and the rest are of the form

for some element

, with ⊙ denoting the product law. A way of identifying the coset is by selecting a representative from each coset, for example the smallest element in the coset.

RightCosetRepresentative

compute smallest group element in a coset

Computation of a canonical coset representative.

Take two permutations and the group generated by them:

In[1]:=1

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-8bxqkz

Out[2]=2

This group partitions

into 210 disjoint cosets:

In[3]:=3

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-ievrp

Out[3]=3

Given any other permutation, it is possible to list the elements of its associated right coset:

In[4]:=4

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-1yulg

In[5]:=5

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-0uueab

Out[5]=5

The canonical representative of the right coset is taken to be the least permutation in the order defined by images:

In[6]:=6

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-wrjm6z

Out[6]=6

Construct the canonical representative directly, without listing the permutations in the coset:

In[7]:=7

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-gdh7cv

Out[7]=7

Check that this also agrees with the minimum-rank permutation (in the group

) in the coset:

In[8]:=8

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-636cov

In[9]:=9

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-gjeyd5

Out[9]=9

In[10]:=10

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-wmgn67

Out[10]=10

In[11]:=11

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-bn39j6

Out[11]=11

For bigger groups, it is not possible to list or rank all permutations, but you can still use RightCosetRepresentative.

Take two permutations and construct the group generated by them:

In[12]:=12

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-0tne4s

This is the number of cosets induced by this group on

In[13]:=13

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-xd9iev

Out[13]=13

For any permutation belonging to the group itself, the canonical representative is always the identity permutation:

In[14]:=14

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-wy2lgk

Out[14]=14

In[15]:=15

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-m174dj

Out[15]=15

Now take some random permutation in

In[16]:=16

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-5d2mhc

Out[16]=16

This is its coset representative:

In[17]:=17

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-4x9x16

Out[17]=17

Check that the representative indeed belongs to the same coset. This will be the case if there exists a permutation h in the original group such that permPermutationProduct[h,rep]:

In[18]:=18

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-echn38

Out[18]=18

In[19]:=19

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-4fnq1a

Out[19]=19

Centralizer

The centralizer

of an element

in a group

is the subgroup of elements of

that commute with

GroupCentralizer

compute the centralizer subgroup of some group element

Computation of centralizers.

Take the group:

In[20]:=20

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-w5mqi

Out[21]=21

Choose a permutation:

In[22]:=22

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-4hr5wq

This is its centralizer in the group:

In[23]:=23

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-k0b4c9

Out[23]=23

In[24]:=24

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-p4x92g

Out[24]=24

Check the result by direct computation of all commutators in the group:

In[25]:=25

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-xmvnn2

In[26]:=26

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-pfdngt

In[27]:=27

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-o0spt4

Out[27]=27

In[28]:=28

✖

https://wolfram.com/xid/0bpqql8h3uhy0z-ujainx

Out[28]=28

Setwise Stabilizer

The (pointwise) stabilizer of a group

is the subgroup of elements of

fixing a set of one or several points of the domain of action. This concept can be extended to the setwise stabilizer, which is the subgroup of elements either fixing those points or moving them among themselves.