Math 157: Intro to Mathematical Software

UC San Diego, fall 2018

Created by Zhen Duan on December 5th.

December 6, 2018: Permutation groups in Sage

In this lecture, we are going to discuss permutation groups. We will learn about its basic concepts, and its expressive method and usage in Sage.

Permutations

Before we discuss permutation groups, let's make sure we are clear about permutations. A permutation of a set is a bijection function from this set to this set.

Examples:

1. Let $A$ be a set, where $A=\{0,1,2,3\}$ So, a permutation of set $A$ would be: $1\rightarrow3$ $2\rightarrow4$ $3\rightarrow1$ $4\rightarrow2$ We can see that a permutation is a function or a relation from set $A$ to itself. Let $\sigma$ be a permutation of $A$ Then, we can denote $\sigma$ as: $\sigma=(1\space3)(2\space4)$

2. Let $B$ be a set, where $B=\{0,1,2,3,4,5,6,7,8,9\}$ A permutation of $B$ is: $1\rightarrow2$ $2\rightarrow3$ $3\rightarrow4$ $4\rightarrow1$ $5\rightarrow5$ $6\rightarrow9$ $7\rightarrow7$ $8\rightarrow6$ $9\rightarrow8$ This permutation would be denoted as $(1\space2\space3\space4)(5)(6\space9\space8)(7)$

Permutations in Sage:

Sage uses “disjoint cycle notation” for permutations. Composition occurs left to right, which is not what you might expect and is exactly the reverse of what Judson and many others use. (There are good reasons to support either direction, you just need to be certain you know which one is in play.) There are two ways to write the permutation $σ=(1\space2\space3)(4\space5\space6)$:

• As a text string (include quotes): "(1,2,3) (4,5,6)"

• As a Python list of “tuples”: [(1,2,3), (4,5,6)]

(see details at Sage Documentation v8.4)

In Sage, we use command SymmetricGroup(n) to build symmetric group of all possible permutations of $1$ to $n$.

Also, we can do multiplication of permutation in Sage

We will get the same permutation if it's multipled by identity.

Also, we have sign as one of attributes of permutatin, where

• even permutations have sign of 1

• odd permutations have sign of -1

The order of a permutation is the smallest number $k$ such that $σ^k$ equals the identity permutation.

This line of code shows that the order of $\sigma$ is $3$, which means $\sigma^3$ is equal to the identity, $(1)(2)(3)(4)(5)(6)$, and $3$ is the smallest number that satisfies this equation. We can use permutation multiplication to verify it.

Here we go! The third power of $\sigma$ is $()$, which is the identity!

Permutation Groups

In mathematics, a permutation group is a group $G$ whose elements are permutations of a given set $M$ and whose group operation is the composition of permutations in $G$. The group of all permutations of a set $M$ is the symmetric group of $M$, often written as $Sym(M)$. The term permutation group thus means a subgroup of the symmetric group. If $M = \{1,2,...,n\}$ then, $Sym(M)$, the symmetric group on $n$ letters is usually denoted by $S_n$. (from wikipedia permutation group)

Creating Groups

Following are some popular permutation groups, and commands to build them in Sage.

• SymmetricGroup(n): All $n!$ permutations on $n$ symbols.

• DihedralGroup(n): Symmetries of an $n-gon$. Rotations and flips, $2n$ in total.

• CyclicPermutationGroup(n): Rotations of an $n-gon$ (no flips), $n$ in total.

• AlternatingGroup(n): Alternating group on $n$ symbols having $n!/2$ elements.

• KleinFourGroup(): The non-cyclic group of order $4$.

Abelian

An Abelian group, also known as commutative group, is a group that satisfies the operation on its elements but not depend on the order of element as operands. In sage, we can use a simple command is_ablelian() to check if a group is a Abeliam group.

We can briefly check this.