CoCalc -- Collaborative Calculation in the Cloud
Sharedsage_worksheets / ADS_Permutation_Groups.sws.sagewsOpen in CoCalc

Worksheets related to Applied Discrete Structures

Permutation Groups using SageMath 

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial -  No Derivative Works 3.0 United States License.

By Cayley's Theorem, all groups can be represented as permutation groups, subgroups of the full permutation group on the group's domain. For finite groups, the set on which the permutations are performed can be simplifed to a set of integers with cardinality equal to the order of the group.

These topics are introduced in Chapter 15 of Applied Discrete Structures.

G=SymmetricGroup(8)
G
Symmetric group of order 8! as a permutation group

Individual elements of GG are represented with cycle notation and the wrapper G( ). The identity is G(()). The output form of these elements drops the outer wrapper.

r=G((1,2,3,4,5,6,7,8))
r
(1,2,3,4,5,6,7,8)
f=G([(2,8),(3,7),(4,6)])
f
(2,8)(3,7)(4,6)

Use an asterisk, *, and integer exponents for operating on elements of a group. Here is the conjugate of f with respect to r. Notice that since GG is nonabelian, rr and its inverse do no cancel out. However, the cycle structure is preserved: f and its conjugate both consist of three disjoint transpositions.

r^-1*f*r
(1,3)(4,8)(5,7)

We can make a similar observation when we conjugate r with respect to f.

f^-1*r*f
(1,8,7,6,5,4,3,2)

Here is a list of powers of r starting with r^0 = () and ending with r^7. Recall that range(8) evaluates to the list of integers from 0 to 7.


map(lambda k:r^k,range(8))
[(), (1,2,3,4,5,6,7,8), (1,3,5,7)(2,4,6,8), (1,4,7,2,5,8,3,6), (1,5)(2,6)(3,7)(4,8), (1,6,3,8,5,2,7,4), (1,7,5,3)(2,8,6,4), (1,8,7,6,5,4,3,2)]

Of course since r is a cycle of length 8, its order is 8 and we get this result:

r^8
()

Other common groups are available, represented with permutations. Here we examine the dihedral group D4D_4. Among the other groups are cyclic groups (CyclicPermutationGroup); dicyclic groups (DiCyclicGroup), which include the quaternion group; and the alternating groups (AlternatingGroup).


D4=DihedralGroup(4)
D4.list()
[(), (1,4)(2,3), (1,2,3,4), (1,3)(2,4), (1,3), (2,4), (1,4,3,2), (1,2)(3,4)]
D4.cayley_table(names='digits')
* 0 1 2 3 4 5 6 7 +---------------- 0| 0 1 2 3 4 5 6 7 1| 1 0 5 7 6 2 4 3 2| 2 4 3 6 7 1 0 5 3| 3 7 6 0 5 4 2 1 4| 4 2 1 5 0 3 7 6 5| 5 6 7 4 3 0 1 2 6| 6 5 0 2 1 7 3 4 7| 7 3 4 1 2 6 5 0

Knowing a set of generators for D4D_4, we could have used PermutationGroup to generate the group. We do that here for D5D_5

D5=PermutationGroup([(1,2,3,4,5),[(1,2),(3,5)]])
D5.cayley_graph().show()

For each subgroup of D5D_5, we print the order of the subgroup followed by a generating set. This shows that all subgroups of D5D_5 are cyclic but D5D_5 itself is not.

for H in D5.subgroups():
    print H.order(),H.gens()
1 [()] 2 [(2,5)(3,4)] 2 [(1,2)(3,5)] 2 [(1,3)(4,5)] 2 [(1,4)(2,3)] 2 [(1,5)(2,4)] 5 [(1,2,3,4,5)] 10 [(2,5)(3,4), (1,2,3,4,5)]

Here are the normal subgroups of D5D_5.

for H in D5.normal_subgroups():
    print H.order(),H.gens()
1 [()] 5 [(1,2,3,4,5)] 10 [(1,2)(3,5), (1,2,3,4,5)]

Here, we see why the subgroup generated by (1,5)(2,4)(1,5)(2,4) isn't normal because we get a different subgroup when whe conjugate it with (1,2,3,4,5)(1,2,3,4,5).

g=D5([(1,5),(2,4)])
H=D5.subgroup([g])
[H.list(),H.conjugate([(1,2,3,4,5)]).list()]
[[(), (1,5)(2,4)], [(), (1,2)(3,5)]]