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 $G$ 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 $G$ is nonabelian, $r$ 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 $D_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 $D_4$, we could have used PermutationGroup to generate the group. We do that here for $D_5$

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

D5.cayley_graph().show()


For each subgroup of $D_5$, we print the order of the subgroup followed by a generating set. This shows that all subgroups of $D_5$ are cyclic but $D_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 $D_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)$ isn't normal because we get a different subgroup when whe conjugate it with $(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)]]