A permutation of a set is an **arrangement of its members into a sequence**, or if the set is already order a **rearrangement** of its elements. A permutation of a set A is a bijection from a set A onto itself, that is, a function that is both one-to-one and onto. A permutation of a set is a bijection from a set A onto itself, that is, a function that is both one-to-one and onto.

All permutations of a set with n elements form a group under function composition. S_{A}. It is called the **symmetric group**.

Proof:

- Closure. ∀π, σ ∈ S
_{n}⇒ πσ ∈ S_{n}because the composition of bijections is itself a bijection. - Associativity. ∀π, σ, η ∈ S, (πσ)η = π(ση) because function composition is always associative.
- Identity. The identity map is a permutation of S, Id(σ) = σ, ∀σ ∈ S.
- The inverse of πσ is σ
^{-1}π^{-1}.

A convenient way to write a permutation is to write it in array form and show where each element goes.

σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 5 & 1 & 4 & 6\end{smallmatrix}\bigr)$

This means that σ(1)=3, σ(2)=2, σ(3)=5, and so on.

σ^{-1} = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 4 & 2 & 1 & 5 & 3 & 6\end{smallmatrix}\bigr)$

Let σ = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1\end{smallmatrix}\bigr)$ and η = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{smallmatrix}\bigr)$. ση (first apply η and then σ) = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 2 & 4 & 1 & 3\end{smallmatrix}\bigr)$, e.g., ση(1)=σ(η(1))=σ(1)=2.

If sets A and B have the same cardinality, then S_{A}≃S_{B}. That’s because the structure of the group S_{A} is **concerned only with the number of elements in the set A, and not with the elements themselves**.

If sets A and B have the same cardinality, let f: A → B be a one-to-one function mapping A onto B. We define the function ϕ: S_{A} → S_{B}, σ ∈ S_{A}, then **ϕ(σ) is the permutation σ’ ∈ S _{B} such that σ’(f(a)) = f(σ(a))**.

Example: A = {1, 2, 3}, B = {a, b, c}, let f: A → B defined as f(1)=a, f(2)=b, f(3)=c. ϕ: S_{A} → S_{B}, $ϕ(\begin{smallmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{smallmatrix}\bigr)=(\begin{smallmatrix}a & b & c\\ b & c & a\end{smallmatrix}\bigr)$

Therefore, we can take {1, 2, …, n} to be a **prototype for a finite set A of n elements,** e.g., S_{3}. This is also the group D_{3} of symmetries of an equilateral triangle = { id (identity), two rotations (ρ_{1}, ρ_{2}), and three mirror images (μ_{1}, μ_{2}, μ_{3})}.

Notice that μ_{1}ρ_{1} ≠ μ_{1}ρ_{1}, so therefore S_{3} is non Abelian.

Definition. A **cycle** is a permutation which maps a finite set {a_{1}, a_{2}, …, a_{n}} by a_{1} → a_{2} → … → a_{n} → a_{1}. A cycle of length 2 is called a transposition. A **transposition is a permutation that swaps two elements and leaves everything else fixed**.

Examples: δ_{1} = (1, 3) or (13) is the transposition that swaps 1 and 3 and leaves everything else fixed. μ_{1} = (12)(34) and ρ_{1} = (1234). Therefore, μ_{1}ρ_{1} = (12)(34)(1234) = (1)(24)(3) = (24) - We do not write cycles of length one.- = δ_{2}.

Theorem. Every permutation on a finite set can we written as a product of disjoint cycles, that is, no element is moved by both of them, e.g. (135) and (24).

Proof. Let’s induct on the number of elements in the set A.

Let’s prove the result for a set with just one element. This is trivial, there is only one permutation, the identity, and it is the cycle {a}.

Suppose that a permutation on a set with less than n elements set can be written as a product of disjoint cycles. Let’s take a permutation on a set with n element, that is, σ ∈S_{n}.

Let m be the order of σ, a_{1} ∈ A and consider the set Q = {a_{1}, σ(a_{1}), σ^{2}(a_{1}),… σ^{m-1}(a_{1})} We know that m exists because the sequence a_{1}, σ(a_{1}), σ^{2}(a_{1}) must be finite.

If Q = A, σ is the cycle. Otherwise, |A - Q| < n, and by the induction assumption A - Q can be written as a product of disjoint cycles, A - Q = η_{1}η_{2}…η_{k}, and therefore the whole set A can be written as a product of disjoint cycles, more specifically, as (a_{1} σ(a_{1}) σ^{2}(a_{1})… σ^{m-1}(a_{1}))η_{1}η_{2}…η_{k}.

**Disjoint Cycles Commute**. If two cycles move different sets of elements, then their effects are independent and it does not matter in which order they’re applied. More formally, If two pair of cycles σ and η have no entries in common, then ση=ησ.

Proof. Suppose σ and η are disjoint cycles, σ = {a_{1}, a_{2},…, a_{m}} and η = {b_{1}, b_{2},…, b_{n}}, and {a_{1}, a_{2},…, a_{m}} ∩ {b_{1}, b_{2},…, b_{n}} = ∅. Let A = {a_{1}, a_{2},…, a_{m}, b_{1}, b_{2},…, b_{n}, c_{1}, c_{2},…, c_{s}} where c’s are the elements left fixed by both σ and η.

Then, ση(i)=ησ(i) ∀i∈A because (ση)(a_{i})=σ(η(a_{i}))=σ(a_{i}) = a_{i+1} where a_{m+1}=a_{1}. (ησ)(a_{i})=η(σ(a_{i}))=η(a_{i+1}) = a_{i+1}

A similar argument shows that (ση)(b_{i}) = (ησ)(b_{i}).

Finally, (ση)(c_{i})=σ(η(c_{i}))=σ(c_{i}) = c_{i}. (ησ)(c_{i})=η(σ(c_{i}))=η(c_{i}) = c_{i}

Theorem. The order of a permutation of a finite set A written in disjoint cycle form is the least common multiple of the lengths of the cycles.

Proof:

Case 1. If α is a permutation on A and can be represented as a cycle of length n, then it has order n. Therefore, the order of α is equal to the length of its cycle and the result holds for this case.

Case 2. Let us now now suppose that α can be written as product of two disjoint cycles α = α_{1}α_{2} where α_{1} and α_{2} are disjoint cycles of lengths m and n respectively. |α| = t. We need to show that t = lcm (m, n).

lcm(m, n) = k ⇒ k = ms_{1} = ns_{2}.

α^{k} = (α_{1}α_{2})^{k} = [∴ disjoint cycles commute] α_{1}^{k}α_{2}^{k} = α_{1}^{ms1}α_{2}^{ns2} = (α_{1}^{m})^{s1}(α_{2}^{n})^{s2} = ee = e ⇒ |α| = t divides lcm(m, n).

Let α^{t} = (α_{1}α_{2})^{t} = [∴ disjoint cycles commute] α_{1}^{t}α_{2}^{t} = e ⇒ α_{1}^{t} = α_{2}^{-t}. However, α_{1} and α_{2} are disjoint, they share no common symbol ⇒ α_{1}^{t} and α_{2}^{-t} share not common symbol either. If these two cycles are both equal and yet, they share no symbol, it follow that they are both the identity because every symbol that no appears in a permutation is fixed by it, so every symbol in α_{1}^{t} is fixed by α_{2}^{t} and vice-versa.

Therefore, both m and n must divide t ⇒ lcm(m, n) divides t, too. Then, t = lcm(m, n).

The general case is quite similar. α = α_{1}α_{2}…α_{r} where α_{1}, α_{2},… α_{r} are disjoint cycles of lengths m_{1}, m_{2},…. m_{2} respectively. |α| = t. We need to show that t = lcm (m_{1}, m_{2},… m_{r}).

lcm (m_{1}, m_{2},… m_{r}) = k ⇒ k = m_{1}s_{1}m_{2}s_{2}…m_{r}s_{r}

α^{k} = (α_{1}α_{2}…α_{r})^{k} = [∴ disjoint cycles commute] α_{1}^{k}α_{2}^{k}…α_{r}^{k} = α_{1}^{m1s1}α_{2}^{m2s2}…α_{r}^{mrsr} = (α_{1}^{m1})^{s1}(α_{2}^{m2})^{s2}…(α_{r}^{mr})^{sr}= ee…e = e ⇒ |α| = t divides lcm(m_{1}, m_{2}, … m_{r}).

Let α^{t} = (α_{1}α_{2}…α_{r})^{t} = [∴ disjoint cycles commute] α_{1}^{t}α_{2}^{t}…α_{r}^{t} = e. For the same reasons of two disjoint cycles, α_{1}^{t} = α_{2}^{t} = … = α_{r}^{t} = e ⇒ m_{1}, m_{2},… m_{r} divide t ⇒ lcm(m_{1}, m_{2}, … m_{r}) divides t.

Examples:

- α = (123)(456) ⇒ |α|=lcm(3, 3) = 3.
- α = (12)(345) ⇒ |α|=lcm(2, 3) = 6.
- α = (12345) ⇒ |α| = 5.
- α = (1234)(567)(89) ⇒ |α| = 12.

Definition. A transposition is a permutation which interchanges two elements and leaves everything else fixed. In other words, a transposition is a cycle of length 2.

Theorem. Every permutation is a product of transpositions. More formally, every permutation α ∈ S_{n}, n > 1 is a product of transpositions.

Proof.

Every permutation on a finite set can be written as a product of disjoint cycles, in the form,
(a_{1}a_{2}…a_{k})(b_{1}b_{2}…b_{t})…(c_{1}c_{2}…c_{s}).

However, every permutation is a product of cycles, e.g., (a_{1}a_{2}…a_{n}) = (a_{1}a_{n})(a_{1}a_{n-1})…(a_{1}a_{2})

And therefore, (a_{1}a_{2}…a_{k})(b_{1}b_{2}…b_{t})…(c_{1}c_{2}…c_{s}) = (a_{1}a_{k})(a_{1}a_{k-1})…(a_{1}a_{2})(b_{1}b_{t})(b_{1}b_{t-1})…(b_{1}b_{2})(c_{1}c_{s})(c_{1}c_{s-1})…(c_{1}c_{2}).

Examples:

- (12345) = (15)(14)(13)(12)
- (2745) = (25)(24)(27)
- (16)(253) = (16)(23)(25)

Definition. A permutation that can be written or expressed as a product of an even number of transpositions or 2-cycles is called an **even permutation**. A permutation that can be written or expressed as a product of an odd number of transpositions or 2-cycles is called an **odd permutation.**

Lemma. **The identity permutation is an even permutation.** An even permutation can be obtained as the composition of an even and only and even number of transposition. More formally, If β^{1}β^{2}…β^{n} = e where the β’s are transpositions, then n is even.

Proof.

n ≠ 1 because a transposition could never be the identity.

n = 2. Then, the lemma is true.

⇒ |α| = 5.⇒ |α| = 5.

Suppose n > 2, and we proceed by induction.

β^{n-1}β^{n} can be expressed in one of the following forms:

- e = (ab)(ab)
- (ab)(bc) = (ac)(ab)
- (ac)(cb) = (cb)(ab)
- (ab)(cd) = (cd)(ab)

If we are in the first case, e = (ab)(ab) ⇒ β^{1}β^{2}…β^{n-2} = e. By induction hypothesis, n-2 is even ⇒ n is even.

In the other cases, we replace the form of β^{n-1}β^{n} on the right by its counterpart on the left. We obtain a product of n transpositions where the rightmost occurrence of a is in the *second from the right transpose of the product.* We repeat the process, and the rightmost occurrence of a is in the *third from the right transpose of the product.*

There are two options:

- We obtain a product of (n-2) transpose equal to the identity (e = (ab)(ab)) ⇒ n - 2 is even ⇒ n is even.
- Otherwise, we have a product of transpose equal to the identity in which the only occurrence of a is in the leftmost cycle, and such a product does not fix a, so it is not the identity, ⊥.

Theorem. **A permutation cannot be written as a product of both an odd and an even number of transpositions**.

Proof. Let α = β_{1}β_{2}…β_{r} = ζ_{1}ζ_{2}…ζ_{s}

e = ζ_{1}ζ_{2}…ζ_{s}β_{r}^{-1}…β_{2}^{-1}β_{1}^{-1} = ζ_{1}ζ_{2}…ζ_{s}β_{r}…β_{2}β_{1} [a transposition is its own inverse]. By the previous theorem, r+s is even ⇒ r and s are both even or both odd.

Theorem. **The alternating group of degree n A _{n} is the subgroup of S_{n} consisting of the even permutations**.

Proof.

- The identity permutation is an even permutation.
- If α and β are even permutations, then β
^{-1}is even, because we just need to decompose β into an even number of transpositions and write the product backwards. Therefore, αβ^{-1}is an even permutation, αβ^{-1}∈ A_{n}.

Theorem. For n > 1, **A _{n} has order n!/2**.

Proof. Let A_{n} be the set of even permutations in S_{n}, and B_{n} be the set of odd permutations.

Let’s define a one-to-one function from A_{n} onto B_{n}, and therefore A_{n} and B_{n} has the same number of elements.

First, we define the function Φ: A_{n} → B_{n}, by Φ(α)=(12)α, α is even so it can be written or expressed as a product of an even number of transpositions, so (12)α ∈ B_{n}.

is Φ a one-to-one function? Φ(α) = Φ(β) ⇒ (12)α = (12)β ⇒ [S_{n} is a group, and by the Cancellation property] α = β.

If α ∈ B_{n}, (12)^{-1}α = (12)α ∈ A_{n} ⇒ Φ((12)α) =(12)(12)α = α

S_{n} is split equally in both even and odd permutations, |S_{n}| = n! = 2|A_{n}| ⇒ |A_{n}| = n!/2.