permutation
If X is a nonempty set, a permutation of X is a bijection α : X → X. That is, a permutation is a one-to-one function from X onto X.
symmetric group
If X is a non-empty set, the symmetric group on X, denoted by Sx, is the set of all permutations on X under the operation of composition of mappings.
If |X| = n (elements/degree) then we may write Sx = Sn where |Sn|=n! is no. of permutations
fixed & moved elements
Let X = {1, 2, 3, · · · , n} and α ∈ Sn.
An element k ∈ X is fixed by α if α(k) = k. We may just write αk for α(k).
If α(k) != k then we say that k is moved by α.
disjoint permutations
Let X = {1, 2, 3, · · · , n} and α ∈ Sn.
Two permutations α and β are disjoint if no element of X is moved by both α and β.
α and β commute and αβ=βα.
orbit
Let σ ∈ Sn. On X = {1, 2, 3, · · · , n} define the equivalence a ≡ b if b = σ^(r)(a) for some r ∈ Z. We assume that σ0 = e. The equivalence class of a = [a] = {σr(a)|r ∈ Z}.
This is called the orbit of a under σ.
cycle
The Cycle σ = (k1 k2 · · · kr) is the permutation in Sn defined by
σ(ki) = ki+1 if 1 ≤ i ≤ r − 1, σ(kr) = k1 and σ(k) = k if k /∈ {k1, k2, · · · , kr}.
We say that σ has length r and refer to σ as an r-cycle.
inverse permutations
If σ is an r-cycle, then σ^(−1) is also an r-cycle. In fact if σ = (k1 k2 · · · kr) then
σ^(−1) = (kr kr−1 · · · k1).
Cycle Decomposition Theorem
If σ != e is in Sn, then σ is the product of one or more disjoint cycles of length at least 2.
It can be proved that this factorisation is unique up to the order of the factors.
cyclic structure
Two permutations have the same cyclic structure if, when they are factored into disjoint cycles, they have the same number of cycles of each length.
transposition
A cycle of length 2.
NoteiIf δ is a transposition, then δ = (m n) for m, n in X. Certainly δ^2 = e and so δ^(-1) = δ
Let σ = (1 2)(3 4). σ^2 = e and so σ^(−1) = σ, but σ is not a transposition.
product of transpositions
Theorem:
Every cycle of length r > 1 is a product of r − 1 transpositions.
In fact (k1 k2 · · · kr−1 kr) = (k1 kr)(k1 kr−1) · · · (k1 k3)(k1 k2).
product of e
Lemma:
If the identity permutation e can be written as a product of n ≥ 3 transpositions, then it
can be written as a product of n − 2 transpositions.
Parity Theorem
If a permutation σ has two factorisations
σ = γnγn−1 · · · γ2γ1 = ρmρm−1 · · · ρ2ρ1
where each γi and ρj is a transposition, then both m and n are even or both are odd.
(no of transpositions)
order
- An element α of Sn has order r > 0 if α^r = e, and no smaller positive power of α is e.
- The order of a k cycle is k.
- The order of the product of disjoint cycles is the lcm of the orders of the cycles.
conjugate permutations
Two permutations σ and τ in Sn are conjugate in Sn if we can find γ ∈ Sn such that
γσγ^(−1) = τ and γ^(−1)τγ = σ.
Also if and only if they have the same cyclic structure.
define ≡ on Sn
σ ≡ τ if and only if σ and τ are conjugate in Sn. Then ≡ is an
equivalence relation on Sn. The equivalence classes of Sn under ≡ partition Sn into sets of distinct cyclic structure.
the Alternating
Group
The set of all even permutations in Sn is denoted by An and is called the Alternating Group of degree n.
Theorem:
If n ≥ 2, the set An has the following properties.
1. e is in An and if σ and τ are in An then so are their inverses and composition.
2. |An| = (1/2)n!
