CoCalc -- presentation-xil545.ipynb

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Project: Xiaojie Liu - Math 157: Intro to Mathematical Software

Path: assignments/2018-03-16/presentation-xil545.ipynb

Views: ⁹²

Kernel: SageMath 8.1

Permutation Group

Definition

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 (which are thought of as bijective functions from the set M to itself). 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.

I know it is hard to understand what permutation group is from the boring definition of it, but you are getting to know it in the rest of note

There is a lot of intersting things about permutation group. But we only have 20 minites, therefore I just put some basic knowledge about the permutation group

First, we need to know how permutation look like

In [3]:

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

Out[3]:

Permutation Group with generators [(1,2,3)(4,5)]

Permutation Group Element

Check if an element is in this permutation group

In [4]:

g = G.random_element()
g

Out[4]:

(1,3,2)(4,5)

In [5]:

g in G

Out[5]:

True

In [6]:

h = (2,3)
h in G

Out[6]:

False

In [7]:

p = PermutationGroupElement([(1,2),(3,4,5)])

In [8]:

from sage.groups.perm_gps.permgroup_element import is_PermutationGroupElement
is_PermutationGroupElement(p)

Out[8]:

True

We also can see the the order of a group, which is the number of elements in the group

The number of order of a group n is the smallest positive integer n such that G^n = identity permutation group

http://ksuweb.kennesaw.edu/~plaval/math4361/permutations

In [9]:

G = PermutationGroup(['(1,2,3)(4,5)'])
n = G.order()
n

Out[9]:

6

In [10]:

#X.gen(i) means the i-th generator of self
g = G.gen(0)
g

Out[10]:

(1,2,3)(4,5)

In [11]:

G.gen()

Out[11]:

(1,2,3)(4,5)

In [12]:

G = PermutationGroup([[(1,2,3)],[(2,3,4)]])
G.gen(1)

Out[12]:

(1,2,3)

Besides, we can see the orbit of the integer n under this group element, as a sorted list

In [13]:

G = PermutationGroup(['(1,2,3)(4,5)'])
g = G.gen(0)

In [14]:

g.orbit(4)

Out[14]:

[4, 5]

In [15]:

g.orbit(3)

Out[15]:

[1, 2, 3]

In [16]:

g.orbit(10)

Out[16]:

[10]

And the sign of self, which is (−1)s, where s is the number of swaps

In [17]:

g.sign()

Out[17]:

-1

Let's do some calculation

Multiplication of two permutation groups

In [18]:

H = PermutationGroup([(3,5,8,9)])
h = H.gen(0)
h

Out[18]:

(3,5,8,9)

In [19]:

g*h

Out[19]:

(1,2,5,4,8,9,3)

In [20]:

g*h**2

Out[20]:

(1,2,8,3)(4,9,5)

In [21]:

g*h**3

Out[21]:

(1,2,9,8,5,4,3)

Since bijections have inverses, the permutation groups also have inverses

In [22]:

g**(-1)

Out[22]:

(1,3,2)(4,5)

Square of permutation group

In [23]:

g**2

Out[23]:

(1,3,2)

In [24]:

g**3

Out[24]:

(4,5)

Exercise: try to find the least power of permutation group n, which can make g^n be itself

In [25]:

Answer:

In [26]:

G = PermutationGroup(['(1,2,3)(4,5)'])
g = G.gen(0)
number = G.degree()
h = g
l = []
for i in range(2,100):
    if g**i == h:
        l.append(i) 
print l[0]

Out[26]:

7

Permutation Group

We can count the number of elements of this group

In [27]:

G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
G.cardinality()

Out[27]:

12

Also we can count the degree of this premutation group

The degree of a group of permutations of a finite set is the number of elements in the set

In [28]:

G.degree()

Out[28]:

5

If we want to know the subgroup of elements that commute with every element of this group, we can use x.center()

In [29]:

G.center()

Out[29]:

Subgroup of (Permutation Group with generators [(1,2), (1,2,3)(4,5)]) generated by [(4,5)]

It is also easy to find the fixed point in permutation group

In [30]:

G = PermutationGroup([(1,2,3),(5,6,9)])
G.fixed_points()

Out[30]:

[4, 7, 8]

In [31]:

G = PermutationGroup([[(1,4,7)],[(4,3),(6,7)]])
G.fixed_points()

Out[31]:

[2, 5]

What more, we are able to see the underlying set that this permutation group acts on

In [32]:

G = PermutationGroup([(1,2),(3,5)])
G.domain()

Out[32]:

{1, 2, 3, 4, 5}

Find the composition series of this group as a list of permutation groups

In [33]:

set_random_seed(0)
G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
G.composition_series()

Out[33]:

[Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [(3,4), (1,2,3)(4,5)],
 Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [(1,5,3), (1,5)(3,4), (1,5)(2,4)],
 Subgroup of (Permutation Group with generators [(3,4), (1,2,3)(4,5)]) generated by [()]]

In [34]:

G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
CS = G.composition_series()
CS[3]

Out[34]:

Subgroup of (Permutation Group with generators [(1,2), (1,2,3)(4,5)]) generated by [()]

Also we can find the group formed by conjugating self with g

In [35]:

G = DihedralGroup(6)
a = PermutationGroupElement("(1,2,3,4)")
G.conjugate(a)

Out[35]:

Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]

The element performing the conjugation can be specified in several ways, not only formed by conjugating other things

In [36]:

G = DihedralGroup(6)
strng = "(1,2,3,4,5)"
G.conjugate(strng)

Out[36]:

Permutation Group with generators [(1,3)(2,6)(4,5), (1,6,2,3,4,5)]

Exercise: What else form of thing can be conjugated?

In [0]:

Answer:

In [37]:

G = DihedralGroup(6)
lst = [2,3,4,1,5]
G.conjugate(lst)

Out[37]:

Permutation Group with generators [(1,4)(2,6)(3,5), (1,5,6,2,3,4)]

In [38]:

G = DihedralGroup(6)
cycles = [(1,2,3,4,5)]
G.conjugate(cycles)

Out[38]:

Permutation Group with generators [(1,3)(2,6)(4,5), (1,6,2,3,4,5)]

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Permutation Group

Permutation Group Element

Permutation Group

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place. Commercial Alternative to JupyterHub.

Permutation Group

Permutation Group Element

Permutation Group

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.