Permutation Groups

Study Sheet

Permutation Groups

Cycle notation, composing permutations, order, parity, and Cayley's theorem

Permutations and Cycle Notation

Concept
Permutations and SnS_n

A permutation of {1,2,…,n}\{1, 2, \ldots, n\} is a bijection from that set to itself. Composing two permutations (apply one, then the other) gives another permutation, so the n!n! permutations of {1,…,n}\{1,\ldots,n\} form a group under composition, the symmetric group SnS_n. A permutation that sends a1↦a2↦⋯↦ak↦a1a_1 \mapsto a_2 \mapsto \cdots \mapsto a_k \mapsto a_1 and fixes every other point is a kk-cycle, written (a1 a2 ⋯ ak)(a_1\,a_2\,\cdots\,a_k); writing a permutation as a product of disjoint cycles, one for each orbit of points it moves, is cycle notation. A 11-cycle, a fixed point, is normally left out.

Cycle notation is shorter than listing where every point goes, and it shows a permutation's structure at a glance: how many points move together, and in what pattern. Every permutation of a finite set factors uniquely into disjoint cycles uniquely up to which point starts each cycle, since (1 3 5)(1\,3\,5) and (3 5 1)(3\,5\,1) name the same cycle. This decomposition is the lens for everything in this topic: the order of a permutation, whether it is even or odd, and (later) its conjugates all read off from the lengths of its cycles, not from the raw list of images.

Example
From two-row to cycles
1122334455667788
σ sends 1↦3↦5↦1 and 4↦8↦4 and 6↦7↦6, and fixes 2.

The permutation σ∈S8\sigma \in S_8 sends 1,2,…,81,2,\ldots,8 to 3,2,5,8,1,7,6,43,2,5,8,1,7,6,4 respectively. Track orbits: 1→3→5→11 \to 3 \to 5 \to 1 closes a 33-cycle; 2→22 \to 2 is fixed; 4→8→44 \to 8 \to 4 closes a 22-cycle; 6→7→66 \to 7 \to 6 closes another. So σ=(1 3 5)(4 8)(6 7)\sigma = (1\,3\,5)(4\,8)(6\,7), with 22 fixed and left out. Check: every one of 1,…,81,\ldots,8 appears in exactly one cycle (or is the omitted fixed point), and each cycle's last entry maps back to its first.

Example
From cycles to two-row

Write τ=(1 4 6 2)(3 5)∈S6\tau = (1\,4\,6\,2)(3\,5) \in S_6 in two-row form. Reading each cycle as an arrow chain: 1→41\to4, 4→64\to6, 6→26\to2, 2→12\to1, and separately 3→53\to5, 5→35\to3. So τ\tau sends 1,2,3,4,5,61,2,3,4,5,6 to 4,1,5,6,3,24,1,5,6,3,2. Check it is a bijection: the bottom row 4,1,5,6,3,24,1,5,6,3,2 is a rearrangement of 1,…,61,\ldots,6 with no repeats.

Example
Counting the 55-cycles in S5S_5

S5S_5 has 5!=1205! = 120 elements. How many of them are a single 55-cycle, i.e. have cycle type (5)(5)? A 55-cycle is named by a cyclic order of its 55 points; there are 5!=1205! = 120 orderings of 1,…,51,\ldots,5, but a cycle can be written starting from any of its 55 points, so each 55-cycle is named 55 times over. The number of distinct 55-cycles is therefore 5!/5=4!=245!/5 = 4! = 24.

Side note
Where it goes wrong

Writing the same cycle starting from a different point is fine (1 3 5)=(3 5 1)=(5 1 3)(1\,3\,5) = (3\,5\,1) = (5\,1\,3), all the same permutation but REVERSING the order is not: (1 2 3)(1\,2\,3) sends 1→2→3→11\to2\to3\to1, with two-row image 2,3,12,3,1, while (1 3 2)(1\,3\,2) sends 1→3→2→11\to3\to2\to1, with image 3,1,23,1,2. These are different permutations (one is the inverse of the other), even though they list the same three symbols.

Try it
Try it: cycle notation

Write the permutation sending 1,2,3,41,2,3,4 to 3,1,4,23,1,4,2 in cycle notation.

Show the answer

Track the orbit from 11: 1→31\to3, 3→43\to4, 4→24\to2, 2→12\to1 one 44-cycle through every point. The permutation is (1 3 4 2)\mathbf{(1\,3\,4\,2)}.

Composing Permutations

Concept
Composing permutations

For σ,τ∈Sn\sigma, \tau \in S_n, the product στ\sigma\tau is the permutation (στ)(i)=σ(τ(i))(\sigma\tau)(i) = \sigma(\tau(i)): apply τ\tau first, then σ\sigma, reading right to left like function composition. Composition is associative (it IS function composition) and closed, SnS_n has an identity (the permutation fixing everything), and every σ\sigma has an inverse undoing it reverse each cycle: (a1 a2 ⋯ ak)−1=(ak ak−1 ⋯ a1)(a_1\,a_2\,\cdots\,a_k)^{-1} = (a_k\,a_{k-1}\,\cdots\,a_1). These are exactly the group axioms of Topic 1, so SnS_n is a group but for n≥3n \ge 3 it is not abelian.

The right-to-left convention matches reading σ(τ(i))\sigma(\tau(i)) as English: do τ\tau's job on ii first, then feed the result to σ\sigma. Non-commutativity is the biggest difference between SnS_n and the cyclic and modular groups of the Gallery of Groups (Topic 2), where abab always equals baba. Reversing a cycle to invert it works because composing a cycle with its reverse sends every point straight back where it started the arrow chain just runs backwards.

Example
A non-commuting product
S_3∘e(12)(13)(23)(123)(132)ee(12)(13)(23)(123)(132)(12)(12)e(132)(123)(23)(13)(13)(13)(123)e(132)(12)(23)(23)(23)(132)(123)e(13)(12)(123)(123)(13)(23)(12)(132)e(132)(132)(23)(12)(13)e(123)
Row (123), column (12) gives (13); row (12), column (123) gives (23): not symmetric.

In S3S_3, let σ=(1 2 3)\sigma = (1\,2\,3) and τ=(1 2)\tau = (1\,2). Compute στ\sigma\tau by applying τ\tau first: (στ)(1)=σ(τ(1))=σ(2)=3(\sigma\tau)(1) = \sigma(\tau(1)) = \sigma(2) = 3; (στ)(2)=σ(τ(2))=σ(1)=2(\sigma\tau)(2) = \sigma(\tau(2)) = \sigma(1) = 2; (στ)(3)=σ(τ(3))=σ(3)=1(\sigma\tau)(3) = \sigma(\tau(3)) = \sigma(3) = 1. So στ=(1 3)\sigma\tau = (1\,3), fixing 22. Now the other order: (τσ)(1)=τ(σ(1))=τ(2)=1(\tau\sigma)(1) = \tau(\sigma(1)) = \tau(2) = 1; (τσ)(2)=τ(σ(2))=τ(3)=3(\tau\sigma)(2) = \tau(\sigma(2)) = \tau(3) = 3; (τσ)(3)=τ(σ(3))=τ(1)=2(\tau\sigma)(3) = \tau(\sigma(3)) = \tau(1) = 2. So τσ=(2 3)\tau\sigma = (2\,3), fixing 11 a different permutation from στ\sigma\tau: S3S_3 is not abelian.

Example
Composing two-row permutations

Let pp send 1,2,3,4→2,3,1,41,2,3,4 \to 2,3,1,4 and qq send 1,2,3,4→1,4,2,31,2,3,4 \to 1,4,2,3. Compute p∘qp \circ q (apply qq first): (p∘q)(1)=p(q(1))=p(1)=2(p\circ q)(1) = p(q(1)) = p(1) = 2; (p∘q)(2)=p(q(2))=p(4)=4(p\circ q)(2) = p(q(2)) = p(4) = 4; (p∘q)(3)=p(q(3))=p(2)=3(p\circ q)(3) = p(q(3)) = p(2) = 3; (p∘q)(4)=p(q(4))=p(3)=1(p\circ q)(4) = p(q(4)) = p(3) = 1. So p∘qp \circ q sends 1,2,3,4→2,4,3,11,2,3,4 \to 2,4,3,1, which in cycle notation is (1 2 4)(1\,2\,4) with 33 fixed. Check: it moves exactly the 33 points visited by that cycle and fixes the rest.

Example
Solving σx=τ\sigma x = \tau for xx

In S5S_5, let σ=(1 2 3 4 5)\sigma = (1\,2\,3\,4\,5) and τ=(1 3 5 2 4)\tau = (1\,3\,5\,2\,4). Find the permutation xx with σx=τ\sigma x = \tau. Multiply both sides on the left by σ−1=(1 5 4 3 2)\sigma^{-1} = (1\,5\,4\,3\,2): x=σ−1τx = \sigma^{-1}\tau. Computing x(i)=σ−1(τ(i))x(i) = \sigma^{-1}(\tau(i)) for each ii: τ\tau sends 1,2,3,4,5→3,4,5,1,21,2,3,4,5 \to 3,4,5,1,2, and applying σ−1\sigma^{-1} (which sends 1,2,3,4,5→5,1,2,3,41,2,3,4,5 \to 5,1,2,3,4) to each of those gives xx sending 1,2,3,4,5→2,3,4,5,11,2,3,4,5 \to 2,3,4,5,1. That is x=(1 2 3 4 5)=σx = (1\,2\,3\,4\,5) = \sigma itself. Check: σσ=σ2\sigma\sigma = \sigma^2 should equal τ\tau, and indeed σ2\sigma^2 sends 1→σ(σ(1))=σ(2)=31 \to \sigma(\sigma(1)) = \sigma(2) = 3, matching τ(1)=3\tau(1) = 3.

Side note
Where it goes wrong

Applying the permutations in the wrong order. Asked for στ\sigma\tau in the example above, a student who multiplies "left to right" applying σ\sigma first, then τ\tau actually computes τσ=(2 3)\tau\sigma = (2\,3), not στ=(1 3)\sigma\tau = (1\,3): a genuinely different, wrong answer, not just a relabeling. The convention (στ)(i)=σ(τ(i))(\sigma\tau)(i) = \sigma(\tau(i)) always applies the RIGHTMOST permutation first.

Try it
Try it: an inverse

Find the inverse of ρ=(1 4 5 2)(3 6)∈S6\rho = (1\,4\,5\,2)(3\,6) \in S_6, and check that ρρ−1\rho\rho^{-1} is the identity.

Show the answer

Reverse each cycle: ρ−1=(1 2 5 4)(3 6)\rho^{-1} = (1\,2\,5\,4)(3\,6). Check at one point: ρ\rho sends 1→41 \to 4, and ρ−1\rho^{-1} sends 4→14 \to 1, back where it started; the same happens at every point, so ρρ−1=e\rho\rho^{-1} = \mathbf{e}, the identity.

The Order of a Permutation

Concept
The order of a permutation

The order of σ∈Sn\sigma \in S_n is the least positive integer kk with σk=e\sigma^k = e the same notion of order as Topic 3, applied to the cyclic subgroup ⟨σ⟩\langle\sigma\rangle. If σ\sigma's disjoint cycle decomposition has cycle lengths ℓ1,…,ℓm\ell_1, \ldots, \ell_m (its cycle type), then ∣σ∣=lcm⁡(ℓ1,…,ℓm)|\sigma| = \operatorname{lcm}(\ell_1, \ldots, \ell_m).

Disjoint cycles move disjoint sets of points, so they act independently and commute with each other; raising σ\sigma to the kk-th power raises every cycle to the kk-th power separately. A single ℓ\ell-cycle returns every point home exactly when kk is a multiple of ℓ\ell rotating ℓ\ell seats by kk steps lines everyone back up only when ℓ∣k\ell \mid k. For every cycle to be home at once, kk must be a multiple of every ℓi\ell_i simultaneously, and the least such kk is their lcm. This is why a permutation can have surprisingly large order even in a small SnS_n: a disjoint 44-cycle and 33-cycle combine to order 1212, far more than either alone.

Example
Order from cycle type
1122334455667788991010
A 5-cycle, a 2-cycle, and a 3-cycle, all disjoint: order lcm(5,2,3) = 30.

The permutation σ=(1 2 3 4 5)(6 7)(8 9 10)∈S10\sigma = (1\,2\,3\,4\,5)(6\,7)(8\,9\,10) \in S_{10} has cycle type (5,2,3)(5,2,3), so its order is lcm⁡(5,2,3)\operatorname{lcm}(5,2,3). Since 55, 22, 33 share no common factors, lcm⁡(5,2,3)=5⋅2⋅3=30\operatorname{lcm}(5,2,3) = 5\cdot2\cdot3 = 30. Check: σ30\sigma^{30} raises the 55-cycle to a multiple of 55 (back home), the 22-cycle to a multiple of 22 (back home), and the 33-cycle to a multiple of 33 (back home) all at once, and no smaller kk is a multiple of 55, 22, and 33 simultaneously.

Example
The largest possible order in S7S_7

What is the largest order an element of S7S_7 can have? The order depends only on the cycle type, a partition of 77, via the lcm of its parts. Checking partitions: 7→77 \to 7; 6+1→66{+}1 \to 6; 5+2→105{+}2 \to 10; 5+1+1→55{+}1{+}1 \to 5; 4+3→124{+}3 \to 12; 4+2+1→44{+}2{+}1 \to 4; 3+3+1→33{+}3{+}1 \to 3; 3+2+2→63{+}2{+}2 \to 6; and the remaining, smaller partitions all give less. The winner is 4+3=74+3=7 with lcm⁡(4,3)=12\operatorname{lcm}(4,3) = 12: a permutation such as (1 2 3 4)(5 6 7)(1\,2\,3\,4)(5\,6\,7), a 44-cycle disjoint from a 33-cycle, has order 12\mathbf{12} larger than the 77-cycle's order of 77.

Example
Every order that occurs in S5S_5

Which positive integers occur as the order of some element of S5S_5? Running through the partitions of 55 and their lcms: 5→55 \to 5; 4+1→44{+}1 \to 4; 3+2→63{+}2 \to 6; 3+1+1→33{+}1{+}1 \to 3; 2+2+1→22{+}2{+}1 \to 2; 2+1+1+1→22{+}1{+}1{+}1 \to 2; 1+1+1+1+1→11{+}1{+}1{+}1{+}1 \to 1. The orders that occur are {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\} note that 66 appears even though no element of S5S_5 moves more than 55 points, because lcm⁡(3,2)=6\operatorname{lcm}(3,2) = 6 exceeds both parts.

Side note
Where it goes wrong

Guessing that the order equals the length of the LONGEST cycle. Take ρ=(1 2)(3 4 5)∈S5\rho = (1\,2)(3\,4\,5) \in S_5: the longest cycle has length 33, but ρ3=(1 2)\rho^3 = (1\,2) the 22-cycle survives an odd power while the 33-cycle vanishes so ρ3≠e\rho^3 \ne e. Likewise ρ2=(3 5 4)\rho^2 = (3\,5\,4): the 22-cycle vanishes but the 33-cycle does not, so ρ2≠e\rho^2 \ne e either. Only ρ6=e\rho^6 = e: the true order is lcm⁡(2,3)=6\operatorname{lcm}(2,3) = 6, not 33.

Try it
Try it: order from cycles

Find the order of σ=(1 5 3)(2 8)(4 7 6)∈S8\sigma = (1\,5\,3)(2\,8)(4\,7\,6) \in S_8.

Show the answer

Cycle type (3,2,3)(3,2,3), so ∣σ∣=lcm⁡(3,2,3)=6|\sigma| = \operatorname{lcm}(3,2,3) = \mathbf{6}.

Even and Odd Permutations

Concept
Even and odd permutations

A transposition is a 22-cycle, swapping two points and fixing the rest. Every permutation factors as a product of transpositions, and although the factorization is never unique, the PARITY of the number of transpositions used always is: σ\sigma is even if some (hence every) factorization uses an even number, and odd otherwise. From the cycle type (ℓ1,…,ℓm)(\ell_1,\ldots,\ell_m), sgn⁡(σ)=(−1)(ℓ1−1)+⋯+(ℓm−1)\operatorname{sgn}(\sigma) = (-1)^{(\ell_1-1)+\cdots+(\ell_m-1)}, since an ℓ\ell-cycle itself factors into ℓ−1\ell - 1 transpositions, e.g. (1 2 3)=(1 3)(1 2)(1\,2\,3) = (1\,3)(1\,2).

Parity behaves like a ±1\pm1 measurement that composition respects: sgn⁡(στ)=sgn⁡(σ)sgn⁡(τ)\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau), so sgn⁡\operatorname{sgn} is a homomorphism from SnS_n to {±1}\{\pm1\} (Why It Works proves it is even well defined). The even permutations therefore form a subgroup AnA_n, and as Cosets and Lagrange (Topic 5) will show AnA_n has exactly half of SnS_n's elements. Reading parity off the cycle type alone, without ever writing a transposition factorization, is one of the main payoffs of thinking in cycles rather than two-row notation.

Example
Parity from cycle type

Is (1 2 3)(4 5)∈S5(1\,2\,3)(4\,5) \in S_5 even or odd? The 33-cycle contributes 3−1=23 - 1 = 2 transpositions (even); the 22-cycle contributes 2−1=12 - 1 = 1 (odd). Altogether 2+1=32 + 1 = 3 transpositions, an odd number, so sgn⁡((1 2 3)(4 5))=−1\operatorname{sgn}\big((1\,2\,3)(4\,5)\big) = -1: the permutation is odd. Check directly: (1 2 3)=(1 3)(1 2)(1\,2\,3) = (1\,3)(1\,2), so (1 2 3)(4 5)=(1 3)(1 2)(4 5)(1\,2\,3)(4\,5) = (1\,3)(1\,2)(4\,5), visibly 33 transpositions.

Example
Even or odd in S9S_9

Is σ=(1 2 3 4 5 6 7)(8 9)∈S9\sigma = (1\,2\,3\,4\,5\,6\,7)(8\,9) \in S_9 even or odd? The 77-cycle contributes 7−1=67-1=6 transpositions (even); the 22-cycle contributes 11 (odd). The total 6+1=76+1=7 is odd, so σ\sigma is odd one extra transposition is enough to flip the parity of an otherwise-even 77-cycle.

Example
Half of S4S_4 is even

S4S_4 has 4!=244! = 24 elements, split by cycle type: the identity (11, even), transpositions ((42)=6\binom{4}{2} = 6, odd), 33-cycles (88, even), 44-cycles (66, odd), and double transpositions of type (2,2)(2,2) (33, even). Adding the even counts, 1+8+3=121 + 8 + 3 = 12; adding the odd counts, 6+6=126 + 6 = 12. Exactly half of S4S_4's 2424 elements are even: ∣A4∣=12|A_4| = 12, the n=4n=4 case of the index-22 fact above.

Side note
Where it goes wrong

Confusing a cycle's LENGTH with its parity in the wrong direction: a 33-cycle (length 33, odd) is EVEN, while a transposition (length 22, even) is ODD. The rule is ℓ\ell-cycle →\to ℓ−1\ell-1 transpositions, so odd-length cycles are even and even-length cycles are odd exactly backwards from what the word "odd" suggests at first glance.

Try it
Try it: parity

Is (1 2)(3 4 5 6)(7 8 9)∈S9(1\,2)(3\,4\,5\,6)(7\,8\,9) \in S_9 even or odd?

Show the answer

Transposition: 2−1=12-1=1. 44-cycle: 4−1=34-1=3. 33-cycle: 3−1=23-1=2. Total 1+3+2=61+3+2=6, an even number: the permutation is even.

Cayley's Theorem

Concept
Cayley's theorem

Every group GG is isomorphic to a subgroup of a symmetric group: a subgroup of Sym⁡(G)\operatorname{Sym}(G), the group of all bijections G→GG \to G under composition, and so a subgroup of SnS_n when ∣G∣=n|G| = n is finite. The isomorphism sends each g∈Gg \in G to the permutation λg ⁣:x↦gx\lambda_g\colon x \mapsto gx left multiplication by gg of the underlying set GG.

Every group, however it was originally defined by matrices, by symmetries, by remainders mod nn turns out to secretly BE a group of permutations, acting on its own elements. Left multiplication by a fixed gg is a bijection of GG, with inverse x↦g−1xx \mapsto g^{-1}x by the inverse axiom of Topic 1, so each gg really does give a permutation λg\lambda_g of the set GG; and λgh=λgλh\lambda_{gh} = \lambda_g\lambda_h because (gh)x=g(hx)(gh)x = g(hx), so the correspondence respects the group operation. This is why the symmetric groups are not just one more family of examples: in a precise sense they are the universal example, and every abstract group sits inside one.

Example
The regular representation of Z4\mathbb Z_4

In Z4={0,1,2,3}\mathbb Z_4 = \{0,1,2,3\} under addition mod 44, left multiplication by 11 is λ1 ⁣:x↦x+1(mod4)\lambda_1\colon x \mapsto x+1 \pmod 4. Tracking where each point goes: 0→1→2→3→00\to1\to2\to3\to0. So λ1\lambda_1 is the 44-cycle (0 1 2 3)(0\,1\,2\,3), of order 44 matching the order of 11 in Z4\mathbb Z_4, as it must, since λg\lambda_g always has the same order as gg. This embeds Z4\mathbb Z_4 into S4S_4 as the cyclic subgroup ⟨(0 1 2 3)⟩\langle(0\,1\,2\,3)\rangle.

Example
The regular representation of the Klein four-group
V·eabceeabcaaecbbbceaccbae
V's table: every row is e,a,b,c rearranged, and every element is its own inverse.

Let V={e,a,b,c}V = \{e,a,b,c\} be the Klein four-group, where a,b,ca,b,c all have order 22 and ab=cab=c, bc=abc=a, ca=bca=b. Left multiplication by aa sends e↦ae=ae\mapsto ae=a, a↦aa=ea\mapsto aa=e, b↦ab=cb\mapsto ab=c, c↦ac=bc\mapsto ac=b. So λa\lambda_a swaps e↔ae \leftrightarrow a and b↔cb \leftrightarrow c: the permutation (e a)(b c)(e\,a)(b\,c). Unlike Z4\mathbb Z_4's regular representation above, this is two disjoint 22-cycles, not a single 44-cycle because aa has order 22, not 44, in VV.

Example
Is U(5)U(5)'s regular representation a 44-cycle?

U(5)={1,2,3,4}U(5) = \{1,2,3,4\} under multiplication mod 55 is cyclic, generated by 22 (since 21=2,22=4,23=3,24=12^1=2, 2^2=4, 2^3=3, 2^4=1). Left multiplication by 22 sends 1→21\to2, 2→42\to4, 3→2⋅3=6≡13\to2\cdot3=6\equiv1, 4→2⋅4=8≡34\to2\cdot4=8\equiv3. Tracking the orbit: 1→2→4→3→11\to2\to4\to3\to1, a single 44-cycle (1 2 4 3)(1\,2\,4\,3) of order 44. Since U(5)U(5) is cyclic of order 44, its regular representation is, like Z4\mathbb Z_4's above, a single 44-cycle the regular representation of ANY cyclic group of order nn is an nn-cycle.

Side note
Where it goes wrong

Cayley's theorem does NOT say GG equals S∣G∣S_{|G|} or Sym⁡(G)\operatorname{Sym}(G) only that GG is isomorphic to some subgroup of it, usually a tiny one. Z4\mathbb Z_4 has only 44 elements, yet it embeds inside S4S_4, a group of 4!=244! = 24 elements: the image ⟨(0 1 2 3)⟩\langle(0\,1\,2\,3)\rangle is a cyclic subgroup of order 44 sitting inside a far larger group, not all of S4S_4.

Try it
Try it: the regular representation of Z3\mathbb Z_3

In Z3={0,1,2}\mathbb Z_3 = \{0,1,2\} under addition mod 33, find the permutation λ1\lambda_1 (left multiplication by 11) in cycle notation, and give its order.

Show the answer

λ1\lambda_1 sends 0→1→2→00\to1\to2\to0: the permutation is (0 1 2)\mathbf{(0\,1\,2)}, of order 3\mathbf{3}, matching the order of 11 in Z3\mathbb Z_3.

Why It Works

Let σ∈Sn\sigma \in S_n have disjoint cycle decomposition σ=c1c2⋯cm\sigma = c_1c_2\cdots c_m with lengths ℓ1,…,ℓm\ell_1,\ldots,\ell_m (including fixed points as 11-cycles, so every point is covered exactly once). Disjoint cycles move disjoint sets of points, so they commute, and for any kk, σk=c1kc2k⋯cmk\sigma^k = c_1^k c_2^k \cdots c_m^k; since the cic_i act on disjoint sets, σk\sigma^k fixes every point if and only if every single cikc_i^k does. A cycle ci=(a1 a2 ⋯ aℓi)c_i = (a_1\,a_2\,\cdots\,a_{\ell_i}) sends a1↦a1+k mod ℓia_1 \mapsto a_{1+k \bmod \ell_i} under its kk-th power, so cikc_i^k fixes a1a_1, and hence every point of the cycle (each is some power of cic_i applied to a1a_1), exactly when ℓi∣k\ell_i \mid k. Therefore σk=e\sigma^k = e if and only if ℓi∣k\ell_i \mid k for every ii, i.e. kk is a common multiple of ℓ1,…,ℓm\ell_1,\ldots,\ell_m, and the least positive such kk is lcm⁡(ℓ1,…,ℓm)\operatorname{lcm}(\ell_1,\ldots,\ell_m) by definition exactly the order of σ\sigma.

Write c(σ)c(\sigma) for the number of cycles in σ\sigma's disjoint decomposition, counting fixed points as 11-cycles, so c(e)=nc(e) = n. Claim: multiplying σ\sigma on the left by a transposition τ=(a b)\tau = (a\,b) changes c(σ)c(\sigma) by exactly 11: it decreases by 11 if a,ba,b lie in the same cycle of σ\sigma, and increases by 11 if they lie in different cycles. If a,ba,b are in the same cycle, write it as (a x1 ⋯ xr b y1 ⋯ ys)(a\,x_1\,\cdots\,x_r\,b\,y_1\,\cdots\,y_s); composing with (a b)(a\,b) on the left redirects the arrow that pointed into bb to instead point where the arrow into aa used to point, splitting this one cycle into the two cycles (a x1 ⋯ xr)(a\,x_1\,\cdots\,x_r) and (b y1 ⋯ ys)(b\,y_1\,\cdots\,y_s). If a,ba,b lie in different cycles (a x1 ⋯ xr)(a\,x_1\,\cdots\,x_r) and (b y1 ⋯ ys)(b\,y_1\,\cdots\,y_s), the same redirection instead splices the two into the single cycle (a x1 ⋯ xr b y1 ⋯ ys)(a\,x_1\,\cdots\,x_r\,b\,y_1\,\cdots\,y_s). Either way every other cycle of σ\sigma is untouched, so c(τσ)=c(σ)±1c(\tau\sigma) = c(\sigma) \pm 1. Now define ε(σ)=(−1)n−c(σ)\varepsilon(\sigma) = (-1)^{n - c(\sigma)}; the claim says each left multiplication by a transposition flips the sign of ε\varepsilon. Starting from ε(e)=(−1)0=1\varepsilon(e) = (-1)^0 = 1 and building σ=t1t2⋯tk\sigma = t_1 t_2 \cdots t_k by multiplying transpositions one at a time, each step flips the sign, so ε(σ)=(−1)k\varepsilon(\sigma) = (-1)^k. But ε(σ)\varepsilon(\sigma) depends only on σ\sigma's cycle type, not on how it was factored so (−1)k(-1)^k, and hence the parity of kk, is the SAME for every transposition factorization of σ\sigma. Parity is therefore well defined, and sgn⁡(σ)=ε(σ)=(−1)n−c(σ)\operatorname{sgn}(\sigma) = \varepsilon(\sigma) = (-1)^{n-c(\sigma)}, the same formula as (−1)∑(ℓi−1)(-1)^{\sum(\ell_i-1)} from the cycle lengths, since ∑ℓi=n\sum\ell_i = n gives ∑(ℓi−1)=n−m=n−c(σ)\sum(\ell_i - 1) = n - m = n - c(\sigma).

Let GG be a group. For each g∈Gg \in G define λg ⁣:G→G\lambda_g\colon G \to G by λg(x)=gx\lambda_g(x) = gx. Each λg\lambda_g is a bijection: it has inverse λg−1\lambda_{g^{-1}}, since λg−1(λg(x))=g−1(gx)=(g−1g)x=x\lambda_{g^{-1}}(\lambda_g(x)) = g^{-1}(gx) = (g^{-1}g)x = x and likewise the other way, using associativity and the inverse axiom. So λg∈Sym⁡(G)\lambda_g \in \operatorname{Sym}(G) for every gg, giving a function λ ⁣:G→Sym⁡(G)\lambda\colon G \to \operatorname{Sym}(G). This λ\lambda is a homomorphism: for all x∈Gx \in G, λgh(x)=(gh)x=g(hx)=λg(λh(x))=(λgλh)(x)\lambda_{gh}(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x)) = (\lambda_g\lambda_h)(x) by associativity, so λgh=λgλh\lambda_{gh} = \lambda_g\lambda_h. And λ\lambda is injective: if λg=λh\lambda_g = \lambda_h then in particular λg(e)=λh(e)\lambda_g(e) = \lambda_h(e), i.e. ge=hege = he, i.e. g=hg = h. An injective homomorphism is an isomorphism onto its image, so G≅λ(G)≤Sym⁡(G)G \cong \lambda(G) \le \operatorname{Sym}(G): GG is isomorphic to a subgroup of Sym⁡(G)\operatorname{Sym}(G). When GG is finite with ∣G∣=n|G|=n, any bijection between GG and {1,…,n}\{1,\ldots,n\} identifies Sym⁡(G)\operatorname{Sym}(G) with SnS_n, so GG is isomorphic to a subgroup of SnS_n.