A square has eight geometric symmetries, but the moment we label its vertices those symmetries become rearrangements of the set $\{1,2,3,4\}$. This translation is powerful and dangerous at the same time: powerful because it turns motion into algebra, dangerous because the same abstract group can look different when it acts on a different set. A rotation group may act faithfully on vertices, less faithfully on diagonals, and in a completely different way on cosets of a subgroup. Permutation groups answer the central question: what can be learned about a group by watching how it moves points of a set? Instead of treating a group only as a multiplication table, we study its orbits, stabilisers, cycles, signs, and invariant decompositions. The payoff is that many abstract questions become concrete questions about rearrangements. Here is the notation used in the first example. A permutation of a set is a bijective rearrangement of that set. The [symmetric group](/page/Symmetric%20Group) on $\{1,2,3,4\}$ is denoted $S_4$ and consists of all permutations of the four labels. Cycle notation records repeated images: $(1\ 2\ 3\ 4)$ means $1\mapsto 2$, $2\mapsto 3$, $3\mapsto 4$, and $4\mapsto 1$. If $q$ is a group element, then $\langle q\rangle$ denotes the subgroup generated by $q$, meaning all powers of $q$; the notation $H\le G$ means that $H$ is a subgroup of $G$. [example: Rotations of a Square as Permutations] Let $X=\{1,2,3,4\}$ label the vertices of a square in cyclic order, and let $q$ be the quarter-turn rotation sending each vertex to the next labelled vertex. Thus \begin{align*} q(1)=2,\quad q(2)=3,\quad q(3)=4,\quad q(4)=1. \end{align*} By the definition of the cycle $(1\ 2\ 3\ 4)$, this is exactly the permutation \begin{align*} q=(1\ 2\ 3\ 4)\in S_4. \end{align*} We compute the powers of $q$ by applying $q$ repeatedly to each element of $X$. For the square $q^2$, we get \begin{align*} q^2(1)=q(q(1))=q(2)=3,\quad q^2(3)=q(q(3))=q(4)=1. \end{align*} Also, \begin{align*} q^2(2)=q(q(2))=q(3)=4,\quad q^2(4)=q(q(4))=q(1)=2. \end{align*} Thus $q^2$ sends $1\mapsto 3\mapsto 1$ and $2\mapsto 4\mapsto 2$, so \begin{align*} q^2=(1\ 3)(2\ 4). \end{align*} For the third power, use the values of $q^2$ just computed: \begin{align*} q^3(1)=q(q^2(1))=q(3)=4,\quad q^3(4)=q(q^2(4))=q(2)=3. \end{align*} Similarly, \begin{align*} q^3(3)=q(q^2(3))=q(1)=2,\quad q^3(2)=q(q^2(2))=q(4)=1. \end{align*} Therefore $q^3$ sends $1\mapsto 4$, $4\mapsto 3$, $3\mapsto 2$, and $2\mapsto 1$, so \begin{align*} q^3=(1\ 4\ 3\ 2). \end{align*} For the fourth power, apply $q$ once more: \begin{align*} q^4(1)=q(q^3(1))=q(4)=1,\quad q^4(2)=q(q^3(2))=q(1)=2. \end{align*} Also, \begin{align*} q^4(3)=q(q^3(3))=q(2)=3,\quad q^4(4)=q(q^3(4))=q(3)=4. \end{align*} Since $q^4$ fixes every element of $X$, we have \begin{align*} q^4=\operatorname{id}_X. \end{align*} The subgroup generated by $q$ consists of the distinct powers before the identity repeats: \begin{align*} \langle q\rangle=\{\operatorname{id}_X,q,q^2,q^3\}. \end{align*} Substituting the computed cycle forms gives \begin{align*} \langle q\rangle=\{\operatorname{id}_X,(1\ 2\ 3\ 4),(1\ 3)(2\ 4),(1\ 4\ 3\ 2)\}\le S_4. \end{align*} Labelling the vertices has turned the geometric rotation group of the square into a concrete subgroup of the symmetric group on the four vertex labels. [/example] The same square also shows the first failure mode. If the rotations act on the two diagonals instead of the four vertices, the half-turn becomes invisible, so the action no longer remembers the full cyclic rotation group. We need definitions that keep track of both the group and the set being moved. ## Definition Before a group of rearrangements can be studied, we need the individual rearrangements. A permutation of a set $X$ is a bijective function \begin{align*} \sigma: X \to X. \end{align*} A single permutation is only one motion, so it is not enough for studying a whole symmetry system. The symmetric group on $X$, denoted $\operatorname{Sym}(X)$, collects all permutations of $X$ into one group under composition. For $X=\{1,\dots,n\}$, this group is denoted $S_n$. The full symmetric group is usually too large: a square does not admit every rearrangement of its vertices as a geometric symmetry. The next definition names the smaller collection of rearrangements that are actually allowed in a given problem. [definition: Permutation Group] A permutation group on a set $X$ is a subgroup \begin{align*} G \le \operatorname{Sym}(X). \end{align*} The set $X$ is called the permutation domain of $G$. [/definition] This definition is deliberately concrete. It remembers the ambient set, so it can distinguish two actions of the same abstract group when they move different domains or forget different elements. To explain where such subgroups come from, we now pass from listed permutations to actions of abstract groups. [example: Two Actions of $C_4$] Let $C_4=\langle r:r^4=e\rangle$. We compare two ways for the same abstract group to act by permutations. First let $C_4$ act on $X=\{1,2,3,4\}$ by sending the generator $r$ to \begin{align*} \sigma=(1\ 2\ 3\ 4). \end{align*} By the definition of this cycle, \begin{align*} \sigma(1)=2,\quad \sigma(2)=3,\quad \sigma(3)=4,\quad \sigma(4)=1. \end{align*} Compute the powers by applying $\sigma$ repeatedly. For $\sigma^2$, \begin{align*} \sigma^2(1)=\sigma(\sigma(1))=\sigma(2)=3,\quad \sigma^2(3)=\sigma(\sigma(3))=\sigma(4)=1. \end{align*} Also, \begin{align*} \sigma^2(2)=\sigma(\sigma(2))=\sigma(3)=4,\quad \sigma^2(4)=\sigma(\sigma(4))=\sigma(1)=2. \end{align*} Thus $\sigma^2$ swaps $1$ with $3$ and swaps $2$ with $4$, so \begin{align*} \sigma^2=(1\ 3)(2\ 4). \end{align*} For the third power, \begin{align*} \sigma^3(1)=\sigma(\sigma^2(1))=\sigma(3)=4,\quad \sigma^3(4)=\sigma(\sigma^2(4))=\sigma(2)=3. \end{align*} Similarly, \begin{align*} \sigma^3(3)=\sigma(\sigma^2(3))=\sigma(1)=2,\quad \sigma^3(2)=\sigma(\sigma^2(2))=\sigma(4)=1. \end{align*} So $\sigma^3$ sends $1\mapsto 4\mapsto 3\mapsto 2\mapsto 1$, and therefore \begin{align*} \sigma^3=(1\ 4\ 3\ 2). \end{align*} For the fourth power, \begin{align*} \sigma^4(1)=\sigma(\sigma^3(1))=\sigma(4)=1,\quad \sigma^4(2)=\sigma(\sigma^3(2))=\sigma(1)=2. \end{align*} Also, \begin{align*} \sigma^4(3)=\sigma(\sigma^3(3))=\sigma(2)=3,\quad \sigma^4(4)=\sigma(\sigma^3(4))=\sigma(3)=4. \end{align*} Hence $\sigma^4$ fixes every element of $X$, so \begin{align*} \sigma^4=\operatorname{id}_X. \end{align*} The defining relation $r^4=e$ is therefore respected by the assignment $r\mapsto\sigma$. The induced permutation group is \begin{align*} \langle \sigma\rangle=\{\operatorname{id}_X,(1\ 2\ 3\ 4),(1\ 3)(2\ 4),(1\ 4\ 3\ 2)\}\le S_4. \end{align*} These four permutations are distinct because their values at $1$ are respectively $1,2,3,4$. Thus this action distinguishes the four elements $e,r,r^2,r^3$ of $C_4$. Now let $C_4$ act on $Y=\{a,b\}$ by sending $r$ to \begin{align*} \tau=(a\ b). \end{align*} Then \begin{align*} \tau(a)=b,\quad \tau(b)=a. \end{align*} Applying $\tau$ twice gives \begin{align*} \tau^2(a)=\tau(\tau(a))=\tau(b)=a,\quad \tau^2(b)=\tau(\tau(b))=\tau(a)=b. \end{align*} Thus $\tau^2$ fixes every element of $Y$, so \begin{align*} \tau^2=\operatorname{id}_Y. \end{align*} Consequently, \begin{align*} \tau^4=\tau^2\tau^2=\operatorname{id}_Y\operatorname{id}_Y=\operatorname{id}_Y. \end{align*} The relation $r^4=e$ is again respected. The four powers of the generator act as \begin{align*} e\mapsto \operatorname{id}_Y,\quad r\mapsto (a\ b),\quad r^2\mapsto \operatorname{id}_Y,\quad r^3\mapsto (a\ b), \end{align*} because $\tau^0=\operatorname{id}_Y$, $\tau^1=\tau$, $\tau^2=\operatorname{id}_Y$, and $\tau^3=\tau^2\tau=\operatorname{id}_Y\tau=\tau$. Therefore the induced permutation group is \begin{align*} \{\operatorname{id}_Y,(a\ b)\}\le \operatorname{Sym}(Y). \end{align*} The first action remembers all four powers of the generator, while the second identifies $e$ with $r^2$ and identifies $r$ with $r^3$; it records only whether the exponent of $r$ is even or odd. [/example] The example raises a structural question: how does an abstract group produce permutations of a set without first being given as a subgroup of a symmetric group? The next definition is needed because it records the compatibility between group multiplication and the motion of points. [definition: Group Action] Let $G$ be a group and let $X$ be a set. A left action of $G$ on $X$ is a map \begin{align*} G \times X \to X \end{align*} written $(g,x) \mapsto g \cdot x$, such that for all $g,h \in G$ and all $x \in X$, \begin{align*} e \cdot x = x \end{align*} and \begin{align*} g \cdot (h \cdot x) = (gh) \cdot x. \end{align*} [/definition] The action axioms say exactly that each group element acts as a permutation and that multiplication in $G$ matches composition of the resulting permutations. This motivates the formal bridge from actions to symmetric groups. [quotetheorem:5004] The homomorphism $\rho$ is called the permutation representation associated with the action. Because a representation may collapse non-identity elements, the next question is when the action loses no group information. [definition: Faithful Action] Let $G$ be a group acting on a set $X$. The action is faithful if the associated homomorphism \begin{align*} \rho: G \to \operatorname{Sym}(X) \end{align*} is injective. [/definition] Faithfulness is often checked by asking which elements fix every point of the domain. If a non-identity element fixes every point, then the action cannot distinguish it from the identity permutation. The obstruction to faithfulness is therefore the subgroup of elements that act invisibly on all of $X$, and this subgroup should coincide with the kernel of the permutation representation. [quotetheorem:10134] The criterion makes faithful actions measurable, but it does not yet say that every group has one. Without a general source of faithful actions, permutation groups would be a special class rather than a model for all finite group behaviour. To show that permutation actions are not merely examples but a universal language for finite groups, we need a canonical faithful action attached to an arbitrary group. The left-regular action provides exactly this: each group element moves the group itself, so no non-identity element can act invisibly. [quotetheorem:795] Cayley’s theorem is reassuring but not always economical. It embeds a group of order $n$ into $S_n$, while a smaller faithful action may exist and may reveal more structure. ## Orbits and Stabilisers Once a group acts, the first structural question is which points can be reached from which other points. The reachable set from a point is its orbit. [definition: Orbit] Let $G$ act on a set $X$, and let $x \in X$. The orbit of $x$ is \begin{align*} G \cdot x = \{g \cdot x : g \in G\} \subset X. \end{align*} [/definition] An action with several orbits decomposes into independent pieces, while some actions have only one reachable piece. To separate these two situations cleanly, we need a term for actions in which there is no orbit-level separation at all: every point can be transported to every other point by some group element. [definition: Transitive Action] Let $G$ act on a set $X$. The action is transitive if for all $x,y \in X$, there exists $g \in G$ such that \begin{align*} g \cdot x = y. \end{align*} [/definition] Reachability describes movement away from a point, but symmetry also has a local part. To count and compare transitive actions, we need the subgroup of elements that keep a chosen point fixed. [definition: Stabiliser] Let $G$ act on a set $X$, and let $x \in X$. The stabiliser of $x$ in $G$ is \begin{align*} G_x = \{g \in G : g \cdot x = x\}. \end{align*} [/definition] The orbit and stabiliser measure opposite features of the same action. A group element is determined, for counting purposes, by where it sends a chosen point and by the residual freedom left after that destination is fixed. This creates a concrete counting problem: can the size of the whole group be recovered from the number of possible destinations and the number of symmetries that keep the chosen point still? For finite actions, the answer is the orbit-stabiliser formula. The formula also uses coset notation. If $H\le G$ and $g\in G$, then the left coset $gH$ is the subset $\{gh:h\in H\}$ of $G$. The notation $G/H$ means the set of all left cosets of $H$ in $G$; here it is a quotient set, not necessarily a [quotient group](/theorems/790). In particular, $G/G_x$ denotes the set of left cosets of the stabiliser $G_x$. The obstruction to counting the orbit directly is that many group elements can send $x$ to the same point. If $g\cdot x=h\cdot x$, then $h^{-1}g$ fixes $x$, so $g$ and $h$ differ by an element of the stabiliser. Conversely, multiplying by an element of $G_x$ does not change the image of $x$. Thus each possible destination should correspond to one left coset of $G_x$, and the theorem below packages this correspondence into both a bijection and a counting formula. [quotetheorem:845] This theorem turns many counting problems into stabiliser computations. It also explains why transitive actions can be studied by focusing on a single point and its stabiliser. [example: Stabiliser of a Vertex in $D_8$] Let $D_8$ act on the vertices $X=\{1,2,3,4\}$ of a square labelled in cyclic order. Write the quarter-turn as $q=(1\ 2\ 3\ 4)$, and let $s=(2\ 4)$ be the reflection through the diagonal joining vertices $1$ and $3$. We use right-to-left composition, so $qs$ means first apply $s$ and then apply $q$. The eight symmetries are \begin{align*} D_8=\{\operatorname{id},q,q^2,q^3,s,qs,q^2s,q^3s\}. \end{align*} The powers of $q$ move vertex $1$ through all four vertices. Since $q=(1\ 2\ 3\ 4)$, \begin{align*} \operatorname{id}(1)=1,\quad q(1)=2,\quad q^2(1)=q(q(1))=q(2)=3,\quad q^3(1)=q(q^2(1))=q(3)=4. \end{align*} Therefore $1,2,3,4\in D_8\cdot 1$. Since every element of $D_8$ is a permutation of $X$, every image of $1$ lies in $X$, so $D_8\cdot 1\subseteq X$. Hence \begin{align*} D_8\cdot 1=\{1,2,3,4\}. \end{align*} Now compute which of the eight listed elements fix $1$. Among the rotations, \begin{align*} \operatorname{id}(1)=1,\quad q(1)=2,\quad q^2(1)=3,\quad q^3(1)=4, \end{align*} so the only rotation fixing $1$ is $\operatorname{id}$. Since $s=(2\ 4)$, the points moved by $s$ are $2$ and $4$, so \begin{align*} s(1)=1. \end{align*} Using right-to-left composition, the reflected elements send $1$ to \begin{align*} qs(1)=q(s(1))=q(1)=2,\quad q^2s(1)=q^2(s(1))=q^2(1)=3,\quad q^3s(1)=q^3(s(1))=q^3(1)=4. \end{align*} Thus exactly two elements of $D_8$ fix $1$, namely $\operatorname{id}$ and $s$, so \begin{align*} (D_8)_1=\{\operatorname{id},s\}. \end{align*} The orbit has four elements and the stabiliser has two elements: \begin{align*} |D_8\cdot 1|=4,\quad |(D_8)_1|=2. \end{align*} Multiplying gives \begin{align*} |D_8\cdot 1|\, |(D_8)_1|=4\cdot 2=8=|D_8|. \end{align*} The orbit records the four possible destinations of vertex $1$, while the stabiliser records the two symmetries that leave that vertex in place. [/example] If the action is not transitive, orbit-stabiliser applies separately to each reachable piece. For this piece-by-piece analysis to make sense, reachable sets must not overlap partially. The key structural question is whether two orbits can share a point without being the same orbit. The answer rules out tangled overlap and shows that the domain breaks into disjoint orbit pieces. [quotetheorem:5001] This partition result is what lets us study a non-transitive action one orbit at a time: every point belongs to exactly one reachable piece, and no element can sit halfway between two different pieces. It also explains why later calculations can focus on the motion inside a single orbit without losing information about the rest of the set. A particularly important special case comes from letting one permutation act by repeated application. Then its orbits are the finite loops that appear in cycle notation. ## Cycle Structure ### Single Permutations For a finite permutation group, it is useful to understand one permutation at a time. Repeatedly applying a single permutation makes each point travel around a finite loop, and the notation for that loop is a cycle. [definition: Cycle] Let $X$ be a set and let $x_1,\dots,x_k \in X$ be distinct elements with $k \ge 2$. The cycle $(x_1\ x_2\ \cdots\ x_k)$ is the permutation $\sigma \in \operatorname{Sym}(X)$ defined by \begin{align*} \sigma(x_i) = x_{i+1} \text{ for } 1 \le i < k \end{align*} and \begin{align*} \sigma(x_k) = x_1, \end{align*} with $\sigma(x) = x$ for all $x \in X \setminus \{x_1,\dots,x_k\}$. [/definition] Cycles move only the points that appear in them, while every other point is fixed. When multiplying permutations, it matters which points are actually affected and which are spectators. To state this distinction without repeatedly listing fixed and moved points, we need a compact way to isolate the active part of a permutation. This is especially useful when comparing two permutations: if their active parts do not overlap, then their actions cannot interfere point by point. The support records exactly the points where a permutation differs from the identity, leaving all fixed points outside the notation. [definition: Support of a Permutation] Let $X$ be a set and let $\sigma \in \operatorname{Sym}(X)$. The support of $\sigma$ is \begin{align*} \operatorname{supp}(\sigma) = \{x \in X : \sigma(x) \ne x\}. \end{align*} [/definition] Once support is available, we can express independence between cycles precisely. The obstruction to independence is overlap in the points they move: if two cycles both act on some point, their effects can interfere. When their supports are separate, each cycle changes a different part of the set, which is the condition we need to name. [definition: Disjoint Cycles] Let $X$ be a set. Two cycles $\sigma,\tau \in \operatorname{Sym}(X)$ are disjoint if \begin{align*} \operatorname{supp}(\sigma) \cap \operatorname{supp}(\tau) = \varnothing. \end{align*} [/definition] Disjoint cycles give independent simultaneous motions, but a general permutation may initially look like an unstructured rearrangement. Starting from any point and repeatedly applying the permutation traces a finite loop; points not yet visited begin new loops. The question is whether this process always accounts for every point and produces a canonical product of independent cycles. [quotetheorem:775] [Disjoint cycle decomposition](/theorems/775) is the structural reason permutations become computable objects rather than arbitrary bijections. It separates the action of a permutation into independent loops, so questions about powers, orders, fixed points, and comparison between permutations can be reduced to the lengths of those loops. The uniqueness is just as important as existence: it means that the list of cycle lengths is not an artifact of how we happened to write the permutation, but an invariant attached to the permutation itself. ### Cycle Type and Conjugacy A relabelling of the underlying set changes the names in the cycles but preserves the cycle lengths. To capture the part of cycle decomposition that survives relabelling, we use cycle type. [definition: Cycle Type] Let $\sigma \in S_n$. The cycle type of $\sigma$ is the partition of $n$ obtained by listing the lengths of the disjoint cycles in the disjoint cycle decomposition of $\sigma$, including fixed points as cycles of length $1$. [/definition] Cycle type is a useful invariant for any subgroup of $S_n$, but in the whole symmetric group it fully determines conjugacy. This makes conjugacy in $S_n$ a combinatorial question about partitions of $n$. [quotetheorem:798] This theorem is a classification result for conjugacy inside the full symmetric group. It says that once every relabelling of the underlying symbols is available, the only information that survives conjugation is the multiset of cycle lengths. The qualification "inside $S_n$" matters: in a proper subgroup of $S_n$, two permutations can have the same cycle type but fail to be conjugate because the relabelling that conjugates them may not lie in the subgroup. This is why permutation-group arguments often distinguish statements about the whole symmetric group from statements about its subgroups. [example: Cycle Type and Order] Let \begin{align*} \sigma = (1\ 4\ 2)(3\ 5) \in S_5. \end{align*} The support of $(1\ 4\ 2)$ is $\{1,4,2\}$, and the support of $(3\ 5)$ is $\{3,5\}$. These supports are disjoint, and together they contain all five symbols. Therefore the disjoint cycle lengths are $3$ and $2$, with no fixed symbols left over, so the cycle type of $\sigma$ is $(3,2)$. We compute the order by tracking the two disjoint cycles separately. On the $3$-cycle, \begin{align*} \sigma(1)=4,\quad \sigma^2(1)=\sigma(4)=2,\quad \sigma^3(1)=\sigma(2)=1. \end{align*} Starting from $4$ gives \begin{align*} \sigma(4)=2,\quad \sigma^2(4)=\sigma(2)=1,\quad \sigma^3(4)=\sigma(1)=4. \end{align*} Starting from $2$ gives \begin{align*} \sigma(2)=1,\quad \sigma^2(2)=\sigma(1)=4,\quad \sigma^3(2)=\sigma(4)=2. \end{align*} Thus $\sigma^3$ fixes $1,4,2$. The smaller positive powers do not fix this whole cycle, since \begin{align*} \sigma(1)=4\ne 1,\quad \sigma^2(1)=2\ne 1. \end{align*} Hence $\sigma^m$ fixes $1,4,2$ exactly when $3\mid m$. On the transposition, \begin{align*} \sigma(3)=5,\quad \sigma^2(3)=\sigma(5)=3. \end{align*} Also, \begin{align*} \sigma(5)=3,\quad \sigma^2(5)=\sigma(3)=5. \end{align*} So $\sigma^2$ fixes $3$ and $5$, while $\sigma$ does not, because $\sigma(3)=5\ne 3$. Hence $\sigma^m$ fixes $3,5$ exactly when $2\mid m$. The permutation $\sigma^m$ is the identity exactly when it fixes every symbol $1,2,3,4,5$. From the two computations above, this requires and is required by \begin{align*} 3\mid m \quad\text{and}\quad 2\mid m. \end{align*} The least positive integer divisible by both $3$ and $2$ is $6$, so \begin{align*} \operatorname{ord}(\sigma)=\operatorname{lcm}(3,2)=6. \end{align*} This example shows that cycle notation records both the relabelling-invariant cycle type and the arithmetic needed to compute powers. [/example] ## Generators, Parity, and Alternating Groups ### Elementary Swaps Large permutation groups are often controlled by small motions, and the smallest non-identity motion exchanges two points while leaving everything else fixed. These swaps are the elementary moves behind many decompositions of permutations, so they need a separate name before they can be used as generators. [definition: Transposition] Let $X$ be a set. A transposition is a cycle of length $2$ in $\operatorname{Sym}(X)$. [/definition] A definition of transposition is useful only because swaps can build more complicated rearrangements. The basic generation problem is whether arbitrary finite permutations require larger cycles as primitive moves, or whether repeated two-point exchanges already suffice. Sorting a permutation back to the identity by successive swaps suggests that transpositions generate the full symmetric group. [quotetheorem:8540] For computations, adjacent swaps are even more efficient because they mirror sorting by neighbouring exchanges. The next generating theorem is the algebraic form of that idea. [quotetheorem:10135] This theorem says more than the earlier transposition-generation result: the whole group is generated by the $n-1$ nearest-neighbour swaps alone. That makes the result computational, because it is the algebraic form of sorting by moving entries one position at a time. Its limitation is just as important: it gives existence of an adjacent-swap word, not a canonical or unique word for the permutation. The next invariant asks what remains well defined when the chosen sequence of swaps is allowed to change. ### Parity A permutation can have many transposition decompositions, so the raw number of swaps is not an invariant of the permutation. The useful question is whether two different decompositions can disagree in parity. If parity is forced to be the same across all decompositions, then evenness and oddness become intrinsic properties of the permutation rather than artifacts of a chosen factorisation. [quotetheorem:7876] Because parity is stable, it can be used as a genuine invariant. To use parity in computations, we need to package it as a function rather than as a phrase about decompositions. The natural values are multiplicative, assigning one value to permutations built from an even number of swaps and the other to permutations built from an odd number. [definition: Sign of a Permutation] Let $n \ge 1$. The sign map is the function \begin{align*} \operatorname{sgn}:S_n\to\{1,-1\} \end{align*} defined by sending a permutation $\sigma\in S_n$ to $1$ if $\sigma$ is expressible as a product of an even number of transpositions and to $-1$ if $\sigma$ is expressible as a product of an odd number of transpositions. [/definition] The sign does not merely classify individual permutations; it should also interact with multiplication. The obstruction is that parity was defined using factorizations into transpositions, so it is not automatic that the sign of a product is the product of the signs. We need this compatibility before sign can be used as a homomorphism and before its kernel can be treated as a [normal subgroup](/page/Normal%20Subgroup). [quotetheorem:778] Once sign is a homomorphism, the even permutations are no longer just a parity class; they form the kernel of a group map. The kernel construction turns the parity condition into a subgroup with its own internal multiplication. This removes a recurring obstruction in later arguments: if we only refer to "the even elements of $S_n$," every use has to recheck that products and inverses stay even. Naming the kernel records that closure once and lets the even permutations be treated as a group in their own right, with the operation inherited from $S_n$. [definition: Alternating Group] For $n \ge 1$, the alternating group $A_n$ is \begin{align*} A_n = \ker(\operatorname{sgn}: S_n \to \{1,-1\}). \end{align*} [/definition] After defining $A_n$, the first numerical question is its size. The possible obstruction is imbalance: a priori there could be more even permutations than odd ones, or conversely. For $n \ge 2$, multiplication by a fixed transposition pairs each even permutation with an odd one, so the even permutations should account for exactly half of $S_n$. [quotetheorem:7880] [example: Even and Odd Permutations in $S_4$] In $S_4$, the transposition $(1\ 2)$ is itself a product of one transposition, so by the definition of sign, \begin{align*} \operatorname{sgn}(1\ 2)=-1. \end{align*} The same argument applies to every transposition in $S_4$. Now consider the $3$-cycle $(1\ 2\ 3)$. With right-to-left composition, the product $(1\ 3)(1\ 2)$ sends $1$ to $2$, since \begin{align*} (1\ 3)(1\ 2)(1)=(1\ 3)(2)=2. \end{align*} It sends $2$ to $3$, since \begin{align*} (1\ 3)(1\ 2)(2)=(1\ 3)(1)=3. \end{align*} It sends $3$ to $1$, since \begin{align*} (1\ 3)(1\ 2)(3)=(1\ 3)(3)=1. \end{align*} It fixes $4$, since \begin{align*} (1\ 3)(1\ 2)(4)=(1\ 3)(4)=4. \end{align*} Therefore \begin{align*} (1\ 2\ 3)=(1\ 3)(1\ 2). \end{align*} This expression uses two transpositions, so \begin{align*} \operatorname{sgn}(1\ 2\ 3)=1. \end{align*} More generally, for distinct $a,b,c$, the same calculation gives \begin{align*} (a\ b\ c)=(a\ c)(a\ b), \end{align*} so every $3$-cycle in $S_4$ is even. The double transposition $(1\ 2)(3\ 4)$ is already written as a product of two transpositions. Hence \begin{align*} \operatorname{sgn}((1\ 2)(3\ 4))=1. \end{align*} The same applies to every product of two disjoint transpositions. For comparison, a $4$-cycle is odd. For example, with right-to-left composition, \begin{align*} (1\ 4)(1\ 3)(1\ 2)(1)=(1\ 4)(1\ 3)(2)=(1\ 4)(2)=2. \end{align*} Also, \begin{align*} (1\ 4)(1\ 3)(1\ 2)(2)=(1\ 4)(1\ 3)(1)=(1\ 4)(3)=3. \end{align*} Next, \begin{align*} (1\ 4)(1\ 3)(1\ 2)(3)=(1\ 4)(1\ 3)(3)=(1\ 4)(1)=4. \end{align*} Finally, \begin{align*} (1\ 4)(1\ 3)(1\ 2)(4)=(1\ 4)(1\ 3)(4)=(1\ 4)(4)=1. \end{align*} Thus \begin{align*} (1\ 2\ 3\ 4)=(1\ 4)(1\ 3)(1\ 2), \end{align*} so this $4$-cycle is a product of three transpositions and has sign $-1$. The same formula \begin{align*} (a\ b\ c\ d)=(a\ d)(a\ c)(a\ b) \end{align*} shows that every $4$-cycle in $S_4$ is odd. We now count the even permutations in $S_4$. There is one identity permutation, and it is even because it is a product of zero transpositions: \begin{align*} \operatorname{sgn}(\operatorname{id})=1. \end{align*} To form a $3$-cycle, choose the three moved symbols from $\{1,2,3,4\}$, giving \begin{align*} \binom{4}{3}=4 \end{align*} choices. On a chosen three-element set $\{a,b,c\}$, the two distinct $3$-cycles are \begin{align*} (a\ b\ c)\quad\text{and}\quad(a\ c\ b). \end{align*} The three cyclic rotations of the first notation give the same permutation: \begin{align*} (a\ b\ c)=(b\ c\ a)=(c\ a\ b). \end{align*} The three cyclic rotations of the reverse notation also give the same permutation: \begin{align*} (a\ c\ b)=(c\ b\ a)=(b\ a\ c). \end{align*} Thus the number of $3$-cycles in $S_4$ is \begin{align*} \binom{4}{3}\cdot 2=4\cdot 2=8. \end{align*} The double transpositions pair the four symbols into two unordered pairs. Listing the pair containing $1$ gives all possibilities: \begin{align*} (1\ 2)(3\ 4),\quad (1\ 3)(2\ 4),\quad (1\ 4)(2\ 3). \end{align*} So there are $3$ double transpositions. Every permutation in $S_4$ has one of the following cycle shapes: the identity, a transposition, a product of two disjoint transpositions, a $3$-cycle with one fixed point, or a $4$-cycle. The even ones among these are exactly the identity, the $3$-cycles, and the double transpositions. Since $A_4$ is the subgroup of even permutations, \begin{align*} |A_4|=1+8+3=12. \end{align*} Thus parity separates $S_4$ into twelve even permutations and twelve odd permutations: the identity, $3$-cycles, and double transpositions lie in $A_4$, while transpositions and $4$-cycles lie outside it. [/example] ## Blocks and Primitive Actions Transitivity says that the group can move any point to any other point, but it may still preserve a decomposition of the set into larger pieces. Blocks are designed to detect such hidden systems. [definition: Block of Imprimitivity] Let $G$ act transitively on a set $X$. A nonempty subset $B \subset X$ is a block of imprimitivity if for every $g \in G$, \begin{align*} gB = B \text{ or } gB \cap B = \varnothing, \end{align*} where $gB = \{g \cdot b : b \in B\}$. [/definition] A block moves as a unit: every group element either preserves it or sends it away from itself. However, singleton subsets and $X$ itself always behave this way, so they do not reveal any hidden decomposition. The real obstruction to irreducible transitive behaviour is an intermediate block system; actions without such intermediate blocks need a separate name. [definition: Primitive Action] Let $G$ act transitively on a set $X$. The action is primitive if the only blocks of imprimitivity are the singleton subsets of $X$ and the whole set $X$. [/definition] Primitive actions are transitive actions with no nontrivial block system. When such a system does exist, we need the complementary term because the action can often be reduced to an action on blocks together with actions inside the blocks. [definition: Imprimitive Action] Let $G$ act transitively on a set $X$. The action is imprimitive if there exists a block of imprimitivity $B \subset X$ such that \begin{align*} 1 < |B| < |X|. \end{align*} [/definition] The primitive-imprimitive distinction is one of the main organising principles for finite permutation groups. To use it effectively, we need a test that does not require searching through all subsets of $X$. The obstruction to primitivity is a nontrivial block containing a chosen point, and such a block is controlled by the elements of $G$ that preserve that point. This turns the question into one about intermediate subgroups between a point stabiliser and the whole group. [quotetheorem:10136] The criterion converts a geometric-looking question about invariant block systems into a subgroup question. The transitivity hypothesis is essential, because without one orbit tying the domain together, stabilisers at different points do not control the whole action uniformly. In practice, the theorem is used in two directions: maximality of a point stabiliser proves primitivity, while an intermediate subgroup between $G_x$ and $G$ produces a nontrivial block system and therefore proves imprimitivity. The next example illustrates the second direction by making such a preserved block system visible. [example: An Imprimitive Action on Four Points] Let \begin{align*} G = \langle (1\ 2), (3\ 4), (1\ 3)(2\ 4) \rangle \le S_4 \end{align*} act on $X=\{1,2,3,4\}$. Write \begin{align*} a=(1\ 2),\quad b=(3\ 4),\quad c=(1\ 3)(2\ 4). \end{align*} We first show that the action is transitive. Since $a\in G$, $c\in G$, and $bc\in G$, the point $1$ reaches the other three points as follows: \begin{align*} \operatorname{id}(1)=1,\quad a(1)=2,\quad c(1)=3,\quad bc(1)=b(c(1))=b(3)=4. \end{align*} Therefore every point of $X$ lies in the orbit of $1$: \begin{align*} X=\{1,2,3,4\}\subseteq G\cdot 1. \end{align*} Conversely, every element of $G$ is a permutation of $X$, so every image of $1$ under an element of $G$ lies in $X$. Hence \begin{align*} G\cdot 1\subseteq X. \end{align*} The two inclusions give \begin{align*} G\cdot 1=X. \end{align*} Now let $x,y\in X$. Since $G\cdot 1=X$, there exist $u,v\in G$ such that \begin{align*} u(1)=x,\quad v(1)=y. \end{align*} Because $G$ is a subgroup, $u^{-1}\in G$ and $vu^{-1}\in G$. Applying this element to $x$ gives \begin{align*} vu^{-1}(x)=vu^{-1}(u(1))=v(1)=y. \end{align*} Thus for every $x,y\in X$ there is an element of $G$ sending $x$ to $y$, so the action is transitive. Now let \begin{align*} B=\{1,2\},\quad C=\{3,4\}. \end{align*} We compute the images of these two subsets under the generators. For $a=(1\ 2)$, \begin{align*} aB=\{a(1),a(2)\}=\{2,1\}=B,\quad aC=\{a(3),a(4)\}=\{3,4\}=C. \end{align*} For $b=(3\ 4)$, \begin{align*} bB=\{b(1),b(2)\}=\{1,2\}=B,\quad bC=\{b(3),b(4)\}=\{4,3\}=C. \end{align*} For $c=(1\ 3)(2\ 4)$, \begin{align*} cB=\{c(1),c(2)\}=\{3,4\}=C,\quad cC=\{c(3),c(4)\}=\{1,2\}=B. \end{align*} Each generator is its own inverse: \begin{align*} a^2=\operatorname{id},\quad b^2=\operatorname{id},\quad c^2=\operatorname{id}. \end{align*} Hence \begin{align*} a^{-1}=a,\quad b^{-1}=b,\quad c^{-1}=c. \end{align*} So every generator and every inverse generator sends each of the two sets $B,C$ to one of the two sets $B,C$. Every element $g\in G$ is a finite product of letters chosen from $a,b,c,a^{-1},b^{-1},c^{-1}$. Starting with $B$, after applying the first letter the image is either $B$ or $C$; after applying the second letter it is again either $B$ or $C$; continuing through the word shows that \begin{align*} gB=B \text{ or } gB=C. \end{align*} If $gB=B$, then \begin{align*} gB\cap B=B. \end{align*} If $gB=C$, then \begin{align*} gB\cap B=C\cap B=\varnothing. \end{align*} Thus for every $g\in G$, \begin{align*} gB=B \text{ or } gB\cap B=\varnothing. \end{align*} So $B$ is a block of imprimitivity. Finally, \begin{align*} 1<|B|=2<4=|X|. \end{align*} Therefore the transitive action is imprimitive: it preserves the two-point block system $\{\{1,2\},\{3,4\}\}$. [/example] ## Coset Actions and Internal Structure A group can act on structures built from its own subgroups. If $H \le G$, left multiplication moves the left cosets of $H$, giving a transitive action whose stabiliser remembers $H$. [definition: Coset Action] Let $G$ be a group and let $H \le G$. The left coset action of $G$ on $G/H$ is the action \begin{align*} g \cdot (aH) = (ga)H \end{align*} for $g,a \in G$. [/definition] Coset actions are the standard model for transitive actions, but the model is useful only after the base point calculation is known. The first issue is whether left multiplication really reaches every coset and which elements leave the distinguished coset $H$ fixed. These two checks show exactly how the subgroup $H$ is visible inside the action. The next formal result records this base point calculation so that coset actions can be used without recomputing their transitivity and stabilisers each time. It turns the definition into a reusable bridge between subgroup data and action-theoretic data. [quotetheorem:4967] After that calculation, a broader question remains: does every transitive action arise in this way, or are coset actions only a special family? Choosing one point $x \in X$ in a transitive action gives a stabiliser $G_x$, and transitivity suggests that every point of $X$ should be represented by some coset of $G_x$. The obstruction to this representation is well-definedness: different group elements may carry $x$ to the same point, and the coset description must identify exactly those elements. [quotetheorem:845] A coset action may still have a kernel, so the subgroup $H$ alone does not reveal whether the action is faithful. The next definition is needed to name the part of $H$ that survives conjugation by every element of $G$ and is therefore invisible in the coset action. [definition: Core of a Subgroup] Let $G$ be a group and let $H \le G$. The core of $H$ in $G$ is \begin{align*} \operatorname{Core}_G(H) = \bigcap_{g \in G} gHg^{-1}. \end{align*} [/definition] The core is the part of $H$ that remains normal inside all of $G$. It is exactly the subgroup that acts invisibly on the coset space. [quotetheorem:10137] [example: Action of $S_3$ on Cosets of $A_3$] Let $G=S_3$ and $H=A_3$. Explicitly, \begin{align*} H=A_3=\{\operatorname{id},(1\ 2\ 3),(1\ 3\ 2)\}. \end{align*} We use right-to-left composition. The left coset represented by $(1\ 2)$ is \begin{align*} (1\ 2)H=\{(1\ 2),(1\ 2)(1\ 2\ 3),(1\ 2)(1\ 3\ 2)\}. \end{align*} For the product $(1\ 2)(1\ 2\ 3)$, the right factor acts first. Tracking the three symbols gives \begin{align*} 1\mapsto 2\mapsto 1,\quad 2\mapsto 3\mapsto 3,\quad 3\mapsto 1\mapsto 2. \end{align*} Thus $1$ is fixed, $2$ is sent to $3$, and $3$ is sent to $2$, so \begin{align*} (1\ 2)(1\ 2\ 3)=(2\ 3). \end{align*} For the product $(1\ 2)(1\ 3\ 2)$, tracking symbols gives \begin{align*} 1\mapsto 3\mapsto 3,\quad 2\mapsto 1\mapsto 2,\quad 3\mapsto 2\mapsto 1. \end{align*} Thus $2$ is fixed, $1$ is sent to $3$, and $3$ is sent to $1$, so \begin{align*} (1\ 2)(1\ 3\ 2)=(1\ 3). \end{align*} Hence \begin{align*} (1\ 2)H=\{(1\ 2),(2\ 3),(1\ 3)\}. \end{align*} The three elements of $H$ are the even permutations in $S_3$, and the three elements of $(1\ 2)H$ are the transpositions, so the six elements of $S_3$ split into the two left cosets \begin{align*} G/H=\{H,(1\ 2)H\}. \end{align*} The left coset action is \begin{align*} g\cdot(aH)=(ga)H. \end{align*} Therefore the associated permutation representation has the form \begin{align*} \rho:S_3\to \operatorname{Sym}(G/H)\cong S_2. \end{align*} We determine the kernel by checking which elements fix both cosets. If $h\in H$, then \begin{align*} h\cdot H=hH=H, \end{align*} because $hH=H$ for every $h\in H$. Now check the other coset for the three elements of $H$. First, \begin{align*} \operatorname{id}\cdot((1\ 2)H)=\operatorname{id}(1\ 2)H=(1\ 2)H. \end{align*} Next, \begin{align*} (1\ 2\ 3)(1\ 2)=(1\ 3), \end{align*} because \begin{align*} 1\mapsto 2\mapsto 3,\quad 2\mapsto 1\mapsto 2,\quad 3\mapsto 3\mapsto 1. \end{align*} Since $(1\ 3)\in (1\ 2)H$, its left coset equals $(1\ 2)H$, and therefore \begin{align*} (1\ 2\ 3)\cdot((1\ 2)H)=(1\ 3)H=(1\ 2)H. \end{align*} Finally, \begin{align*} (1\ 3\ 2)(1\ 2)=(2\ 3), \end{align*} because \begin{align*} 1\mapsto 2\mapsto 1,\quad 2\mapsto 1\mapsto 3,\quad 3\mapsto 3\mapsto 2. \end{align*} Since $(2\ 3)\in (1\ 2)H$, we get \begin{align*} (1\ 3\ 2)\cdot((1\ 2)H)=(2\ 3)H=(1\ 2)H. \end{align*} Thus every element of $H=A_3$ fixes both cosets. It remains to check that every element outside $H$ swaps the two cosets. The elements outside $H$ are \begin{align*} (1\ 2),\quad (2\ 3),\quad (1\ 3), \end{align*} and all three lie in $(1\ 2)H$. Hence for each $u\in\{(1\ 2),(2\ 3),(1\ 3)\}$, \begin{align*} u\cdot H=uH=(1\ 2)H. \end{align*} Now compute their images of the other coset. For $u=(1\ 2)$, \begin{align*} (1\ 2)\cdot((1\ 2)H)=(1\ 2)(1\ 2)H=\operatorname{id}H=H. \end{align*} For $u=(2\ 3)$, \begin{align*} (2\ 3)\cdot((1\ 2)H)=(2\ 3)(1\ 2)H=(1\ 3\ 2)H=H, \end{align*} where $(2\ 3)(1\ 2)=(1\ 3\ 2)$ follows from \begin{align*} 1\mapsto 2\mapsto 3,\quad 2\mapsto 1\mapsto 1,\quad 3\mapsto 3\mapsto 2. \end{align*} For $u=(1\ 3)$, \begin{align*} (1\ 3)\cdot((1\ 2)H)=(1\ 3)(1\ 2)H=(1\ 2\ 3)H=H, \end{align*} where $(1\ 3)(1\ 2)=(1\ 2\ 3)$ follows from \begin{align*} 1\mapsto 2\mapsto 2,\quad 2\mapsto 1\mapsto 3,\quad 3\mapsto 3\mapsto 1. \end{align*} Therefore each element outside $H$ sends $H$ to $(1\ 2)H$ and sends $(1\ 2)H$ to $H$. The kernel consists exactly of the elements acting as the identity permutation on the two-point set $G/H$. We have shown that the elements of $H$ fix both cosets and that the elements outside $H$ swap them, so \begin{align*} \ker\rho=H=A_3. \end{align*} The image contains exactly two permutations of $G/H$: the identity permutation and the transposition exchanging $H$ with $(1\ 2)H$. Hence \begin{align*} |\operatorname{im}\rho|=2. \end{align*} This coset action records only whether a permutation is even or odd: all three even permutations act identically, while all three odd permutations induce the same swap of the two cosets. [/example] ## Beyond and Connected Topics Permutation groups are a natural continuation of the action viewpoint in [Cambridge IA Groups](/page/Cambridge%20IA%20Groups), where orbit-stabiliser, Cayley’s theorem, conjugation actions, and coset actions first appear. The study of normal subgroups and quotient groups in [Cambridge IB Groups, Rings and Modules](/page/Cambridge%20IB%20Groups%2C%20Rings%20and%20Modules) deepens the role of permutation representations. Kernels of actions, cores of subgroups, and the sign map all convert motion on a set into quotient information. Linear representations provide a second direction. A permutation of a finite set acts on the [vector space](/page/Vector%20Space) with that set as a basis, producing permutation matrices and connecting the subject to [Cambridge IB Linear Algebra](/page/Cambridge%20IB%20Linear%20Algebra). A more advanced direction leads toward finite reflection groups and Weyl groups. Although permutation groups are discrete, they appear naturally inside matrix groups and in the structural background of [Lie Algebras II: Structure and Classification](/page/Lie%20Algebras%20II%3A%20Structure%20and%20Classification). Primitive permutation groups lead toward deep classification theorems. The finite simple groups enter the subject through the analysis of primitive actions, especially when stabilisers, minimal normal subgroups, and highly transitive actions interact. ## References Androma, [Cambridge IA Groups](/page/Cambridge%20IA%20Groups). Androma, [Cambridge IB Groups, Rings and Modules](/page/Cambridge%20IB%20Groups%2C%20Rings%20and%20Modules). Androma, [Cambridge IB Linear Algebra](/page/Cambridge%20IB%20Linear%20Algebra). Androma, [Lie Algebras II: Structure and Classification](/page/Lie%20Algebras%20II%3A%20Structure%20and%20Classification). Dummit and Foote, *Abstract Algebra* (2004). Rotman, *An Introduction to the Theory of Groups* (1995). Dixon and Mortimer, *Permutation Groups* (1996).