Chapter 3: Software and Calculations

The package "Groups.m" can be used to make useful calculations in permutation groups. To start you must load it:

<< Groups.m

Next you have to know how our notation for permutations is implemented. In this package a permutation (in mapping notation) is given by the list of its images with the header M.  For example

(({{1, 2, 3, 4, 5, 6}, {2, 4, 1, 6, 3, 5}}))

is represented by

M[2,4,1,6,3,5]

You can name this permutation:

a = M[2, 4, 1, 6, 3, 5]

If  b  is another permutation then the product  ab  is given by

a.b

For example if

b  =  M[4, 2, 3, 6, 1, 5]

then entering

a . b

To find the inverse of  a , enter

Inverse[a]

A permutation in cycle notation is written as the list of its cycles, which are in turn lists, and is preceded by the header P. For example  (1 2)(3 4 5)  is represented by

P[{1,2},{3,4,5}]

You can take products and inverses using cycle notation just as with mapping notation:

P[{1, 2}, {3, 4, 5}].P[{1, 2, 3, 4, 5}]

Inverse[P[{1, 2}, {3, 4, 5}]]

Output is in standard mathematical cycle notation.

	You can apply these functions to lists of permutations. When you take the product of two lists of permutations, the product of every permutation in the first list with every one in the second will be computed: for example

{a, b} . {a, b}

These functions are useful for checking whether a set of permutations form a group. For example let

G  =  {M[2, 3, 1, 5, 4],  M[4, 1, 2, 5, 3],  M[1, 3, 5, 2, 4],  
        M[2, 1, 3, 4, 5],  M[1, 2, 3, 4, 5]}

Inverse[G]

So

(((({{1, 2, 3, 4, 5}, {2, 3, 1, 5, 4}})))^(-1))=  (({{1, 2, 3, 4, 5}, {3, 1, 2, 5, 4}}))

is not in the set  G  and therefore  G  is not a permutation group.

The function  Group  calculates the permutation group generated by a given set of permutations. All computations take place in (Subscript[S, n]) where n  is the largest number occurring in the cycles in the input. The algorithm used is the one given in exercise 3.8. For example, the permutation group  G = <(1 2 3 4 5), (1 2)(3 5)>  is given by

G =  Group[ P[{1, 2, 3, 4, 5}] ,  P[{1, 2}, {3, 5}] ]

To see a list of the elements in G, you use the function Elements:

Elements[G]

The function Generators will print out the generators of G again:

Generators[G]

The order of the permutation group is given by the function  Order :

Order[G]

We can verify by computation that (1 2) and (1 2 3 4 5 6) generate (Subscript[S, 6]):

Order[ Group[ P[{1, 2}], P[{1, 2, 3, 4, 5, 6}] ] ]

Since  6! = 720  , they  do generate (Subscript[S, 6]).

Let's look for generators of (Subscript[A, 4]), which is also not cyclic. We know that the even permutations of degree 4 are the 3-cycles, the products of 2 disjoint transpositions and the identity. We first try two 3-cycles:

Order[ Group[ P[{1, 2, 3}], P[{2, 3, 4}] ] ]

It is not hard to show that the order of (Subscript[A, n]) is n!/2 (see exercise 3.11). Therefore the two 3-cycles do generate (Subscript[A, 4]). How about a 3-cycle and a product of two disjoint transpositions?

Order[ Group[ P[{1, 2, 3}], P[{1, 2}, {3, 4}] ] ]

These two appear to generate (Subscript[A, 4])as well. Let's see how these calculations extend to (Subscript[A, 5]). We could use two 3-cycles again. But that would not work in (Subscript[A, 6]). So we shall try with a 5-cycle and a 3-cycle:

Order[ Group[ P[{1, 2, 3, 4, 5}],  P[{1, 2, 3}] ] ]

And 60 is the order of (Subscript[A, 5]). We now try 5-cycle and a product of two disjoint transpositions;

Order[Group[P[{1, 2, 3, 4, 5}],  P[{1, 2}, {3, 4}]]]

This works too. Do these calculations extend to (Subscript[A, 6])? Do they generalize to (Subscript[A, n]), for arbitrary n?