Section 5.1 Definitions and Notation
Theorem 5.1.
The symmetric group on
Proof.
The identity of
Example 5.2.
Consider the subgroup
The following table tells us how to multiply elements in the permutation group
Remark 5.3.
Though it is natural to multiply elements in a group from left to right, functions are composed from right to left. Let
Example 5.4.
Permutation multiplication is not usually commutative. Let
Then
but
Subsection Cycle Notation
The notation that we have used to represent permutations up to this point is cumbersome, to say the least. To work effectively with permutation groups, we need a more streamlined method of writing down and manipulating permutations. A permutationExample 5.5.
The permutation
is a cycle of length
is a cycle of length
Not every permutation is a cycle. Consider the permutation
This permutation actually contains a cycle of length 2 and a cycle of length
Example 5.6.
It is very easy to compute products of cycles. Suppose that
If we think of
and
then for
or
Example 5.7.
The cycles
The product of two cycles that are not disjoint may reduce to something less complicated; the product of disjoint cycles cannot be simplified.
Proposition 5.8.
Let
Proof.
Let
Do not forget that we are multiplying permutations right to left, which is the opposite of the order in which we usually multiply group elements. Now suppose that
However,
Similarly, if
Theorem 5.9.
Every permutation in
Proof.
We can assume that
then
Example 5.10.
Let
Using cycle notation, we can write
Remark 5.11.
From this point forward we will find it convenient to use cycle notation to represent permutations. When using cycle notation, we often denote the identity permutation by
Subsection Transpositions
The simplest permutation is a cycle of lengthProposition 5.12.
Any permutation of a finite set containing at least two elements can be written as the product of transpositions.
Example 5.13.
Consider the permutation
As we can see, there is no unique way to represent permutation as the product of transpositions. For instance, we can write the identity permutation as
or by
but
Lemma 5.14.
If the identity is written as the product of
then
Proof.
We will employ induction on
where
The first equation simply says that a transposition is its own inverse. If this case occurs, delete
By induction
In each of the other three cases, we can replace
At some point either we will have two adjacent, identical transpositions canceling each other out or
Theorem 5.15.
If a permutation
Proof.
Suppose that
where
Subsection The Alternating Groups
One of the most important subgroups ofTheorem 5.16.
The set
Proof.
Since the product of two even permutations must also be an even permutation,
where
is also in
Proposition 5.17.
The number of even permutations in
Proof.
Let
by
Suppose that
Therefore,
Example 5.18.
The group
One of the end-of-chapter exercises will be to write down all the subgroups of