Groups

Groups, subgroups, homomorphisms and group actions.

In this chapter 9

Tick a unit to add it to your PDF basket.

Basic group theory

Basic group theory

Definition

Groups and subgroups

Adapted

Add to PDF

Gives the group axioms and the uniqueness and cancellation laws they force, the one-line test for a subset to be a subgroup, and the order of an element together with the cyclic subgroup it generates.

Definition(Group)AdaptedAdapted from Dummit & Foote (2004), §1.1, the definitions of a binary operation and of a group, pp. 16-17, and the power notation, p. 20; Riley, Hobson & Bence (2006), §28.1.1, the four axioms (i)-(iv), p. 1043; Hassani (2013), §23.1, the order $|G|$ and the powers $a^k$, p. 703

A binary operation on a set $G$ is a map $G \times G \to G$ . We write it as juxtaposition, $(x,y) \mapsto xy$ , and call $xy$ the product of $x$ and $y$ ; that the product always lands back in $G$ is the closure requirement, and it is built into the word "map". When a second operation is in play we write $x \star y$ instead.

A group is a set $G$ with a binary operation satisfying three axioms.

(G1) Associativity. $(xy)z = x(yz)$ for all $x, y, z \in G$ .
(G2) Identity. There is an $e \in G$ with $ex = xe = x$ for every $x \in G$ .
(G3) Inverses. For each $x \in G$ there is an $x^{-1} \in G$ with $x x^{-1} = x^{-1} x = e$ .

Axiom (G2) requires $G$ to have at least one element, so a group is never empty. The group is abelian, or commutative, if in addition $xy = yx$ for all $x,y$ ; most groups of physical interest are not. A finite group is one with finitely many elements, and the number of elements of a finite group is its order, written $|G|$ . An infinite group is said to have infinite order.

For $n \in \mathbb{N}$ we write $x^n$ for the product of $n$ copies of $x$ , $x^{-n}$ for the product of $n$ copies of $x^{-1}$ , and $x^0 = e$ ; then $x^{i}x^{j} = x^{i+j}$ for all $i, j \in \mathbb{Z}$ . When the operation is addition the same objects are written $e = 0$ , $x^{-1} = -x$ and $x^n = nx$ .

Two conventions are worth fixing at the start. First, (G2) only postulates an identity; its uniqueness is a theorem, proved below. Some texts, Riley, Hobson and Bence (Riley, Hobson & Bence (2006), §28.1.1, axiom (iii), p. 1043) among them, write "unique" into the axiom itself, which costs nothing because the two readings agree. Second, when the elements are operations acting on something, $XY$ means "do $Y$ first, then $X$ ", matching the order in which composed functions and matrices act.

Note(Where groups come from)AdaptedAdapted from Riley, Hobson & Bence (2006), §28.1, the symmetry operations of the hydrogen and ammonia molecules, pp. 1041-1042; Arfken, Weber & Harris (2013), §17.1, Examples 17.1.1-17.1.3, pp. 817-819; Hassani (2013), §23.1, Example 23.1.2, pp. 703-704, and §23.2, Example 23.2.2 with Boxes 23.1.7, 23.2.3 and 23.2.4, pp. 705-706

The axioms are an abstraction of two quite different situations.

Numbers. $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{R}$ and $\mathbb{C}$ are abelian groups under addition; $\mathbb{Q}\setminus\{0\}$ , $\mathbb{R}\setminus\{0\}$ , $\mathbb{C}\setminus\{0\}$ and $\mathbb{R}^{+}$ are abelian groups under multiplication. $\mathbb{Z}\setminus\{0\}$ is not a group under multiplication: $2$ has no integer reciprocal. Any vector space is an abelian group under vector addition, its scalar multiplication simply forgotten.

Symmetries. Fix an object and collect every transformation that leaves it looking the same. Composition of two such transformations is another, undoing one is another, and doing nothing is the identity, so the collection is a group. Riley, Hobson and Bence (Riley, Hobson & Bence (2006), §28.1, pp. 1041-1042) start from the hydrogen and ammonia molecules in exactly this way. For an equilateral triangle the group has six elements — the identity, two rotations by $\pm 120^{\circ}$ , and three reflections — and it is not abelian, since a rotation followed by a reflection generally differs from the same two performed in the other order (Arfken, Weber and Harris (Arfken, Weber & Harris (2013), Example 17.1.1 and Table 17.1, pp. 817-818)). For a circular disk the symmetries form the continuous abelian group of rotations $R(\varphi)$ , with $R(\varphi)R(\theta) = R(\varphi + \theta)$ .

Matrices. The invertible $n \times n$ matrices over a field $F$ form the general linear group $GL(n,F)$ under matrix multiplication; more abstractly, $GL(V)$ is the group of invertible linear maps of a vector space $V$ to itself (Linear maps and matrices). Inside it sit the groups that physics uses constantly: $SL(n,F)$ (determinant $1$ ), $O(n)$ and $SO(n)$ (Unitary and orthogonal matrices), $U(n)$ and $SU(n)$ , the Lorentz group $O(3,1)$ , and the symplectic group $Sp(2n,\mathbb{R})$ of Hamiltonian mechanics. These are collected in The classical matrix groups.

A group may also be specified by nothing but its multiplication table, with no numbers or geometry attached at all; Arfken, Weber and Harris (Arfken, Weber & Harris (2013), Example 17.1.3 and Table 17.2, p. 819) give the four-element Vierergruppe that way.

Definition(Uniqueness, inverses and cancellation)AdaptedAdapted from Dummit & Foote (2004), §1.1, Proposition 1 parts (1)-(4), p. 18, and Proposition 2 with the two remarks following it, p. 20

Let $G$ be a group with identity $e$ , and let $a, b, u, v \in G$ .

The identity is unique: if $f \in G$ satisfies $fx = xf = x$ for all $x$ , then $f = e$ .
Inverses are unique: if $ab = ba = e$ and $ac = ca = e$ then $b = c$ . We may therefore speak of the inverse $a^{-1}$ .
$(a^{-1})^{-1} = a$ and $(ab)^{-1} = b^{-1}a^{-1}$ , in that order.
The equations $ax = b$ and $ya = b$ have exactly one solution each, namely $x = a^{-1}b$ and $y = ba^{-1}$ . In particular both cancellation laws hold: $au = av$ implies $u = v$ , and $ub = vb$ implies $u = v$ .
One side suffices: if $ab = e$ for some $b$ , then $b = a^{-1}$ (and likewise if $ba = e$ ); and if $ab = a$ for a single $a$ , then $b = e$ .

Consequently a product $a_1 a_2 \cdots a_n$ needs no brackets, and in a finite group each row and each column of the multiplication table is a rearrangement of the elements of $G$ .

Idea of the proofOriginal

Everything here comes from multiplying by an inverse and from the fact that an inverse exists on both sides. Uniqueness of the identity is the one statement that does not need inverses at all: two identities $e$ and $f$ can be multiplied together, and each then claims the product for itself. Uniqueness of inverses is the same trick with a third element in the middle: evaluate $cab$ two ways, bracketing it once to the left and once to the right. The cancellation laws, and with them the rearrangement of the multiplication table, are the single observation that multiplying by $a^{-1}$ undoes multiplying by $a$ .

ProofAdaptedAdapted from Dummit & Foote (2004), §1.1, the proofs of Proposition 1 (1)-(4), pp. 18-19, and of Proposition 2, p. 20

1. Consider the product $ef$ . Reading $e$ as an identity gives $ef = f$ ; reading $f$ as an identity gives $ef = e$ . Hence $e = f$ .

2. Suppose $ab = ba = e$ and $ac = ca = e$ . Bracket the product $c(ab)$ in the two ways permitted by (G1):

c(ab) = ce = c, \qquad (ca)b = eb = b .

Associativity says the two left-hand sides are equal, so $b = c$ . (Only $ab = e$ and $ca = e$ were used, which is more than we need and will be sharpened in part 5.)

3. The defining equations $a a^{-1} = a^{-1} a = e$ say, read with the roles of $a$ and $a^{-1}$ exchanged, that $a$ is an inverse of $a^{-1}$ . By part 2 the inverse of $a^{-1}$ is unique, so it is $a$ . For the second identity, compute directly, using (G1) to move the brackets:

(ab)(b^{-1}a^{-1}) = a\bigl(b b^{-1}\bigr)a^{-1} = a e a^{-1} = a a^{-1} = e ,

and symmetrically $(b^{-1}a^{-1})(ab) = e$ . So $b^{-1}a^{-1}$ is an inverse of $ab$ , hence by part 2 it is $(ab)^{-1}$ . The reversal of order is not optional: in a non-abelian group $a^{-1}b^{-1}$ generally fails.

4. $x = a^{-1}b$ solves $ax = b$ , since $a(a^{-1}b) = (aa^{-1})b = b$ . If $x'$ is any solution, multiply $ax' = b$ on the left by $a^{-1}$ and use (G1): $x' = (a^{-1}a)x' = a^{-1}b$ . So the solution is unique, and the same argument on the other side handles $ya = b$ . For left cancellation, $au = av$ gives $u = a^{-1}(au) = a^{-1}(av) = v$ ; right cancellation follows by multiplying on the right by $b^{-1}$ .

5. If $ab = e$ then, multiplying on the left by $a^{-1}$ , $b = a^{-1}(ab) = a^{-1}e = a^{-1}$ . If $ba = e$ , multiply on the right by $a^{-1}$ instead. If $ab = a$ , then $ab = ae$ , and left cancellation gives $b = e$ .

Bracketing and the multiplication table. That a product of $n$ factors is independent of its bracketing follows by induction on $n$ : the cases $n \le 3$ are (G1), and any bracketing of $a_1 \cdots a_n$ splits at some point into a product $(a_1\cdots a_k)(a_{k+1}\cdots a_n)$ of two shorter bracketed products, which by the inductive hypothesis have unambiguous values; repeated use of (G1) then moves every split to the same place. Finally, fix $a$ and consider the row of the table indexed by $a$ , that is, the list $x \mapsto ax$ . By part 4 this map is injective (cancellation) and surjective (solve $ax = b$ ), so the row contains every element of $G$ exactly once; columns are the same with the other factor fixed. $\square$

Definition(Subgroup)AdaptedAdapted from Dummit & Foote (2004), §2.1, the definition of a subgroup and the paragraph identifying its identity and inverses with those of $G$, p. 46; Hassani (2013), §23.2, Definition 23.2.1 and the remark that $e \in S$ follows, pp. 705-706; Riley, Hobson & Bence (2006), §28.6, the definition and the trivial and proper subgroups, p. 1061

A subset $H$ of a group $G$ is a subgroup, written $H \le G$ , if $H$ is non-empty and is closed under the two operations of $G$ : $xy \in H$ and $x^{-1} \in H$ whenever $x, y \in H$ .

Such an $H$ is a group in its own right under the restricted operation. Associativity is inherited for free, since an equation among elements of $H$ is an equation in $G$ ; the identity of $H$ is the identity of $G$ , because $e_H e_H = e_H = e_H e$ in $G$ and cancellation gives $e_H = e$ ; and for the same reason the inverse of $x$ in $H$ is its inverse in $G$ . In particular $e \in H$ for every subgroup, so no two subgroups are disjoint.

Every group has the two trivial subgroups $\{e\}$ and $G$ ; any other subgroup is proper. The relation $\le$ is transitive: a subgroup of a subgroup of $G$ is a subgroup of $G$ . An intersection of subgroups is again a subgroup, since each defining condition is inherited from every member of the family; a union of subgroups usually is not.

Definition(Subgroup criterion)AdaptedAdapted from Dummit & Foote (2004), §2.1, Proposition 1 and the sentence on finite subsets that follows it, pp. 47-48

Let $H$ be a subset of a group $G$ . The following two conditions are equivalent.

$H$ is a subgroup of $G$ .
(S1) $H$ has at least one element, and (S2) the combination $xy^{-1}$ belongs to $H$ whenever both $x$ and $y$ do.

Should $H$ happen to have only finitely many elements, a third equivalent condition joins the list:

$H$ has at least one element, and $xy$ belongs to $H$ whenever both $x$ and $y$ do.

So for a finite candidate the single word "inverses" may be struck from the definition, while for an infinite one it may not.

Idea of the proofOriginal

One condition does the work of two because $xy^{-1}$ can be specialised. Feed it the same element twice and it produces the identity; feed it the identity and an element and it produces that element's inverse; once inverses are available, feeding it $x$ and $y^{-1}$ produces the product $xy$ . For the finite case there are no inverses to manufacture out of nothing, so one uses finiteness instead: the powers of an element of a finite set must eventually repeat, and a repetition $x^{a} = x^{b}$ turns some positive power of $x$ into the identity, which puts the inverse of $x$ among its own positive powers.

ProofAdaptedAdapted from Dummit & Foote (2004), §2.1, the proof of Proposition 1 and the finite-subset argument, pp. 47-48

A subgroup satisfies (S1) and (S2). It is non-empty by definition, and if $x, y \in H$ then $y^{-1} \in H$ by closure under inverses and $xy^{-1} \in H$ by closure under products.

(S1) and (S2) give a subgroup. Three applications of (S2), in order.

By (S1) pick some $x \in H$ . Taking both arguments equal to $x$ , $e = x x^{-1} \in H$ .
Now take the first argument to be $e$ and the second to be any $y \in H$ : $y^{-1} = e y^{-1} \in H$ . So $H$ is closed under inverses.
Finally let $x, y \in H$ . By the previous step $y^{-1} \in H$ , so (S2) applied to the pair $x, y^{-1}$ gives $x(y^{-1})^{-1} = xy \in H$ , using $(y^{-1})^{-1} = y$ . So $H$ is closed under products.

Hence $H \le G$ .

The finite case. Assume $H$ is a finite non-empty subset closed under products, and let $x \in H$ . All the powers $x, x^2, x^3, \dots$ lie in $H$ by closure, and $H$ is finite, so they cannot all be distinct: there are exponents $a < b$ with $x^{a} = x^{b}$ . Cancelling $x^{a}$ gives $x^{\,b-a} = e$ with $n := b - a \ge 1$ . Therefore $e = x^{n} \in H$ , and

x\,x^{\,n-1} = x^{n} = e ,

so by part 5 of the uniqueness statement $x^{-1} = x^{\,n-1}$ . If $n = 1$ this reads $x^{-1} = x^{0} = e = x$ , which is correct. In either case $x^{-1}$ is a power of $x$ with a non-negative exponent, hence lies in $H$ . So $H$ is closed under inverses as well, and is a subgroup. $\square$

Definition(Order of an element; cyclic groups)AdaptedAdapted from Dummit & Foote (2004), §1.1, the definition of the order $|x|$, p. 20, and §2.3, the definition of a cyclic group and of $\\langle x \\rangle$, p. 54; Hassani (2013), §23.2, Definition 23.2.5 and the cyclic subgroup $\\langle a \\rangle$, p. 707

Let $x$ be an element of a group $G$ . The order of $x$ , written $|x|$ , is the least $n \in \mathbb{N}$ with $x^{n} = e$ ; if no positive power of $x$ equals $e$ , then $x$ has infinite order. The identity is the only element of order $1$ .

The set of all integer powers of $x$ ,

\langle x \rangle = \{\, x^{k} : k \in \mathbb{Z} \,\},

is a subgroup of $G$ : it is non-empty, and $x^{j}(x^{k})^{-1} = x^{\,j-k}$ lies in it, so (S2) holds. It is the cyclic subgroup generated by $x$ , and it is abelian because powers of one element commute. A group $G$ is cyclic if $G = \langle x \rangle$ for some $x \in G$ , and any such $x$ is a generator. A cyclic group may have several generators: $\langle x \rangle = \langle x^{-1}\rangle$ always, since $-k$ runs over $\mathbb{Z}$ as $k$ does.

The same symbol $|\cdot|$ is used for the order of an element and for the order of a group. The statement below shows the clash is harmless.

Definition(The cyclic subgroup generated by one element)AdaptedAdapted from Dummit & Foote (2004), §2.3, Proposition 2, Proposition 3 and Proposition 5(2), pp. 55-57

Let $G$ be a group and $x \in G$ .

$|\langle x \rangle| = |x|$ , with the convention that one side is infinite exactly when the other is. More precisely, if $|x| = n < \infty$ then $e, x, x^{2}, \dots, x^{\,n-1}$ are distinct and exhaust $\langle x \rangle$ , while if $|x| = \infty$ then all the powers $x^{k}$ , $k \in \mathbb{Z}$ , are distinct.
If $x^{m} = e$ for some $m \in \mathbb{Z}$ , then $|x|$ divides $m$ . Conversely $x^{m} = e$ whenever $|x|$ divides $m$ .
If $|x| = n < \infty$ and $a \in \mathbb{Z}$ , then $|x^{a}| = n/\gcd(n,a)$ . In particular $x^{a}$ generates $\langle x \rangle$ exactly when $\gcd(n,a) = 1$ .

Idea of the proofOriginal

Both of the first two parts are the division algorithm in disguise. Any exponent $k$ can be written $k = qn + r$ with $0 \le r < n$ ; since $x^{n} = e$ , the quotient part collapses and $x^{k} = x^{r}$ . That simultaneously shows the list $e, x, \dots, x^{n-1}$ is everything, and that $x^{k} = e$ forces $x^{r} = e$ with $r$ below the minimum $n$ , so $r = 0$ and $n \mid k$ . Part 3 then follows by asking for the smallest $m > 0$ with $n \mid am$ , which is a statement about least common multiples.

ProofAdaptedAdapted from Dummit & Foote (2004), §2.3, the proofs of Propositions 2, 3 and 5(2), pp. 55-57

Part 1, finite case. Let $|x| = n < \infty$ . The listed elements are distinct: if $x^{a} = x^{b}$ with $0 \le a < b \le n-1$ , then cancelling $x^{a}$ gives $x^{\,b-a} = e$ with $1 \le b-a \le n-1$ , contradicting the minimality of $n$ in the definition of order. They exhaust $\langle x \rangle$ : given $k \in \mathbb{Z}$ , divide, $k = qn + r$ with $0 \le r < n$ , and use the exponent law,

x^{k} = \bigl(x^{n}\bigr)^{q} x^{r} = e^{q} x^{r} = x^{r} .

So $|\langle x \rangle| = n = |x|$ .

Part 1, infinite case. Let $|x| = \infty$ . If $x^{a} = x^{b}$ with $a < b$ then $x^{\,b-a} = e$ with $b - a \ge 1$ , so $x$ would have finite order. Hence all powers are distinct and $\langle x \rangle$ is infinite.

Part 2. Suppose $x^{m} = e$ . If $m = 0$ there is nothing to prove, and $x^{-m} = (x^{m})^{-1} = e$ , so we may assume $m > 0$ . Then $x$ has finite order; write $n = |x|$ and divide, $m = qn + r$ with $0 \le r < n$ . As in part 1, $x^{r} = x^{m} = e$ . Since $n$ is the least positive exponent with that property and $r < n$ , the only possibility is $r = 0$ , that is, $n \mid m$ . The converse is immediate: if $m = nq$ then $x^{m} = (x^{n})^{q} = e$ .

Part 3. Put $n = |x|$ , $d = \gcd(n,a)$ , and write $n = db$ , $a = dc$ with $\gcd(b,c) = 1$ and $b > 0$ . First, $(x^{a})^{b} = x^{ab} = x^{\,dcb} = (x^{\,db})^{c} = (x^{n})^{c} = e$ , so $x^{a}$ has finite order, and by part 2 that order divides $b$ . Conversely let $m = |x^{a}|$ , so $x^{am} = e$ ; by part 2 again $n \mid am$ , that is, $db \mid dcm$ , hence $b \mid cm$ . Since $\gcd(b,c) = 1$ , $b$ divides $m$ . The two divisibilities give $m = b = n/d$ , which is the claim. The last sentence follows because $\langle x^{a}\rangle \subseteq \langle x\rangle$ and, by part 1, the two have sizes $n/d$ and $n$ , so they coincide exactly when $d = 1$ . $\square$

Remark(Where the hypotheses are used)AdaptedAdapted from Dummit & Foote (2004), §1.1, the non-associativity of the vector cross product, p. 16, and §2.1, Example 5(b) on $\\mathbb{Z}^{+}$, p. 47; Hassani (2013), §23.2, Example 23.2.2 item 3, p. 706

Associativity (G1) is a real restriction. The cross product is a perfectly good binary operation on $\mathbb{R}^{3}$ , but $\mathbf{e}_1 \times (\mathbf{e}_1 \times \mathbf{e}_2) = -\mathbf{e}_2$ while $(\mathbf{e}_1 \times \mathbf{e}_1) \times \mathbf{e}_2 = \mathbf{0}$ , so it is not associative and $(\mathbb{R}^{3}, \times)$ is not a group. Without (G1) the proof of uniqueness of inverses fails at its first line, and products of three or more elements stop having well-defined values.

Inverses are not implied by closure. The positive integers are closed under addition, contain no identity for it, and contain no additive inverses; $\mathbb{Z}^{+}$ is therefore not a subgroup of $(\mathbb{Z},+)$ . This is also the hypothesis that the finite half of the subgroup criterion replaces: the shortcut "closed under products" is valid only for finite $H$ , and $\mathbb{Z}^{+} \subset \mathbb{Z}$ is precisely the infinite counterexample. The proof shows where finiteness enters — in the pigeonhole step that forces two powers of $x$ to coincide.

The operation must be the one inherited from $G$ . $\mathbb{Q}\setminus\{0\}$ is a group under multiplication and a subset of the additive group $\mathbb{R}$ , but it is not a subgroup of it: the operations are different. " $H \le G$ " always means $H$ carries the restriction of $G$ 's operation.

Non-emptiness. The empty set satisfies (S2) vacuously, so (S1) cannot be dropped. In practice one verifies (S1) by exhibiting $e \in H$ .

Minimality in the definition of order. Part 2 above fails without it. The element $x = \mathrm{i}$ of $\mathbb{C}\setminus\{0\}$ satisfies $x^{4} = 1$ and $x^{8} = 1$ ; it is only because $4$ is the least such exponent that one may conclude $4 \mid m$ from $x^{m} = 1$ .

What is special about cyclic groups. Every cyclic group is abelian, so a non-abelian group is never cyclic — the six-element symmetry group of the equilateral triangle, for instance. The converse fails: $\mathbb{Z}$ is cyclic, but the group computed in the example below is abelian of order $8$ and not cyclic. Subgroups of $\mathbb{Z}$ are the exception in which cyclicity is automatic: each is $m\mathbb{Z} = \langle m \rangle$ for a unique $m \ge 0$ .

Example(A group of order eight that is not cyclic)Original

Let

G = (\mathbb{Z}/15\mathbb{Z})^{\times} = \{\, \bar a : 1 \le a \le 14,\ \gcd(a,15) = 1 \,\},

the residue classes modulo $15$ that have a multiplicative inverse, under multiplication of classes. This is a group: multiplication of classes is associative and has identity $\bar 1$ ; it is closed, because $\gcd(a,15) = \gcd(b,15) = 1$ gives $\gcd(ab,15) = 1$ ; and each class is invertible by construction. Discarding the multiples of $3$ and of $5$ leaves

G = \{\bar 1, \bar 2, \bar 4, \bar 7, \bar 8, \bar{11}, \bar{13}, \bar{14}\}, \qquad |G| = 8 .

We drop the bars from here on.

Orders of the elements. Work out the powers of $2$ modulo $15$ :

2^{1} = 2, \quad 2^{2} = 4, \quad 2^{3} = 8, \quad 2^{4} = 16 = 1 ,

so $|2| = 4$ and $\langle 2 \rangle = \{1,2,4,8\}$ , a subgroup of order $4$ — which matches part 1 of the statement above. For $7$ :

7^{2} = 49 = 45 + 4 = 4, \quad 7^{3} = 7 \cdot 4 = 28 = 13, \quad 7^{4} = 7 \cdot 13 = 91 = 90 + 1 = 1 ,

so $|7| = 4$ . The remaining elements are quicker. $4^{2} = 16 = 1$ , so $|4| = 2$ ; $11^{2} = 121 = 120 + 1 = 1$ , so $|11| = 2$ ; $14^{2} = 196 = 195 + 1 = 1$ , so $|14| = 2$ (indeed $14 = -1$ modulo $15$ ). For $8 = 2^{3}$ part 3 applies with $n = 4$ and $a = 3$ : $|8| = 4/\gcd(4,3) = 4$ . For $13 = 7^{3}$ the same gives $|13| = 4$ . Collecting:

element	$1$	$2$	$4$	$7$	$8$	$11$	$13$	$14$
order	$1$	$4$	$2$	$4$	$4$	$2$	$4$	$2$

Conclusion. The largest order occurring is $4$ . By part 1, a generator of a cyclic group of order $8$ would have to be an element of order $8$ , and there is none. Hence $G$ is abelian of order $8$ but not cyclic, and no single element generates it. Two elements do: every element of $G$ is $2^{i} 11^{j}$ with $i \in \{0,1,2,3\}$ and $j \in \{0,1\}$ , since $11 \notin \langle 2\rangle$ and $4 \cdot 2 = 8$ counts the products correctly.

Two checks. First, the orders listed are all divisors of $|G| = 8$ , as Lagrange's theorem requires. Second, the four elements of order dividing $2$ , namely $\{1, 4, 11, 14\}$ , are closed under multiplication — $4 \cdot 11 = 44 = 45 - 1 = 14$ , $4 \cdot 14 = 56 = 45 + 11 = 11$ , $11 \cdot 14 = 154 = 150 + 4 = 4$ — and so form a subgroup of order $4$ by the finite subgroup criterion. The final number to carry away: $G$ has exactly $4$ elements of order $4$ , namely $2$ , $7$ , $8$ and $13$ .

ApplicationOriginal

Symmetry as a bookkeeping device. A Hamiltonian, a crystal, a molecule or a field theory comes with a group of transformations that leave it unchanged, and almost everything one can say about the system without solving it follows from that group. Which transformations are symmetries is a closure question: the set of them is automatically a group, which is why the axioms are the right abstraction and why one may speak of "the" symmetry group of a configuration. The finite ones are the point groups of molecules and crystals (Point groups and crystal symmetry); the continuous ones are the matrix groups $SO(3)$ , $SU(2)$ , $SU(3)$ and the Lorentz group (Matrix Lie groups and Lie algebras).

Orders control what can happen. The order of an element is the number of times an operation must be repeated to get back to the start, so it is directly observable: a rotation axis of a crystal has order $2$ , $3$ , $4$ or $6$ and nothing else, and that single arithmetic fact is the crystallographic restriction. In the quantum-mechanical setting the order of a symmetry operation limits the phases it can multiply a state by: if $S^{n} = \mathbb{1}$ and $S$ acts on an eigenstate by a number $\lambda$ , then $\lambda^{n} = 1$ , so $\lambda$ is an $n$ th root of unity. Parity ( $n = 2$ , $\lambda = \pm 1$ ) is the familiar case.

Cyclic groups and periodicity. A cyclic group of order $n$ is the symmetry group of anything with $n$ -fold periodicity: the rotations of a regular $n$ -gon, the Bloch phases $e^{2\pi \mathrm{i} k/n}$ of a ring of $n$ lattice sites, the discrete Fourier transform. The classification of these groups is as complete as it could be — cyclic groups of equal order are always isomorphic to one another, so for each $n$ there is only one (Dummit and Foote (Dummit & Foote (2004), §2.3, Theorem 4, p. 56)), and the infinite one is $\mathbb{Z}$ . That is why "the" $\mathbb{Z}_n$ symmetry of a model is a well-posed phrase.

Subgroups and symmetry breaking. When a system cools through a phase transition or has a field applied, the symmetry group shrinks to a subgroup: $SO(3)$ to a point group in a crystal, a point group to one of its subgroups under strain. The subgroup criterion is then the practical test for which sets of surviving operations are consistent, and the degeneracy of the energy levels splits accordingly (Representations of groups).

Arithmetic. $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , the group of the example, is the computational backbone of public-key cryptography and of the fast algorithms for modular exponentiation; the order of an element there is the period of the corresponding repeating decimal or pseudorandom sequence.

Theorem

Cosets and Lagrange's theorem

Adapted

Add to PDF

Shows that the left cosets of a subgroup cut a group into equal-sized disjoint pieces, so that in a finite group the order of a subgroup divides the order of the group, and draws out the consequences for orders of elements and for groups of prime order.

Prerequisites: Groups and subgroups

Definition(Cosets, representatives and the index)AdaptedAdapted from Dummit & Foote (2004), §3.1, the definition of $gN$ and $Ng$ and of a representative, p. 77, and §3.2, the definition of the index, p. 90; Hassani (2013), §23.2, Definition 23.2.10 with the footnote on the left-right convention, p. 708

Let $H \le G$ be a subgroup (Groups and subgroups) and let $g \in G$ . The left coset of $H$ with representative $g$ is the subset

gH = \{\, gh : h \in H \,\},

and the right coset is $Hg = \{\, hg : h \in H \,\}$ . In additive notation these are written $g + H$ and $H + g$ . One coset is $H$ itself, since $eH = H$ ; every other left coset misses $e$ and is therefore not a subgroup. Each element of a coset represents it, in a sense made precise below: the notation $gH$ names a set, and different $g$ 's may name the same set.

The set of left cosets of $H$ in $G$ is written $G/H$ , and the number of them is the index of $H$ in $G$ , written $[G:H]$ . The index is defined whether or not $G$ is finite, and it may be finite even when $G$ is not: in $(\mathbb{Z},+)$ the subgroup $n\mathbb{Z}$ has index $n$ , while the subgroup $\{0\}$ has infinite index.

Which of $gH$ and $Hg$ is called "left" is not universal; some authors, as Hassani (Hassani (2013), §23.2, footnote 5, p. 708) notes, exchange the two names. We follow the convention above throughout, and the statement after next shows that the choice never affects a count.

Theorem(Cosets partition the group)AdaptedAdapted from Dummit & Foote (2004), §3.1, Proposition 4, p. 80; Hassani (2013), §23.2, Theorem 23.2.12 and the paragraph on the cardinality of a coset, pp. 708-709; Riley, Hobson & Bence (2006), §28.7.2, the three bullet points, pp. 1066-1067

Let $H \le G$ and let $u, v, g \in G$ .

$g \in gH$ , so the left cosets cover $G$ : $\;G = \bigcup_{g \in G} gH$ .
$uH = vH$ if and only if $v^{-1}u \in H$ ; equivalently, if and only if $u \in vH$ .
Two left cosets are either identical or disjoint. Thus the left cosets form a partition of $G$ : every element of $G$ lies in exactly one of them.
Every left coset has the same cardinality as $H$ ; the map $h \mapsto gh$ is a bijection from $H$ onto $gH$ .
All four statements hold verbatim for right cosets. Moreover $gH \mapsto Hg^{-1}$ is a well-defined bijection from the left cosets onto the right cosets, so the two families have the same number of members and $[G:H]$ is unambiguous.

Idea of the proofOriginal

A coset is the subgroup pushed sideways by one element, and two pushes land on the same place exactly when they differ by something already inside the subgroup. That single sentence contains both the overlap statement and the equality test: if $uH$ and $vH$ share a point then $u$ and $v$ differ by an element of $H$ , and once they do, each coset is contained in the other. Equal size is even simpler — translation by $g$ is undone by translation by $g^{-1}$ , so it cannot collapse two elements into one. The left-right dictionary comes from inversion, which turns the product $gh$ into $h^{-1}g^{-1}$ and so turns a left coset into a right one.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.1, the proof of Proposition 4, p. 80, and §3.2, p. 95, for the left-right bijection; Hassani (2013), §23.2, the bijection $\\varphi(s) = sa$ used for the cardinality, p. 709

Part 1. $e \in H$ because $H$ is a subgroup, so $g = ge \in gH$ . Since $g$ was arbitrary, the cosets cover $G$ .

Part 2. Suppose $uH = vH$ . By part 1, $u \in uH = vH$ , so $u = vh$ for some $h \in H$ , and multiplying on the left by $v^{-1}$ gives $v^{-1}u = h \in H$ . Conversely suppose $v^{-1}u = h_0 \in H$ , so $u = vh_0$ . For any $h \in H$ we get $uh = v(h_0 h) \in vH$ , using closure of $H$ under products; hence $uH \subseteq vH$ . Also $v = u h_0^{-1}$ , with $h_0^{-1} \in H$ because $H$ is closed under inverses, so the same argument with $u$ and $v$ exchanged gives $vH \subseteq uH$ . Hence $uH = vH$ . The reformulation " $u \in vH$ " is the statement $u = vh$ for some $h \in H$ , which is what $v^{-1}u \in H$ says.

Part 3. Suppose $uH \cap vH \neq \emptyset$ and pick $x$ in the intersection. Then $x \in uH$ , so $uH = xH$ by part 2 applied to the pair $x, u$ ; and $x \in vH$ , so $vH = xH$ likewise. Hence $uH = vH$ . So two cosets that meet at all coincide, and with part 1 this makes the distinct left cosets a partition of $G$ .

Part 4. Fix $g$ and define $\lambda : H \to gH$ by $\lambda(h) = gh$ . It is onto by the definition of $gH$ . It is one-to-one by the left cancellation law: $gh_1 = gh_2$ forces $h_1 = h_2$ . So $\lambda$ is a bijection and $|gH| = |H|$ , as cardinalities; this is the step at which the group structure of $G$ , and not merely the partition, is used.

Part 5. For right cosets, repeat parts 1 to 4 with the products written on the other side; the test in part 2 becomes $uv^{-1} \in H$ and the bijection in part 4 becomes $h \mapsto hg$ . For the dictionary, let $\iota(gH) = Hg^{-1}$ .

Well defined. If $uH = vH$ then $v^{-1}u \in H$ , so its inverse $u^{-1}v$ lies in $H$ too, which by the right-coset test says $Hu^{-1} = Hv^{-1}$ .
Injective. Running the same chain backwards, $Hu^{-1} = Hv^{-1}$ gives $u^{-1}v \in H$ , hence $v^{-1}u \in H$ and $uH = vH$ .
Surjective. A right coset $Hg$ is the image of $g^{-1}H$ .

So $\iota$ is a bijection and the two families are equinumerous. $\square$

Theorem(Lagrange's theorem)AdaptedAdapted from Dummit & Foote (2004), §3.2, Theorem 8 and the definition of the index that follows it, pp. 89-90; Riley, Hobson & Bence (2006), §28.7.2, the statement and both proofs, pp. 1065-1067

Suppose $G$ is a finite group and $H$ is one of its subgroups. The order of the group is then the product of two integers, the index and the order of the subgroup:

|G| = [G:H] \cdot |H| .

Two readings follow. The order of a subgroup is always a divisor of the order of the whole group; and the index, defined above by counting cosets, can be computed instead as the quotient $|G|/|H|$ .

If $K \le H \le G$ is a chain of subgroups of a finite group, then $[G:K] = [G:H]\,[H:K]$ .

Idea of the proofOriginal

The two previous facts about cosets do all the work, and they pull in opposite directions in exactly the way a counting argument needs: the cosets are disjoint and cover the group, so their sizes add up to $|G|$ ; and they all have the same size $|H|$ . A sum of equal numbers is a product, and the number of terms is by definition the index. Nothing about $H$ beyond its being a subgroup enters, which is why the conclusion is so strong for so little input.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.2, the proof of Theorem 8, pp. 89-90; Riley, Hobson & Bence (2006), §28.7.2, the final paragraph of the second proof, p. 1067

Write $k = [G:H]$ for the number of distinct left cosets of $H$ , which is finite because $G$ is, and list them as $g_1H, \dots, g_kH$ . By part 3 of the partition statement these sets are pairwise disjoint and their union is $G$ , so the cardinality of $G$ is the sum of theirs:

|G| = \sum_{i=1}^{k} |g_iH| .

By part 4 each term equals $|H|$ . Hence $|G| = k|H| = [G:H]\,|H|$ , which is the displayed identity. Since $k$ is a positive integer, $|H|$ divides $|G|$ and $k = |G|/|H|$ .

For the chain, apply the identity three times. $K$ is a subgroup of the finite group $H$ as well as of $G$ , so

[G:K] = \frac{|G|}{|K|} = \frac{|G|}{|H|}\cdot\frac{|H|}{|K|} = [G:H]\,[H:K] ,

the middle step being multiplication and division by the positive integer $|H|$ . $\square$

Theorem(Consequences for elements and for prime order)AdaptedAdapted from Dummit & Foote (2004), §3.2, Corollary 9 and Corollary 10 with their proofs, p. 90; Riley, Hobson & Bence (2006), §28.6, the deduction that a group of prime order is cyclic with no proper subgroups, p. 1062

Let $G$ be a finite group of order $n = |G|$ .

The order of every element divides $n$ : $|x|$ divides $n$ for all $x \in G$ .
$x^{\,n} = e$ for every $x \in G$ .
If $n = p$ is prime, then $G$ is cyclic, generated by any element other than $e$ ; consequently $G$ is abelian and has no proper subgroups.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.2, the proofs of Corollaries 9 and 10, p. 90

Part 1. The cyclic subgroup $\langle x \rangle$ satisfies $|\langle x \rangle| = |x|$ (Groups and subgroups), and it is a subgroup of $G$ . Lagrange's theorem applied to $H = \langle x \rangle$ gives $|x| \mid n$ .

Part 2. By part 1, $n = |x| \, q$ for some positive integer $q$ , so $x^{n} = \bigl(x^{|x|}\bigr)^{q} = e^{q} = e$ .

Part 3. Let $n = p$ be prime and take any $x \in G$ with $x \neq e$ . Then $\langle x \rangle$ is a subgroup containing both $e$ and $x$ , so $|\langle x \rangle| \ge 2$ ; and by Lagrange $|\langle x \rangle|$ divides $p$ . The only divisors of a prime are $1$ and $p$ , so $|\langle x \rangle| = p = |G|$ , and a subgroup of the same finite cardinality as $G$ is $G$ . Hence $G = \langle x \rangle$ is cyclic. Cyclic groups are abelian, since powers of one element commute. Finally, any subgroup has order dividing $p$ , hence order $1$ or $p$ , hence is one of the two trivial subgroups.

$\square$

Theorem(Euler's and Fermat's theorems)Original

Let $m \ge 2$ be an integer and let $\varphi(m)$ be the number of integers in $\{1,\dots,m\}$ coprime to $m$ . If $\gcd(a,m) = 1$ then

a^{\varphi(m)} \equiv 1 \pmod{m} .

When $m = p$ is prime this reads $a^{\,p-1} \equiv 1 \pmod{p}$ for every $a$ not divisible by $p$ , which is Fermat's little theorem.

ProofOriginal

The residue classes modulo $m$ that are coprime to $m$ form a group $(\mathbb{Z}/m\mathbb{Z})^{\times}$ under multiplication of classes: the operation is well defined and associative on classes, the class of $1$ is the identity, coprimality to $m$ is preserved by multiplication, and each such class is invertible, since $\gcd(a,m)=1$ gives integers $u,v$ with $au + mv = 1$ and hence $au \equiv 1$ . Its order is $\varphi(m)$ , by the definition of $\varphi$ .

The hypothesis $\gcd(a,m) = 1$ places the class of $a$ in this group, so part 2 of the previous statement applies to it and yields $a^{\varphi(m)} \equiv 1 \pmod m$ . For $m = p$ prime, each of $1, \dots, p-1$ is coprime to $p$ , so $\varphi(p) = p - 1$ , and $p \nmid a$ is the same condition as $\gcd(a,p) = 1$ . $\square$

Remark(Where the hypotheses are used)AdaptedAdapted from Dummit & Foote (2004), §3.2, the index of $\\{0\\}$ and of $\\langle n \\rangle$ in $\\mathbb{Z}$, p. 90, the tetrahedral counterexample to the converse and the partial converses Theorems 11 and 12, pp. 92-93, and the closing discussion of left versus right cosets, p. 95

Finiteness. Only the final count needs it. Parts 1 to 5 of the partition statement hold in any group, and the index $[G:H]$ is meaningful for infinite groups; what fails for infinite $G$ is the arithmetic, since $|G|/|H|$ is not a number. The subgroups $\{0\}$ and $n\mathbb{Z}$ of $\mathbb{Z}$ show that an infinite group can have subgroups of infinite index and of finite index at the same time.

$H$ must be a subgroup, not just a subset. Every step used one of the two closure properties: part 1 of the partition statement needs $e \in H$ , part 2 needs closure under products and inverses, and part 4 needs cancellation. For a subset that is not a subgroup the translates $gS$ still all have $|S|$ elements but they overlap irregularly, and no count follows.

The converse of Lagrange is false. A divisor of $|G|$ need not be the order of a subgroup. Dummit and Foote (Dummit & Foote (2004), §3.2, p. 92) give the group $A$ of symmetries of a regular tetrahedron, which they take to have order $12$ — the twelve rotations: if $A$ had a subgroup $H$ of order $6$ then $[A:H] = 2$ , every square $g^{2}$ would lie in $H$ , and for an element $g$ of order $3$ we would get $g = (g^{2})^{2} \in H$ ; but a tetrahedron has eight rotations of order $3$ , too many for a subgroup with six elements. What does survive is one-directional: Cauchy's theorem supplies an element, hence a subgroup, of order $p$ for each prime $p$ dividing $|G|$ , and Sylow's theorem supplies a subgroup of order $p^{a}$ when $p^{a}$ is the largest power of $p$ dividing $|G|$ .

Left is not right, but the counts agree. A left coset need not be a right coset, as the worked example below shows. Nonetheless the number of left cosets equals the number of right cosets, by part 5 of the partition statement, so the index is the same number either way. What one may not do is mix the two families when a partition is wanted.

Cosets are not subgroups. Only $H$ itself contains $e$ ; the other cosets are not closed under products. They are translates, and the geometric picture is exact: the cosets of a plane through the origin in $\mathbb{R}^{3}$ are the planes parallel to it (Hassani (Hassani (2013), §23.2, Example 23.2.11, p. 709)).

Method(Using Lagrange on a concrete group)Original

To list the cosets of a known subgroup $H \le G$ and settle the index:

Start the list with $H$ itself, which is the coset of $e$ .
Choose any element $g$ of $G$ not yet listed, and form $gH = \{gh : h \in H\}$ . By part 3 of the partition statement this is disjoint from every coset already written down, so no checking is needed.
Repeat step 2 until the listed cosets exhaust $G$ . The number of cosets is $[G:H]$ , and if $G$ is finite it must come out to $|G|/|H|$ — a useful arithmetic check on the work.
To confirm that a particular $g'$ lies in an already-listed coset $gH$ , test whether $g^{-1}g' \in H$ rather than multiplying out the whole coset.
For right cosets, repeat with $Hg$ and the test $g'g^{-1} \in H$ . If some $gH \neq Hg$ , then $H$ is not normal and the quotient construction is unavailable for it.

To constrain the subgroups of a finite group before hunting for them:

Factor $|G|$ . Only divisors of $|G|$ can be subgroup orders, and only divisors can be orders of elements.
Divisors that are prime do occur, by Cauchy's theorem; composite divisors may or may not.
An element $x$ of order $n$ gives a subgroup $\langle x\rangle$ of order $n$ at once, so finding one element of large order often settles the structure. If some $x$ has $|x| = |G|$ , the group is cyclic and the search is over.

Example(Cosets in the symmetry group of a square)Original

Let $G = D_4$ be the group of the eight symmetries of a square: the rotations by $0, 90, 180, 270$ degrees and four reflections. Write $r$ for the rotation by $90^{\circ}$ and $s$ for the reflection in a fixed diagonal, so that

r^{4} = e, \qquad s^{2} = e, \qquad sr = r^{-1}s = r^{3}s ,

the last relation saying that conjugating a rotation by a reflection reverses it. Every element is then uniquely $r^{a}s^{b}$ with $a \in \{0,1,2,3\}$ and $b \in \{0,1\}$ :

G = \{\, e,\ r,\ r^{2},\ r^{3},\ s,\ rs,\ r^{2}s,\ r^{3}s \,\}, \qquad |G| = 8 .

A subgroup whose left and right cosets differ. Take $H = \{e, s\}$ , a subgroup of order $2$ since $s^{2} = e$ . Following the method, start with $eH = \{e,s\}$ and pick elements not yet used:

rH = \{r, rs\}, \qquad r^{2}H = \{r^{2}, r^{2}s\}, \qquad r^{3}H = \{r^{3}, r^{3}s\} .

These four sets are disjoint and contain all eight elements, so there is nothing left to pick and

[G:H] = 4 = \frac{8}{2} = \frac{|G|}{|H|} ,

in agreement with Lagrange's theorem. Now the right cosets. Here $Hr = \{r, sr\}$ , and the relation $sr = r^{3}s$ turns this into

Hr = \{r, r^{3}s\} \neq \{r, rs\} = rH .

So $H$ has a left coset that is not equal to the corresponding right coset. The complete list of right cosets is $\{e,s\}$ , $\{r, r^{3}s\}$ , $\{r^{2}, r^{2}s\}$ , $\{r^{3}, rs\}$ — again four of them, as part 5 of the partition statement promises, even though two of the four sets differ from their left counterparts.

A subgroup whose cosets agree. Take $K = \{e, r^{2}\}$ instead. Since $s r^{2} = r^{-2}s = r^{2}s$ , the element $r^{2}$ commutes with both $r$ and $s$ and hence with everything, so $gK = Kg$ for every $g$ . The four cosets are

K = \{e, r^{2}\}, \quad rK = \{r, r^{3}\}, \quad sK = \{s, r^{2}s\}, \quad rsK = \{rs, r^{3}s\},

and $[G:K] = 4$ again.

Consistency check on element orders. Part 1 of the corollaries says every element order divides $8$ . Direct computation gives $|e| = 1$ ; $|r| = |r^{3}| = 4$ ; $|r^{2}| = 2$ ; and each of the four reflections $s, rs, r^{2}s, r^{3}s$ squares to $e$ , for instance $(rs)(rs) = r(sr)s = r(r^{3}s)s = r^{4}s^{2} = e$ . So the orders are $1, 2, 2, 2, 2, 2, 4, 4$ : all divisors of $8$ , with six elements of order dividing $2$ and two of order $4$ . Note that $8$ itself never occurs, so $D_4$ is not cyclic — consistent with its being non-abelian, since $rs \neq sr$ .

Example(Lagrange as an arithmetic shortcut)Original

Compute $2^{2026} \bmod 15$ without computing $2^{2026}$ .

The units modulo $15$ form the group $G = (\mathbb{Z}/15\mathbb{Z})^{\times} = \{1,2,4,7,8,11,13,14\}$ , so $|G| = \varphi(15) = 8$ . Since $\gcd(2,15) = 1$ , the class of $2$ lies in $G$ , and part 2 of the corollaries above gives $2^{8} \equiv 1 \pmod{15}$ — which one can confirm directly, $2^{4} = 16 \equiv 1$ , hence $2^{8} \equiv 1$ . Divide the exponent by the group order:

2026 = 8 \cdot 253 + 2 .

Therefore

2^{2026} = \bigl(2^{8}\bigr)^{253} \cdot 2^{2} \equiv 1^{253} \cdot 4 = 4 \pmod{15} .

The answer is $2^{2026} \equiv 4 \pmod{15}$ .

The sharper statement uses the order of the element rather than the order of the group: $|2| = 4$ in $G$ , and $4$ divides $8$ as Lagrange requires. Reducing the exponent modulo $4$ instead, $2026 = 4\cdot 506 + 2$ , gives the same residue $4$ with less arithmetic. This is the general pattern: Lagrange's theorem guarantees that the exponent may always be reduced modulo $|G|$ , and the true period, $|x|$ , is one of its divisors.

ApplicationOriginal

Counting the states produced by symmetry breaking. When a system with symmetry group $G$ settles into a configuration whose own symmetry is only the subgroup $H$ , the remaining operations of $G$ do not vanish; they map the chosen configuration to the other, equally good configurations. Two operations give the same configuration precisely when they differ by an element of $H$ , so the distinct ordered states are in bijection with the cosets $G/H$ , and there are exactly $[G:H]$ of them. A uniaxial ferromagnet breaking $O(3)$ down to the rotations about the magnetisation axis has a continuum of ground states, the sphere of directions; an Ising magnet breaking a two-element symmetry down to the trivial group has $[G:H] = 2$ states, which is why it has domains of two kinds. The same quotient is the order-parameter space whose topology classifies the defects — domain walls, vortices, monopoles — that the ordered phase can support.

Which subgroups a symmetry group can have. Lagrange's theorem is the first filter in any classification of molecular or crystal symmetry. A molecule whose point group has order $12$ can have symmetry subgroups only of orders $1, 2, 3, 4, 6, 12$ ; a substitution or a distortion that would leave a set of six operations in a group of order $8$ is impossible before any geometry is examined. Combined with Cauchy's theorem it also works the other way: a symmetry group of order divisible by $3$ must contain a three-fold operation. The orders that actually occur are worked out in Point groups and crystal symmetry.

Degeneracies and the order of an element. Because $x^{|G|} = e$ , any symmetry operation of a finite group, applied $|G|$ times, returns the system to its starting state; and because $|x|$ divides $|G|$ , it does so for the first time after a number of steps dividing the group order. For a symmetry operation acting on a quantum state this restricts the phase it can produce to a $|G|$ th root of unity, which is the arithmetic behind the labelling of states by characters in Representations of groups.

Public-key cryptography. Fermat's and Euler's theorems, proved above, are Lagrange's theorem applied to $(\mathbb{Z}/m\mathbb{Z})^{\times}$ , and they are what makes RSA work: encryption and decryption exponents are chosen to multiply to $1$ modulo $\varphi(m)$ , so that the round trip raises a message to the power $1 + k\varphi(m)$ and the group order absorbs the $k\varphi(m)$ . The security rests on $\varphi(m)$ , hence the group order, being hard to obtain without the factorisation of $m$ .

Theorem

Homomorphisms and quotient groups

Adapted

Add to PDF

Defines structure-preserving maps of groups, identifies their kernels as exactly the normal subgroups, builds the quotient group on the cosets of a normal subgroup, and proves that every homomorphic image is such a quotient.

Prerequisites: Cosets and Lagrange's theorem

Definition(Homomorphism, kernel, image)AdaptedAdapted from Dummit & Foote (2004), §3.1, the definition of the kernel, p. 75; Hassani (2013), §23.1, Definition 23.1.5, p. 705, and §23.2, Definition 23.2.9, p. 708; Riley, Hobson & Bence (2006), §28.5, the definitions of isomorphic groups and of a homomorphism, pp. 1059-1060

Let $G$ and $H$ be groups, with identities $e_G$ and $e_H$ . A map $\varphi : G \to H$ is a homomorphism if it turns products into products:

\varphi(xy) = \varphi(x)\,\varphi(y) \qquad \text{for all } x, y \in G .

The product on the left is formed in $G$ , the one on the right in $H$ ; the condition says that multiplying first and then mapping gives the same answer as mapping first and then multiplying.

A bijective homomorphism is an isomorphism, written $G \cong H$ ; an isomorphism of a group with itself is an automorphism. Isomorphic groups are the same group in different clothing, and no statement expressible in terms of the group operation can distinguish them.

Two subsets measure how far a homomorphism is from being an isomorphism:

\ker \varphi = \{\, g \in G : \varphi(g) = e_H \,\}, \qquad \operatorname{im} \varphi = \varphi(G) = \{\, \varphi(g) : g \in G \,\} .

The first is the kernel, the second the image. The map $g \mapsto e_H$ is the trivial homomorphism, with kernel all of $G$ .

Some physics texts define a homomorphism as a correspondence that is many-to-one, as Arfken, Weber and Harris (Arfken, Weber & Harris (2013), §17.1, p. 817) do. That reading is the common case, a surjective non-injective homomorphism, but we use the definition above, under which an isomorphism is a homomorphism too.

Theorem(What a homomorphism preserves)AdaptedAdapted from Dummit & Foote (2004), §3.1, Proposition 1, p. 75, and §3.3, Corollary 17(1), p. 97; Riley, Hobson & Bence (2006), §28.5, the three consequences (i)-(iii), p. 1060, and §28.6, the theorem that image and kernel are subgroups, pp. 1062-1063

Let $\varphi : G \to H$ be a homomorphism. Then:

$\varphi(e_G) = e_H$ .
$\varphi(x^{-1}) = \varphi(x)^{-1}$ for every $x \in G$ , and more generally $\varphi(x^{n}) = \varphi(x)^{n}$ for every $n \in \mathbb{Z}$ .
$\ker \varphi$ is a subgroup of $G$ and $\operatorname{im}\varphi$ is a subgroup of $H$ .
$\varphi$ is injective if and only if $\ker \varphi = \{e_G\}$ .
If $x$ has finite order, then $\varphi(x)$ has finite order and $|\varphi(x)|$ divides $|x|$ . If $\varphi$ is injective the two orders are equal; without injectivity they need not be.

Idea of the proofOriginal

A homomorphism is pinned down by what it does to products, so every claim is proved by writing the element in question as a product and pushing $\varphi$ through. The identity is the product of itself with itself; an inverse is whatever multiplies to the identity; a power is a product of copies. Part 4 is the one statement with content beyond this bookkeeping, and it is cancellation in disguise: $\varphi(x) = \varphi(y)$ says $\varphi(xy^{-1}) = e_H$ , so the failures of injectivity are exactly the non-identity elements of the kernel, and they are all alike. Part 5 then follows because $x^{|x|} = e_G$ is carried to an equation saying that $|x|$ is one exponent killing $\varphi(x)$ — not necessarily the smallest.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.1, the proof of Proposition 1, p. 75; Riley, Hobson & Bence (2006), §28.6, the proofs that image and kernel are subgroups, p. 1063

Part 1. Apply $\varphi$ to $e_G e_G = e_G$ : it gives $\varphi(e_G)\varphi(e_G) = \varphi(e_G)$ . Now cancel $\varphi(e_G)$ on the right in $H$ (Groups and subgroups) to get $\varphi(e_G) = e_H$ .

Part 2. Apply $\varphi$ to $x x^{-1} = e_G$ and use part 1: $\varphi(x)\varphi(x^{-1}) = e_H$ . By the one-sided inverse rule this already identifies $\varphi(x^{-1})$ as $\varphi(x)^{-1}$ . For powers, $\varphi(x^{n}) = \varphi(x)^{n}$ holds for $n = 0$ by part 1 and for $n \ge 1$ by induction, the step being $\varphi(x^{n}) = \varphi(x^{\,n-1}x) = \varphi(x)^{\,n-1}\varphi(x)$ ; for $n < 0$ write $x^{n} = (x^{-n})^{-1}$ and combine the positive case with the inverse rule.

Part 3. Use the subgroup criterion in both cases. Kernel: $e_G \in \ker\varphi$ by part 1, so it is non-empty; and if $\varphi(x) = \varphi(y) = e_H$ then

\varphi(xy^{-1}) = \varphi(x)\varphi(y)^{-1} = e_H e_H^{-1} = e_H ,

so $xy^{-1} \in \ker\varphi$ . Image: $e_H = \varphi(e_G) \in \operatorname{im}\varphi$ ; and if $u = \varphi(a)$ and $v = \varphi(b)$ lie in the image then $uv^{-1} = \varphi(a)\varphi(b)^{-1} = \varphi(ab^{-1})$ does too.

Part 4. Suppose $\varphi$ is injective. If $g \in \ker\varphi$ then $\varphi(g) = e_H = \varphi(e_G)$ by part 1, so $g = e_G$ by injectivity; hence the kernel is trivial. Conversely suppose $\ker\varphi = \{e_G\}$ and $\varphi(x) = \varphi(y)$ . Then

\varphi(xy^{-1}) = \varphi(x)\varphi(y)^{-1} = e_H ,

so $xy^{-1} \in \ker\varphi = \{e_G\}$ , giving $xy^{-1} = e_G$ and $x = y$ .

Part 5. Let $n = |x| < \infty$ . By part 2, $\varphi(x)^{n} = \varphi(x^{n}) = \varphi(e_G) = e_H$ , so $\varphi(x)$ has finite order, and the divisibility criterion for orders (Groups and subgroups) gives $|\varphi(x)| \mid n$ . If $\varphi$ is injective, put $m = |\varphi(x)|$ ; then $\varphi(x^{m}) = \varphi(x)^{m} = e_H = \varphi(e_G)$ , so $x^{m} = e_G$ by injectivity and $n \mid m$ . With $m \mid n$ this forces $m = n$ . $\square$

Definition(Conjugates and normal subgroups)AdaptedAdapted from Dummit & Foote (2004), §3.1, the definition of the conjugate $gng^{-1}$, of $gNg^{-1}$ and of a normal subgroup, p. 82; Hassani (2013), §23.2, Definition 23.2.13, p. 709; Riley, Hobson & Bence (2006), §28.6, the defining property of a normal subgroup, p. 1063

For $g, n$ in a group $G$ , the element $gng^{-1}$ is the conjugate of $n$ by $g$ . For a subset $N \subseteq G$ write $gNg^{-1} = \{\, gng^{-1} : n \in N \,\}$ .

A subgroup $N \le G$ is normal, written $N \trianglelefteq G$ , if

gNg^{-1} = N \qquad \text{for every } g \in G .

Normality is a statement about how $N$ sits inside $G$ , not about $N$ as a group on its own: the same abstract group can be a normal subgroup of one group and a non-normal subgroup of another.

Two families are normal for trivial reasons. In any group, $\{e\}$ and $G$ are normal. In an abelian group every subgroup is normal, since $gng^{-1} = gg^{-1}n = n$ . So the notion has content only for non-abelian $G$ .

Theorem(Normal subgroups, quotients and kernels)AdaptedAdapted from Dummit & Foote (2004), §3.1, Proposition 5, Theorem 6 and Proposition 7, pp. 81-83; Hassani (2013), §23.2, the argument preceding Definition 23.2.13 and Theorem 23.2.14, pp. 709-710

Let $N \le G$ be a subgroup. The following are equivalent.

$N \trianglelefteq G$ , that is, $gNg^{-1} = N$ for all $g \in G$ .
$gNg^{-1} \subseteq N$ for all $g \in G$ .
$gN = Ng$ for all $g \in G$ : every left coset is the corresponding right coset.
The rule

(uN)\cdot(vN) = (uv)N

is a well-defined operation on the set $G/N$ of left cosets — that is, the coset on the right depends only on the two cosets on the left and not on the representatives $u$ and $v$ chosen for them.

When these hold, $G/N$ with that operation is a group, the quotient group of $G$ by $N$ , with identity $N = eN$ and $(gN)^{-1} = g^{-1}N$ . Its order is the index: $|G/N| = [G:N]$ , so $|G/N| = |G|/|N|$ for finite $G$ . The natural projection

\pi : G \to G/N, \qquad \pi(g) = gN

is a surjective homomorphism with $\ker \pi = N$ .

Consequently the normal subgroups of $G$ are precisely the kernels of homomorphisms defined on $G$ , and nothing else is.

Idea of the proofOriginal

Condition 4 is the one we actually want, and the other three are what it costs. Suppose we insist that cosets multiply by multiplying representatives. Replacing the representative $v$ by $vn$ for some $n \in N$ changes the product $uv$ into $uvn$ , which is harmless; but replacing $u$ by $un$ changes it into $unv$ , and to recognise this as a member of $uvN$ we must be able to move $n$ past $v$ at the cost of some other element of $N$ . That is exactly the demand $v^{-1}nv \in N$ , which is condition 2 with $g = v^{-1}$ . Everything else is routine: the group axioms for $G/N$ descend from those of $G$ because the operation is defined by representatives, and the projection is a homomorphism by the very formula that defines the operation. The last sentence is then a short circle: a kernel is normal because $\varphi(gng^{-1}) = \varphi(g)e_H\varphi(g)^{-1} = e_H$ , and a normal subgroup is a kernel because it is the kernel of its own projection.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.1, the proof of Proposition 5 and the construction of the natural projection in Proposition 7, pp. 81-83; Hassani (2013), §23.2, the computation of $f(gxg^{-1})$ in Theorem 23.2.16, p. 710

1 $\Rightarrow$ 2 is immediate, equality being a special case of inclusion.

2 $\Rightarrow$ 1. Assume $gNg^{-1} \subseteq N$ for every $g$ . Applying this to $g^{-1}$ in place of $g$ gives $g^{-1}Ng \subseteq N$ as well. Conjugating that inclusion by $g$ — pre-multiplying by $g$ and post-multiplying by $g^{-1}$ — gives $N \subseteq gNg^{-1}$ . The two inclusions give $gNg^{-1} = N$ . (It is worth noticing that the quantifier over all $g$ is what makes this work; a single $g$ with $gNg^{-1} \subseteq N$ need not satisfy equality in an infinite group.)

1 $\Leftrightarrow$ 3. Multiplying $gNg^{-1} = N$ on the right by $g$ gives $gN = Ng$ , and multiplying $gN = Ng$ on the right by $g^{-1}$ gives it back.

2 $\Rightarrow$ 4. Let $u_1 \in uN$ and $v_1 \in vN$ , say $u_1 = un$ and $v_1 = vm$ with $n, m \in N$ . Insert $v^{-1}v$ and regroup:

u_1v_1 = u n v m = (uv)\bigl(v^{-1}nv\bigr)m .

By condition 2 applied with $g = v^{-1}$ , the element $n' := v^{-1}nv$ lies in $N$ , and $N$ is closed under products, so $n'm \in N$ . Hence $u_1v_1 \in (uv)N$ , and since cosets are disjoint or equal (Cosets and Lagrange's theorem), $u_1v_1N = uvN$ . The product therefore does not depend on the representatives.

4 $\Rightarrow$ 2. Assume the operation is well defined. Fix $g \in G$ and $n \in N$ . The cosets $eN = N$ and $nN$ are the same coset, because $n \in N$ ; so are $g^{-1}N$ and itself. Multiplying the pair $(N, g^{-1}N)$ using the representatives $e$ and $g^{-1}$ gives $g^{-1}N$ ; using the representatives $n$ and $g^{-1}$ gives $ng^{-1}N$ . Well-definedness forces

ng^{-1}N = g^{-1}N ,

so $ng^{-1} \in g^{-1}N$ , say $ng^{-1} = g^{-1}n_1$ with $n_1 \in N$ . Multiplying on the left by $g$ gives $gng^{-1} = n_1 \in N$ . As $g$ and $n$ were arbitrary, condition 2 holds.

The quotient is a group. Assume the four conditions. Associativity: for $u,v,w \in G$ ,

\bigl((uN)(vN)\bigr)(wN) = (uv)N \cdot wN = \bigl((uv)w\bigr)N = \bigl(u(vw)\bigr)N = uN \cdot (vw)N = (uN)\bigl((vN)(wN)\bigr),

the middle equality being associativity in $G$ . The coset $N = eN$ satisfies $(eN)(gN) = (eg)N = gN$ and likewise on the other side, so it is the identity; and $(gN)(g^{-1}N) = (gg^{-1})N = eN = N$ , so $g^{-1}N$ is the inverse of $gN$ . The elements of $G/N$ are by definition the left cosets, and their number is $[G:N]$ ; Lagrange's theorem supplies $|G|/|N|$ for finite $G$ .

The projection. $\pi(g) = gN$ is surjective because every coset has a representative. It is a homomorphism because $\pi(g_1g_2) = (g_1g_2)N = (g_1N)(g_2N) = \pi(g_1)\pi(g_2)$ , which is the defining rule read from right to left. Its kernel is $\{g : gN = N\}$ , and $gN = N = eN$ holds exactly when $e^{-1}g = g$ lies in $N$ ; so $\ker \pi = N$ .

Normal $\Leftrightarrow$ kernel. If $N \trianglelefteq G$ then $N = \ker \pi$ for the projection just built. Conversely let $N = \ker\varphi$ for a homomorphism $\varphi : G \to H$ . For $g \in G$ and $n \in N$ ,

\varphi\bigl(gng^{-1}\bigr) = \varphi(g)\,\varphi(n)\,\varphi(g)^{-1} = \varphi(g)\,e_H\,\varphi(g)^{-1} = e_H ,

so $gng^{-1} \in N$ . That is condition 2, hence $N \trianglelefteq G$ . $\square$

Theorem(First isomorphism theorem)AdaptedAdapted from Dummit & Foote (2004), §3.3, Theorem 16 and Corollary 17, p. 97; Hassani (2013), §23.2, Theorem 23.2.16, p. 710

Let $\varphi : G \to H$ be any homomorphism of groups. Its kernel is a normal subgroup of $G$ , so the quotient $G/\ker\varphi$ is defined; and the recipe "send a coset to the common value of $\varphi$ on it",

\bar\varphi : G/\ker\varphi \longrightarrow \operatorname{im}\varphi, \qquad \bar\varphi\bigl(g\ker\varphi\bigr) = \varphi(g),

is unambiguous and is an isomorphism onto the image. In short,

G/\ker\varphi \;\cong\; \operatorname{im}\varphi .

Counting the two sides gives $[\,G : \ker\varphi\,] = |\operatorname{im}\varphi|$ , and therefore, when $G$ is finite,

|G| = |\ker\varphi| \cdot |\operatorname{im}\varphi| .

Idea of the proofOriginal

A homomorphism loses exactly the information in its kernel and nothing else, so if we agree in advance to stop distinguishing elements that differ by a kernel element, what is left is a faithful copy of the image. "Agreeing to stop distinguishing" is precisely passing to the cosets of the kernel, and the previous statement has already made those cosets into a group. All that remains is to check that the obvious map is unambiguous and loses nothing, and both checks reduce to the same computation: $\varphi(u) = \varphi(v)$ if and only if $u^{-1}v \in \ker\varphi$ , which is the test for $u$ and $v$ to name the same coset. The counting formula is then Lagrange's theorem read on the quotient; for linear maps it is the rank-nullity theorem.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.3, Theorem 16 and Corollary 17 with the observation that these restate §3.1, p. 97; Hassani (2013), §23.2, the proof of Theorem 23.2.16, p. 710

Write $K = \ker\varphi$ . That $K$ is a subgroup is part 3 of the preservation statement, and that it is normal is the final step of the previous proof, so the quotient group $G/K$ exists.

The key equivalence. For $u, v \in G$ ,

\varphi(u) = \varphi(v) \iff \varphi(u)^{-1}\varphi(v) = e_H \iff \varphi\bigl(u^{-1}v\bigr) = e_H \iff u^{-1}v \in K \iff uK = vK ,

the second step using parts 1 and 2 of the preservation statement and the last being the coset-equality test (Cosets and Lagrange's theorem).

$\bar\varphi$ is well defined. If $uK = vK$ then, reading the chain from right to left, $\varphi(u) = \varphi(v)$ . So the proposed value $\varphi(g)$ depends only on the coset $gK$ , not on the representative $g$ .

$\bar\varphi$ is a homomorphism. Using the quotient operation and then the homomorphism property of $\varphi$ ,

\bar\varphi\bigl((uK)(vK)\bigr) = \bar\varphi\bigl((uv)K\bigr) = \varphi(uv) = \varphi(u)\varphi(v) = \bar\varphi(uK)\,\bar\varphi(vK) .

$\bar\varphi$ is injective. If $\bar\varphi(uK) = \bar\varphi(vK)$ then $\varphi(u) = \varphi(v)$ , and the chain read from left to right gives $uK = vK$ . (Equivalently, by part 4 of the preservation statement: $\bar\varphi(gK) = e_H$ forces $g \in K$ , that is, $gK = K$ , so the kernel of $\bar\varphi$ is trivial.)

$\bar\varphi$ is surjective onto $\operatorname{im}\varphi$ . Every element of $\operatorname{im}\varphi$ is $\varphi(g)$ for some $g \in G$ , and $\varphi(g) = \bar\varphi(gK)$ .

So $\bar\varphi$ is a bijective homomorphism, that is, an isomorphism, and $G/K \cong \operatorname{im}\varphi$ . Counting, $[G:K] = |G/K| = |\operatorname{im}\varphi|$ , and multiplying by $|K|$ and using Lagrange's theorem gives $|G| = |K|\,|\operatorname{im}\varphi|$ when $G$ is finite. $\square$

Remark(Where the hypotheses are used)AdaptedAdapted from Dummit & Foote (2004), §3.2, the proof that a subgroup of index 2 is normal, p. 91, and the example of a non-normal subgroup whose coset product is ill defined, pp. 91-92; Riley, Hobson & Bence (2006), §28.5, consequence (iii) on p. 1060 and the example $\\Phi : \\mathbb{R}\\to U(1)$, $x \\mapsto e^{ix}$, p. 1060

Normality is exactly what the quotient needs, and nothing less. Take $G = D_4$ with $r^{4} = s^{2} = e$ and $sr = r^{3}s$ , and the subgroup $H = \{e,s\}$ of order $2$ . It is not normal, since

r s r^{-1} = r\,(s r^{3}) = r\,(r\,s) = r^{2}s \notin H ,

using $sr^{3} = r^{-3}s = rs$ . The coset product fails accordingly. The left cosets are $H = \{e,s\}$ and $rH = \{r, rs\}$ , among others. Multiply $H$ by $rH$ using the representatives $e$ and $r$ : the answer is $er = r$ , lying in $rH$ . Multiply using the representatives $s \in H$ and $r \in rH$ instead: the answer is $sr = r^{3}s$ , which lies in $r^{3}H = \{r^{3}, r^{3}s\}$ , a different coset. So "multiply the representatives" does not define an operation on $D_4/H$ , and there is no quotient group. The same group has normal subgroups — $\{e,r^{2}\}$ and $\{e,r,r^{2},r^{3}\}$ — for which it does.

Index two is always enough. If $[G:H] = 2$ then $H \trianglelefteq G$ , with no computation: for $g \notin H$ the two left cosets are $H$ and $gH$ , so $gH = G \setminus H$ ; the two right cosets are $H$ and $Hg$ , so $Hg = G\setminus H$ as well; hence $gH = Hg$ , and for $g \in H$ this is clear. In $D_4$ this is why the rotation subgroup is normal while the reflection subgroup of order $2$ is not.

Finiteness is not needed. Nothing in the construction of $G/N$ or in the first isomorphism theorem assumes $G$ finite; only the numerical form $|G| = |\ker\varphi|\,|\operatorname{im}\varphi|$ does. The quotient $\mathbb{R}/2\pi\mathbb{Z} \cong U(1)$ is the standard infinite instance.

A conflict between our sources, over part 5. Riley, Hobson and Bence (Riley, Hobson & Bence (2006), §28.5, consequence (iii), p. 1060) conclude that under a homomorphism an element and its image always have "the same order", whereas Dummit and Foote (Dummit & Foote (2004), §3.1, Proposition 1(3), p. 75) give only the exponent rule $\varphi(x^{n}) = \varphi(x)^{n}$ , from which divisibility and no more follows. We follow Dummit and Foote: part 5 above asserts only that $|\varphi(x)|$ divides $|x|$ , with equality when $\varphi$ is injective. Equality does fail in general, and it fails for the example given on the same page of Riley, Hobson and Bence: in $\Phi : (\mathbb{R},+) \to U(1)$ , $x \mapsto e^{\mathrm{i}x}$ , the element $x = \pi$ has infinite order in $\mathbb{R}$ while its image $-1$ has order $2$ . The argument printed there establishes only that $\Phi(x)^{m} = I'$ when $x^{m} = I$ , which is the divisibility statement.

Where each hypothesis enters the isomorphism theorem. The homomorphism property is used twice: once to make $K$ a subgroup and normal, and once to make $\bar\varphi$ multiplicative. Injectivity of $\bar\varphi$ is where passing to the kernel's cosets matters — cosets of a smaller normal subgroup would leave $\bar\varphi$ well defined but no longer injective, and cosets of a larger one would make it ill defined.

Method(Identifying a quotient group)Original

A quotient $G/N$ is almost never described usefully by listing cosets. The efficient route is to recognise it as the image of a map.

Guess the answer: find a group $H$ and a map $\varphi : G \to H$ that forgets exactly the information $N$ carries — a determinant, a sign, a modulus, a residue, a projection onto one coordinate.
Check that $\varphi$ is a homomorphism, by verifying $\varphi(xy) = \varphi(x)\varphi(y)$ on general elements.
Compute $\ker\varphi$ by solving $\varphi(g) = e_H$ . If it comes out as $N$ , then $N$ is normal automatically, with no conjugation to check.
Compute $\operatorname{im}\varphi$ . Surjectivity onto $H$ is usually easiest to see by exhibiting one preimage for each element of $H$ .
Conclude $G/N \cong \operatorname{im}\varphi$ by the first isomorphism theorem.
For finite groups, check the arithmetic: $|G| = |\ker\varphi|\cdot|\operatorname{im}\varphi|$ .

To go the other way and test a given subgroup $N$ for normality, in decreasing order of cheapness: is $G$ abelian? is $[G:N] = 2$ ? is $N$ visibly a kernel? otherwise verify $gng^{-1} \in N$ for $g$ and $n$ running over generating sets of $G$ and $N$ .

Example(A quotient of the units modulo fifteen)Original

Let $G = (\mathbb{Z}/15\mathbb{Z})^{\times} = \{1,2,4,7,8,11,13,14\}$ , an abelian group of order $8$ under multiplication of residue classes, and let

\varphi : G \to G, \qquad \varphi(x) = x^{2} .

It is a homomorphism. $\varphi(xy) = (xy)^{2} = xyxy = x^{2}y^{2} = \varphi(x)\varphi(y)$ , where the middle step uses commutativity. (On a non-abelian group squaring is not a homomorphism; this is a genuine use of the hypothesis.)

Kernel. Square each element modulo $15$ :

1^{2} = 1,\quad 2^{2} = 4,\quad 4^{2} = 16 = 1,\quad 7^{2} = 49 = 4,\quad 8^{2} = 64 = 4,\quad 11^{2} = 121 = 1,\quad 13^{2} = 169 = 4,\quad 14^{2} = 196 = 1 .

(Each reduction subtracts a multiple of $15$ : $16-15 = 1$ , $49-45 = 4$ , $64-60 = 4$ , $121-120 = 1$ , $169-165 = 4$ , $196-195=1$ .) Hence

K = \ker\varphi = \{1, 4, 11, 14\}, \qquad |K| = 4 ,

and $\operatorname{im}\varphi = \{1,4\}$ , of order $2$ .

The arithmetic check. $|G| = 8 = 4 \cdot 2 = |\ker\varphi|\cdot|\operatorname{im}\varphi|$ , as the first isomorphism theorem requires.

The quotient explicitly. $G$ is abelian, so $K$ is normal and $G/K$ exists, with $[G:K] = 8/4 = 2$ : there are exactly two cosets. One is $K$ itself; the other is

2K = \{2\cdot 1,\ 2\cdot 4,\ 2\cdot 11,\ 2\cdot 14\} = \{2,\ 8,\ 22,\ 28\} = \{2, 8, 7, 13\} ,

reducing $22 = 15+7$ and $28 = 15+13$ . The two cosets $\{1,4,11,14\}$ and $\{2,7,8,13\}$ are disjoint and together give all eight elements, as they must. The multiplication table of $G/K$ is forced: $K$ is the identity, and $(2K)(2K) = 4K = K$ because $4 \in K$ . So $G/K$ is cyclic of order $2$ .

And it matches the image. $\operatorname{im}\varphi = \{1,4\}$ is also cyclic of order $2$ , with $4^{2} = 1$ . The isomorphism $\bar\varphi$ of the theorem sends $K \mapsto 1$ and $2K \mapsto 4$ . Reading it the other way: the map $\varphi$ "forgets" which of the four square roots an element is, and $K$ is precisely the set of four elements that $\varphi$ cannot distinguish from $1$ .

A second quotient of the same group, for contrast. Take $L = \langle 2 \rangle = \{1,2,4,8\}$ , of order $4$ and index $2$ . Its two cosets are $L$ and $7L = \{7, 14, 13, 11\}$ , and $G/L$ is again cyclic of order $2$ . So two different normal subgroups of the same order can have isomorphic quotients while being different subgroups: $K$ is the Klein four-group, since every element of $K$ squares to $1$ , while $L$ is cyclic, generated by $2$ of order $4$ . The quotient records less than the subgroup does.

Example(Two quotients that physics uses constantly)Original

Phase and the circle. Let $\omega > 0$ be a fixed frequency and define

\Phi : (\mathbb{R},+) \to U(1), \qquad \Phi(t) = e^{\mathrm{i}\omega t} ,

where $U(1) = \{z \in \mathbb{C} : |z| = 1\}$ under multiplication. It is a homomorphism because $e^{\mathrm{i}\omega(t_1+t_2)} = e^{\mathrm{i}\omega t_1}e^{\mathrm{i}\omega t_2}$ , which is the statement that the exponential turns sums into products. It is surjective, since every unit-modulus number is $e^{\mathrm{i}\theta}$ for some real $\theta$ and we may take $t = \theta/\omega$ . Its kernel is the set of $t$ with $\omega t \in 2\pi\mathbb{Z}$ , that is,

\ker \Phi = \frac{2\pi}{\omega}\,\mathbb{Z} ,

the integer multiples of the period. The first isomorphism theorem gives

\mathbb{R}\Big/\tfrac{2\pi}{\omega}\mathbb{Z} \;\cong\; U(1) .

For $\omega = 4\ \mathrm{s}^{-1}$ the kernel is generated by the period $T = 2\pi/4 = \pi/2 \approx 1.5708\ \mathrm{s}$ : two instants of time give the same phase exactly when they differ by a whole number of half- $\pi$ seconds. This is the precise sense in which the phase of an oscillator is "time modulo the period", and it is why phase lives on a circle rather than a line.

Determinant and the unimodular group. The determinant $\det : GL(n,\mathbb{R}) \to \mathbb{R}\setminus\{0\}$ is a homomorphism, because $\det(AB) = \det A \det B$ (Determinants). It is surjective: $\operatorname{diag}(\lambda, 1, \dots, 1)$ has determinant $\lambda$ for any $\lambda \neq 0$ . Its kernel is $SL(n,\mathbb{R})$ , the matrices of determinant $1$ . So $SL(n,\mathbb{R})$ is normal in $GL(n,\mathbb{R})$ without any conjugation being computed, and

GL(n,\mathbb{R}) \big/ SL(n,\mathbb{R}) \;\cong\; \mathbb{R}\setminus\{0\} ,

as Hassani (Hassani (2013), §23.2, Example 23.2.17, p. 711) observes. The same argument with $\det : U(n) \to U(1)$ gives $U(n)/SU(n) \cong U(1)$ , which is the statement that a unitary transformation is a special unitary one together with an overall phase.

ApplicationOriginal

Representations are homomorphisms. A representation of a group is a homomorphism into a group of matrices, so everything above applies to it directly. The kernel is the set of symmetry operations the representation cannot see; a representation is faithful exactly when its kernel is trivial, which is part 4 of the preservation statement, and an unfaithful representation is really a representation of the quotient by its kernel, which is the first isomorphism theorem. That is why the representations of $G$ that are trivial on a normal subgroup $N$ are in bijection with the representations of $G/N$ — the standard first step in reducing a large symmetry group to a manageable one (Representations of groups).

Gauge symmetry and physical configurations. In gauge theory the configurations of a field are acted on by a group of gauge transformations, and two configurations related by one of them are physically the same. The physical configuration space is the quotient, and the statement that it is a space with a group structure, rather than an unstructured collection, is the normality condition. The same construction gives the order-parameter spaces $G/H$ of condensed-matter physics and the quotient $\mathbb{R}/2\pi\mathbb{Z}$ that makes a phase angle well defined.

Two-to-one maps and spin. Many of the most useful homomorphisms in physics are not injective, and the kernel is the physics. The map $SU(2) \to SO(3)$ that sends a unit quaternion to the rotation it performs has kernel $\{\pm \mathbb{1}\}$ , of order $2$ , so $SO(3) \cong SU(2)/\{\pm\mathbb{1}\}$ : a rotation corresponds to two elements of $SU(2)$ , differing by a sign, which is exactly why a spin- $\tfrac12$ state changes sign under a rotation by $2\pi$ (The rotation group and SU(2); Quaternions). The determinant maps of the previous example do the same job for $U(n)$ : separating an overall phase, which is unobservable, from the rest.

Conserved quantities and selection rules. Parity is the homomorphism from a symmetry group onto $\{\pm 1\}$ whose kernel is the subgroup of orientation-preserving operations — a subgroup of index $2$ , hence normal with no work. Because the target group is $\{\pm 1\}$ , the possible parity values form a group of order $2$ and multiply: a product of two odd operations is even. Every multiplicative quantum number used in a selection rule arises this way, as a homomorphism of the symmetry group onto a small abelian group, and the rule that forbids a transition is the statement that the two states lie over different elements of the quotient.

Modular arithmetic as a quotient. $\mathbb{Z}/n\mathbb{Z}$ is the quotient of $(\mathbb{Z},+)$ by the normal subgroup $n\mathbb{Z}$ , and the first isomorphism theorem applied to $k \mapsto e^{2\pi \mathrm{i}k/n}$ identifies it with the group of $n$ th roots of unity. That identification is the algebraic content of the discrete Fourier transform and of Bloch's theorem on a lattice of $n$ sites.

Theorem

Group actions

Adapted

Add to PDF

Gives the vocabulary of a group acting on a set — orbit, stabilizer, transitivity — proves that the orbit of a point is in bijection with the cosets of its stabilizer, and derives the counting lemma that averages fixed points to count orbits.

Prerequisites: Groups and subgroups, Cosets and Lagrange's theorem

Definition(Actions, orbits and stabilizers)AdaptedAdapted from Dummit & Foote (2004), §1.7, p. 41 and §4.1, pp. 112-115; Hassani (2013), §23.3, Defs 23.3.1 and 23.3.3, pp. 713-714; Lee (2013), Ch. 7, pp. 161-162

Let $G$ be a group with identity $e$ and let $A$ be a non-empty set. A left action of $G$ on $A$ is a map $G \times A \to A$ , written $(g, a) \mapsto g \cdot a$ , such that

g_1 \cdot (g_2 \cdot a) = (g_1 g_2) \cdot a \qquad \text{and} \qquad e \cdot a = a

for all $g_1, g_2 \in G$ and all $a \in A$ . We then say that $G$ acts on $A$ . A right action is a map $A \times G \to A$ , written $(a,g) \mapsto a \cdot g$ , with $(a \cdot g_1)\cdot g_2 = a \cdot (g_1g_2)$ and $a \cdot e = a$ .

Fix an action of $G$ on $A$ . For $g \in G$ write $\sigma_g \colon A \to A$ for the map $\sigma_g(a) = g \cdot a$ . The following names are used throughout.

The orbit of $a \in A$ is $G \cdot a = \{\, g \cdot a : g \in G \,\}$ , the set of points reachable from $a$ . The set of orbits is written $A/G$ and called the orbit space.
The stabilizer of $a$ is $G_a = \{\, g \in G : g \cdot a = a \,\}$ , also called the isotropy group or the little group at $a$ .
The kernel of the action is $\{\, g \in G : g \cdot a = a \text{ for all } a \in A \,\} = \bigcap_{a \in A} G_a$ . The action is faithful (or effective) if its kernel is $\{e\}$ , and free if $G_a = \{e\}$ for every $a$ .
The action is transitive if there is only one orbit: for any $a, b \in A$ there is a $g \in G$ with $g \cdot a = b$ .
For $g \in G$ , the fixed-point set is $\mathrm{Fix}(g) = \{\, a \in A : g \cdot a = a \,\}$ .

Two elementary facts are used below. First, each $\sigma_g$ is a bijection of $A$ , with inverse $\sigma_{g^{-1}}$ : indeed $\sigma_{g^{-1}}(\sigma_g(a)) = g^{-1}\cdot(g \cdot a) = (g^{-1}g)\cdot a = e \cdot a = a$ by the first and then the second axiom, and the same computation with $g$ and $g^{-1}$ exchanged gives $\sigma_g \circ \sigma_{g^{-1}} = \mathrm{id}$ . Second, $g \mapsto \sigma_g$ is a homomorphism from $G$ into the group $S_A$ of all bijections of $A$ (The symmetric group), because the first axiom says precisely $\sigma_{g_1g_2} = \sigma_{g_1}\circ\sigma_{g_2}$ ; this homomorphism is the permutation representation afforded by the action, and its kernel is the kernel of the action. In particular each $G_a$ is a subgroup of $G$ : it is the preimage of the subgroup $\{\,\pi \in S_A : \pi(a) = a\,\}$ , or directly, $e \in G_a$ , and if $g, h$ fix $a$ then $(gh)\cdot a = g\cdot(h\cdot a) = g \cdot a = a$ and $g^{-1}\cdot a = g^{-1}\cdot (g\cdot a) = a$ .

Theorem(Orbit–stabilizer theorem)AdaptedAdapted from Dummit & Foote (2004), §4.1, Prop. 2, pp. 114-115

Let a group $G$ act on a non-empty set $A$ .

The relation $a \sim b$ defined by " $b = g \cdot a$ for some $g \in G$ " is an equivalence relation on $A$ , and its equivalence classes are exactly the orbits. Hence the orbits partition $A$ .
For each $a \in A$ the map

\Phi \colon \{\text{left cosets of } G_a \text{ in } G\} \longrightarrow G \cdot a , \qquad \Phi(g\,G_a) = g \cdot a ,

is a well-defined bijection. Consequently

\lvert G \cdot a \rvert = [\,G : G_a\,] ,

the index of the stabilizer, whether or not $G$ is finite. 3. If $G$ is finite then $\lvert G \cdot a\rvert$ divides $\lvert G\rvert$ and

\lvert G \cdot a \rvert \cdot \lvert G_a \rvert = \lvert G \rvert .

Idea of the proofOriginal

A point of the orbit of $a$ is named by a group element that carries $a$ to it, and two group elements give the same point exactly when they differ by something that leaves $a$ alone. "Differing by an element of $G_a$ " is precisely the relation that defines the left cosets of $G_a$ , so the names and the points match up one for one. Part 3 is then part 2 read through Lagrange's theorem, which says that the number of cosets times the size of the subgroup is the order of the group.

ProofAdaptedAdapted from Dummit & Foote (2004), §4.1, Prop. 2, pp. 114-115

Part 1: $\sim$ is an equivalence relation.

Reflexive. $a = e \cdot a$ by the second axiom, so $a \sim a$ .
Symmetric. If $b = g \cdot a$ then acting by $g^{-1}$ and using the first axiom, $g^{-1}\cdot b = (g^{-1}g)\cdot a = e \cdot a = a$ , so $b \sim a$ .
Transitive. If $b = g \cdot a$ and $c = h \cdot b$ then $c = h \cdot (g \cdot a) = (hg)\cdot a$ by the first axiom, and $hg \in G$ because $G$ is closed under multiplication; so $a \sim c$ .

The class of $a$ is $\{\,b : b = g\cdot a \text{ for some } g\,\} = G\cdot a$ , which is the orbit. The classes of an equivalence relation are disjoint and cover the set, which is the assertion that the orbits partition $A$ .

Part 2: $\Phi$ is well defined and injective. For $g, h \in G$ ,

g \cdot a = h \cdot a \iff h^{-1}\cdot (g\cdot a) = h^{-1}\cdot(h \cdot a) \iff (h^{-1}g)\cdot a = a \iff h^{-1}g \in G_a \iff g\,G_a = h\,G_a .

The first equivalence is obtained by acting with $h^{-1}$ , which is reversible because $\sigma_{h^{-1}}$ is a bijection; the second uses the first axiom on both sides together with $e\cdot a = a$ ; the third is the definition of $G_a$ ; the fourth is the standard criterion for equality of left cosets (Cosets and Lagrange's theorem). Reading the chain from right to left says that $\Phi$ does not depend on the coset representative, so it is well defined; reading it from left to right says that $\Phi$ is injective.

Part 2: $\Phi$ is surjective. A point of the orbit is by definition $g\cdot a$ for some $g \in G$ , and that point is the image $\Phi(g\,G_a)$ .

Hence $\Phi$ is a bijection, and the number of elements of $G \cdot a$ equals the number of left cosets of $G_a$ , which is by definition the index $[G : G_a]$ .

Part 3. $G_a$ is a subgroup of $G$ , as checked in the definition above. If $G$ is finite, Lagrange's theorem gives $\lvert G\rvert = [G:G_a]\,\lvert G_a\rvert$ , and substituting $[G:G_a] = \lvert G\cdot a\rvert$ from part 2 gives the displayed product; in particular $\lvert G \cdot a\rvert$ divides $\lvert G\rvert$ . $\square$

Remark(Where the hypotheses are used)Original

Both axioms are needed, and each does a separate job. The axiom $e \cdot a = a$ is what makes $\sim$ reflexive and what puts $e$ in $G_a$ ; without it the "action" $g \cdot a = a_0$ for a fixed $a_0$ satisfies $g_1\cdot(g_2\cdot a) = a_0 = (g_1g_2)\cdot a$ , yet no point other than $a_0$ lies in its own orbit and the partition statement fails. The composition axiom is used at every other step: in symmetry and transitivity of $\sim$ , in the proof that $\sigma_g$ is invertible, and in the middle equivalence of the chain defining $\Phi$ .

Finiteness is used only in part 3. Parts 1 and 2 hold for any group and any set: $[G:G_a]$ is defined as the cardinality of the set of cosets, and the bijection $\Phi$ is a statement about cardinalities. The product formula needs $\lvert G \rvert$ to be a number. For instance $G = \mathbb{Z}$ acting on $A = \mathbb{Z}$ by $n \cdot a = n + a$ has one orbit and trivial stabilizers, so part 2 reads $\lvert A \rvert = [\mathbb{Z}:\{0\}]$ , correctly, while " $\lvert G\cdot a\rvert \cdot \lvert G_a\rvert = \lvert G\rvert$ " says only $\infty \cdot 1 = \infty$ .

Left cosets, not right. The chain in the proof produces the condition $h^{-1}g \in G_a$ , which is the criterion for $gG_a = hG_a$ . Had we written $\Phi(G_a g) = g\cdot a$ the map would not be well defined in general, because $G_a g = G_a h$ means $gh^{-1} \in G_a$ , a different condition unless $G_a$ is normal. For a right action the roles are exchanged and right cosets appear. (Lee (2013), Ch. 7, p. 162) notes that the two kinds of action carry the same information: given a right action, $g \cdot a := a \cdot g^{-1}$ is a left action, and conversely; the inverse is what repairs the order of composition.

The stabilizers along an orbit are conjugate, not equal. If $b = g\cdot a$ then $G_b = g\,G_a\,g^{-1}$ , since $h \cdot b = b \iff (g^{-1}hg)\cdot a = a$ . So "the" stabilizer of an orbit is only a conjugacy class of subgroups (Conjugacy classes); its order, and hence the orbit-stabilizer count, is nevertheless the same at every point of the orbit.

Theorem(The counting lemma (Burnside, Cauchy–Frobenius))AdaptedAdapted from Dummit & Foote (2004), §19.1, Exercise 8, p. 877

Let a finite group $G$ act on a finite set $A$ , and let $t$ be the number of orbits. Then

t = \frac{1}{\lvert G\rvert}\sum_{g \in G} \lvert \mathrm{Fix}(g)\rvert :

the number of orbits is the average number of points left fixed, the average being taken over the whole group.

(Dummit & Foote (2004), §19.1, Exercise 8, p. 877) states the identity in the equivalent product form $t\lvert G\rvert = \sum_{g\in G}\lvert\mathrm{Fix}(g)\rvert$ for a subgroup $G \leq S_n$ acting on $\{1, \dots, n\}$ , and records that the result is often called Burnside's lemma although it goes back to Frobenius. The proof below is for a general finite group acting on a general finite set; the case Dummit and Foote state is the case $A = \{1,\dots,n\}$ .

Idea of the proofOriginal

Count the pairs $(g, a)$ with $g \cdot a = a$ in two ways. Summing first over group elements gives $\sum_g \lvert\mathrm{Fix}(g)\rvert$ ; summing first over points of the set gives $\sum_a \lvert G_a\rvert$ . The orbit–stabilizer theorem converts each $\lvert G_a\rvert$ into $\lvert G\rvert/\lvert G\cdot a\rvert$ , and then the points of one orbit contribute $\lvert G\rvert$ between them, once per orbit.

ProofOriginal

Let

S = \{\,(g,a) \in G \times A : g\cdot a = a \,\} ,

a finite set because $G$ and $A$ are finite.

Counting $S$ by its first coordinate. For each fixed $g$ , the pairs in $S$ with that first coordinate are $(g, a)$ with $a \in \mathrm{Fix}(g)$ , so

\lvert S\rvert = \sum_{g \in G} \lvert \mathrm{Fix}(g)\rvert .

Counting $S$ by its second coordinate. For each fixed $a$ , the pairs in $S$ with that second coordinate are $(g,a)$ with $g \in G_a$ , so

\lvert S\rvert = \sum_{a \in A} \lvert G_a\rvert .

Replacing stabilizers by orbit sizes. $G$ is finite, so part 3 of the orbit–stabilizer theorem applies at every $a$ and gives $\lvert G_a\rvert = \lvert G\rvert / \lvert G\cdot a\rvert$ . Hence

\lvert S\rvert = \sum_{a \in A} \frac{\lvert G\rvert}{\lvert G\cdot a\rvert} = \lvert G\rvert \sum_{a\in A} \frac{1}{\lvert G\cdot a\rvert} .

Grouping the sum by orbits. By part 1 the orbits partition $A$ , so the last sum may be taken orbit by orbit. Let $O_1, \dots, O_t$ be the distinct orbits. Every $a$ in the orbit $O_i$ has $G\cdot a = O_i$ , so it contributes $1/\lvert O_i\rvert$ , and there are $\lvert O_i\rvert$ such points:

\sum_{a \in A} \frac{1}{\lvert G\cdot a\rvert} = \sum_{i=1}^{t} \sum_{a \in O_i} \frac{1}{\lvert O_i\rvert} = \sum_{i=1}^{t} \lvert O_i\rvert \cdot \frac{1}{\lvert O_i\rvert} = t .

Therefore $\lvert S\rvert = t\,\lvert G\rvert$ . Equating the two counts of $\lvert S\rvert$ and dividing by $\lvert G\rvert \neq 0$ gives the stated formula. $\square$

Remark(Where the hypotheses are used in the counting lemma)Original

$G$ finite is used twice: to apply the product form of the orbit–stabilizer theorem, and to divide by $\lvert G\rvert$ at the end. $A$ finite is used to make $\lvert S \rvert$ and the sum over $a$ finite, so that the two counts may be equated and rearranged. Both are essential. Take $G = \mathbb{Z}$ acting on $A = \mathbb{Z}$ by translation: there is one orbit, $\mathrm{Fix}(0) = \mathbb{Z}$ and $\mathrm{Fix}(n) = \emptyset$ for $n \neq 0$ , and the right-hand side is the meaningless $\infty/\infty$ . Take $G = \{\pm 1\}$ acting on $A = \mathbb{Z}$ by $\varepsilon \cdot a = \varepsilon a$ : here $A$ is infinite, $\mathrm{Fix}(1) = \mathbb{Z}$ , $\mathrm{Fix}(-1) = \{0\}$ , and again the average is not defined, although the number of orbits is.

Nothing requires the action to be faithful, free or transitive. Elements acting trivially simply contribute $\lvert A\rvert$ each to the sum, which is correct: if the kernel has order $k$ then the action factors through a faithful action of a group of order $\lvert G\rvert/k$ on $A$ , and both sides of the identity are multiplied by $k$ .

Method(Counting configurations up to a symmetry)Original

To count the configurations of a finite object that are distinct once a symmetry group is allowed to move them:

Identify the set $A$ . List the configurations as labelled objects, so that $A$ is a plain finite set with no symmetry quotient taken yet. For colourings of $n$ positions with $q$ colours, $\lvert A\rvert = q^n$ .
Identify the group $G$ and check it acts. Verify the two axioms, usually by exhibiting $G$ as a group of symmetries of the underlying object; then $g$ acts on a configuration by moving its positions.
Find $\lvert G\rvert$ , often most easily by the orbit–stabilizer theorem applied to some convenient set of geometric features: $\lvert G\rvert = (\text{size of one orbit}) \times (\text{order of the stabilizer of one of its points})$ .
Sort $G$ into types of element with the same cycle structure on the $n$ positions, and record how many elements each type has. (Elements in the same conjugacy class always have the same cycle structure, so the classes are a safe sorting.)
Compute $\lvert\mathrm{Fix}(g)\rvert$ for one element of each type. A colouring is fixed by $g$ exactly when it is constant on every cycle of $g$ acting on the positions, so $\lvert \mathrm{Fix}(g)\rvert = q^{\,c(g)}$ where $c(g)$ is the number of cycles, fixed positions included.
Average. Add up $(\text{number of elements of the type}) \times q^{c(g)}$ over the types and divide by $\lvert G\rvert$ . The answer is an integer; if it is not, a cycle count or a class size is wrong.

Example(Colouring the faces of a cube with three colours)Original

How many ways are there to paint the six faces of a cube, each face one of three colours, if two paintings are the same when one can be rotated into the other?

Step 1: the set. $A$ is the set of colourings of the six labelled faces, so $\lvert A\rvert = 3^6 = 729$ .

Step 2: the group. $G$ is the group of rotations of the cube (rotations only, not reflections), acting on $A$ by $(g\cdot f)(\text{face}) = f(g^{-1}\,\text{face})$ ; this is a left action because the inverse reverses the order of composition twice.

Step 3: the order of $G$ , by orbit–stabilizer. Let $G$ act on the six faces. The action is transitive, because a face can be brought to any other by a quarter- or half-turn, so the orbit of a face has $6$ elements. The rotations fixing a given face are the four turns through $0, \pi/2, \pi, 3\pi/2$ about the axis through that face and the opposite one, so the stabilizer has order $4$ . By part 3 of the orbit–stabilizer theorem,

\lvert G\rvert = 6 \times 4 = 24 .

Step 4: the types of rotation and their cycle structures on the faces.

Type of rotation	Number	Cycles on the 6 faces	$c(g)$	$3^{c(g)}$
identity	$1$	six fixed faces	$6$	$729$
$\pm\pi/2$ about a face axis	$3 \times 2 = 6$	$2$ fixed, one $4$ -cycle	$3$	$27$
$\pi$ about a face axis	$3$	$2$ fixed, two $2$ -cycles	$4$	$81$
$\pm 2\pi/3$ about a vertex axis	$4 \times 2 = 8$	two $3$ -cycles	$2$	$9$
$\pi$ about an edge axis	$6$	three $2$ -cycles	$3$	$27$

The counts add to $1 + 6 + 3 + 8 + 6 = 24 = \lvert G\rvert$ , which checks Step 3 and confirms that no rotation has been missed. (There are $3$ face axes, $4$ body diagonals and $6$ pairs of opposite edges.)

Step 5: the fixed colourings. A colouring is fixed by $g$ precisely when every face of a cycle of $g$ gets the same colour, so there are $3$ free choices per cycle and $\lvert\mathrm{Fix}(g)\rvert = 3^{c(g)}$ , as tabulated.

Step 6: the average.

\sum_{g\in G}\lvert\mathrm{Fix}(g)\rvert = 1\cdot 729 + 6\cdot 27 + 3\cdot 81 + 8\cdot 9 + 6\cdot 27 = 729 + 162 + 243 + 72 + 162 = 1368 ,

so the number of orbits is

t = \frac{1368}{24} = 57 .

There are $57$ distinct three-colourings of the cube's faces.

Checks. First, $57$ is an integer, as it must be. Second, the same six steps with $q$ colours in place of $3$ give the polynomial

t(q) = \frac{q^6 + 3q^4 + 12 q^3 + 8 q^2}{24} ,

the four terms coming from the five rows of the table with the two rows of three cycles combined. At $q = 1$ this must give $1$ , since there is only one colouring at all, and indeed $(1 + 3 + 12 + 8)/24 = 1$ . At $q = 2$ it gives $(64 + 48 + 96 + 32)/24 = 240/24 = 10$ , the known number of distinct ways to paint a cube's faces black or white. At $q = 3$ it returns $1368/24 = 57$ .

ApplicationOriginal

Degeneracy is an orbit, and symmetry explains it. If a Hamiltonian commutes with every element of a symmetry group $G$ , then $G$ acts on each energy eigenspace, and the states of a degenerate multiplet form orbits under that action. When the action on a chosen state is understood geometrically, the orbit–stabilizer theorem gives the size of the multiplet directly as $\lvert G\rvert$ divided by the order of the subgroup that leaves the state alone — the "little group" of the state. The same arithmetic organises the splitting of a level when a perturbation shrinks $G$ to a subgroup $H$ : the single $G$ -orbit breaks into $H$ -orbits, and the orbit–stabilizer theorem applied to $H$ gives the sizes of the pieces. The representation-theoretic refinement of this bookkeeping is the subject of Representations of groups and Orthogonality relations and characters.

Site multiplicities in a crystal. A crystallographic point group $G$ acts on the positions in a unit cell. The number of positions equivalent to a given one is $\lvert G \rvert / \lvert G_a\rvert$ , where $G_a$ is the site-symmetry group of that position: an atom on a general position has $G_a = \{e\}$ and multiplicity $\lvert G\rvert$ , while an atom sitting on a mirror plane or a rotation axis has a larger $G_a$ and correspondingly fewer copies. This is exactly the orbit–stabilizer theorem and it is how the multiplicities in crystallographic tables are generated; see Point groups and crystal symmetry.

Counting distinct structures. The counting lemma is the standard tool for enumerating configurations that symmetry makes indistinguishable: substituted isomers of a molecule (how many distinct dichloro-derivatives of a given skeleton exist), occupations of the sites of a crystal lattice by two species of atom in alloy thermodynamics, and distinct spin configurations on a symmetric cluster in statistical mechanics. In each case one is counting orbits of a finite symmetry group on a finite set of labelled configurations, and the average-of-fixed-points formula turns the problem into a short sum over the symmetry types, as in the worked example.

Homogeneous spaces. For continuous groups the bijection of part 2 survives as a diffeomorphism between an orbit and a coset space. The rotation group $\mathrm{SO}(3)$ acts transitively on the unit sphere, and the rotations fixing the north pole are the rotations about the vertical axis, a copy of $\mathrm{SO}(2)$ ; so the sphere is $\mathrm{SO}(3)/\mathrm{SO}(2)$ . (Lee (2013), Ch. 21, p. 541) develops the orbit space $M/G$ in this setting, and The rotation group and SU(2) takes up the rotation group itself. The same description underlies the identification of the space of pure spin- $\tfrac12$ states with the Bloch sphere $\mathrm{SU}(2)/\mathrm{U}(1)$ , and the classification of vacua in a theory whose symmetry $G$ is spontaneously broken to a subgroup $H$ : the degenerate vacua form one orbit, so the vacuum manifold is $G/H$ .

Definition

Conjugacy classes

Adapted

Add to PDF

Defines conjugation, conjugacy classes, the centralizer and the centre, shows that a class has as many elements as the centralizer has cosets, and assembles these counts into the class equation.

Prerequisites: Groups and subgroups, Cosets and Lagrange's theorem, Group actions

Definition(Conjugation, classes, centralizer, centre)AdaptedAdapted from Dummit & Foote (2004), §4.3, pp. 122-123; Hassani (2013), Def. 23.2.18, p. 711; Riley, Hobson & Bence (2006), §28.7.3, pp. 1068-1069

Let $G$ be a group. For $g, x \in G$ the element

{}^{g}x \;=\; g\,x\,g^{-1}

is the conjugate of $x$ by $g$ , and $x, y \in G$ are conjugate if $y = gxg^{-1}$ for some $g \in G$ . The set

K_x \;=\; \{\, g x g^{-1} : g \in G \,\}

of all elements conjugate to $x$ is the conjugacy class of $x$ .

Two subgroups attached to $x$ record how much of $G$ fails to move it:

the centralizer $C_G(x) = \{\, g\in G : gx = xg \,\}$ , the elements that commute with $x$ ;
the centre $Z(G) = \{\, z \in G : zg = gz \text{ for all } g \in G \,\} = \bigcap_{x \in G} C_G(x)$ , the elements that commute with everything.

More generally, for a subset $S \subseteq G$ one writes $gSg^{-1} = \{\,gsg^{-1} : s \in S\,\}$ , calls $S$ and $T$ conjugate subsets when $T = gSg^{-1}$ for some $g$ , and calls $N_G(S) = \{\, g \in G : gSg^{-1} = S \,\}$ the normalizer of $S$ ; a subgroup is normal exactly when its normalizer is all of $G$ (Homomorphisms and quotient groups). A function $f$ on $G$ with $f(gxg^{-1}) = f(x)$ for all $g, x$ , that is, a function constant on each class, is a class function.

Convention. We conjugate on the left, $x \mapsto gxg^{-1}$ , following (Dummit & Foote (2004), §4.3, p. 122) and (Hassani (2013), Def. 23.2.18, p. 711). (Riley, Hobson & Bence (2006), §28.7.3, p. 1068) writes the relation the other way round, $Y = G_i^{-1} X G_i$ . The two give the same classes, since $G_i^{-1} X G_i$ is the conjugate of $X$ by $G_i^{-1}$ , but they differ by an inverse in every intermediate formula, so a convention must be fixed before any computation.

Definition(Classes and centralizers)AdaptedAdapted from Dummit & Foote (2004), §4.3, pp. 122-123, Prop. 6; Riley, Hobson & Bence (2006), §28.7.3, pp. 1068-1069

Let $G$ be a group.

$g \cdot x = gxg^{-1}$ defines an action of $G$ on the set $G$ , and its orbits are the conjugacy classes. In particular the classes partition $G$ : distinct classes are disjoint and every element lies in one.
The stabilizer of $x$ under this action is the centralizer $C_G(x)$ , which is therefore a subgroup, and

\lvert K_x\rvert \;=\; [\,G : C_G(x)\,] .

If $G$ is finite, $\lvert K_x\rvert$ divides $\lvert G\rvert$ and $\lvert K_x\rvert\,\lvert C_G(x)\rvert = \lvert G\rvert$ . 3. $\lvert K_x\rvert = 1$ , that is $K_x = \{x\}$ , if and only if $x \in Z(G)$ . The centre is an abelian normal subgroup of $G$ , and it is the union of the one-element classes. 4. Conjugate elements have the same order, and conjugation by a fixed $g$ is an automorphism of $G$ .

Idea of the proofOriginal

A group can be made to act on itself in more than one way, and conjugation is the way that sees the group's internal structure rather than just its size. Once it is recognised as an action, everything in Group actions applies with no further work: orbits are classes, stabilizers are centralizers, and the orbit–stabilizer theorem turns the question "how big is this class?" into the question "how much of the group commutes with this element?". The elements with the largest possible centralizer, namely all of $G$ , are exactly the ones whose class is as small as possible.

ProofAdaptedAdapted from Dummit & Foote (2004), §4.3, pp. 122-123

Part 1: the axioms. For $g_1, g_2, x \in G$ ,

g_1\cdot(g_2\cdot x) = g_1(g_2xg_2^{-1})g_1^{-1} = (g_1g_2)\,x\,(g_1g_2)^{-1} = (g_1g_2)\cdot x ,

where the middle equality uses associativity and $(g_1g_2)^{-1} = g_2^{-1}g_1^{-1}$ . Also $e \cdot x = exe^{-1} = x$ . So the two axioms of a left action hold. The orbit of $x$ is $\{gxg^{-1} : g \in G\} = K_x$ by definition, and orbits partition the set acted on, by part 1 of the orbit–stabilizer theorem.

Part 2: the stabilizer. By definition the stabilizer of $x$ is

G_x = \{\, g \in G : gxg^{-1} = x \,\} = \{\, g\in G : gx = xg\,\} = C_G(x) ,

the middle step being multiplication on the right by $g$ . A stabilizer is a subgroup, so $C_G(x)$ is one, and part 2 of the orbit–stabilizer theorem gives $\lvert K_x\rvert = [G : C_G(x)]$ . When $G$ is finite, Lagrange's theorem turns this into $\lvert K_x\rvert\,\lvert C_G(x)\rvert = \lvert G\rvert$ , so $\lvert K_x\rvert$ divides $\lvert G\rvert$ .

Part 3: one-element classes. $K_x = \{x\}$ says $gxg^{-1} = x$ for every $g \in G$ , that is $gx = xg$ for every $g$ , that is $x \in Z(G)$ ; and conversely. For the rest: $e \in Z(G)$ ; if $z, w$ commute with every $g$ then so does $zw$ , since $(zw)g = z(wg) = z(gw) = (zg)w = g(zw)$ ; and $zg = gz$ gives $gz^{-1} = z^{-1}g$ on multiplying by $z^{-1}$ on both sides. So $Z(G)$ is a subgroup, abelian because its elements commute with everything and in particular with each other, and normal because $gzg^{-1} = zgg^{-1} = z \in Z(G)$ for $z \in Z(G)$ . Finally, $Z(G)$ is the union of the classes of its elements, each of which is a single point by the first sentence.

Part 4. Write $\gamma_g(x) = gxg^{-1}$ . Then $\gamma_g(x)\gamma_g(y) = gxg^{-1}gyg^{-1} = g(xy)g^{-1} = \gamma_g(xy)$ , so $\gamma_g$ is a homomorphism, and it is a bijection with inverse $\gamma_{g^{-1}}$ ; hence it is an automorphism. By induction $(gxg^{-1})^n = gx^ng^{-1}$ , because the inner factors $g^{-1}g$ cancel in pairs; so $(gxg^{-1})^n = e$ if and only if $gx^ng^{-1} = e$ , that is $x^n = e$ . The two elements therefore satisfy exactly the same power relations and have the same order. $\square$

Definition(The class equation)AdaptedAdapted from Dummit & Foote (2004), §4.3, Thm 7, p. 124

Take $G$ finite. Its classes of size one are the central elements, by part 3; write $K_{g_1}, \dots, K_{g_r}$ for the remaining classes, picking one $g_i$ out of each. Adding the sizes of all the classes then gives the class equation

\lvert G\rvert \;=\; \lvert Z(G)\rvert \;+\; \sum_{i=1}^{r} \bigl[\,G : C_G(g_i)\,\bigr] ,

in which each index appearing in the sum exceeds $1$ and divides $\lvert G\rvert$ .

Idea of the proofOriginal

Add up the sizes of the classes. The classes of size one are precisely the central elements, and together they contribute $\lvert Z(G)\rvert$ ; each remaining class contributes its size, which part 2 of the previous statement writes as an index. That is the whole argument, and its force comes from the last sentence: the right-hand side is a sum of divisors of $\lvert G\rvert$ , each bigger than $1$ , which is a strong arithmetic constraint on how a finite group can be built.

ProofAdaptedAdapted from Dummit & Foote (2004), §4.3, Thm 7, p. 124

By part 1 of the previous statement the classes partition $G$ , so $\lvert G\rvert$ is the sum of the sizes of all the distinct classes.

Split that sum in two. By part 3, a class has one element exactly when that element is central, so the one-element classes are $\{z\}$ for $z \in Z(G)$ and there are $\lvert Z(G)\rvert$ of them, contributing $\lvert Z(G)\rvert$ in total. Every other class has at least two elements and so is disjoint from the centre; let $K_{g_1}, \dots, K_{g_r}$ be these, with the $g_i$ chosen one from each.

By part 2, $\lvert K_{g_i}\rvert = [G : C_G(g_i)]$ . Hence

\lvert G\rvert = \sum_{z \in Z(G)} 1 \;+\; \sum_{i=1}^{r}\lvert K_{g_i}\rvert = \lvert Z(G)\rvert + \sum_{i=1}^{r}\bigl[G : C_G(g_i)\bigr] .

Each index is a divisor of $\lvert G\rvert$ by Lagrange's theorem, and it exceeds $1$ because $g_i \notin Z(G)$ forces $C_G(g_i) \neq G$ . $\square$

Definition(Prime-power order forces a non-trivial centre)AdaptedAdapted from Dummit & Foote (2004), §4.3, Thm 8, p. 125

Suppose $\lvert P\rvert = p^{a}$ , with $p$ prime and $a \geq 1$ . Then $Z(P)$ contains something besides the identity, so $\lvert Z(P)\rvert \geq p$ .

Idea of the proofOriginal

Read the class equation modulo $p$ . Every non-central index divides $p^{a}$ and exceeds $1$ , so it is a positive power of $p$ ; the order $\lvert P\rvert$ is a positive power of $p$ as well. That leaves $\lvert Z(P)\rvert$ as the only term in the equation not yet known to be divisible by $p$ — and a sum in which all but one term is divisible by $p$ can equal a multiple of $p$ only if the remaining term is too. Since the centre is never empty, being divisible by $p$ forces it to have at least $p$ elements.

ProofAdaptedAdapted from Dummit & Foote (2004), §4.3, Thm 8, p. 125

Apply the class equation to $P$ :

p^{a} = \lvert Z(P)\rvert + \sum_{i=1}^{r}\bigl[P : C_P(g_i)\bigr] .

For each $i$ the index $[P:C_P(g_i)]$ divides $p^a$ and is greater than $1$ , so it is $p^{b_i}$ with $b_i \geq 1$ and is divisible by $p$ . The left-hand side is divisible by $p$ because $a \geq 1$ . Subtracting, $p$ divides $\lvert Z(P)\rvert$ . Since $\lvert Z(P)\rvert \geq 1$ (the identity is central), this forces $\lvert Z(P)\rvert \geq p > 1$ . $\square$

Remark(Where the hypotheses are used)Original

Finiteness. Parts 1, 3 and 4 of "Classes and centralizers", and the identity $\lvert K_x\rvert = [G:C_G(x)]$ , hold in any group. Finiteness enters only where orders are multiplied or summed: in the divisibility statement, and throughout the class equation, whose left-hand side must be a number and whose right-hand side must be a finite sum. In an infinite group the classes still partition $G$ , but there may be infinitely many of them and they may be infinite; the general linear group $\mathrm{GL}_2(\mathbb{C})$ , for example, has a two-parameter family of classes of diagonalizable matrices, one for each unordered pair $\{\lambda_1, \lambda_2\}$ of non-zero eigenvalues.

$a \geq 1$ in the prime-power corollary. With $a = 0$ the group is trivial and its centre is trivial too, so the conclusion fails; the proof uses $a \geq 1$ exactly at the point where $p$ is said to divide $\lvert P\rvert$ . The hypothesis that $\lvert P\rvert$ is a prime power is equally essential: $S_3$ has order $6$ and class equation $6 = 1 + 2 + 3$ , with trivial centre. There no single prime divides all the non-central indices, and the argument has nothing to work with.

Why the centre must be separated out. One might try to write the class equation as a sum over all classes of $[G:C_G(g_i)]$ with no special term. That is true but useless: the central classes contribute $1$ each, and the information in the equation — that the non-central terms are proper divisors of $\lvert G\rvert$ greater than $1$ — is only visible once they are collected.

Normal subgroups are unions of classes. If $N \trianglelefteq G$ and $x \in N$ then $gxg^{-1} \in gNg^{-1} = N$ for every $g$ , so $K_x \subseteq N$ . This is the most common way the class equation is used: the order of a normal subgroup must be a sum of class sizes, one of which is the class of the identity. In the worked example below, the class sizes $1, 2, 2, 5$ allow only $1, 1+2+2 = 5$ and $1+2+2+5 = 10$ as such sums that also divide $10$ , which exhibits $\langle r\rangle$ as the only non-trivial proper normal subgroup.

Conjugacy is not equality of order. Conjugate elements have the same order (part 4), but not conversely: in the example below, $r$ and $r^2$ both have order $5$ and are not conjugate.

Method(Finding the conjugacy classes of a finite group)Original

Start with the identity. $K_e = \{e\}$ always, since $geg^{-1} = e$ .
Find the centre by checking which elements commute with a generating set; each contributes a class of its own, by part 3.
Pick an element $x$ not yet placed. Compute $gxg^{-1}$ as $g$ runs over a generating set of $G$ , then over products of those, until no new elements appear. The set obtained is $K_x$ , because it is closed under conjugation by the generators and hence by all of $G$ .
Check the size. $\lvert K_x\rvert$ must divide $\lvert G\rvert$ , by part 2. If it does not, an element has been missed.
Identify the centralizer as a cross-check: $\lvert C_G(x)\rvert = \lvert G\rvert / \lvert K_x\rvert$ , and $\langle x\rangle \subseteq C_G(x)$ always, so the order of $x$ must divide $\lvert C_G(x)\rvert$ .
Repeat from step 3 until every element is placed, then verify the class equation: the sizes must add to $\lvert G\rvert$ .

Example(The symmetries of a regular pentagon)Original

Let $G = D_5$ be the symmetry group of a regular pentagon: the rotations through multiples of $2\pi/5$ and the five reflections in the axes through a vertex and the midpoint of the opposite side. Writing $r$ for the rotation through $2\pi/5$ and $s$ for one reflection,

G = \{\, e, r, r^2, r^3, r^4,\ s, rs, r^2s, r^3s, r^4s \,\}, \qquad r^5 = s^2 = e, \qquad s r s^{-1} = r^{-1} ,

so $\lvert G\rvert = 10$ . Everything below follows from the single relation $srs^{-1} = r^{-1}$ , equivalently $sr^{k} = r^{-k}s$ .

Step 1: the identity. $K_e = \{e\}$ , of size $1$ .

Step 2: conjugating a rotation. Conjugating $r^{m}$ by a rotation changes nothing, since powers of $r$ commute: $r^{k}r^{m}r^{-k} = r^{m}$ . Conjugating by a reflection $r^{k}s$ , and using $(r^ks)^{-1} = s^{-1}r^{-k} = sr^{-k}$ together with $sr^{m} = r^{-m}s$ ,

(r^{k}s)\,r^{m}\,(r^{k}s)^{-1} = r^{k}s\,r^{m}\,s\,r^{-k} = r^{k}\,(r^{-m}s)\,s\,r^{-k} = r^{k}\,r^{-m}\,r^{-k} = r^{-m} ,

using $s^2 = e$ at the third equality and the commutativity of the powers of $r$ at the fourth. So the class of $r^{m}$ is $\{r^{m}, r^{-m}\}$ :

K_{r} = \{r, r^{4}\}, \qquad K_{r^{2}} = \{r^{2}, r^{3}\} ,

each of size $2$ . Geometrically, a rotation and its inverse are conjugate because a reflection reverses the sense of rotation.

Step 3: conjugating a reflection. First by rotations, using $sr^{-k} = r^{k}s$ :

r^{k}\,s\,r^{-k} = r^{k}\,r^{k}s = r^{2k}s .

As $k$ runs over $0,1,2,3,4$ , the exponent $2k$ runs over $0,2,4,1,3$ modulo $5$ — all residues, because $2$ is invertible modulo the prime $5$ (indeed $2\cdot 3 = 6 \equiv 1$ ). So the five reflections $s, rs, r^2s, r^3s, r^4s$ are already all conjugate to $s$ , and

K_{s} = \{\, s,\ rs,\ r^2s,\ r^3s,\ r^4s \,\} ,

of size $5$ . Conjugating by reflections produces nothing new, since $(r^{k}s)\,s\,(r^{k}s)^{-1} = (r^{k}s)\,s\,(r^{k}s) = r^{k}\,(ss)\,r^{k}s = r^{2k}s$ , the same list.

Step 4: the counts. The four classes have sizes $1, 2, 2, 5$ , and each divides $\lvert G\rvert = 10$ , as part 2 requires. They account for $1+2+2+5 = 10$ elements, so no element has been missed and these are all the classes.

Step 5: centralizers and the centre. By $\lvert C_G(x)\rvert = \lvert G\rvert/\lvert K_x\rvert$ ,

\lvert C_G(r)\rvert = \frac{10}{2} = 5, \qquad \lvert C_G(s)\rvert = \frac{10}{5} = 2 .

These are confirmed directly: $C_G(r) = \langle r\rangle$ , the five rotations, and $C_G(s) = \{e, s\}$ . Only the identity has a class of size $1$ , so by part 3

Z(D_5) = \{e\} .

Step 6: the class equation. With $Z(G) = \{e\}$ and the three non-central classes,

10 = \underbrace{1}_{\lvert Z(G)\rvert} + \underbrace{2}_{[G:C_G(r)]} + \underbrace{2}_{[G:C_G(r^2)]} + \underbrace{5}_{[G:C_G(s)]} ,

and indeed $1 + 2 + 2 + 5 = 10$ . Each non-central summand is a divisor of $10$ larger than $1$ , as the theorem promises. The count of classes, four, is the number that will reappear as the number of inequivalent irreducible representations of $D_5$ (Orthogonality relations and characters).

ApplicationOriginal

Character tables are indexed by classes. The trace of a matrix is unchanged by a similarity transformation, so the character $\chi(g) = \mathrm{tr}\,D(g)$ of a representation satisfies $\chi(hgh^{-1}) = \chi(g)$ : characters are class functions. Every column of a character table therefore stands for a whole class, not a single element, and the table is square because a finite group has exactly as many irreducible representations, counted up to equivalence, as it has conjugacy classes. Counting and sizing the classes, as in the example above, is the first step in building such a table; see Orthogonality relations and characters and Character tables.

Conjugate symmetry operations are physically equivalent. In a molecular point group, two operations are conjugate when the group itself contains an operation carrying the geometric element of the first (an axis, a plane) onto that of the second. A square-planar $\mathrm{ML}_4$ molecule has point group $D_{4h}$ , of order $16$ , and its four in-plane two-fold axes fall into two classes of two: the two axes along the M–L bonds form the class written $2C_2'$ , and the two through the midpoints of the edges of the square form the class $2C_2''$ . A rotation by $\pi/4$ would carry one kind onto the other, but no such operation lies in $D_{4h}$ , so the two classes are not interchangeable and the spectroscopic labels $C_2'$ and $C_2''$ record exactly this distinction. The class sizes are consistent with part 2: $2$ divides $16$ , whereas a class of three could not occur here at all, since $3 \nmid 16$ . Point groups and crystal symmetry develops the classification.

Rotations through the same angle are conjugate. In $\mathrm{SO}(3)$ , if $R$ carries the unit vector $\hat n$ to $\hat n'$ then $R\,R_{\hat n}(\theta)\,R^{-1} = R_{\hat n'}(\theta)$ : the conjugate of a rotation is the rotation through the same angle about the rotated axis, as (Hassani (2013), Box 23.2.20, p. 711) records. The classes of $\mathrm{SO}(3)$ are therefore labelled by the angle alone, which is why the character of an angular-momentum representation is a function of $\theta$ only, and why one may compute it in the convenient frame in which the axis is $\hat z$ (The rotation group and SU(2), Rotation matrices of angular momentum).

Conjugacy in the groups the handbook uses elsewhere. In $\mathrm{GL}_n(\mathbb{C})$ conjugation $A \mapsto PAP^{-1}$ is change of basis (Linear maps and matrices), so the conjugacy classes are the similarity classes of matrices and the Jordan normal form is precisely a list of class representatives (Jordan normal form); part 4 above is the familiar fact that similar matrices share their invariants. In the symmetric group, (Hassani (2013), Thm 23.4.12, p. 719) and (Dummit & Foote (2004), Prop. 11, p. 126) show that two permutations are conjugate exactly when they have the same cycle type, so the classes of $S_n$ are labelled by the partitions of $n$ (The symmetric group). This is the combinatorial engine behind the representation theory of $S_n$ used in the quantum mechanics of identical particles.

Definition

The symmetric group

Adapted

Add to PDF

Defines the group of permutations of n symbols, establishes the disjoint-cycle decomposition and its uniqueness, and constructs the sign homomorphism whose kernel is the alternating group of index two.

Prerequisites: Groups and subgroups, Cosets and Lagrange's theorem, Homomorphisms and quotient groups

Definition(Permutations, cycles and cycle type)AdaptedAdapted from Dummit & Foote (2004), §1.3, pp. 29-31 and §3.5, p. 107; Hassani (2013), §23.4, pp. 715-717; Riley, Hobson & Bence (2006), §28.4, pp. 1056-1057

Let $\Omega$ be a non-empty set. The set $S_\Omega$ of all bijections $\Omega \to \Omega$ is a group under composition: composition of bijections is a bijection and is associative, the identity map is a neutral element, and the inverse function is an inverse. It is the symmetric group on $\Omega$ . For $\Omega = \{1, 2, \dots, n\}$ we write $S_n$ and call its elements permutations of degree $n$ ; its order is

\lvert S_n\rvert = n! ,

since a bijection may send $1$ to any of $n$ values, then $2$ to any of the $n-1$ remaining values, and so on.

Notation and composition order. A permutation is displayed either in two rows, with $\sigma(i)$ under $i$ , or in one row as the list $\sigma(1)\,\sigma(2)\cdots\sigma(n)$ . Products are compositions of functions, so $\sigma\tau$ means "first $\tau$ , then $\sigma$ ": $(\sigma\tau)(i) = \sigma(\tau(i))$ , and a product is read from right to left.

Cycles. For distinct $a_1, \dots, a_m \in \{1,\dots,n\}$ , the cycle $(a_1\,a_2\,\cdots\,a_m)$ is the permutation sending $a_1 \mapsto a_2 \mapsto \cdots \mapsto a_m \mapsto a_1$ and fixing everything else; $m$ is its length, and it is called an $m$ -cycle. Two cycles are disjoint if no symbol occurs in both. A transposition is a $2$ -cycle. By convention $1$ -cycles are omitted from a written product, so a symbol not appearing is understood to be fixed; the same expression therefore denotes a permutation of $S_n$ for every $n$ large enough to contain its symbols.

Cycle type. If $\sigma$ is a product of disjoint cycles of lengths $n_1, n_2, \dots, n_r$ , counting the $1$ -cycles of its fixed points, then $n_1 + \cdots + n_r = n$ and the multiset $\{n_1, \dots, n_r\}$ is the cycle type of $\sigma$ . A partition of $n$ is a way of writing $n$ as a sum of positive integers without regard to order, so a cycle type is a partition of $n$ . We list cycle types in non-decreasing order, as (Dummit & Foote (2004), §4.3, p. 126) does; (Hassani (2013), §23.4, p. 720) writes partitions in non-increasing order instead. The two record the same data.

Definition(Disjoint cycle decomposition)AdaptedAdapted from Dummit & Foote (2004), §1.3, pp. 29-31; Hassani (2013), Prop. 23.4.3, p. 717; Riley, Hobson & Bence (2006), §28.4, p. 1058

Let $\sigma \in S_n$ .

$\sigma$ is a product of pairwise disjoint cycles, and this product is unique up to the order in which the cycles are written and the symbol at which each cycle is started, provided $1$ -cycles are included.
Disjoint cycles commute.
If the cycles of $\sigma$ have lengths $n_1, \dots, n_r$ , then the order of $\sigma$ in $S_n$ is $\mathrm{lcm}(n_1, \dots, n_r)$ .

Idea of the proofOriginal

The cyclic group $\langle \sigma\rangle$ acts on $\{1, \dots, n\}$ , and the cycles of $\sigma$ are nothing but the orbits of that action, each traversed in the order $a, \sigma(a), \sigma^2(a), \dots$ . Existence and uniqueness of the decomposition are therefore not a separate fact: they are the statement that orbits partition a set, which is part 1 of the orbit–stabilizer theorem. Disjoint cycles commute because they alter disjoint sets of symbols, and the order of $\sigma$ is then determined cycle by cycle.

ProofOriginal

Part 1: existence. Let the cyclic subgroup $\langle\sigma\rangle$ act on $A = \{1,\dots,n\}$ by $\sigma^{k}\cdot a = \sigma^{k}(a)$ ; this is an action because $\sigma^{j}(\sigma^{k}(a)) = \sigma^{j+k}(a)$ and $\sigma^0 = \mathrm{id}$ . By Group actions the orbits partition $A$ . Fix an orbit and a point $a$ in it. The powers $a, \sigma(a), \sigma^2(a), \dots$ cannot all be distinct, $A$ being finite, so there are $0 \leq i < j$ with $\sigma^{i}(a) = \sigma^{j}(a)$ ; applying the bijection $\sigma^{-i}$ gives $\sigma^{j-i}(a) = a$ with $j - i \geq 1$ . Let $m$ be the least positive integer with $\sigma^{m}(a) = a$ . Then $a, \sigma(a), \dots, \sigma^{m-1}(a)$ are distinct — an equality $\sigma^{p}(a) = \sigma^{q}(a)$ with $0 \le p < q \le m-1$ would give $\sigma^{q-p}(a) = a$ with $0 < q-p < m$ , contradicting minimality — and they are the whole orbit, because any $\sigma^{k}(a)$ equals $\sigma^{k \bmod m}(a)$ by division with remainder. On this orbit $\sigma$ acts exactly as the cycle $(a\ \sigma(a)\ \cdots\ \sigma^{m-1}(a))$ . Doing this for every orbit produces pairwise disjoint cycles — disjoint because distinct orbits are disjoint — whose product agrees with $\sigma$ at every symbol, since every symbol lies in exactly one orbit.

Part 1: uniqueness. Suppose $\sigma$ is written as a product of pairwise disjoint cycles, $1$ -cycles included. Let $a$ be a symbol and let $(a_1\,\cdots\,a_m)$ be the cycle containing it, say $a = a_1$ after a cyclic rotation of the way it is written. The other cycles do not contain any $a_i$ , so they fix each of them, and the product therefore sends $a_i \mapsto a_{i+1}$ for $i<m$ and $a_m \mapsto a_1$ . Hence $a_{i+1} = \sigma^{i}(a)$ for every $i$ , and $m$ is the least positive integer with $\sigma^{m}(a) = a$ . Both the set of symbols of the cycle and their cyclic order are thus determined by $\sigma$ and $a$ alone; the only freedom is which of its symbols is written first, and in what order the cycles are listed.

Part 2. Let $\gamma$ and $\delta$ be disjoint cycles and let $a$ be any symbol. If $a$ occurs in $\gamma$ , then so does $\gamma(a)$ , so $\delta$ fixes both and $\gamma\delta(a) = \gamma(a) = \delta\gamma(a)$ . The case $a$ in $\delta$ is the same with the roles exchanged, and if $a$ occurs in neither then both sides fix it. So $\gamma\delta = \delta\gamma$ .

Part 3. Write $\sigma = \gamma_1\cdots\gamma_r$ with the $\gamma_t$ disjoint of lengths $n_t$ . Because they commute, $\sigma^{k} = \gamma_1^{k}\cdots\gamma_r^{k}$ , and the factors still move disjoint sets of symbols, so $\sigma^{k} = \mathrm{id}$ if and only if $\gamma_t^{k} = \mathrm{id}$ for every $t$ . A single $m$ -cycle $\gamma$ satisfies $\gamma^{k} = \mathrm{id}$ exactly when $m \mid k$ , by the minimality established in part 1. So $\sigma^k = \mathrm{id}$ if and only if every $n_t$ divides $k$ , and the least such positive $k$ is $\mathrm{lcm}(n_1, \dots, n_r)$ . $\square$

Definition(Transpositions, the sign, and the alternating group)AdaptedAdapted from Dummit & Foote (2004), §3.5, pp. 107-110, Props 23, 24 and 25; Hassani (2013), Props 23.4.8 and 23.4.9, Box 23.4.11, pp. 718-719

Let $n \geq 2$ .

Every $m$ -cycle factors into $m-1$ transpositions:

(a_1\,a_2\,\cdots\,a_m) = (a_1\,a_m)(a_1\,a_{m-1})\cdots(a_1\,a_3)(a_1\,a_2) .

Consequently every element of $S_n$ is a product of transpositions, so the transpositions generate $S_n$ . (The identity is the empty product.) 2. There is a homomorphism $\varepsilon \colon S_n \to \{+1, -1\}$ , the sign, with $\varepsilon(\tau) = -1$ for every transposition $\tau$ . It satisfies $\varepsilon(\sigma) = (-1)^{k}$ whenever $\sigma$ is a product of $k$ transpositions; in particular the parity of $k$ depends only on $\sigma$ and not on the factorisation chosen. A permutation is called even if $\varepsilon(\sigma) = +1$ and odd if $\varepsilon(\sigma) = -1$ . 3. If $\sigma$ has $c(\sigma)$ cycles in its disjoint decomposition, $1$ -cycles included, then

\varepsilon(\sigma) = (-1)^{\,n - c(\sigma)} .

Equivalently, $\sigma$ is odd precisely when the number of even-length cycles in its decomposition is odd. 4. $\varepsilon$ is surjective, and the alternating group $A_n = \ker\varepsilon$ , the set of even permutations, is a normal subgroup of $S_n$ with

\lvert A_n\rvert = \tfrac{1}{2}\,n! , \qquad [\,S_n : A_n\,] = 2 .

Idea of the proofOriginal

Part 1 is a computation: peeling off one symbol at a time with transpositions through a fixed base point rebuilds the cycle. The delicate point is part 2, since the same permutation factors into transpositions in infinitely many ways; what is needed is a quantity attached to $\sigma$ itself that changes sign under every transposition. The Vandermonde polynomial $\Delta = \prod_{i<j}(x_i - x_j)$ supplies one: permuting its variables can only permute the factors and flip some of their signs, so it returns $\pm\Delta$ , and that sign is multiplicative. Part 3 then follows by counting how many transpositions each cycle costs, and part 4 from the first isomorphism theorem.

ProofAdaptedAdapted from Dummit & Foote (2004), §3.5, pp. 107-110; Hassani (2013), Prop. 23.4.8, p. 718

Part 1. Apply the right-hand side to $a_1$ , remembering that products act from the right. The rightmost factor $(a_1\,a_2)$ sends $a_1 \mapsto a_2$ , and no later factor contains $a_2$ , so the product sends $a_1 \mapsto a_2$ . For $2 \leq i \leq m-1$ , the factors to the right of $(a_1\,a_{i})$ fix $a_i$ ; then $(a_1\,a_i)$ sends $a_i \mapsto a_1$ , and the next factor $(a_1\,a_{i+1})$ sends $a_1 \mapsto a_{i+1}$ , which the remaining factors fix. So $a_i \mapsto a_{i+1}$ . Finally $a_m$ is fixed by every factor except the leftmost, $(a_1\,a_m)$ , which sends it to $a_1$ . Any symbol outside $\{a_1,\dots,a_m\}$ is fixed by all factors. The right-hand side therefore agrees with the cycle everywhere, and it has $m-1$ factors. Since every permutation is a product of disjoint cycles, factoring each cycle this way writes it as a product of transpositions.

Part 2: constructing $\varepsilon$ . Work in the polynomial ring $\mathbb{Z}[x_1, \dots, x_n]$ and set

\Delta = \prod_{1 \le i < j \le n} (x_i - x_j) ,

a non-zero polynomial. Let $S_n$ act on polynomials by permuting the indices of the variables, $(\sigma \cdot f)(x_1, \dots, x_n) = f(x_{\sigma(1)}, \dots, x_{\sigma(n)})$ ; this is an action because the indices compose correctly. Now

\sigma\cdot\Delta = \prod_{i<j}\bigl(x_{\sigma(i)} - x_{\sigma(j)}\bigr) .

As $\{i,j\}$ runs over all unordered pairs, so does $\{\sigma(i), \sigma(j)\}$ , because $\sigma$ is a bijection; so the factors of $\sigma\cdot\Delta$ are those of $\Delta$ up to sign, each occurring once. A factor is reversed exactly when $i<j$ but $\sigma(i) > \sigma(j)$ — an inversion of $\sigma$ . Writing $\mathrm{inv}(\sigma)$ for the number of inversions,

\sigma \cdot \Delta = (-1)^{\mathrm{inv}(\sigma)}\,\Delta .

Define $\varepsilon(\sigma)$ to be this sign, so $\sigma\cdot\Delta = \varepsilon(\sigma)\Delta$ and $\varepsilon(\sigma) = (-1)^{\mathrm{inv}(\sigma)}$ .

Part 2: $\varepsilon$ is a homomorphism. Since $f \mapsto \sigma\cdot f$ is an action and multiplication by a constant commutes with it,

\varepsilon(\sigma\tau)\,\Delta = (\sigma\tau)\cdot\Delta = \sigma\cdot(\tau\cdot\Delta) = \sigma\cdot\bigl(\varepsilon(\tau)\Delta\bigr) = \varepsilon(\tau)\,\bigl(\sigma\cdot\Delta\bigr) = \varepsilon(\tau)\varepsilon(\sigma)\,\Delta .

$\Delta \neq 0$ and $\mathbb{Z}[x_1,\dots,x_n]$ has no zero divisors, so $\varepsilon(\sigma\tau) = \varepsilon(\sigma)\varepsilon(\tau)$ .

Part 2: transpositions are odd. First take $\tau = (1\,2)$ . It reverses the factor $x_1 - x_2$ ; a factor $x_1 - x_j$ with $j \geq 3$ becomes $x_2 - x_j$ and a factor $x_2 - x_j$ becomes $x_1 - x_j$ , so these are exchanged in pairs with no sign change; and factors with neither index are untouched. Hence exactly one factor is reversed, $\mathrm{inv}((1\,2)) = 1$ and $\varepsilon((1\,2)) = -1$ . For a general transposition $(i\,j)$ choose $\lambda \in S_n$ with $\lambda(1) = i$ and $\lambda(2) = j$ . Then $\lambda(1\,2)\lambda^{-1} = (i\,j)$ , since the left-hand side sends $i \mapsto 1 \mapsto 2 \mapsto j$ , sends $j \mapsto i$ in the same way, and fixes everything else. Because $\varepsilon$ is a homomorphism into an abelian group,

\varepsilon\bigl((i\,j)\bigr) = \varepsilon(\lambda)\,\varepsilon\bigl((1\,2)\bigr)\,\varepsilon(\lambda)^{-1} = \varepsilon\bigl((1\,2)\bigr) = -1 .

If now $\sigma = \tau_1\cdots\tau_k$ with each $\tau_t$ a transposition, multiplicativity gives $\varepsilon(\sigma) = (-1)^{k}$ . The left-hand side does not refer to the factorisation, so the parity of $k$ is an invariant of $\sigma$ .

Part 3. Let $\sigma$ have disjoint cycles of lengths $n_1, \dots, n_c$ with $c = c(\sigma)$ and $\sum_t n_t = n$ ( $1$ -cycles included). By part 1 the $t$ -th cycle is a product of $n_t - 1$ transpositions, so $\sigma$ is a product of $\sum_t (n_t - 1) = n - c$ of them, and part 2 gives $\varepsilon(\sigma) = (-1)^{n-c}$ . For the restatement: a cycle of length $n_t$ contributes the factor $(-1)^{n_t-1}$ , which is $-1$ exactly when $n_t$ is even, so $\varepsilon(\sigma) = -1$ exactly when an odd number of the cycles have even length. (The $1$ -cycles contribute $(-1)^0 = 1$ and may be ignored in this count.)

Part 4. Since $n \geq 2$ the transposition $(1\,2)$ exists and has sign $-1$ , while $\varepsilon(\mathrm{id}) = +1$ ; so $\varepsilon$ is onto $\{\pm 1\}$ . A kernel is a normal subgroup, so $A_n = \ker\varepsilon \trianglelefteq S_n$ , and the first isomorphism theorem (Homomorphisms and quotient groups) gives $S_n/A_n \cong \{\pm 1\}$ , a group of order $2$ . Hence $[S_n : A_n] = 2$ and, by Lagrange's theorem, $\lvert A_n\rvert = \lvert S_n\rvert/2 = n!/2$ . $\square$

Remark(Where the hypotheses are used)Original

$n \geq 2$ is needed for part 4 only. $S_1$ is the trivial group, it contains no transposition, $\varepsilon$ is not surjective, and $A_1 = S_1$ has index $1$ , not $2$ . Parts 1 to 3 are vacuous or trivially true there. Note also that the identity is the empty product of transpositions and is even, consistently with $c(\mathrm{id}) = n$ in part 3.

Finiteness of $\Omega$ is used in the cycle decomposition, not in the group axioms. $S_\Omega$ is a group for any $\Omega$ , but the argument in part 1 of the decomposition theorem needs $\{1,\dots,n\}$ finite twice: to force a repetition among $a, \sigma(a), \sigma^2(a), \dots$ , and to make the product of the cycles a finite product. A bijection of an infinite set need not decompose into cycles at all — translation $k \mapsto k+1$ on $\mathbb{Z}$ has a single infinite orbit and no finite cycle — and it has no sign.

$\Delta \neq 0$ and the absence of zero divisors are what let us cancel $\Delta$ and conclude multiplicativity. Working with distinct indeterminates is essential: substituting numbers for the $x_i$ could make $\Delta$ vanish and destroy the argument.

Composition order. We compose right to left, as (Dummit & Foote (2004), §1.3, p. 31) and (Hassani (2013), §23.4, p. 715) do. Many physics texts compose left to right; the two conventions give anti-isomorphic products, so a formula such as $\tau\sigma\tau^{-1}$ must be read with the convention of its source. The sign is unaffected, being a homomorphism to an abelian group.

A second convention clash: what a cycle permutes. We follow Dummit and Foote and Hassani in letting $\sigma$ act on symbols, so $(1\,2\,5\,4)$ means $1\mapsto 2 \mapsto 5\mapsto 4 \mapsto 1$ . (Riley, Hobson & Bence (2006), §28.4, p. 1057) instead lets the entries record positions, so that their $(1\,2\,5\,4)$ means the object in position 2 moves to position 1, the object in position 5 to position 2, and so on. The resulting permutation is the inverse of ours. Cycle lengths, cycle type, order and sign are the same under both readings, so the results above are unaffected, but the explicit image of a given symbol is not.

Parity is not the parity of the order. $(1\,2)$ and $(1\,2)(3\,4)$ both have order $2$ , yet the first is odd and the second even. Part 3 counts cycles of even length, not the order of the element.

Note(Conjugacy classes of

S_n

)AdaptedAdapted from Dummit & Foote (2004), §4.3, Props 10 and 11, pp. 125-126; Hassani (2013), Thm 23.4.12, p. 719

Conjugation relabels cycles: if $\sigma$ has a cycle $(a_1\,\cdots\,a_m)$ then $\tau\sigma\tau^{-1}$ has the cycle $(\tau(a_1)\,\cdots\,\tau(a_m))$ , because $\sigma(a) = b$ gives $\tau\sigma\tau^{-1}(\tau(a)) = \tau(b)$ . Hence conjugate permutations have the same cycle type, and conversely any two permutations of the same cycle type are conjugate — align their decompositions and let $\tau$ be the map taking each symbol to the one in the corresponding position. So the conjugacy classes of $S_n$ are exactly the cycle types, and their number is the number of partitions of $n$ . The sign is constant on each class, as it must be, since $\varepsilon$ is a homomorphism into an abelian group and part 3 depends only on the cycle lengths.

Method(Working with a permutation)Original

Given $\sigma \in S_n$ in two-row or one-line form:

Decompose into cycles. Start at the smallest symbol not yet used, say $a$ ; write $a, \sigma(a), \sigma^2(a), \dots$ until $a$ reappears, and close the bracket. Repeat with the smallest unused symbol until all $n$ symbols are used. Keep a note of the $1$ -cycles even if they are not written.
Read off the cycle type, the list of lengths including the $1$ -cycles. It must sum to $n$ ; this is the check that nothing has been dropped.
Order: take the lowest common multiple of the cycle lengths.
Sign: count the cycles, $1$ -cycles included, as $c$ ; then $\varepsilon(\sigma) = (-1)^{n-c}$ . Equivalently, count the cycles of even length: $\sigma$ is odd when that count is odd.
Factor into transpositions when needed, with $(a_1\,\cdots\,a_m) = (a_1\,a_m)\cdots(a_1\,a_2)$ cycle by cycle. The total number of factors is $n - c$ , which re-checks the sign.
Inverse: reverse the symbols inside each cycle.
Size of the conjugacy class: for a cycle type with $\nu_k$ cycles of length $k$ ,

\lvert K_\sigma\rvert = \frac{n!}{\prod_{k\ge 1} k^{\nu_k}\,\nu_k!} , \qquad \lvert C_{S_n}(\sigma)\rvert = \prod_{k\ge 1} k^{\nu_k}\,\nu_k! ,

the denominator counting the cyclic rotations within each cycle and the permutations of equal-length cycles among themselves.

Example(A permutation of nine symbols)Original

Let $\sigma \in S_9$ be given by

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 9 & 7 & 2 & 1 & 3 & 6 & 4 & 8 \end{pmatrix} .

Step 1: cycles. Start at $1$ : $1 \mapsto 5 \mapsto 1$ , giving $(1\,5)$ . The smallest unused symbol is $2$ : $2 \mapsto 9 \mapsto 8 \mapsto 4 \mapsto 2$ , giving $(2\,9\,8\,4)$ . Next is $3$ : $3 \mapsto 7 \mapsto 6 \mapsto 3$ , giving $(3\,7\,6)$ . All nine symbols are now used, so

\sigma = (1\,5)(2\,9\,8\,4)(3\,7\,6) .

Check: the lengths are $2 + 4 + 3 = 9 = n$ , and there are no fixed points.

Step 2: cycle type and number of cycles. The cycle type is $2,3,4$ , a partition of $9$ , and $c(\sigma) = 3$ .

Step 3: order. $\mathrm{lcm}(2,3,4) = 12$ , so $\sigma$ has order $12$ . (Direct check: $\sigma^{12}$ acts as the identity on each cycle because $2 \mid 12$ , $4\mid 12$ and $3\mid 12$ ; and no proper divisor of $12$ is a multiple of both $3$ and $4$ .)

Step 4: sign, three ways.

From part 3: $\varepsilon(\sigma) = (-1)^{\,9-3} = (-1)^{6} = +1$ .
By counting even-length cycles: the $2$ -cycle and the $4$ -cycle are the even ones, two of them, an even number; so $\sigma$ is even.
From the inversions of the one-line form $5\,9\,7\,2\,1\,3\,6\,4\,8$ : the pairs $i<j$ with $\sigma(i) > \sigma(j)$ number $4+7+5+1+0+0+1+0 = 18$ (counting, for each position in turn, the smaller entries to its right), and $(-1)^{18} = +1$ .

All three agree: $\sigma$ is even, $\varepsilon(\sigma) = +1$ , so $\sigma \in A_9$ .

Step 5: as a product of transpositions.

(1\,5) , \qquad (2\,9\,8\,4) = (2\,4)(2\,8)(2\,9), \qquad (3\,7\,6) = (3\,6)(3\,7) ,

\sigma = (1\,5)(2\,4)(2\,8)(2\,9)(3\,6)(3\,7) ,

a product of $6$ transpositions — and $6 = n - c = 9 - 3$ , as step 4 of the method predicts, with $6$ even, confirming once more that $\sigma$ is even.

Step 6: the inverse. Reversing each cycle, $\sigma^{-1} = (5\,1)(4\,8\,9\,2)(6\,7\,3)$ , that is $\sigma^{-1} = (1\,5)(2\,4\,8\,9)(3\,6\,7)$ after rotating each bracket to start at its smallest symbol. Spot check: $\sigma(2) = 9$ and $\sigma^{-1}(9) = 2$ .

Step 7: the conjugacy class. The cycle type $2,3,4$ has $\nu_2 = \nu_3 = \nu_4 = 1$ and no repetitions, so

\lvert C_{S_9}(\sigma)\rvert = 2^1 1! \cdot 3^1 1!\cdot 4^1 1! = 24 , \qquad \lvert K_\sigma\rvert = \frac{9!}{24} = \frac{362\,880}{24} = 15\,120 .

There are therefore exactly $15\,120$ permutations of nine symbols with one $2$ -cycle, one $3$ -cycle and one $4$ -cycle, and $15\,120$ divides $9! = 362\,880$ with quotient $24$ , as the orbit–stabilizer theorem requires. All $15\,120$ of them are even, since the sign depends only on the cycle type.

ApplicationOriginal

Identical particles and the sign. The state of $n$ indistinguishable particles must be unchanged in physical content when the particle labels are permuted, so $S_n$ acts on the $n$ -particle state space. (Arfken, Weber & Harris (2013), §17.6, Eqs (17.23)-(17.24), pp. 840-841) records the two one-dimensional possibilities that nature uses: a boson wavefunction satisfies $P\Psi_B = \Psi_B$ for every permutation $P$ , and a fermion wavefunction satisfies $P\Psi_F = \varepsilon(P)\,\Psi_F$ , with exactly the sign constructed above. The factor $\varepsilon(P)$ is the $n$ -index Levi-Civita symbol. Everything that follows from antisymmetry follows from the single fact that $\varepsilon$ is a homomorphism taking the value $-1$ on transpositions: exchanging two fermions reverses the sign, so two fermions in the same one-particle state give $\Psi_F = -\Psi_F = 0$ , which is the Pauli exclusion principle.

The Slater determinant and the determinant itself. The antisymmetric state built from $n$ one-particle orbitals $\phi_1, \dots, \phi_n$ is

\Psi_F(1,\dots,n) = \frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n} \varepsilon(\sigma)\, \phi_{\sigma(1)}(1)\cdots\phi_{\sigma(n)}(n) ,

which is $1/\sqrt{n!}$ times the determinant of the matrix $[\phi_j(i)]$ . That is no coincidence: the Leibniz formula $\det A = \sum_{\sigma\in S_n}\varepsilon(\sigma)\,A_{1\sigma(1)}\cdots A_{n\sigma(n)}$ defines the determinant as the unique alternating multilinear function normalised at the identity, and the sign in it is the sign homomorphism of this unit (Determinants). The vanishing of a determinant with two equal columns and the Pauli principle are the same statement about $\varepsilon$ . The sign is likewise what makes the Levi-Civita symbol $\epsilon_{ijk}$ of vector calculus well defined, and hence the cross product and the curl.

Permutation symmetry beyond the two extremes. For $n \geq 3$ the symmetric group has irreducible representations of dimension greater than one, labelled by the partitions of $n$ — equivalently by the conjugacy classes, as the note above explains. When a many-electron state is split into a spatial and a spin factor, each factor transforms under one of these higher-dimensional representations and only the product is antisymmetric; the resulting bookkeeping of Young tableaux governs the term symbols of atomic spectra and the exchange splitting responsible for Hund's rules. Representations of groups and Character tables set up the machinery.

Sorting, parity and the sign in computation. Numerically, the sign of a permutation is read off during Gaussian elimination: each row interchange is a transposition and multiplies the determinant by $-1$ , so an implementation tracks a single boolean. The decomposition into disjoint cycles is also how a permutation is applied in place, cycle by cycle, with one temporary variable, and the number of transpositions needed, $n - c(\sigma)$ , is the minimum number of swaps that will sort the data.

Application · advanced

Point groups and crystal symmetry

Adapted

Add to PDF

Classifies the finite symmetry groups of a figure about a fixed point in two and three dimensions, and proves the crystallographic restriction, which allows a lattice only two-, three-, four- and six-fold rotation axes.

Prerequisites: Conjugacy classes, Groups and subgroups, Unitary and orthogonal matrices, Determinants

Definition(Point groups and the operations they contain)AdaptedAdapted from Arfken, Weber & Harris (2013), §17.4, 'Other Discrete Groups', p. 835; Riley, Hobson & Bence (2006), §28.1, pp. 1041-1042

Fix a point of $\mathbb{R}^n$ and call it the origin. A point group is a group of distance-preserving transformations of $\mathbb{R}^n$ that all keep that point fixed. Such a transformation is linear and preserves the Euclidean inner product, so it is given by an orthogonal matrix (Unitary and orthogonal matrices); a point group is therefore a subgroup of $\mathrm{O}(n)$ , and the point group of a figure $F \subseteq \mathbb{R}^n$ is

G(F) = \{\, Q \in \mathrm{O}(n) : Q F = F \,\} .

Here we consider only finite point groups. Arfken, Weber and Harris introduce them as the groups that keep a central point fixed, and note that they are the symmetry groups that arise when one studies properties depending on the shape of a molecule.

In three dimensions the elements are named by what they do:

$C_n$ , a proper rotation by $2\pi/n$ about an axis through the origin; $\det = +1$ . The axis is called an $n$ -fold axis.
$\sigma$ , a reflection in a plane through the origin; $\det = -1$ .
$i$ , the inversion $x \mapsto -x$ ; in three dimensions $\det = -1$ .
$S_n$ , an improper rotation: a rotation by $2\pi/n$ followed by the reflection in the plane perpendicular to its axis; $\det = -1$ . Thus $S_1 = \sigma$ and $S_2 = i$ .

Every element of finite order in $\mathrm{O}(3)$ is of one of these kinds. Indeed, the real canonical form of an orthogonal matrix (Unitary and orthogonal matrices) puts it, in a suitable orthonormal frame, in the shape $\operatorname{diag}(\pm1, R(\theta))$ ; finite order forces $\theta$ to be a rational multiple of $2\pi$ , say $\theta = 2\pi m/n$ , and the two signs give $C_n$ -type and $S_n$ -type elements respectively. The rotations of a point group $G$ form the subgroup $G \cap \mathrm{SO}(3)$ , of index $1$ or $2$ in $G$ .

Two further notations are in use and we record both, since the literature mixes them. In Schoenflies notation the cyclic group generated by one $C_n$ is written $C_n$ , the group generated by $C_n$ together with a perpendicular two-fold axis is $D_n$ , and subscripts $v$ , $h$ mark the addition of vertical or horizontal mirror planes. In Hermann-Mauguin (international, crystallographic) notation a group is named instead by its axes and mirrors written as numbers and the letter $m$ : (Riley, Hobson & Bence (2006), §29.11.3, p. 1110) writes the symmetry group of the equilateral triangle as $3m$ and gives $C_{3v}$ as its chemical synonym, and names the class of its rotations $3_z$ against the chemists' $C_3$ . We use the Schoenflies names and give the crystallographic one when a source does.

Application(Finite point groups of the plane)Original

Let $G \subseteq \mathrm{O}(2)$ be finite and of order $N$ . Then exactly one of the following holds.

$G$ consists of rotations only. Then $G = C_n$ is cyclic of order $n = N$ , generated by the rotation $R(2\pi/n)$ through the smallest positive angle occurring in $G$ .
$G$ contains a reflection. Then $N = 2n$ is even, the rotations of $G$ form a cyclic group $C_n$ , and $G$ consists of those $n$ rotations together with $n$ reflections in $n$ lines through the origin spaced by $\pi/n$ . This group is the symmetry group of a regular $n$ -gon centred at the origin (the dihedral group), for $n \geq 3$ .

Every finite subgroup of $\mathrm{O}(2)$ is therefore a $C_n$ or a dihedral group of order $2n$ .

Notation: following (Dummit & Foote (2004), §1.2, p. 24) we write the dihedral group of the regular $n$ -gon as $D_{2n}$ , the subscript giving its order $2n$ . Physics and chemistry texts write the same group as $D_n$ , the subscript giving the order of the principal axis. We use $D_{2n}$ in this unit and say so wherever a count could be misread.

Idea of the proofOriginal

A finite group of plane isometries fixing the origin is almost forced. Its rotations form a group of angles closed under addition and subtraction, and a finite such set of angles is the set of multiples of its smallest positive member: this is the same division-with-remainder argument that shows a subgroup of $\mathbb{Z}$ is cyclic. If a reflection is present as well, then composing it with each rotation produces the remaining elements and nothing else, because the product of two reflections is a rotation. So there are exactly as many reflections as rotations.

ProofOriginal

By the classification of $2 \times 2$ real orthogonal matrices (Unitary and orthogonal matrices), every element of $\mathrm{O}(2)$ is either a rotation $R(\theta)$ with $\det = +1$ or a reflection $F(\theta)$ in the line at angle $\theta/2$ , with $\det = -1$ .

The rotations form a cyclic group. Let $H = G \cap \mathrm{SO}(2)$ , a subgroup of $G$ since the determinant is multiplicative. Let

A = \{\, \theta \in \mathbb{R} : R(\theta) \in H \,\} .

Because $R(\theta)R(\varphi) = R(\theta + \varphi)$ and $R(\theta)^{-1} = R(-\theta)$ , the set $A$ is a subgroup of $(\mathbb{R}, +)$ containing $2\pi\mathbb{Z}$ . If $H = \{I\}$ put $n = 1$ . Otherwise $A$ contains an angle that is not a multiple of $2\pi$ , and since $G$ is finite the set $A \cap (0, 2\pi)$ is finite and non-empty; let $\alpha$ be its least element. Given any $\theta \in A$ , divide: $\theta = m\alpha + \rho$ with $m \in \mathbb{Z}$ and $0 \le \rho < \alpha$ . Then $\rho = \theta - m\alpha \in A$ , and $\rho < \alpha$ forces $\rho = 0$ by minimality of $\alpha$ . Hence $A = \alpha\mathbb{Z}$ . Since $2\pi \in A$ we get $2\pi = n\alpha$ for some positive integer $n$ , that is $\alpha = 2\pi/n$ , and

H = \{\, R(2\pi k/n) : k = 0, 1, \dots, n-1 \,\} ,

cyclic of order $n$ generated by $R(2\pi/n)$ . Finiteness was used twice: to know that a least positive angle exists, and to know that $n$ is finite.

Case 1. If $G$ contains no reflection then $G = H = C_n$ and $N = n$ .

Case 2. Suppose $G$ contains a reflection $F_0$ . The map $h \mapsto F_0 h$ is a bijection from $H$ onto the set $F_0 H$ of elements of determinant $-1$ in $G$ , with inverse $g \mapsto F_0 g$ (using $F_0^2 = I$ , which holds because a reflection is an involution). Conversely, if $g \in G$ has $\det g = -1$ then $F_0 g$ has determinant $+1$ , so $F_0 g \in H$ and $g \in F_0 H$ . Hence $G = H \sqcup F_0H$ and $N = 2n$ . Writing $F_0 = F(\varphi)$ and using $F(\varphi)R(\theta) = F(\varphi - \theta)$ — both sides send the unit vector at angle $\psi$ to the unit vector at angle $\varphi - \theta - \psi$ — the $n$ reflections are $F(\varphi - 2\pi k/n)$ , $k = 0, \dots, n-1$ . Their mirror lines are at angles $(\varphi - 2\pi k/n)/2$ , consecutive ones differing by $\pi/n$ .

It is the symmetry group of a regular $n$ -gon. Let $P$ be the regular $n$ -gon with one vertex at angle $\varphi/2$ . The rotations in $H$ permute its vertices cyclically and the reflection $F(\varphi)$ fixes the line through that vertex, so $G \subseteq G(P)$ . Conversely a symmetry of $P$ permutes the $n$ vertices and is determined by the image of one vertex together with the choice of orientation, so $|G(P)| \le 2n = |G|$ , by the count in (Dummit & Foote (2004), §1.2, p. 24). Hence $G = G(P)$ . $\square$

Application(The crystallographic restriction)Original

Let $L \subseteq \mathbb{R}^d$ be a lattice of full rank, that is

L = \mathbb{Z}a_1 \oplus \cdots \oplus \mathbb{Z}a_d

for some basis $a_1, \dots, a_d$ of $\mathbb{R}^d$ , and let $Q \in \mathrm{O}(d)$ satisfy $QL = L$ . Then:

The matrix $M$ of $Q$ in the basis $a_1, \dots, a_d$ has integer entries and $\det M = \pm 1$ ; in particular $\operatorname{tr} Q = \operatorname{tr} M \in \mathbb{Z}$ .
$d = 2$ . If $Q$ is a rotation of order $n$ , then $n \in \{1, 2, 3, 4, 6\}$ .
$d = 3$ . If $Q$ is a proper rotation ( $\det Q = +1$ ) of order $n$ , then $n \in \{1, 2, 3, 4, 6\}$ . The same list holds for an improper rotation $S_n$ with $n$ even, and $S_n$ with $n$ odd has order $2n$ with $n \in \{1,3\}$ .

No lattice in two or three dimensions admits a rotation axis of order $5$ , or of any order $\ge 7$ . The point groups compatible with a lattice in three dimensions — the crystallographic point groups — are therefore only finitely many, and (Arfken, Weber & Harris (2013), §17.10, p. 869) records that there are exactly $32$ of them, compatible with the $14$ Bravais lattices and combining with translations into $230$ space groups.

Idea of the proofOriginal

A symmetry of a lattice sends lattice points to lattice points, so in a basis of the lattice its matrix has integer entries — even though in Cartesian coordinates it is full of cosines. The trace does not care which basis is used. So the Cartesian trace, which is $2\cos\theta$ in the plane and $1 + 2\cos\theta$ in space, must be an integer; and $\cos\theta$ is confined to $[-1,1]$ , so only five values of $\theta$ survive. The whole restriction is the statement that $2\cos\theta$ is an integer.

ProofOriginal

Part 1. Each $a_j$ lies in $L$ , so $Qa_j \in QL = L$ and $Qa_j$ is an integer combination of the basis: $Qa_j = \sum_i M_{ij} a_i$ with $M_{ij} \in \mathbb{Z}$ . This is exactly the statement that the matrix of $Q$ in the basis $(a_i)$ is the integer matrix $M$ . The same argument applied to $Q^{-1}$ , which also maps $L$ onto $L$ because $Q L = L$ gives $L = Q^{-1}L$ , produces an integer matrix $M'$ with $MM' = I$ ; taking determinants, $\det M \cdot \det M' = 1$ with both factors integers, so $\det M = \pm 1$ . Finally, if $B$ is the matrix whose columns are the $a_j$ in Cartesian coordinates, then $Q = BMB^{-1}$ , and the trace is invariant under conjugation, so $\operatorname{tr} Q = \operatorname{tr} M$ , an integer. This is the step that uses the full rank of $L$ : the $a_j$ must be a basis of $\mathbb{R}^d$ for $B$ to be invertible.

Part 2 ( $d = 2$ ). A rotation of the plane by $\theta$ has Cartesian matrix $R(\theta)$ with $\operatorname{tr} R(\theta) = 2\cos\theta$ . By part 1 this is an integer, and $|2\cos\theta| \le 2$ , so

2\cos\theta \in \{2,\ 1,\ 0,\ -1,\ -2\}, \qquad \text{so} \qquad \theta \equiv \pm\theta_0 \pmod{2\pi}, \quad \theta_0 \in \left\{0,\ \tfrac{\pi}{3},\ \tfrac{\pi}{2},\ \tfrac{2\pi}{3},\ \pi\right\},

the two lists corresponding term by term. Write $Q = R(\alpha)$ with $\alpha$ one of these angles. The order of $R(\alpha)$ is the least $n \ge 1$ with $n\alpha \in 2\pi\mathbb{Z}$ , which for $\alpha = 0,\ \pm\tfrac{\pi}{3},\ \pm\tfrac{\pi}{2},\ \pm\tfrac{2\pi}{3},\ \pi$ is $1, 6, 4, 3, 2$ respectively. So $n \in \{1,2,3,4,6\}$ .

Part 3 ( $d = 3$ ). A proper rotation of $\mathbb{R}^3$ by $\theta$ about an axis has, in an orthonormal frame adapted to the axis, the matrix $\operatorname{diag}(1, R(\theta))$ (Unitary and orthogonal matrices), so $\operatorname{tr}Q = 1 + 2\cos\theta$ . By part 1 this is an integer, hence $2\cos\theta \in \mathbb{Z}$ again, and the five angles of part 2 are reproduced together with their orders: $n \in \{1,2,3,4,6\}$ .

For an improper element, $S_n$ is the rotation by $2\pi/n$ about an axis followed by the reflection in the perpendicular plane, so in the adapted frame its matrix is $\operatorname{diag}(-1, R(2\pi/n))$ and $\operatorname{tr} S_n = -1 + 2\cos(2\pi/n)$ . Part 1 again gives $2\cos(2\pi/n) \in \mathbb{Z}$ and the same five values of $n$ . The order of $S_n$ as a group element is $n$ when $n$ is even (since $S_n^n = \operatorname{diag}((-1)^n, I) = I$ ) and $2n$ when $n$ is odd; with $n \in \{1,2,3,4,6\}$ the odd cases are $n = 1$ (the reflection $\sigma$ , of order $2$ ) and $n = 3$ (of order $6$ ). $\square$

Remark(Where the hypotheses are used, and what fails without them)Original

The lattice is essential; the point group alone is not restricted. Nothing in the definition of a finite point group forbids a five-fold axis: the regular pentagon has symmetry group $D_{10}$ (order $10$ ) in the plane, and the icosahedron has a point group containing six five-fold axes. Arfken, Weber and Harris make the same point by saying that a point group may have a single $n$ -fold axis for any $n$ , and that the restriction to the tetrahedral, octahedral and icosahedral cases concerns only groups with several axes of order at least three (Arfken, Weber & Harris (2013), p. 835). The crystallographic restriction uses the hypothesis $QL = L$ at the very first line of the proof and nowhere else; drop it and the argument has no content.

Full rank is essential. Take $L = \mathbb{Z}(1,0,0) \subset \mathbb{R}^3$ , a rank-one lattice in three-space, and let $Q$ be the rotation by $2\pi/5$ about the $x$ -axis. Then $QL = L$ , yet $Q$ has order $5$ . The proof breaks at the point where the $a_j$ are used as a basis of $\mathbb{R}^d$ : with one generator there is no such basis, and the Cartesian trace $1 + 2\cos(2\pi/5)$ is not forced to be an integer.

The restriction bounds angles, not groups. Part 2 and part 3 constrain each individual rotation. That there are then only $32$ crystallographic point groups in three dimensions, $14$ Bravais lattices and $230$ space groups is a much longer classification, which we quote from (Arfken, Weber & Harris (2013), §17.10, p. 869) and do not prove.

Quasicrystals are not a counterexample. A material whose diffraction pattern shows a sharp ten-fold symmetry is not periodic: it has no lattice $L$ , so the theorem does not apply to it. The theorem is what made such patterns surprising when they were first seen.

Arfken's tiling argument proves less than the trace argument. Example 17.10.1 of (Arfken, Weber & Harris (2013), p. 869) argues in the plane that an integer number of identical regular polygons must meet at a vertex, which succeeds for the triangle, square and hexagon and fails for the pentagon. That rules out tilings by one regular polygon; it does not by itself rule out a five-fold rotation axis of a lattice whose unit cell is some other shape. The trace argument above does.

Method(Finding the point group of a molecule or a unit cell)Original

Place the origin at the centroid of the figure. Every symmetry fixes the centroid, because an isometry of a finite set of equal masses permutes them and so preserves their mean.
Find the proper rotations. For each candidate axis (through two atoms, through an atom and the centroid, or through the midpoints of two bonds), find the largest $n$ with the rotation by $2\pi/n$ a symmetry. Record the axis of largest $n$ as the principal axis.
Test the improper elements: the inversion $x \mapsto -x$ ; the reflection $\sigma_h$ in the plane perpendicular to the principal axis; the reflections $\sigma_v$ in planes containing it; and the improper rotations $S_{2n}$ about it.
Count. Let $r$ be the number of proper rotations found, including the identity. If no improper element is a symmetry, $|G| = r$ ; otherwise $|G| = 2r$ , by the coset argument used in Case 2 of the planar proof, which needs only that the determinant is a homomorphism onto $\{\pm 1\}$ .
For a crystal, discard any axis of order other than $1, 2, 3, 4, 6$ : by the crystallographic restriction it cannot be a symmetry of the lattice, so an apparent five-fold or seven-fold axis means either that the figure is not the unit cell of a lattice or that an error has been made.
Sort the elements into conjugacy classes (Conjugacy classes), since those are what a character table is indexed by. Two rotations by the same angle about axes related by a symmetry of the figure are conjugate.

Example(The planar hexagonal lattice, and why five-fold symmetry is impossible)Original

Part A: the matrix of a six-fold rotation is an integer matrix. Take the planar hexagonal (triangular) lattice $L = \mathbb{Z}a_1 \oplus \mathbb{Z}a_2$ with

a_1 = (1, 0), \qquad a_2 = \left(-\tfrac12, \tfrac{\sqrt3}{2}\right),

so $\|a_1\| = \|a_2\| = 1$ and the angle between them is $120^\circ$ . Let $Q = R(\pi/3)$ be the rotation by $60^\circ$ . In Cartesian coordinates

Q a_1 = \left(\cos 60^\circ,\ \sin 60^\circ\right) = \left(\tfrac12,\ \tfrac{\sqrt3}{2}\right),

Q a_2 = \left(-\tfrac12\cos 60^\circ - \tfrac{\sqrt3}{2}\sin 60^\circ,\ -\tfrac12\sin 60^\circ + \tfrac{\sqrt3}{2}\cos 60^\circ\right) = \left(-\tfrac14 - \tfrac34,\ -\tfrac{\sqrt3}{4} + \tfrac{\sqrt3}{4}\right) = (-1, 0) .

Both are lattice vectors, since $(\tfrac12, \tfrac{\sqrt3}{2}) = a_1 + a_2$ and $(-1,0) = -a_1$ . So $QL = L$ , and in the basis $(a_1, a_2)$

M = \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix},

an integer matrix, as part 1 of the restriction requires, with $\det M = 1\cdot 0 - (-1)\cdot 1 = +1$ and $\operatorname{tr} M = 1$ . The Cartesian trace agrees: $2\cos 60^\circ = 1$ . Its characteristic polynomial is $\lambda^2 - \lambda + 1$ , whose roots $e^{\pm i\pi/3}$ are primitive sixth roots of unity, and indeed $M^6 = I$ while no smaller positive power is the identity. So $Q$ has order exactly $6$ .

Part B: the point group of this lattice. The six rotations $R(k\pi/3)$ , $k = 0, \dots, 5$ , all preserve $L$ , being powers of the $Q$ of Part A. So does the reflection $\sigma$ in the $x$ -axis: $\sigma a_1 = a_1$ and $\sigma a_2 = (-\tfrac12, -\tfrac{\sqrt3}{2}) = -(a_1 + a_2)$ , both in $L$ . There is nothing else. Indeed the rotation subgroup is some $C_n$ by the planar classification, it contains $R(\pi/3)$ so $6$ divides $n$ , and the crystallographic restriction caps $n$ at $6$ ; hence $n = 6$ exactly, and the presence of $\sigma$ doubles the count by Case 2 of the planar classification. The group is dihedral of order

|G| = 2 \times 6 = 12 ,

that is $D_{12}$ in the order-subscript convention of this unit ( $D_6$ or $6mm$ in the crystallographers' notation). This is the largest point group a planar lattice can have.

Part C: five-fold symmetry is excluded. Suppose some planar lattice $L'$ of full rank had a symmetry $Q'$ of order $5$ . By part 1 its trace in a lattice basis is an integer; by part 2 that trace is $2\cos(2\pi/5)$ . But

2\cos\frac{2\pi}{5} = \frac{\sqrt5 - 1}{2} = 0.6180339887\ldots ,

which is irrational, hence not an integer. The contradiction shows no such $L'$ exists. The same number settles the three-dimensional case, where the trace would be $1 + 0.618\ldots = 1.618\ldots$ , again not an integer. For contrast, $2\cos(2\pi/7) = 1.2469\ldots$ and $2\cos(2\pi/8) = \sqrt2 = 1.4142\ldots$ are likewise non-integers, so seven- and eight-fold axes are excluded too, exactly as the five values $\{-2,-1,0,1,2\}$ of the proof predict.

ApplicationOriginal

Reading a diffraction pattern. X-ray, electron and neutron diffraction from a crystal produce a pattern whose symmetry is that of the crystal's point group, acting on the reciprocal lattice. Because the crystallographic restriction allows only $1,2,3,4,6$ -fold axes, a diffraction photograph of a periodic solid can show only those rotational symmetries, and the observed symmetry immediately narrows the structure to one of the $32$ crystallographic point groups and then, with the systematic absences of reflections, to one of the $230$ space groups (Arfken, Weber & Harris (2013), §17.10, p. 869). This is the first step of every structure determination, and it is a group-theoretic step: no intensity needs to be modelled to take it.

Quasicrystals. In 1982 Shechtman observed, in a rapidly cooled Al-Mn alloy, a sharp electron-diffraction pattern with ten-fold rotational symmetry. The crystallographic restriction says that a lattice cannot do this, so the sample could not be periodic, and the result was resisted for years on exactly that ground. The resolution was that the solid is ordered but aperiodic, built on a Penrose-type tiling; the theorem had not failed, its hypothesis $QL = L$ had. The episode is the clearest case in solid-state physics of a classification theorem forcing a physical conclusion.

Selection rules and degeneracies. The normal modes of a molecule, and the electronic states of an atom in a crystal field, organise themselves into irreducible representations of the point group, and the dimension of the irreducible representation is the degeneracy of the level (Representations of groups, Product representations and selection rules). Whether a transition between two levels is allowed is decided by whether the product representation contains the identity representation, which is a finite calculation in the character table of the point group. Because a crystallographic point group has at most $48$ elements, these calculations are short, and they predict which infrared and Raman lines appear without any dynamical model of the molecule.

Material tensors. A physical property of a crystal expressed as a tensor — electrical conductivity, elasticity, piezoelectric coupling — must be invariant under every element of the point group. Each symmetry operation is a linear constraint on the tensor components, so the point group determines how many independent constants a material can have. The inversion $i$ is the most consequential single element: a tensor of odd rank changes sign under $x \mapsto -x$ , so a centrosymmetric crystal has no piezoelectric effect and no second-harmonic generation at all. Knowing only the point group therefore rules out whole classes of devices for a given material, or selects it for them.

Definition

Rings and fields

Adapted

Add to PDF

Defines rings, ideals, quotient rings, integral domains and fields, records that a quotient by an ideal is a field exactly when the ideal is maximal, and identifies the fields the handbook uses.

Prerequisites: Homomorphisms and quotient groups, Groups and subgroups, Vector spaces and bases

Definition(Rings)AdaptedAdapted from Dummit & Foote (2004), §7.1, pp. 223-224

A ring is a set $R$ carrying two operations, written $+$ and $\times$ (we usually write $ab$ for $a \times b$ ), such that

$(R, +)$ is an abelian group, with identity $0$ and with $-a$ the additive inverse of $a$ ;
multiplication is associative: $(ab)c = a(bc)$ for all $a, b, c \in R$ ;
the two distributive laws hold: $(a+b)c = ac + bc$ and $a(b+c) = ab + ac$ for all $a,b,c \in R$ .

$R$ is commutative if $ab = ba$ always, and $R$ has an identity (or "has a $1$ ") if there is $1 \in R$ with $1a = a1 = a$ for all $a$ . Dummit and Foote note that for a ring with a $1$ the commutativity of addition is not an extra assumption: expanding $(1+1)(a+b)$ by the two distributive laws in the two possible orders gives $a + b + a + b$ and $a + a + b + b$ , and cancelling in the additive group leaves $b + a = a + b$ .

Three facts follow from the axioms alone (Dummit & Foote (2004), Prop. 1, p. 226): $0a = a0 = 0$ ; $(-a)b = a(-b) = -(ab)$ ; and if $R$ has an identity then it is unique and $-a = (-1)a$ .

Let $R$ have an identity $1 \neq 0$ .

A unit is an element $u$ with $uv = vu = 1$ for some $v \in R$ . The units form a group $R^\times$ under multiplication.
A nonzero $a \in R$ is a zero divisor if $ab = 0$ or $ba = 0$ for some nonzero $b \in R$ .
$R$ is a division ring — also called a skew field — when each $a \ne 0$ is a unit. Such an $R$ that is commutative as well is a field.
A commutative $R$ with no zero divisors is an integral domain (Dummit & Foote (2004), p. 228).

A zero divisor is never a unit: if $va = 1$ and $ab = 0$ with $b \neq 0$ , then $b = (va)b = v(ab) = 0$ , a contradiction. So a field has no zero divisors, and every field is an integral domain.

A subring of $R$ is a subgroup of $(R,+)$ closed under multiplication; to check a non-empty subset is a subring it suffices to check closure under subtraction and under multiplication (Dummit & Foote (2004), p. 228).

Definition(Ideals and quotient rings)AdaptedAdapted from Dummit & Foote (2004), §7.3, pp. 241-243

Let $R$ be a ring. A subset $I \subseteq R$ is a left ideal if it is a subring and $rI \subseteq I$ for every $r \in R$ ; a right ideal if it is a subring and $Ir \subseteq I$ for every $r \in R$ ; and a (two-sided) ideal if it is both. In a commutative ring the three notions coincide.

If $I$ is an ideal, the additive cosets $r + I$ form a ring, the quotient ring $R/I$ , under

(r + I) + (s + I) = (r+s) + I, \qquad (r+I)(s+I) = rs + I .

The additive part is the quotient group of Homomorphisms and quotient groups, which needs no hypothesis beyond $I$ being a subgroup, because $(R,+)$ is abelian and every subgroup of it is normal. What the ideal condition buys is that the multiplication is well defined. Dummit and Foote show this is exactly the right condition: writing $r' = r + \alpha$ , $s' = s + \beta$ with $\alpha, \beta \in I$ ,

r's' = rs + r\beta + \alpha s + \alpha\beta ,

and for $r's' + I = rs + I$ for all choices one needs $r\beta$ , $\alpha s$ and $\alpha\beta$ to lie in $I$ for all $r, s \in R$ and $\alpha, \beta \in I$ — that is, precisely that $I$ absorbs multiplication from both sides.

A map $\varphi : R \to S$ of rings is a ring homomorphism if $\varphi(a+b) = \varphi(a) + \varphi(b)$ and $\varphi(ab) = \varphi(a)\varphi(b)$ , and its kernel is $\varphi^{-1}(0)$ .

Two kinds of ideal of a commutative ring $R$ with $1 \neq 0$ are singled out (Dummit & Foote (2004), pp. 253-255):

$M \subsetneq R$ is maximal if no ideal lies strictly between $M$ and $R$ ;
$P \subsetneq R$ is prime if $ab \in P$ implies $a \in P$ or $b \in P$ .

Definition(Quotients, isomorphism, and when a quotient is a field)AdaptedAdapted from Dummit & Foote (2004), §7.3, Thm 7, p. 243; Dummit & Foote (2004), §7.4, Props 12 and 13, pp. 254-255

Let $R$ be a ring.

(First isomorphism theorem for rings.) If $\varphi : R \to S$ is a ring homomorphism, then $\ker\varphi$ is an ideal of $R$ , $\varphi(R)$ is a subring of $S$ , and $R/\ker\varphi \cong \varphi(R)$ as rings. Conversely, for every ideal $I$ the map $r \mapsto r + I$ is a surjective ring homomorphism $R \to R/I$ with kernel $I$ . An ideal is therefore nothing other than a kernel, and a kernel nothing other than an ideal.
Now let $R$ be commutative with $1 \neq 0$ , and let $I$ be an ideal. Then
- $I$ is maximal $\iff$ $R/I$ is a field;
- $I$ is prime $\iff$ $R/I$ is an integral domain.
Since fields are integral domains, maximality implies primality.
Every finite integral domain is a field (Dummit & Foote (2004), Cor. 3, p. 228).

Idea of the proofOriginal

A commutative ring with $1 \ne 0$ is a field exactly when it has no ideals except $0$ and itself: a nonzero element $a$ generates the ideal $aR$ , and $a$ is invertible precisely when that ideal is everything. Quotienting by $I$ collapses the ideals between $I$ and $R$ onto the ideals of $R/I$ , so "nothing strictly between $I$ and $R$ " becomes "no ideals except $0$ and everything" becomes "field". The prime statement is the same translation one level down: " $ab \in P$ forces $a \in P$ or $b \in P$ " is literally " $\bar a \bar b = 0$ forces $\bar a = 0$ or $\bar b = 0$ " in the quotient, which is the absence of zero divisors. Part 3 is a pigeonhole: in a finite domain the map $x \mapsto ax$ is injective by cancellation, hence surjective, so $1$ is hit.

ProofAdaptedAdapted from Dummit & Foote (2004), §7.3, Thm 7, p. 243; Dummit & Foote (2004), §7.4, Props 12 and 13, pp. 254-255; Dummit & Foote (2004), §7.1, Cor. 3, p. 228

Part 1. Let $I = \ker\varphi$ . It is an additive subgroup, and for $r \in R$ , $\alpha \in I$ we get $\varphi(r\alpha) = \varphi(r)\varphi(\alpha) = \varphi(r)\cdot 0 = 0$ and likewise $\varphi(\alpha r) = 0$ , so $rI \subseteq I$ and $Ir \subseteq I$ : $I$ is a two-sided ideal. Define $\Phi : R/I \to \varphi(R)$ by $\Phi(r + I) = \varphi(r)$ . It is well defined and injective because the three conditions $\varphi(r) = \varphi(s)$ , $r - s \in I$ and $r + I = s + I$ are mutually equivalent; it is surjective onto $\varphi(R)$ by construction; and it respects both operations, since $\Phi((r+I)(s+I)) = \Phi(rs + I) = \varphi(rs) = \varphi(r)\varphi(s)$ , using that $\varphi$ is multiplicative. The converse statement is the definition of the quotient together with the observation that $r + I = 0 + I$ exactly when $r \in I$ .

Part 2, the field case. Write $\bar{\phantom{x}}$ for the image in $R/I$ , a commutative ring with identity $\bar1$ .

If $I$ is maximal, $R/I$ is a field. First $\bar 1 \neq \bar 0$ , since $1 \in I$ would force $r = r\cdot 1 \in I$ for every $r$ and hence $I = R$ , contradicting $I \subsetneq R$ . Let $\bar a \neq \bar 0$ , that is $a \notin I$ . The set

J = I + aR = \{\, \alpha + ar : \alpha \in I,\ r \in R \,\}

is an ideal: it is closed under subtraction, and $s(\alpha + ar) = s\alpha + a(sr) \in J$ for every $s \in R$ , using commutativity to move $s$ past $a$ . It contains $I$ and also $a = 0 + a\cdot 1$ , so $J \supsetneq I$ . Maximality now forces $J = R$ , so $1 = \alpha + ab$ for some $\alpha \in I$ , $b \in R$ . Reducing modulo $I$ gives $\bar 1 = \bar a \bar b$ , so $\bar a$ is a unit. Every nonzero element of $R/I$ is a unit, so $R/I$ is a field.

If $R/I$ is a field, $I$ is maximal. Since $\bar 1 \neq \bar 0$ we have $I \neq R$ . Let $J$ be an ideal with $I \subsetneq J \subseteq R$ and pick $a \in J \setminus I$ . Then $\bar a \neq \bar 0$ , so by the field hypothesis there is $b$ with $\bar a\bar b = \bar 1$ , i.e. $1 - ab \in I \subseteq J$ . Also $ab \in J$ because $J$ is an ideal and $a \in J$ . Hence $1 = (1 - ab) + ab \in J$ , and then $r = r \cdot 1 \in J$ for every $r$ , so $J = R$ . No ideal lies strictly between $I$ and $R$ .

Part 2, the domain case. $R/I$ is commutative with identity. $I$ prime means $I \neq R$ , which as above is $\bar1 \neq \bar 0$ , together with: $ab \in I \Rightarrow a \in I$ or $b \in I$ . Translating, $ab \in I$ says $\bar a\bar b = \bar 0$ and $a \in I$ says $\bar a = \bar 0$ , so the condition reads: $\bar a \bar b = \bar 0 \Rightarrow \bar a = \bar 0$ or $\bar b = \bar 0$ , which is exactly the absence of zero divisors in $R/I$ . Both directions are this one translation.

Part 3. Let $R$ be a finite integral domain and $a \neq 0$ . If $ax = ay$ then $a(x - y) = 0$ , and $a$ is not a zero divisor, so $x = y$ : the map $x \mapsto ax$ from $R$ to $R$ is injective. A injective map of a finite set to itself is surjective, so $ab = 1$ for some $b$ , and $a$ is a unit. Hence $R$ is a field. $\square$

Definition(Polynomial rings)AdaptedAdapted from Dummit & Foote (2004), §7.2, pp. 234-235

Let $R$ be a commutative ring with identity and $x$ an indeterminate. A polynomial is a formal sum $f = a_nx^n + \cdots + a_1x + a_0$ with $a_i \in R$ . If $a_n \neq 0$ then $f$ has degree $n$ , leading coefficient $a_n$ , and is monic if $a_n = 1$ ; the degree of the zero polynomial is left undefined and its leading coefficient taken to be $0$ . The set $R[x]$ of all polynomials is a ring under coefficientwise addition and the multiplication determined by $(ax^i)(bx^j) = abx^{i+j}$ , so that the coefficient of $x^k$ in a product is $\sum_{i=0}^{k} a_i b_{k-i}$ . It is commutative with the identity $1$ of $R$ , and $R$ sits inside it as the constant polynomials.

If $R$ is an integral domain then (Dummit & Foote (2004), Prop. 4, p. 235)

\deg(fg) = \deg f + \deg g \quad (f, g \neq 0), \qquad R[x]^\times = R^\times, \qquad R[x] \text{ is an integral domain,}

all three because the leading coefficient of $fg$ is the product of the leading coefficients, which cannot vanish.

For a field $F$ , division with remainder works in $F[x]$ : given $f$ and $g \neq 0$ there are unique $q, r \in F[x]$ with $f = qg + r$ and either $r = 0$ or $\deg r < \deg g$ . A polynomial $p \in F[x]$ of degree $\ge 1$ is irreducible if it is not a product of two polynomials of strictly smaller degree.

Definition(The fields this handbook uses)AdaptedAdapted from Dummit & Foote (2004), §7.1, p. 224; Dummit & Foote (2004), §7.4, p. 255; Dummit & Foote (2004), §13.1, Thms 3 and 4, pp. 512-513

$\mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$ are fields, each a subring of the next, while $\mathbb{Z}$ , whose only units are $\pm 1$ , is an integral domain but not a field. Almost every structure in this handbook — a vector space, a Hilbert space, a solution of a differential equation — has its scalars in $\mathbb{R}$ or $\mathbb{C}$ .
$\mathbb{C} \cong \mathbb{R}[x]/(x^2+1)$ .
For an integer $n \ge 2$ : $\mathbb{Z}/n\mathbb{Z}$ is a field exactly when $n$ is prime (Dummit & Foote (2004), p. 255). The field with $p$ elements is written $\mathbb{F}_p$ .
Let $F$ be a field and $p \in F[x]$ irreducible of degree $n$ . Then $K = F[x]/(p)$ is a field. It contains a copy of $F$ , and the class $t = x + (p)$ is a root of $p$ inside $K$ ; and $1, t, t^2, \dots, t^{n-1}$ is a basis of $K$ as an $F$ -vector space, so $\dim_F K = n$ (Dummit & Foote (2004), Thms 3 and 4, pp. 512-513). Taking $F = \mathbb{F}_p$ gives a field with $p^n$ elements, written $\mathbb{F}_{p^n}$ .

Idea of the proofOriginal

Parts 2 and 4 are the same construction. To make a root of $p$ exist, work with polynomials and declare $p$ to be zero; "declaring an element zero" in ring language means passing to the quotient by the ideal it generates. Irreducibility of $p$ is what makes that ideal maximal in $F[x]$ , and a quotient by a maximal ideal is a field by the statement above. The basis $1, t, \dots, t^{n-1}$ is then just division with remainder: every polynomial is congruent modulo $p$ to its remainder, which has degree below $n$ .

Proof(Parts 2 and 4)AdaptedAdapted from Dummit & Foote (2004), §13.1, Thms 3 and 4, pp. 512-513

$(p)$ is maximal in $F[x]$ when $p$ is irreducible. Let $J$ be an ideal with $(p) \subseteq J \subseteq F[x]$ and let $g \in J$ be nonzero of least degree. Dividing, $p = qg + r$ with $r = 0$ or $\deg r < \deg g$ ; since $p \in (p) \subseteq J$ and $qg \in J$ , also $r = p - qg \in J$ , and minimality of $\deg g$ forces $r = 0$ . So $p = qg$ , and irreducibility leaves two cases: $\deg g = 0$ , in which case $g$ is a nonzero constant, hence a unit, and $J = F[x]$ ; or $\deg g = \deg p$ , in which case $q$ is a constant and $(g) = (p)$ . The same division argument shows $J = (g)$ — every $f \in J$ has remainder $0$ on division by $g$ — so $J$ is $(p)$ or $F[x]$ . Hence $(p)$ is maximal, and $K = F[x]/(p)$ is a field by part 2 of the previous statement.

$F$ embeds and $p$ acquires a root. The composite $F \hookrightarrow F[x] \to K$ is a ring homomorphism sending $1$ to $1$ , so it is not identically zero; its kernel is an ideal of the field $F$ , and a field has only the ideals $0$ and $F$ , so the kernel is $0$ and the map is injective. Identify $F$ with its image. Writing $t$ for the class of $x$ and using that reduction modulo $(p)$ is a ring homomorphism fixing the coefficients,

p(t) = p(x) + (p) = 0 + (p) ,

so $t$ is a root of $p$ in $K$ .

The basis. Let $n = \deg p$ . Spanning: any $f \in F[x]$ divides as $f = qp + r$ with $r = 0$ or $\deg r < n$ , and $qp \in (p)$ , so the class of $f$ equals the class of $r$ , which is an $F$ -combination of $1, t, \dots, t^{n-1}$ . Independence: if $c_0 + c_1t + \cdots + c_{n-1}t^{n-1} = 0$ in $K$ with $c_i \in F$ , then the polynomial $c_0 + \cdots + c_{n-1}x^{n-1}$ lies in $(p)$ , so it is $hp$ for some $h$ ; if $h \neq 0$ then its degree is $\deg h + n \ge n$ , impossible for a polynomial of degree at most $n-1$ , so $h = 0$ and every $c_i = 0$ . Hence $\dim_F K = n$ (Vector spaces and bases).

Part 2. $x^2 + 1$ is irreducible over $\mathbb{R}$ : a factorisation into two degree-one factors would give a real root, and $a^2 + 1 \ge 1 > 0$ for every real $a$ . So $K = \mathbb{R}[x]/(x^2+1)$ is a field with basis $1, t$ over $\mathbb{R}$ and $t^2 = -1$ . The map $a + bt \mapsto a + bi$ is an $\mathbb{R}$ -linear bijection $K \to \mathbb{C}$ , and it is multiplicative because both products are computed by expanding and using $t^2 = -1$ , $i^2 = -1$ :

(a+bt)(c+dt) = (ac - bd) + (ad + bc)t \ \longmapsto\ (ac-bd) + (ad+bc)i = (a+bi)(c+di) .

So $K \cong \mathbb{C}$ .

Part 4, the count. If $F = \mathbb{F}_p$ then $K$ has basis $1, t, \dots, t^{n-1}$ over a field of $p$ elements, so its elements are the $p^n$ tuples of coefficients. $\square$

Remark(Where the hypotheses are used)Original

Commutativity in the maximal-ideal criterion. The proof that a maximal $I$ gives a field used commutativity twice: to know $I + aR$ is a two-sided ideal, and to conclude from $\bar a\bar b = \bar 1$ that $\bar a$ is a two-sided unit. Dummit and Foote state Proposition 12 for commutative rings for this reason, while noting that one half — $R/I$ a field implies $I$ maximal — holds in any ring (Dummit & Foote (2004), p. 255).

$1 \neq 0$ . Without it the zero ring would be a field, and every statement about maximal ideals would acquire an exception; the zero ring has no maximal ideals at all (Dummit & Foote (2004), p. 254).

A subring is not enough for a quotient. $\mathbb{Z}$ is a subring of $\mathbb{Q}$ but not an ideal, and $\mathbb{Q}/\mathbb{Z}$ has no well-defined multiplication: $\tfrac12 + \mathbb{Z} = \tfrac32 + \mathbb{Z}$ , yet $\tfrac12\cdot\tfrac12 = \tfrac14$ and $\tfrac32\cdot\tfrac12 = \tfrac34$ differ by $\tfrac12 \notin \mathbb{Z}$ . This is exactly the absorption condition failing.

Irreducibility in part 4. Drop it and the quotient is not a field. In $\mathbb{R}[x]$ take $p = x^2 - 1 = (x-1)(x+1)$ . In $\mathbb{R}[x]/(p)$ the classes of $x-1$ and $x+1$ are nonzero but their product is zero, so the quotient has zero divisors; it is in fact isomorphic to $\mathbb{R}\times\mathbb{R}$ .

Finiteness in "a finite integral domain is a field". $\mathbb{Z}$ is an infinite integral domain and is not a field; the injective map $x \mapsto 2x$ is not surjective.

Division rings that are not fields exist, but not finite ones. The quaternions (Quaternions) are a non-commutative division ring (Dummit & Foote (2004), p. 224). Dummit and Foote record Wedderburn's theorem, that a finite division ring is necessarily commutative, hence a field (Dummit & Foote (2004), p. 228); we quote it and do not prove it.

Two conventions for "ring". Many texts, including Dummit and Foote, allow a ring without an identity (their example is $2\mathbb{Z}$ ). Others build $1$ into the axioms. We follow Dummit and Foote: a ring need not have a $1$ , and every statement that needs one says so.

Method(Deciding what a quotient ring is)Original

Given a commutative ring $R$ with $1$ and an ideal $I$ :

Find a convenient set of coset representatives. In $\mathbb{Z}/n\mathbb{Z}$ take $0, \dots, n-1$ (division with remainder by $n$ ); in $F[x]/(p)$ with $\deg p = n$ take the polynomials of degree $< n$ (division with remainder by $p$ ).
Write down the multiplication rule on those representatives: multiply in $R$ and then reduce. In $F[x]/(p)$ this means using $p(t) = 0$ to rewrite $t^n$ and higher powers.
Test for zero divisors. A product of two nonzero representatives that reduces to $0$ exhibits a zero divisor; then $I$ is not prime, and in particular not maximal.
Test for a field. If $R/I$ is finite and has no zero divisors, part 3 of the statement above makes it a field at once, with no inverses to compute. Otherwise, invert a general nonzero element directly, or factor $I$ 's generator and use step 3.
Identify it. If you can produce a surjective homomorphism $\varphi: R \to S$ with $\ker\varphi = I$ , the first isomorphism theorem gives $R/I \cong S$ outright. Evaluation maps $f \mapsto f(c)$ are the usual source of these.

Example(Two quotients of a polynomial or integer ring)Original

Part A: $\mathbb{Z}/12\mathbb{Z}$ is not a field, and exactly how it fails. Represent the classes by $0, 1, \dots, 11$ . The class $\bar a$ is a unit if and only if $\gcd(a, 12) = 1$ : if $\gcd(a,12) = 1$ then $ua + v\cdot 12 = 1$ for integers $u, v$ by Bézout, so $\bar u\bar a = \bar 1$ ; and if $d = \gcd(a,12) > 1$ then with $b = 12/d$ we have $0 < b < 12$ , so $\bar b \neq \bar 0$ , while $ab = (a/d)\cdot 12$ is a multiple of $12$ , so $\bar a\bar b = \bar 0$ and $\bar a$ is a zero divisor rather than a unit. Counting,

(\mathbb{Z}/12\mathbb{Z})^\times = \{\bar1, \bar5, \bar7, \bar{11}\}, \qquad \bigl|(\mathbb{Z}/12\mathbb{Z})^\times\bigr| = 4 ,

and the remaining seven nonzero classes $\bar2, \bar3, \bar4, \bar6, \bar8, \bar9, \bar{10}$ are all zero divisors, for instance $\bar3\cdot\bar4 = \bar{12} = \bar0$ . So $12\mathbb{Z}$ is neither a prime nor a maximal ideal of $\mathbb{Z}$ , in accordance with $12$ not being prime.

Part B: building the field of four elements. Take $F = \mathbb{F}_2 = \{0,1\}$ and $p(x) = x^2 + x + 1 \in \mathbb{F}_2[x]$ . It is irreducible over $\mathbb{F}_2$ : a factorisation of a quadratic into smaller degrees would give a root in $\mathbb{F}_2$ , and $p(0) = 1$ , $p(1) = 1 + 1 + 1 = 1$ (recall $1 + 1 = 0$ here), so there is none. By part 4 of the statement,

K = \mathbb{F}_2[x]/(x^2+x+1) = \{\, 0,\ 1,\ \alpha,\ 1+\alpha \,\}

is a field with $2^2 = 4$ elements, where $\alpha$ is the class of $x$ and satisfies $\alpha^2 = \alpha + 1$ (because $\alpha^2 + \alpha + 1 = 0$ and $-1 = 1$ in characteristic $2$ ).

Multiplication table. Using $\alpha^2 = \alpha+1$ and $1+1 = 0$ :

\alpha\cdot\alpha = \alpha+1, \qquad \alpha(1+\alpha) = \alpha + \alpha^2 = \alpha + \alpha + 1 = 1, \qquad (1+\alpha)^2 = 1 + \alpha^2 = 1 + \alpha + 1 = \alpha .

Together with the trivial products $1\cdot\alpha = \alpha$ and $1\cdot(1+\alpha) = 1+\alpha$ , these cover every product of two nonzero elements, and none of them is $0$ ; so $K$ has no zero divisors. The middle identity exhibits the inverses:

\alpha^{-1} = 1 + \alpha, \qquad (1+\alpha)^{-1} = \alpha .

The multiplicative group. $\alpha^1 = \alpha$ , $\alpha^2 = 1+\alpha$ , $\alpha^3 = \alpha\cdot\alpha^2 = \alpha(1+\alpha) = 1$ . So $K^\times$ is cyclic of order $3$ , generated by $\alpha$ , and $|K^\times| = 3 = 4 - 1$ , as it must be for a field with $4$ elements.

A check against part 3 of the statement. $K$ is finite, commutative, with $1 \neq 0$ and no zero divisors, so it is a field by "a finite integral domain is a field" — without computing a single inverse. The inverses above confirm the conclusion.

What goes wrong with a reducible modulus. Replace $p$ by $g(x) = x^2 + 1 = (x+1)^2$ in $\mathbb{F}_2[x]$ (expand: $x^2 + 2x + 1 = x^2 + 1$ since $2 = 0$ ). Then in $\mathbb{F}_2[x]/(g)$ the class $\beta$ of $x+1$ is nonzero but $\beta^2 = 0$ : a ring with $4$ elements that is not a field, confirming that irreducibility is the hypothesis doing the work.

ApplicationOriginal

The complex numbers are a quotient ring, and so is every "adjoin a root". Part 2 is the construction of $\mathbb{C}$ that physics uses implicitly whenever it writes $i^2 = -1$ and manipulates $a + bi$ by ordinary algebra: the legitimacy of those manipulations is exactly the statement that $\mathbb{R}[x]/(x^2+1)$ is a ring, and the existence of $1/z$ for $z \neq 0$ is the statement that the ideal $(x^2+1)$ is maximal. The same construction gives the splitting fields behind the Galois-theoretic proof that the general quintic has no solution in radicals, and, for a rational $D$ that is not a square, the quadratic field $\mathbb{Q}(\sqrt{D}) = \mathbb{Q}[x]/(x^2-D)$ .

Finite fields carry error correction. Reed-Solomon codes, used on compact discs, in QR codes, in DVB and ATSC broadcasting and on deep-space links, treat a block of data as the coefficients of a polynomial over $\mathbb{F}_{2^8}$ — the field with $256$ elements, built as $\mathbb{F}_2[x]/(p)$ for an irreducible $p$ of degree $8$ , so that one field element is one byte. The code word is the list of values of that polynomial at distinct field points, and the decoder recovers the data by polynomial interpolation. The whole scheme rests on part 4: in a field, a nonzero polynomial of degree $k$ has at most $k$ roots, so two distinct messages disagree in many places. Over $\mathbb{Z}/256\mathbb{Z}$ , which is not a field, this fails — $\bar{16}^2 = \bar 0$ there — and the construction collapses.

Modular arithmetic in computation. The number-theoretic transform replaces the complex roots of unity of the discrete Fourier transform (The discrete Fourier transform and the FFT) by roots of unity in $\mathbb{Z}/p\mathbb{Z}$ for a suitable prime $p$ , giving an exact convolution algorithm with no rounding error at all; it is how large-integer multiplication is done in computer-algebra systems. Linear congruential pseudo-random generators are iterations $x \mapsto ax + c$ in $\mathbb{Z}/m\mathbb{Z}$ , and their period is controlled by the unit group $(\mathbb{Z}/m\mathbb{Z})^\times$ computed in Part A of the example above. Public-key cryptography works in $(\mathbb{Z}/p\mathbb{Z})^\times$ and in groups built from fields.

Ideals organise operator algebras and PDE theory. The bounded operators on a Hilbert space form a non-commutative ring in which the compact operators are a two-sided ideal (Compact operators); the quotient, the Calkin algebra, is where the essential spectrum lives, and Fredholm theory is the statement that an operator is invertible in that quotient. In the theory of linear partial differential equations with constant coefficients, a system of equations corresponds to an ideal of the polynomial ring $\mathbb{C}[\xi_1,\dots,\xi_n]$ after Fourier transform, and the quotient ring records exactly the solvability and compatibility conditions of the system.

Definition

Quaternions

Adapted

Add to PDF

Defines the quaternion algebra with its conjugate and norm, shows it is a division algebra, and proves that conjugation by a unit quaternion is a rotation of three-space, giving the two-to-one map onto SO(3) and the identification of the unit quaternions with SU(2).

Prerequisites: Groups and subgroups, Homomorphisms and quotient groups, Linear maps and matrices, Unitary and orthogonal matrices, Vector algebra and index notation

Definition(The quaternion algebra)AdaptedAdapted from Hassani (2013), §3.1, Example 3.1.16, p. 69; Dummit & Foote (2004), §7.1, Example 5, pp. 224-225

The quaternions $\mathbb{H}$ are the four-dimensional real vector space with basis $1, i, j, k$ ,

q = a + bi + cj + dk, \qquad a,b,c,d \in \mathbb{R},

made into a ring by extending the following products bilinearly over $\mathbb{R}$ : $1$ is the identity, and

i^2 = j^2 = k^2 = -1, \qquad ij = -ji = k, \quad jk = -kj = i, \quad ki = -ik = j .

Multiplication is associative and, because $ij \neq ji$ , not commutative. Hassani gives the same algebra as $\mathbb{R}^4$ with structure constants $e_i e_j = \sum_k \varepsilon_{ijk} e_k$ for $i \ne j$ in $\{1,2,3\}$ , the Levi-Civita symbol encoding the three cyclic relations at once (Hassani (2013), Example 3.1.16, p. 69).

Write $q = a + \mathbf{v}$ , where $a = \operatorname{Re} q$ is the real part and $\mathbf{v} = (b,c,d)$ , identified with $bi + cj + dk$ , is the pure (or imaginary) part; $q$ is real if $\mathbf{v} = 0$ and pure if $a = 0$ . The pure quaternions form a copy of $\mathbb{R}^3$ inside $\mathbb{H}$ , which we write $\operatorname{Im}\mathbb{H}$ .

The conjugate and norm are

q^* = a - \mathbf{v}, \qquad |q| = \sqrt{q q^*} .

That $qq^*$ is a non-negative real number, so that the square root makes sense, is part 2 of the statement below.

In this notation the product takes the form given by (Hassani (2013), Eq. (3.6), p. 69): for $q = a + \mathbf{v}$ and $p = e + \mathbf{w}$ ,

qp = \bigl(ae - \mathbf{v}\cdot\mathbf{w}\bigr) + \bigl(a\mathbf{w} + e\mathbf{v} + \mathbf{v}\times\mathbf{w}\bigr) ,

the first bracket being the real part and the second the pure part. The quaternion product thus contains both products of vector algebra (Vector algebra and index notation) at once; indeed for two pure quaternions $\mathbf{v}, \mathbf{w}$ it reads $\mathbf{v}\mathbf{w} = -\mathbf{v}\cdot\mathbf{w} + \mathbf{v}\times\mathbf{w}$ .

Definition(Conjugate, norm, and the division property)AdaptedAdapted from Hassani (2013), pp. 69-70; Dummit & Foote (2004), §7.1, Example 5, p. 225; Lee (2013), Problem 7-22, p. 173

Let $p, q \in \mathbb{H}$ and write $q = a + bi + cj + dk$ .

$(pq)^* = q^*p^*$ , and $(q^*)^* = q$ . Conjugation is $\mathbb{R}$ -linear.
$qq^* = q^*q = a^2 + b^2 + c^2 + d^2$ , a non-negative real number, so $|q|$ is the Euclidean length of $(a,b,c,d)$ and $|q| = 0$ only for $q = 0$ .
$|pq| = |p|\,|q|$ .
Every $q \neq 0$ has the two-sided inverse

q^{-1} = \frac{q^*}{|q|^2} = \frac{a - bi - cj - dk}{a^2+b^2+c^2+d^2} .

Hence $\mathbb{H}$ is a non-commutative division ring, and as an $\mathbb{R}$ -algebra a division algebra (Dummit & Foote (2004), p. 224) (Hassani (2013), p. 70). 5. The unit quaternions $\mathrm{Sp}(1) = \{\, q \in \mathbb{H} : |q| = 1 \,\}$ form a group under multiplication, and as a set they are the unit sphere $S^3 \subset \mathbb{R}^4$ .

Idea of the proofOriginal

Everything follows from the single identity $qq^* = |q|^2$ , which is the statement that the cross terms cancel: in $(a + \mathbf{v})(a - \mathbf{v})$ the pure part is $-a\mathbf{v} + a\mathbf{v} + \mathbf{v}\times(-\mathbf{v}) = 0$ and the real part is $a^2 + \mathbf{v}\cdot\mathbf{v}$ . Once $qq^* = |q|^2$ is known, dividing by $|q|^2$ gives the inverse, and multiplicativity of the norm is the same identity applied to a product, using only that conjugation reverses order.

ProofAdaptedAdapted from Hassani (2013), pp. 69-70; Lee (2013), Problem 7-22, p. 173

Part 1. Conjugation is $\mathbb{R}$ -linear and fixes $1$ while negating $i, j, k$ , so $(q^*)^* = q$ is immediate. For the reversal, both sides of $(pq)^* = q^*p^*$ are $\mathbb{R}$ -bilinear in $(p, q)$ , so it is enough to check it on the basis $1, i, j, k$ . If either argument is $1$ it is trivial. For two distinct basis elements, say $p = i$ , $q = j$ : the left side is $(ij)^* = k^* = -k$ , and the right side is $j^*i^* = (-j)(-i) = ji = -k$ ; the other five ordered pairs are the same computation with the indices cycled or the roles exchanged. For $p = q = i$ : $(i^2)^* = (-1)^* = -1$ and $i^*i^* = (-i)(-i) = i^2 = -1$ ; likewise for $j$ and $k$ . This is Lee's Problem 7-22(b).

Part 2. Put $p = q^*$ in the product formula of the definition, so $e = a$ and $\mathbf{w} = -\mathbf{v}$ :

qq^* = \bigl(a\cdot a - \mathbf{v}\cdot(-\mathbf{v})\bigr) + \bigl(a(-\mathbf{v}) + a\mathbf{v} + \mathbf{v}\times(-\mathbf{v})\bigr) = a^2 + |\mathbf{v}|^2 ,

since $\mathbf{v}\times\mathbf{v} = 0$ and the two terms $\pm a\mathbf{v}$ cancel. Exchanging the roles of $q$ and $q^*$ changes the sign of both $a\mathbf{v}$ terms and of the cross product, which was already zero, so $q^*q$ is the same real number. Writing it out, $a^2 + |\mathbf{v}|^2 = a^2+b^2+c^2+d^2$ , which vanishes only when all four coordinates do.

Part 3. Using associativity, part 1 and part 2, and the fact that $|q|^2$ is a real number and therefore commutes with everything,

|pq|^2 = (pq)(pq)^* = p q q^* p^* = p\,|q|^2\,p^* = |q|^2\,pp^* = |q|^2|p|^2 .

Taking non-negative square roots gives $|pq| = |p||q|$ . This is the norm statement of Lee's Problem 7-22(c).

Part 4. For $q \neq 0$ , part 2 gives $|q|^2 > 0$ , so $q^*/|q|^2$ makes sense, and

q\cdot\frac{q^*}{|q|^2} = \frac{qq^*}{|q|^2} = 1, \qquad \frac{q^*}{|q|^2}\cdot q = \frac{q^*q}{|q|^2} = 1 ,

a two-sided inverse. Since $\mathbb{H}$ has the identity $1 \ne 0$ and every nonzero element is invertible, it is a division ring; it is not commutative because $ij = k \ne -k = ji$ . This is the inverse displayed by (Dummit & Foote (2004), p. 225).

Part 5. If $|p| = |q| = 1$ then $|pq| = 1$ by part 3 and $|q^{-1}| = |q^*|/|q|^2 = 1$ , because $|q^*| = |q|$ by part 2. The set is non-empty ( $1$ belongs to it), so it is a subgroup of the multiplicative group of nonzero quaternions (Groups and subgroups). By part 2 the condition $|q| = 1$ is $a^2+b^2+c^2+d^2 = 1$ , the unit sphere of $\mathbb{R}^4$ . $\square$

Definition(Unit quaternions as rotations)AdaptedAdapted from Lee (2013), Problem 21-21, p. 562

For $q \in \mathrm{Sp}(1)$ define $\rho(q) : \operatorname{Im}\mathbb{H} \to \mathbb{H}$ by

\rho(q)\,\mathbf{v} = q\,\mathbf{v}\,q^* .

Then:

$\rho(q)$ maps $\operatorname{Im}\mathbb{H} \cong \mathbb{R}^3$ into itself and preserves the Euclidean inner product there, so $\rho(q) \in \mathrm{O}(3)$ in the basis $i, j, k$ .
Write $q = \cos\tfrac{\theta}{2} + \sin\tfrac{\theta}{2}\,\hat{\mathbf{n}}$ with $\hat{\mathbf{n}}$ a unit pure quaternion and $\theta \in \mathbb{R}$ ; every unit quaternion has this form. Then $\rho(q)$ is the rotation by the angle $\theta$ about the axis $\hat{\mathbf{n}}$ , in the right-handed sense. In particular $\det\rho(q) = +1$ , so $\rho(q) \in \mathrm{SO}(3)$ , and

\operatorname{tr}\rho(q) = 1 + 2\cos\theta = 4(\operatorname{Re}q)^2 - 1 .

$\rho : \mathrm{Sp}(1) \to \mathrm{SO}(3)$ is a surjective group homomorphism with kernel $\{+1, -1\}$ . Thus $q$ and $-q$ give the same rotation and nothing else does, and $\mathrm{SO}(3) \cong \mathrm{Sp}(1)/\{\pm1\}$ .
$\mathrm{Sp}(1) \cong \mathrm{SU}(2)$ as groups, by

1 \mapsto I, \quad i \mapsto -i\sigma_1, \quad j \mapsto -i\sigma_2, \quad k \mapsto -i\sigma_3, \qquad a + bi + cj + dk \ \longmapsto\ \begin{pmatrix} a - id & -c - ib \\ c - ib & a + id\end{pmatrix},

where $\sigma_1, \sigma_2, \sigma_3$ are the Pauli matrices. Under this map $|q|^2$ becomes the determinant and $q^*$ the conjugate transpose.

Idea of the proofOriginal

Why $q\mathbf{v}q^*$ and not $q\mathbf{v}$ ? Left multiplication by a unit quaternion is a rotation of $\mathbb{R}^4$ , not of $\mathbb{R}^3$ : it moves the real axis. Sandwiching fixes that, because $q1q^* = 1$ pins the real axis down, and what is left is a length-preserving map of the orthogonal complement, which is $\operatorname{Im}\mathbb{H}$ . Then only one computation is needed: $q$ commutes with its own pure part, so $\rho(q)$ fixes the axis $\hat{\mathbf{n}}$ , and on the plane perpendicular to it the two half-angle factors $\cos\tfrac\theta2 \pm \sin\tfrac\theta2\hat{\mathbf{n}}$ act on the same side and add, producing the full angle $\theta$ . The half-angle is also why $q$ and $-q$ agree: changing $\theta$ by $2\pi$ changes $q$ by a sign but changes the rotation not at all.

ProofAdaptedAdapted from Lee (2013), Problem 21-21, p. 562

Throughout, $q$ is a unit quaternion, so $q^* = q^{-1}$ by part 4 of the previous statement.

Step 1: $\rho(q)$ preserves $\operatorname{Im}\mathbb{H}$ . A quaternion $x$ is pure exactly when $x^* = -x$ : writing $x = a + \mathbf{v}$ , the condition $a - \mathbf{v} = -a - \mathbf{v}$ says $a = -a$ , that is $a = 0$ . For pure $\mathbf{v}$ ,

(q\mathbf{v}q^*)^* = (q^*)^*\mathbf{v}^*q^* = q(-\mathbf{v})q^* = -\,q\mathbf{v}q^* ,

using the order-reversal of part 1 twice. So $q\mathbf{v}q^*$ is pure. It is $\mathbb{R}$ -linear in $\mathbf{v}$ because quaternion multiplication is $\mathbb{R}$ -bilinear.

Step 2: it preserves lengths, hence lies in $\mathrm{O}(3)$ . By multiplicativity of the norm and $|q^*| = |q| = 1$ ,

|q\mathbf{v}q^*| = |q|\,|\mathbf{v}|\,|q^*| = |\mathbf{v}| .

For a pure quaternion $|\mathbf{v}|$ is the Euclidean length of the vector $(b,c,d)$ , so $\rho(q)$ is a linear map of $\mathbb{R}^3$ preserving the norm; by the characterisation of orthogonal matrices (Unitary and orthogonal matrices, part 4) its matrix in the orthonormal basis $i,j,k$ is orthogonal. This is the inner-product statement of Lee's Problem 21-21(a).

Step 3: every unit quaternion has the stated form. Write $q = a + \mathbf{v}$ with $a^2 + |\mathbf{v}|^2 = 1$ . Then $a \in [-1,1]$ , so there is a unique $\theta \in [0, 2\pi]$ with $a = \cos\tfrac\theta2$ , and for that $\theta$ we have $\tfrac\theta2 \in [0,\pi]$ , hence $\sin\tfrac\theta2 \ge 0$ and $|\mathbf{v}| = \sqrt{1-a^2} = \sin\tfrac\theta2$ . Set $\hat{\mathbf{n}} = \mathbf{v}/|\mathbf{v}|$ when $\mathbf{v} \neq 0$ ; when $\mathbf{v} = 0$ the quaternion is $\pm1$ , $\theta$ is $0$ or $2\pi$ , and any unit $\hat{\mathbf{n}}$ will do. Note $\hat{\mathbf{n}}^2 = -\hat{\mathbf{n}}\cdot\hat{\mathbf{n}} + \hat{\mathbf{n}}\times\hat{\mathbf{n}} = -1$ by the product formula.

Step 4: the axis is fixed. Abbreviate $c = \cos\tfrac\theta2$ , $s = \sin\tfrac\theta2$ , so $q = c + s\hat{\mathbf{n}}$ and $q^* = c - s\hat{\mathbf{n}}$ . Since $\hat{\mathbf{n}}$ commutes with itself and with the real number $c$ , it commutes with $q$ , and therefore

\rho(q)\hat{\mathbf{n}} = q\hat{\mathbf{n}}q^* = \hat{\mathbf{n}}qq^* = \hat{\mathbf{n}} .

Step 5: the perpendicular plane turns by $\theta$ . Let $\mathbf{u}$ be a unit pure quaternion with $\mathbf{u}\cdot\hat{\mathbf{n}} = 0$ , and put $\mathbf{w} = \hat{\mathbf{n}}\times\mathbf{u}$ , so that $(\hat{\mathbf{n}}, \mathbf{u}, \mathbf{w})$ is a right-handed orthonormal frame. The product formula for two pure quaternions gives

\hat{\mathbf{n}}\mathbf{u} = -\hat{\mathbf{n}}\cdot\mathbf{u} + \hat{\mathbf{n}}\times\mathbf{u} = \mathbf{w}, \qquad \mathbf{u}\hat{\mathbf{n}} = \mathbf{u}\times\hat{\mathbf{n}} = -\mathbf{w} ,

so $\mathbf{u}$ anticommutes with $\hat{\mathbf{n}}$ . Hence $\mathbf{u}q^* = \mathbf{u}(c - s\hat{\mathbf{n}}) = (c + s\hat{\mathbf{n}})\mathbf{u} = q\mathbf{u}$ , and

\rho(q)\mathbf{u} = q\mathbf{u}q^* = q^2\mathbf{u} = (c + s\hat{\mathbf{n}})^2\,\mathbf{u} = \bigl(c^2 - s^2 + 2cs\,\hat{\mathbf{n}}\bigr)\mathbf{u} = \cos\theta\,\mathbf{u} + \sin\theta\,\hat{\mathbf{n}}\mathbf{u} = \cos\theta\,\mathbf{u} + \sin\theta\,\mathbf{w} ,

using $\hat{\mathbf{n}}^2 = -1$ and the double-angle formulas $c^2 - s^2 = \cos\theta$ , $2cs = \sin\theta$ . The same computation with $\mathbf{w}$ in place of $\mathbf{u}$ , noting $\hat{\mathbf{n}}\mathbf{w} = \hat{\mathbf{n}}\times(\hat{\mathbf{n}}\times\mathbf{u}) = -\mathbf{u}$ , gives $\rho(q)\mathbf{w} = -\sin\theta\,\mathbf{u} + \cos\theta\,\mathbf{w}$ . So in the frame $(\hat{\mathbf{n}}, \mathbf{u}, \mathbf{w})$ the matrix of $\rho(q)$ is $\operatorname{diag}(1, R(\theta))$ : the rotation by $\theta$ about $\hat{\mathbf{n}}$ . Its determinant is $+1$ and its trace is $1 + 2\cos\theta$ , which equals $1 + 2(2c^2 - 1) = 4c^2 - 1 = 4(\operatorname{Re}q)^2 - 1$ . This proves parts 1 and 2.

Step 6: homomorphism. For unit $p, q$ and pure $\mathbf{v}$ , using $(pq)^* = q^*p^*$ ,

\rho(pq)\mathbf{v} = (pq)\mathbf{v}(pq)^* = p\,(q\mathbf{v}q^*)\,p^* = \rho(p)\bigl(\rho(q)\mathbf{v}\bigr) ,

so $\rho(pq) = \rho(p)\rho(q)$ .

Step 7: surjectivity. Every element of $\mathrm{SO}(3)$ is a rotation about some axis through some angle: by the real canonical form of an orthogonal matrix (Unitary and orthogonal matrices, part 3) a $Q \in \mathrm{SO}(3)$ is orthogonally similar to $\operatorname{diag}(1, R(\theta))$ , the $+1$ eigenvector being the axis. Given that axis $\hat{\mathbf{n}}$ and angle $\theta$ , step 5 shows $q = \cos\tfrac\theta2 + \sin\tfrac\theta2\hat{\mathbf{n}}$ has $\rho(q) = Q$ .

Step 8: the kernel. Suppose $\rho(q) = I$ , i.e. $q\mathbf{v} = \mathbf{v}q$ for every pure $\mathbf{v}$ . With $q = a + \mathbf{t}$ the product formula gives $q\mathbf{v} - \mathbf{v}q = 2\,\mathbf{t}\times\mathbf{v}$ , which vanishes for all $\mathbf{v}$ only if $\mathbf{t} = 0$ : if $\mathbf{t} \ne 0$ , take $\mathbf{v}$ perpendicular to $\mathbf{t}$ and non-zero, and then $|\mathbf{t}\times\mathbf{v}| = |\mathbf{t}||\mathbf{v}| \ne 0$ . So $q = a$ is real, and $|q| = 1$ forces $a = \pm1$ . Conversely $\rho(\pm1) = I$ . Hence $\ker\rho = \{\pm1\}$ , and the first isomorphism theorem (Homomorphisms and quotient groups) gives $\mathrm{SO}(3) \cong \mathrm{Sp}(1)/\{\pm1\}$ . This is Lee's Problem 21-21(b),(c).

Step 9: part 4, the Pauli form. With the Pauli matrices

\sigma_1 = \begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad \sigma_2 = \begin{pmatrix}0&-i\\i&0\end{pmatrix}, \qquad \sigma_3 = \begin{pmatrix}1&0\\0&-1\end{pmatrix},

we have $\sigma_m^2 = I$ and $\sigma_1\sigma_2 = i\sigma_3$ with its cyclic images. Put $\hat\imath = -i\sigma_1$ , $\hat\jmath = -i\sigma_2$ , $\hat k = -i\sigma_3$ . Then

\hat\imath^{\,2} = (-i)^2\sigma_1^2 = -I, \qquad \hat\imath\hat\jmath = (-i)^2\sigma_1\sigma_2 = -\,i\sigma_3 = \hat k ,

and cyclically, so these three matrices satisfy the defining relations of $i, j, k$ . Since $I, \hat\imath, \hat\jmath, \hat k$ are linearly independent over $\mathbb{R}$ , the $\mathbb{R}$ -linear extension is an injective algebra homomorphism, and multiplying out gives the displayed $2\times2$ matrix $A(q)$ . A direct computation gives $\det A(q) = (a-id)(a+id) - (-c-ib)(c-ib) = a^2 + d^2 + c^2 + b^2 = |q|^2$ and $A(q)^\dagger A(q) = |q|^2 I$ . Hence $|q| = 1$ if and only if $A(q)$ is unitary with determinant $1$ , that is $A(q) \in \mathrm{SU}(2)$ . Conversely every element of $\mathrm{SU}(2)$ has the form

\begin{pmatrix}\alpha & \beta \\ -\bar\beta & \bar\alpha\end{pmatrix} \qquad\text{with}\qquad |\alpha|^2+|\beta|^2 = 1 ,

and setting $\alpha = a - id$ , $\beta = -c - ib$ recovers a unit quaternion. So $A$ restricts to a group isomorphism $\mathrm{Sp}(1) \to \mathrm{SU}(2)$ , which is Lee's Problem 7-23. $\square$

Remark(Where the hypotheses are used, and the conventions)Original

$|q| = 1$ is used only for tidiness. Steps 1 and 6 need nothing. Step 2 needs $|q||q^*| = 1$ ; for a general $q \neq 0$ the map $\mathbf{v}\mapsto q\mathbf{v}q^*$ scales lengths by $|q|^2$ , so it is a rotation composed with a dilation. Replacing $q^*$ by $q^{-1} = q^*/|q|^2$ removes the dilation, and $\mathbf{v}\mapsto q\mathbf{v}q^{-1}$ is a rotation for every nonzero $q$ , depending only on $q$ up to a real scalar. Normalising to $|q|=1$ cuts that freedom down to the sign, which is what makes the kernel exactly $\{\pm1\}$ .

$\mathbf{v}$ must be pure. $\rho(q)$ is defined on $\operatorname{Im}\mathbb{H}$ . The same formula applied to all of $\mathbb{H}$ fixes the real axis pointwise, since $q1q^* = qq^* = 1$ , so in the frame $(1, \hat{\mathbf{n}}, \mathbf{u}, \mathbf{w})$ of step 5 it is $\operatorname{diag}(1, 1, R(\theta))$ — the rotation of $\mathbb{R}^3$ padded with a $1$ , not a rotation of $\mathbb{R}^4$ by $\theta$ .

The half-angle is not a convention, it is forced. The two factors $q$ and $q^*$ each contribute $\theta/2$ on the perpendicular plane, as step 5 shows. A consequence is the two-to-one covering: a continuous path of rotations that returns to the identity after a $2\pi$ turn lifts to a path of quaternions ending at $-1$ , and only after $4\pi$ does the quaternion return to $+1$ . This is the quaternionic form of the spinor sign change; the Lie-theoretic version, with $\mathrm{SU}(2)$ as the universal cover of $\mathrm{SO}(3)$ , is The rotation group and SU(2).

Two sign conventions for the Pauli identification. We use $i \mapsto -i\sigma_1$ , $j\mapsto -i\sigma_2$ , $k \mapsto -i\sigma_3$ . (Arfken, Weber & Harris (2013), Exercise 2.2.9, p. 116) records instead that $1, i\sigma_1, i\sigma_2, -i\sigma_3$ form a basis for the quaternions, which amounts to $i\mapsto i\sigma_1$ , $j\mapsto i\sigma_2$ , $k\mapsto -i\sigma_3$ . Both satisfy the relations — check $(i\sigma_1)(i\sigma_2) = -\sigma_1\sigma_2 = -i\sigma_3$ — and the two differ by the automorphism of $\mathbb{H}$ that negates $i$ and $j$ and fixes $k$ . Neither is more correct; we state ours and use it consistently, and a reader comparing with Arfken, Weber and Harris should expect signs on $i$ and $j$ to differ.

Lee's statements are in his problem sets. Parts 3 and 5 of "Conjugate, norm and the division property" and parts 3 and 4 of "Unit quaternions as rotations" follow (Lee (2013), Problems 7-22, 7-23, p. 173, and 21-21, p. 562), where they are posed as exercises with the route indicated rather than proved in the text. The proofs above are written out here.

$\mathbb{H}$ is not an algebra over $\mathbb{C}$ . It is four-dimensional over $\mathbb{R}$ , and the copy of $\mathbb{C}$ it contains (say $\mathbb{R} + \mathbb{R}i$ ) is not central: $j i = -ij$ . So one cannot "factor out $i$ " and treat $\mathbb{H}$ as two-dimensional over $\mathbb{C}$ in the algebra sense, although the matrix form of part 4 writes a quaternion using two complex numbers.

Method(Computing with quaternions)Original

To rotate, compose and convert:

Axis and angle to quaternion. For a right-handed rotation by $\theta$ about the unit vector $\hat{\mathbf{n}} = (n_1,n_2,n_3)$ , set

q = \cos\tfrac{\theta}{2} + \sin\tfrac{\theta}{2}\,(n_1 i + n_2 j + n_3 k) .

Apply it. Write the vector $\mathbf{x}$ as the pure quaternion $x_1i + x_2j + x_3k$ and compute $q\mathbf{x}q^*$ , reading the rotated vector off the pure part. Writing $q = c + \mathbf{u}$ with $c = \cos\tfrac\theta2$ and $\mathbf{u} = \sin\tfrac\theta2\,\hat{\mathbf{n}}$ , applying the product formula twice gives the expanded form

\rho(q)\mathbf{x} = \mathbf{x} + 2c\,(\mathbf{u}\times\mathbf{x}) + 2\,\mathbf{u}\times(\mathbf{u}\times\mathbf{x}) ,

which costs far fewer operations than building a matrix for a single vector. 3. Compose. "First $q_1$ , then $q_2$ " is the single quaternion $q_2q_1$ — the same order as matrices, because $\rho$ is a homomorphism. Multiplying two quaternions costs $16$ real multiplications against $27$ for two $3\times3$ matrices. 4. Quaternion to matrix. For $q = a + bi + cj + dk$ with $|q| = 1$ ,

\rho(q) = \begin{pmatrix} a^2+b^2-c^2-d^2 & 2(bc - ad) & 2(bd + ac) \\ 2(bc + ad) & a^2-b^2+c^2-d^2 & 2(cd - ab) \\ 2(bd - ac) & 2(cd + ab) & a^2-b^2-c^2+d^2 \end{pmatrix}.

Matrix to axis and angle. From $\operatorname{tr}\rho(q) = 1 + 2\cos\theta$ get $\theta$ , then solve $(\rho(q) - I)\hat{\mathbf{n}} = 0$ for the axis and fix its sign so that the rotation is right-handed. Then use step 1.
Renormalise. After many compositions, numerical drift makes $|q|$ differ from $1$ ; divide by $|q|$ . This is one division of four numbers, against the Gram-Schmidt re-orthogonalisation (Orthonormal bases and Gram-Schmidt) a drifting rotation matrix would need.

Example(A 120-degree rotation, and composing two quarter turns)Original

Part A: $q = \tfrac12(1 + i + j + k)$ . Its norm is

|q|^2 = \tfrac14(1 + 1 + 1 + 1) = 1 ,

so $q$ is a unit quaternion. Its real part is $\cos\tfrac\theta2 = \tfrac12$ , giving $\theta/2 = 60^\circ$ and $\theta = 120^\circ$ ; its pure part has length $\sqrt{3}/2 = \sin 60^\circ$ , so the axis is

\hat{\mathbf{n}} = \frac{(i+j+k)/2}{\sqrt3/2} = \frac{i+j+k}{\sqrt3} ,

the body diagonal of the cube. Check the action on the basis vectors. Using $q^* = \tfrac12(1 - i - j - k)$ and the relations,

qi = \tfrac12(i + i^2 + ji + ki) = \tfrac12(-1 + i + j - k) ,

using $i^2 = -1$ , $ji = -k$ and $ki = j$ . Multiplying on the right by $q^*$ ,

qiq^* = \tfrac14(-1 + i + j - k)(1 - i - j - k) .

Expanding the sixteen terms and sorting them by basis element:

	$1$	$-i$	$-j$	$-k$
$-1$	$-1$	$+i$	$+j$	$+k$
$+i$	$+i$	$+1$	$-k$	$+j$
$+j$	$+j$	$+k$	$+1$	$-i$
$-k$	$-k$	$+j$	$-i$	$-1$

The real entries are $-1+1+1-1 = 0$ ; the $i$ entries are $+i+i-i-i = 0$ ; the $k$ entries are $+k-k+k-k = 0$ ; and the $j$ entries are $j+j+j+j = 4j$ . Hence $qiq^* = \tfrac14\cdot 4j = j$ . The same computation cyclically gives

\rho(q): \quad i \mapsto j, \qquad j \mapsto k, \qquad k \mapsto i ,

so in the basis $(i,j,k)$

\rho(q) = \begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix} ,

the cyclic permutation of the coordinate axes — which is indeed the rotation by $120^\circ$ about $(1,1,1)/\sqrt3$ . Two checks: $\det\rho(q) = +1$ , and

\operatorname{tr}\rho(q) = 0 = 1 + 2\cos 120^\circ = 1 + 2(-\tfrac12) ,

in agreement with the trace formula, which also reads $4(\operatorname{Re}q)^2 - 1 = 4\cdot\tfrac14 - 1 = 0$ . Finally $q^3 = -1$ : the rotation has order $3$ , the quaternion order $6$ , exactly the doubling the kernel $\{\pm1\}$ predicts.

Part B: a quarter turn about $z$ , then a quarter turn about $x$ . Let

q_1 = \cos45^\circ + \sin45^\circ\,k = \tfrac{\sqrt2}{2}(1 + k), \qquad q_2 = \cos45^\circ + \sin45^\circ\,i = \tfrac{\sqrt2}{2}(1 + i) .

"First $q_1$ , then $q_2$ " is

q_2q_1 = \tfrac12(1+i)(1+k) = \tfrac12\bigl(1 + k + i + ik\bigr) = \tfrac12(1 + i - j + k) ,

using $ik = -j$ . Its norm is $\tfrac12\sqrt{1+1+1+1} = 1$ , as it must be. Its real part is $\tfrac12$ , so again $\theta = 120^\circ$ , now about

\hat{\mathbf{n}} = \frac{(i - j + k)/2}{\sqrt3/2} = \frac{(1,-1,1)}{\sqrt3} .

Verify against the matrices: the quarter turn about $z$ sends $(x,y,z)\mapsto(-y,x,z)$ and the quarter turn about $x$ sends $(x,y,z)\mapsto(x,-z,y)$ , so the composite sends

(x,y,z) \ \longmapsto\ (-y, x, z) \ \longmapsto\ (-y, -z, x), \qquad M = \begin{pmatrix} 0&-1&0\\0&0&-1\\1&0&0\end{pmatrix}.

Its trace is $0 = 1 + 2\cos120^\circ$ , confirming the angle, and solving $(M - I)\mathbf{n} = 0$ gives $\mathbf{n} \propto (1,-1,1)$ , confirming the axis. Two quarter turns about perpendicular axes therefore make a third of a turn about a body diagonal. The matrix route confirms this; the quaternion route also explains it, since the axis and the angle are read straight off the four components of $q_2q_1$ .

ApplicationOriginal

Attitude control and computer graphics. Spacecraft, aircraft, drones, inertial measurement units, robot arms and animation systems all store orientation as a unit quaternion rather than as three Euler angles or a $3\times3$ matrix. Three reasons, all visible above. First, no gimbal lock: Euler angles parametrise $\mathrm{SO}(3)$ with coordinate singularities at which two axes align and a degree of freedom is lost, whereas the quaternion parametrisation by $S^3$ is smooth and singular nowhere. Second, cheap composition and cheap correction: step 3 of the method composes orientations in $16$ multiplications, and step 6 removes accumulated drift by renormalising four numbers, where a matrix needs re-orthogonalisation. Third, interpolation: a smooth motion between two orientations is the great-circle arc on $S^3$ joining the corresponding unit quaternions, which is the spherical linear interpolation ("slerp") of animation software and of attitude planners; the corresponding interpolation of matrices leaves $\mathrm{SO}(3)$ altogether. The two-to-one map means software must choose the lift with $\operatorname{Re}(q_2 q_1^*) \ge 0$ to interpolate along the short arc.

Spin one-half. Part 4 identifies the unit quaternions with $\mathrm{SU}(2)$ , the group that acts on the two-component spinor of a spin- $\tfrac12$ particle, and part 3 says that this group covers the rotations twice. The physical content is that rotating a spin- $\tfrac12$ state by $2\pi$ multiplies it by $-1$ and only a $4\pi$ rotation restores it — an effect confirmed in neutron interferometry, where rotating the neutron spin by $2\pi$ in one arm of the interferometer reverses the interference fringes. The quaternionic statement is simply that $q = \cos\tfrac\theta2 + \sin\tfrac\theta2\hat{\mathbf{n}}$ equals $-1$ at $\theta = 2\pi$ . The Lie-group account is The rotation group and SU(2), and the generalisation to arbitrary quadratic forms, of which $\mathbb{H}$ is the Clifford algebra of the negative-definite form on $\mathbb{R}^2$ , is Clifford algebras and spinors.

Rigid-body kinematics. Differentiating $q(t)$ along a motion with angular velocity $\boldsymbol\omega$ (as a pure quaternion, in body coordinates) gives the kinematic equation $\dot q = \tfrac12 q\,\boldsymbol\omega$ , a linear ordinary differential equation in four unknowns with no trigonometric functions in it. Numerical integrators for spacecraft and for molecular dynamics of rigid molecules use this in place of the Euler-angle equations, whose right-hand sides blow up near the gimbal-lock configurations.