# Chapter 3: Software and Calculations # # The package "groups" can be used to make useful calculations in # permutation groups. To start you must load it: # > read groups; # # 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 enclosed in square brackets. For # example # [1 2 3 4 5 6] [ ] [2 4 1 6 3 5] # # is represented by > [2, 4, 1, 6, 3, 5]# # You can name this permutation: # > a := [2, 4, 1, 6, 3, 5]; a := [2, 4, 1, 6, 3, 5] # # If b is another permutation then the product ab is given by # # a &* b # For example if # > b := [4, 2, 3, 6, 1, 5]; b := [4, 2, 3, 6, 1, 5] # # then entering # > a&*b; [6, 4, 1, 5, 2, 3] # # To find the inverse of a , enter # > Inverse(a); [3, 1, 5, 2, 6, 4] # # A permutation in cycle notation is written as the list of its cycles, # which are in turn lists. For example (1 2)(3 4 5) is represented by # # [[1 2], [3 4 5]] # # You can take products and inverses using cycle notation just as with # mapping notation: # > [[1, 2],[3, 4, 5]] &* [[1, 2, 3, 4, 5]]; [[2, 4, 3, 5]] > Inverse( [[1, 2],[3, 4, 5]] ); [[1, 2], [3, 5, 4]] # # 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}; {[4, 6, 2, 5, 1, 3], [2, 6, 4, 5, 3, 1], [6, 2, 3, 5, 4, 1], [6, 4, 1, 5, 2, 3]} # # These functions are useful for checking whether a set of permutations # form a group. For example let # > G := { [2, 3, 1, 5, 4], [4, 1, 2, 5, 3], [1, 3, 5, 2, 4], [2, 1, 3, 4, > 5], > [1, 2, 3, 4, 5] }; G := {[1, 2, 3, 4, 5], [1, 3, 5, 2, 4], [4, 1, 2, 5, 3], [2, 1, 3, 4, 5], [2, 3, 1, 5, 4]} > Inverse(G); {[1, 4, 2, 5, 3], [2, 3, 5, 1, 4], [1, 2, 3, 4, 5], [3, 1, 2, 5, 4], [2, 1, 3, 4, 5]} # # So the inverse of [2, 3, 1, 5, 4] , which is [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 a 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( [[1, 2, 3, 4, 5]] , [[1, 2],[3, 5]] ); G := [[[[1, 2, 3, 4, 5]], [[1, 2], [3, 5]]], {[], [[1, 2], [3, 5]], [[1, 5, 4, 3, 2]], [[1, 3, 5, 2, 4]], [[1, 4, 2, 5, 3]], [[1, 5], [2, 4]], [[1, 4], [2, 3]], [[2, 5], [3, 4]], [[1, 3], [4, 5]], [[1, 2, 3, 4, 5]]}] # # The result consists of the two generators followed by the list of the # elements in the group G. If the group # is a bit larger , it is a good idea to use a colon ":" at the end of # the input statement so that you do not get pages of output. To just # see a list of the elements in G, you use the function Elements: # > Elements(G); {[], [[1, 2], [3, 5]], [[1, 5, 4, 3, 2]], [[1, 3, 5, 2, 4]], [[1, 4, 2, 5, 3]], [[1, 5], [2, 4]], [[1, 4], [2, 3]], [[2, 5], [3, 4]], [[1, 3], [4, 5]], [[1, 2, 3, 4, 5]]} # # The function Generators will print out the generators of G again: # > Generators(G); [[[1, 2, 3, 4, 5]], [[1, 2], [3, 5]]] # # The order of the permutation group is given by the function Ord : # > Ord(G); 10 # # We can verify by computation that (1 2) and (1 2 3 4 5 6) generate S6: # > Ord( Group( [[1, 2]], [[1, 2, 3, 4, 5, 6]] ) ); 720 # # Since 6! = 720 , they do generate S6. # # Let's look for generators of A4, 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: # > Ord( Group( [[1, 2, 3]], [[2, 3, 4]] ) ); 12 # # It is not hard to show that the order of An is n!/2 (see exercise # 3.11). Therefore the two 3-cycles do generate a. How about a 3-cycle # and a product of two disjoint transpositions? # > Ord( Group( [[1, 2, 3]], [[1,2],[3, 4]] ) ); 12 # # These two appear to generate A4 as well. Let's see how these # calculations extend to A5 . We could use two 3-cycles again. But that # would not work in A6 . So we shall try with a 5-cycle and a 3-cycle: # > Ord( Group( [[1, 2, 3, 4, 5]], [[1, 2, 3]] ) ); 60 # # And 60 is the order of A5 . We now try 5-cycle and a product of two # disjoint transpositions; # > Ord( Group( [[1, 2, 3, 4, 5]], [[1,2],[3, 4]] ) ); 60 # # This works too. Do these calculations extend to A6 ? Do they # generalize to An , for arbitrary n? #