**Definition**: The set of all permutations of a set
**S** is denoted by Sym(S).

The set of all permutations of the set {1,2,...,n} is
denoted by S_{n}

**Proposition.** If S is any nonempty set, then Sym(S) is
a group under the operation of composition of functions.

**Theorem.** Every permutation
in S_{n} can be written as a product of disjoint cycles. The cycles
that appear in the product are unique.

**Proposition.** If a
permutation in S_{n} is written as a product of disjoint cycles, then
its order is the least common multiple of the lengths of its cycles.

**Definition.** Any subgroup of
the **symmetric group** Sym(S) on a set S is called a **permutation group**
or **group of permutations.**

**Definition.** A permutation is
called **even** if it can be written as a product of an even number of
transpositions, and **odd** if it can be written as a product of an odd
number of transpositions.

**Proposition.** The set of all
even permutations of S_{n} is a subgroup of S_{n}.

**Definition.** The set of all
even permutations of S_{n} is called the **alternating group** on n
elements, and will be denoted by A_{n}.

Among the most interesting entities in abstract algebra is
the *permutation group*. To fix ideas, consider the following example:

Let S = {1, 2, 3} and define the group G = {*The set of all
permutations on S*}

a) Write out all the members of G

b) Show that G obeys group properties and determine whether or not it is Abelian

*Solution*:

= 3 x 2 x 1 = 6.

The components can then be found:

(1,2, 3), (1, 3, 2), (3, 2, 1), (3, 1, 2), (2, 1, 3) and (2, 3, 1)

These *are not* the
elements themselves, which must be written as (2 x 3) matrices. For example,
the ** identity** element will be:

**e**=

[1 2 3]

[1 2 3]

**s ****1** =

[2 3 1]

**s ****2** =

[1 2 3]

[3 1 2]

**t**** ****1** =

[1 2 3}

[1 3 2]

** ****t**** ****2** =

[1 2 3]

[3 2 1]

**t** **3** =

[1 2 3]

[2 1 3]

Given the above relationships to assorted groups members, we can now prepare a group table to show the operation is binary and G meets the Group definition. We have for G = {The set of all permutations on S}:

e---- **s**** 1**---

**s**

**---**

*2***t**

**---**

*1***t**

**---**

*2***t**

*3***--------------------------------------------------**

e -- e ---**s**1--- **s**2 --- **t**1 --- **t**2--- **t**3

**s**** 1** --

**s**1---

**s**2--- e ----

**t**2 ----

**t**3 ----

**t**1

**s**** 2** --

**s**2----e ---

**s**1---

**t**3---

**t**1----

**t**2

**t**** 1 ** ---

**t**1-

**t**3-

**t**2 --- e ---

**s**2 -----

**s**1

**t**** 2 ** ----

**t**2---

**t**1--

**t**3- -

**s**1--- e-------

**s**2

**t**** 3** -----

**t**3 ---

**t**2 ---

**t**1 ----

**s**2 ---

**s**1---- e

------------------------------------------------

The shaded highlights shown are intended to emphasize the symmetries in the table (which can also be found for the s elements). Is G Abelian? If we check any two elements and find they don’t meet the commutative property (4) then the answer is no. By inspection:

**t**1 • **t**** ** 2 = **s** 1
=

[1 2 3]

[2 3 1]

**t**** 2** • **t****
**1 = **s** 2 =

[1 2 3]

[3 1 2]

__ not
__Abelian.

*s** *** t** and will be a permutation if it
is one-to-one and onto A.

*Definitional illustrations*:

**s ** **t**)
= a2(**s ** **t**),
then (a1 **s** ) **t**
= (a2 **s**
) **t** and (a1** s**) = (a1** s** ) (since **t** is 1:1) and a1 =
a2.

**s ** **t****)
** is 1:1.

**t**
= (a” **s**
) **t** = a” (**s ** **t**).

Example: Let A = {1, 2, 3, 4, 5} and

**s** =

[1 2 3 4 5]

[4 2 5 3 1]

In this case: 1** s** = 4, 2** s** = 2, 3** s** = 5, 4** s** = 3, and 5** s** = 1

**t** =

[3 5 4 2 1]

Then: 1**t** = 3, 2**t**
= 5, 3**t** = 4, 4**t**
= 2, and 5**t** = 1

[1 2 3 4 5]

[2 5 1 4 3]

(Which the reader should be able to verify!)

--------------------

**Extending Permutation Groups: Transpositions**:

T2 **= I** (identity permutation, e.g
the permutation such that I(i) = i for all i = 1,...n)

A permutation p of the integers {1, . . . n} is denoted by

[1 .. . .. n]

[p(1).. p(n)]

So, for example:

[1 2 3]

[2 1 3]

denotes the permutation p such that p(1) = 2, p(2) = 1, and p(3) = 3.

Now, let's look at EVEN and ODD permutations:

Let P _{n } denote the polynomial of n variables x_{ 1}, x _{2} ……x _{n} which
is the product of all the factors x _{i} .. x _{j } with i < j. That is:

P _{n }( x_{ 1}, x _{2} ……x _{n}) = P(x _{i} .. x _{j})

The symmetric group S(n) acts on the polynomial P _{n} by
permuting the variables. For p Î S(n) we have:

P _{n }( x_p(1), x_p(2). . .x_p(n)) = (sgn p) P _{n} (
x_{ 1}, x _{2} ……x _{n})

where sgn p = __+__** 1**. If the sign is positive
then p is called an even permutation, if the sign is negative then p is called
an odd permutation. Thus: the product of two even or two odd permutations is
even. The product of an even and an odd permutation is odd.

Back to transpositions! We just saw:

[1 2 3]

[2 1 3]

The above permutation is actually a transposition 2 <-> 1 (leaving 3
fixed). Now, let p' be the permutation:

[1 2 3]

[3 1 2]

Then pp' is the permutation such that:

pp'(1) = p(p'(1)) = p(3) = 3

pp'(2) = p(p'(2)) = p(1) = 2

pp'(3) = p(p'(3)) = p(2) = 1

It isn’t difficult to ascertain that: sgn (ps) = (sgn p) (sgn s) so that we may
write:

pp' =

[1 2 3]

[3 2 1]

Now, find the inverse p^-1 of the above. (Note: the inverse permutation,
denoted by p ^{-}^{ 1} is defined as the
map: p ^{-}^{ 1} : Zn -> Zn), Since
p'(1) = 3, then p ^{-}^{ 1} (3) = 1

Since p'(2) = 1 then p ^{-}^{ 1} (1) = 2

Since p'(3) = 2 then p ^{-}^{ 1} (2) = 3

Therefore: p ^{-}^{ 1} =

[1 2 3]

[ 2 3 1]

**Disjoint permutations**:

Expressing a permutation as a product of disjoint cyclic permutations is not hard at all, once one gets the hang of it. The key is to “cycle through” the mapping in the original to yield the different disjoint cycles, taking care to stop when the end element leads to a number (on the top of the original) that repeats. For example:

Express as disjoint permutations:

[1 2 3 4 5 6 7]

[4 5 6 7 3 1 2]

*Solution*: 1 goes into 4, 4 goes into 7, 7 goes into 2 – STOP!
(Since 2 commences new cycle in next top position). So first disjoint cycle is:
(1, 4, 7, 2).

Now, 2 goes into 5, 5 goes into 3, *STOP!* (3 repeats) So cycle is: (2, 5,
3). Then 3 goes into 6, and 6 into 1. Stop.

*Answer:
(1, 4, 7, 2)(2, 5, 3)(6).*

*Permutations applied to solid geometry (tetrahedron )*:

Call the ordering '1234'. In terms of signage (sign rules - e.g. for (+) or (-) being followed, it's important to note that a segment (1 2) induces orientation (+1) in the associated complex, but a segment (2 1) induces (-1). This is how differing segments acquire negative signage in the complex.

* boundary*
of the tetrahedron, in terms of its four faces can than be written:

**-**** (1 2 3) - (1 3 4) + (1 2 4) + (1 3 4)**

__Suggested Problems:__

*1*__)__ Let A = {1, 2, 3, 4, 5} and **s** be the result (**s****t**)

**t**, 2**t** , 3**t** , 4**t**, and 5**t**

Compare to: 1 **s****t**, 2**s****t** , 3**s****t** , 4**s****t**, and 5**s****t**

2)Express p =

[1 2 3 4][2 3 1 4]

as the product of transpositions, and determine the sign (+1 or -1) of the resulting end permutation

## No comments:

Post a Comment