University Mathematics — Year 1 · Bachelor Year 1

7Algebraic Structures

The same computation rules keep reappearing: integers, real numbers, complex numbers, congruence classes, and soon polynomials (Chapter 8), vectors and matrices (Chapters 18 and 21). Algebra extracts the common patterns and names them: group, ring, field. Proving a fact once, at the level of the structure, proves it for every example at once.

7.1 Laws of composition

Definition 7.1

A law of composition on a set $E$ is a map $E \times E \to E$ , written $(x, y) \mapsto x * y$ . It is associative when $(x*y)*z = x*(y*z)$ always, commutative when $x * y = y * x$ always. An element $e$ is an identity when $e * x = x * e = x$ for all $x$ ; then $x'$ is an inverse of $x$ when $x * x' = x' * x = e$ .

Proposition 7.2 (Uniqueness)

A law has at most one identity; for an associative law with identity, each element has at most one inverse.

Proof. If $e$ and $e'$ are identities: $e = e * e' = e'$ . If $x'$ and $x''$ invert $x$ : $x' = x' * e = x' * (x * x'') = (x' * x) * x'' = e * x'' = x''$ . ∎

7.2 Groups

Definition 7.3 (Group)

A group $(G, *)$ is a set with an associative law admitting an identity and in which every element has an inverse. The group is abelian when the law is commutative.

Example 7.4

$(\Z, +)$ , $(\Q, +)$ , $(\R, +)$ , $(\C, +)$ ; $(\Q^*, \times)$ , $(\R^*, \times)$ , $(\C^*, \times)$ , $(\mathbb{U}_n, \times)$ (roots of unity, Definition 3.17); the set $\mathfrak{S}(E)$ of bijections of a set $E$ onto itself, under composition — the symmetric group of $E$ , non-abelian as soon as $\abs E \geq 3$ . Not groups: $(\N, +)$ (no inverses), $(\Z, \times)$ (only $\pm 1$ invertible).

Proposition 7.5 (Computation rules)

In a group $G$ (written multiplicatively, identity $e$ ):

cancellation: $ax = ay \implies x = y$ and $xa = ya \implies x = y$ ;
$(ab)^{-1} = b^{-1} a^{-1}$ and $(a^{-1})^{-1} = a$ ;
for $a, b \in G$ , each equation $ax = b$ and $xa = b$ has a unique solution ( $x = a^{-1}b$ , resp. $x = b a^{-1}$ ).

Proof. (1) Multiply by $a^{-1}$ on the appropriate side, using associativity. (2) $(b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}b = e$ and symmetrically; uniqueness of the inverse concludes; the second point is Proposition 7.2 applied to $a^{-1}$ . (3) Substitute and use (1) for uniqueness. ∎

Example 7.6 (The symmetries of a rectangle)

A (non-square) rectangle admits exactly four isometries onto itself: the identity $e$ , the horizontal-axis reflection $h$ , the vertical-axis reflection $v$ , and the half-turn $r$ about the center. Composition makes this four-element set a group: each element is its own inverse ( $h^2 = v^2 = r^2 = e$ ), and the product of any two distinct non-identity elements is the third ( $hv = vh = r$ : reflecting in both axes is the half-turn). The full table is symmetric, so the group is abelian — yet it is not the same group as the rotations $\mathbb U_4$ of Example 7.15: there, $\iu$ has order $4$ , while here every element has order $\leq 2$ . Two groups of the same size can thus have genuinely different multiplication structures — the figure below displays both tables side by side. This four-element group returns as $\{\pm1\} \times \{\pm1\}$ , and Exercise 7.7 explains why any group with all squares trivial must, like this one, be abelian.

Two groups with four elements: U_4 = \e, , -1, - \ (left) and the rectangle group (right), with the identity’s positions shaded. On the left the identity meanders (one element of order 4 generates everything); on the right it fills the diagonal (every element squares to e). No relabeling can turn one table into the other: the groups are not isomorphic. — Two groups with four elements: $\mathbb U_4 = \{e, \iu, -1, -\iu\}$ (left) and the rectangle group (right), with the identity’s positions shaded. On the left the identity meanders (one element of order $4$ generates everything); on the right it fills the diagonal (every element squares to $e$ ). No relabeling can turn one table into the other: the groups are not isomorphic.

Definition 7.7 (Subgroup)

A subset $H$ of a group $G$ is a subgroup (written $H \leq G$ ) when it contains $e$ , is stable under the law and under inversion. Then $H$ is itself a group.

Criterion: a nonempty $H \subseteq G$ is a subgroup if and only if

\forall x, y \in H, \quad x y^{-1} \in H .

Proof of the criterion. A subgroup obviously satisfies it. Conversely, let $H \neq \emptyset$ satisfy it, and pick $x_0 \in H$ . Then $e = x_0 x_0^{-1} \in H$ ; for $y \in H$ , $y^{-1} = e\,y^{-1} \in H$ ; and for $x, y \in H$ , $xy = x (y^{-1})^{-1} \in H$ . ∎

Example 7.8

$\mathbb{U}_n \leq (\C^*, \times)$ : nonempty, and for $z, w \in \mathbb{U}_n$ , $(zw^{-1})^n = z^n (w^n)^{-1} = 1$ . The subgroups of $(\Z, +)$ are exactly the $n\Z$ (proved in Theorem 6.4). An intersection of subgroups is always a subgroup, but a union almost never is (Exercise 7.6).

Remark 7.9 (Common pitfalls with structures)

Stability under the law is not enough. $\N$ is stable under addition inside $\Z$ , contains $0$ , yet is no subgroup: inverses are missing. The criterion $xy^{-1} \in H$ tests everything at once — but only after checking $H \neq \emptyset$ .
Nonabelian reflexes. In a general group, $(ab)^2 = abab$ , which is $a^2b^2$ only when $a$ and $b$ commute; likewise $(ab)^{-1} = b^{-1}a^{-1}$ , order reversed. Every identity imported from school algebra must be re-derived from the axioms or flagged as commutative.
Kernel versus image. $\ker f$ lives in the source, $\operatorname{im} f$ in the target; “ $f$ injective iff $\ker f$ trivial” (Proposition 7.11) has no analogue with the image ( $\operatorname{im} f = G'$ is surjectivity).
Rings are not groups for $\times$ . In a ring, most elements need not be invertible, and cancellation by $a$ requires $a$ to be a unit or the ring to be an integral domain: in $\Z/12\Z$ , $\overline3\,\overline2 = \overline3\,\overline6$ yet $\overline2 \neq \overline6$ (Example 7.27).

Definition 7.10 (Group morphism)

Let $(G, *)$ and $(G', \star)$ be groups. A map $f \colon G \to G'$ is a morphism when

\forall x, y \in G, \qquad f(x * y) = f(x) \star f(y).

Then $f(e_G) = e_{G'}$ and $f(x^{-1}) = f(x)^{-1}$ . The kernel and image of $f$ are

\ker f = f^{-1}(\{e_{G'}\}) \leq G, \qquad \operatorname{im} f = f(G) \leq G' .

A bijective morphism is an isomorphism; its inverse map is then automatically a morphism.

Proof of the assertions. $f(e) = f(e * e) = f(e)\star f(e)$ , and cancelling $f(e)$ gives $e_{G'} = f(e)$ . Then $f(x)\star f(x^{-1}) = f(x x^{-1}) = e_{G'}$ identifies $f(x^{-1})$ as the inverse. Kernel: $e \in \ker f$ ; if $x, y \in \ker f$ , $f(xy^{-1}) = f(x)f(y)^{-1} = e$ ; the criterion applies. Image: same criterion with $f(x)f(y)^{-1} = f(xy^{-1})$ . Inverse of an isomorphism: for $u, v \in G'$ , write $u = f(x)$ , $v = f(y)$ ; then $f^{-1}(u \star v) = f^{-1}(f(xy)) = xy = f^{-1}(u) f^{-1}(v)$ . ∎

Proposition 7.11 (Injectivity via the kernel)

A group morphism $f$ is injective if and only if $\ker f = \{e\}$ .

Proof. If $f$ is injective, $\ker f$ can only contain the one preimage of $e_{G'}$ , which is $e$ . Conversely, if $\ker f = \{e\}$ and $f(x) = f(y)$ , then $f(xy^{-1}) = f(x) f(y)^{-1} = e_{G'}$ , so $xy^{-1} = e$ , i.e. $x = y$ . ∎

Example 7.12

$\exp \colon (\R, +) \to (\R_+^*, \times)$ is a morphism ( $\eu^{x+y} = \eu^x \eu^y$ ), bijective (Proposition 4.1): the additive and multiplicative structures are isomorphic — the historical raison d’être of logarithms. Another morphism: $\theta \mapsto \eu^{\iu\theta}$ from $(\R, +)$ onto the unit circle $(\mathbb{U}, \times)$ , with kernel $2\pi\Z$ .

Example 7.13 (The sign morphism)

The map $s \colon (\R^*, \times) \to (\{\pm1\}, \times)$ sending $x$ to its sign is a morphism: the sign of a product is the product of the signs. Its kernel is $\intoo0{+\infty}$ (a subgroup, as Definition 7.10 promises), its image all of $\{\pm1\}$ : surjective, massively non-injective. Two general lessons in miniature. First, a morphism may crush information: $s$ remembers nothing of $x$ but one bit, and that is its virtue — sign arguments are exactly the computations that factor through $s$ . Second, morphisms to $\{\pm1\}$ are the simplest “invariants”: the signature of permutations, built in this chapter’s weekend problem, is the same phenomenon on the group $\mathfrak S_n$ , and the parity arguments it powers all descend through such a two-valued morphism.

Definition 7.14 (Powers, order of an element)

In a group $G$ (multiplicative notation), set $x^0 = e$ , $x^{k+1} = x^k x$ and $x^{-k} = (x^k)^{-1}$ for $k \in \N$ ; then $x^{k+l} = x^k x^l$ for all $k, l \in \Z$ , so $k \mapsto x^k$ is a morphism $(\Z, +) \to G$ whose image $\langle x \rangle = \{x^k : k \in \Z\}$ is a subgroup, the subgroup generated by $x$ . The order of $x$ is the least $m \geq 1$ with $x^m = e$ if one exists (then $\langle x\rangle = \{e, x, \dots, x^{m-1}\}$ has exactly $m$ elements, and $x^k = e \iff m \mid k$ ), and $\infty$ otherwise.

Example 7.15

In $(\C^*, \times)$ : $\iu$ has order $4$ , with $\langle \iu \rangle = \{1, \iu, -1, -\iu\} = \mathbb{U}_4$ ; more generally $\omega = \eu^{2\iu\pi/n}$ has order $n$ and $\langle\omega\rangle = \mathbb{U}_n$ . In $(\Z, +)$ , every $x \neq 0$ has infinite order. Why the claims in the definition hold: if $x$ has order $m$ , divide any $k$ by $m$ ( $k = mq + r$ , $0 \leq r < m$ , Theorem 6.2): $x^k = (x^m)^q x^r = x^r$ , so the powers cycle with period $m$ , the listed elements are pairwise distinct by minimality of $m$ , and $x^k = e$ forces $r = 0$ . Orders of permutations are computed in the weekend problem below.

Example 7.16 (Orders inside $\mathbb U_{12}$ )

What is the order of $\omega^k$ in $\mathbb U_n$ , for $\omega = \eu^{2\iu\pi/n}$ ? One has $(\omega^k)^m = 1$ iff $n \mid km$ , and writing $d = \gcd(n, k)$ , $n = dn'$ , $k = dk'$ with $\gcd(n', k') = 1$ : $n \mid km \iff n' \mid k'm \iff n' \mid m$ (Gauss’s lemma, Theorem 6.8). The least such $m \geq 1$ is $n' = \frac{n}{\gcd(n,k)}$ . In $\mathbb U_{12}$ for instance, $\omega^8$ has order $\frac{12}{\gcd(12,8)} = 3$ (indeed $\omega^8 = \eu^{4\iu\pi/3} \in \mathbb U_3$ ), while $\omega^5$ has order $12$ : it generates the whole group, though it is not the “standard” generator. Counting the generators — the $k$ with $\gcd(k, n) = 1$ — recovers the coprime counts of Example 2.25: group theory and counting meet.

7.3 Rings and fields

Definition 7.17 (Ring)

A ring $(A, +, \times)$ is a set with two laws such that: $(A, +)$ is an abelian group (identity $0$ ); $\times$ is associative with an identity $1$ ; and $\times$ distributes over $+$ on both sides. The ring is commutative when $\times$ is. An element $a$ is invertible (a unit) when $ab = ba = 1$ for some $b$ ; the units form a group $(A^\times, \times)$ .

Proof that the units form a group. Stability: if $a, a'$ are units with inverses $b, b'$ , then

(aa')(b'b) = a(a'b')b = a\,1\,b = ab = 1, \qquad (b'b)(aa') = 1

symmetrically, so $aa'$ is a unit. The element $1$ is a unit (its own inverse), associativity is inherited from $A$ , and the inverse $b$ of a unit $a$ is itself a unit (with inverse $a$ ). So $(A^\times, \times)$ satisfies all group axioms. Every group in this book that is not built from permutations arises this way: $\Q^* = \Q^\times$ , $\R^*$ , $\C^*$ , the units of $\Z/n\Z$ below, and later the invertible matrices (Chapter 21). ∎

Example 7.18

$\Z, \Q, \R, \C$ are commutative rings; $\Z^\times = \{1, -1\}$ , $\Q^\times = \Q^*$ . Later: polynomial rings $K[X]$ (Chapter 8), matrix rings (non-commutative, Chapter 21), and $\Z/n\Z$ below. In every ring, $0 \times a = 0$ (from distributivity: $0a = (0+0)a = 0a + 0a$ ), and $(-1)a = -a$ .

Example 7.19 (Idempotents: new phenomena in new rings)

In $\Z$ , the equation $x^2 = x$ , i.e. $x(x - 1) = 0$ , has only the solutions $0$ and $1$ . In $\Z/6\Z$ , testing all classes: $\overline0^2 = \overline0$ , $\overline1^2 = \overline1$ , $\overline3^2 = \overline9 = \overline3$ and $\overline4^2 = \overline{16} = \overline4$ — four idempotents. The two exotic ones come from zero divisors: $\overline3\,(\overline3 - \overline1) = \overline3 \times \overline2 = \overline6 = \overline0$ with neither factor zero. Such computations calibrate one’s instincts: familiar facts about equations survive in integral domains and fields, but a general ring can and does behave differently — see also the Boolean rings of Exercise 7.10, where every element is idempotent.

Proposition 7.20 (Binomial theorem in a commutative ring)

If $a, b$ are elements of a commutative ring (more generally, if $ab = ba$ ), then for $n \in \N$ :

(a+b)^n = \sum_{k=0}^n \binom nk a^k b^{n-k}, \qquad a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{\,n-1-k} .

Proof. The proofs of Theorem 2.16 and of the geometric identity use only associativity, commutativity of the two elements, and distributivity — they apply verbatim. ∎

Example 7.21 (The binomial theorem in an unfamiliar ring)

Two quick payoffs of the generality. In $\Z/p\Z$ ( $p$ prime), the middle binomial coefficients vanish (Theorem 6.23’s first step), so the theorem collapses to the freshman’s dream

(a + b)^p = a^p + b^p \qquad \text{in } \Z/p\Z ,

a genuine identity there, however criminal it looks over $\R$ . And in any commutative ring containing an element $\varepsilon$ with $\varepsilon^2 = 0$ , the theorem truncates: $(a + \varepsilon)^n = a^n + n\,a^{n-1}\varepsilon$ , all higher terms carrying a factor $\varepsilon^2 = 0$ . The coefficient $n\,a^{n-1}$ of $\varepsilon$ is the derivative of $x^n$ — no accident, and a first hint that derivatives are algebra as much as analysis (compare the formal derivative of Chapter 8).

Definition 7.22 (Integral domain, field)

A commutative ring $A \neq \{0\}$ is an integral domain when it has no zero divisors: $ab = 0 \implies a = 0$ or $b = 0$ . It is a field when every nonzero element is invertible. Every field is an integral domain ( $ab = 0$ and $a \neq 0$ give $b = a^{-1}ab = 0$ ).

Example 7.23

$\Q$ , $\R$ , $\C$ are fields; $\Z$ is an integral domain but not a field. In an integral domain, cancellation holds for $\times$ : $ab = ac$ and $a \neq 0$ imply $b = c$ .

7.4 The ring $\Z/n\Z$

Definition 7.24

Fix $n \in \N^*$ . The congruence classes mod $n$ (Example 1.32) form a set $\Z/n\Z$ of $n$ elements, written $\overline 0, \overline 1, \dots, \overline{n-1}$ . The operations

\overline a + \overline b = \overline{a + b}, \qquad \overline a \times \overline b = \overline{ab}

are well defined — the classes of the results do not depend on the representatives, precisely because congruence is compatible with $+$ and $\times$ (Definition 6.18) — and make $\Z/n\Z$ a commutative ring.

Theorem 7.25 (Units of $\Z/n\Z$ ; the fields $\Z/p\Z$ )

$\overline a$ is invertible in $\Z/n\Z$ if and only if $\gcd(a, n) = 1$ .
$\Z/n\Z$ is a field if and only if $n$ is prime.

Proof. (1) is Proposition 6.20 rewritten with classes.

(2) If $n = p$ is prime, every $\overline a \neq \overline 0$ has $p \nmid a$ , so $\gcd(a, p) = 1$ : invertible by (1) — a field. If $n = ab$ with $1 < a, b < n$ , then $\overline a\, \overline b = \overline n = \overline 0$ with $\overline a, \overline b \neq \overline 0$ : zero divisors, so not even an integral domain; and $n = 1$ gives the zero ring, excluded. ∎

Example 7.26 (How many square roots of $1$ ?)

Solve $x^2 = \overline 1$ in $\Z/8\Z$ and in $\Z/7\Z$ . Testing the eight classes mod $8$ : $1^2 = 1$ , $3^2 = 9 \equiv 1$ , $5^2 = 25 \equiv 1$ , $7^2 = 49 \equiv 1$ — four solutions $\{\overline1, \overline3, \overline5, \overline7\}$ , even though the polynomial $X^2 - 1$ has degree $2$ . In the field $\Z/7\Z$ , by contrast, $x^2 = \overline1$ means $(x - \overline1)(x + \overline1) = \overline0$ , and a field has no zero divisors: $x = \pm\overline1$ , two solutions only. The failure mod $8$ is traceable: $(3-1)(3+1) = 2 \times 4 = 8 \equiv 0$ without either factor vanishing. Moral: the familiar rule “a degree- $d$ equation has at most $d$ roots” is a theorem about integral domains (Corollary 8.8 proves it over fields); in rings with zero divisors it silently fails — which is exactly why the pairing proof of Wilson’s theorem (Exercise 6.11) needed $p$ prime.

Example 7.27 (Computing in $\Z/n\Z$ )

In $\Z/12\Z$ : the units are $\overline 1, \overline 5, \overline 7, \overline{11}$ (the classes coprime to $12$ ), and each is its own inverse ( $5^2 = 25 \equiv 1$ , $7^2 = 49 \equiv 1$ , $11^2 = 121 \equiv 1$ ). The equation $\overline 3\, x = \overline 6$ has three solutions ( $x \in \{\overline 2, \overline 6, \overline{10}\}$ ): without invertibility, no cancellation. In $\Z/11\Z$ by contrast, every equation $\overline a x = \overline b$ with $\overline a \neq \overline 0$ has exactly one solution.

Example 7.28 (Group axioms as a solving license)

In the group $\bigl((\Z/7\Z)^*, \times\bigr)$ , solve $\overline 3\,x = \overline 5$ . By Proposition 7.5 (3) the solution exists, is unique, and equals $\overline3^{-1}\, \overline5$ ; since $\overline3 \times \overline5 = \overline{15} = \overline1$ , the inverse of $\overline 3$ is $\overline 5$ , so

x = \overline5 \times \overline5 = \overline{25} = \overline4, \qquad\text{check: } \overline3 \times \overline4 = \overline{12} = \overline5 .

The point is less the answer than the guarantee: in a group, every such equation is solvable uniquely before any computation, so a solving procedure can never run into “no solution” or “several”. Compare $\overline3\,x = \overline6$ in $\Z/12\Z$ above, where the guarantee fails — knowing which structure one is in is knowing what one may take for granted.

Example 7.29 (Direct products)

If $G$ and $H$ are groups, the product set $G \times H$ with the componentwise law $(g, h)(g', h') = (gg', hh')$ is a group: axioms are checked coordinate by coordinate, with identity $(e_G, e_H)$ and inverses $(g^{-1}, h^{-1})$ . Orders combine by the lcm: $(g, h)^m = (g^m, h^m)$ is the identity iff the order of $g$ and the order of $h$ both divide $m$ . Thus in $\Z/2\Z \times \Z/2\Z$ (additive) every nonzero element has order $2$ — this is exactly the rectangle group of Example 7.6 in coordinates — while $\Z/4\Z$ has an element of order $4$ : a second, computation-free proof that the two groups of size $4$ are not isomorphic (an isomorphism preserves orders). Products are the easiest way to manufacture new groups from old, and the plane $\R^2 = \R \times \R$ of Chapter 18 is the construction’s most important instance.

Remark 7.30 (Fermat, structurally)

In the field $\Z/p\Z$ , the nonzero classes form a multiplicative group with $p - 1$ elements, and Fermat’s little theorem (Theorem 6.23) says: every element $x$ of this group satisfies $x^{p-1} = \overline 1$ . This is an instance of a general fact about finite groups (Lagrange’s theorem), proved in the second year; the pairing proof of Wilson’s theorem (Exercise 6.11) already had this group-theoretic flavor.

Remark 7.31 (Interlude: what abstraction buys)

It is fair to ask what was gained by proving, say, Proposition 7.2 for an abstract law rather than for numbers. The answer is leverage. That two-line argument now covers, at once: inverses of functions under composition (Theorem 1.24, whose uniqueness proof it repeats word for word), inverses mod $n$ (Proposition 6.20), inverses of nonzero reals, of units in any ring, and — sight unseen — of the invertible matrices of Chapter 21, where uniqueness of $A^{-1}$ will not need a single line of proof. The same economy holds for Proposition 7.11 (one injectivity criterion, reused for linear maps in Chapter 20) and for the subgroup criterion. Abstraction here is not generality for its own sake: it is the refusal to prove the same lemma five times under five names. The price — keeping track of which axioms each statement really used — is exactly what the exercises of this chapter train.

Remark 7.32 (Where this chapter is used)

The vocabulary of this chapter is the grammar of the rest of the volume. Rings and fields organize Chapter 8 ( $K[X]$ is a ring imitating $\Z$ ) and Chapter 9 ( $K(X)$ is its field of fractions); vector spaces (Chapter 18) are abelian groups with a field acting on them; matrices (Chapter 21) form the volume’s first seriously non-commutative ring, and their invertible elements a group whose study is linear algebra itself. Morphisms and kernels return as linear maps and null spaces in Chapter 20 — Proposition 7.11 is the injectivity criterion of that chapter, proved once and for all here. The symmetric group, star of the weekend problem below, supplies the signature on which determinants are built in Chapter 22.

7.5 Exercises

Exercise 7.1 ★

On $E = \R \setminus \{1\}$ , define $x * y = x + y - xy$ . Prove that $(E, *)$ is an abelian group. (Identify the identity and the inverse of $x$ ; check stability: why is $x * y \neq 1$ ?)

Solution

Solution of Exercise 7.1.

Stability: $x * y = 1 \iff x + y - xy = 1 \iff (1-x)(1-y) = 0$ , impossible for $x, y \neq 1$ . Indeed the key identity is

1 - x * y = (1 - x)(1 - y):

the map $\varphi(x) = 1 - x$ sends $(E, *)$ to $(\R^*, \times)$ with $\varphi(x * y) = \varphi(x)\varphi(y)$ — a bijective morphism. All axioms now transport: associativity and commutativity follow from those of $\times$ ; the identity is $\varphi^{-1}(1) = 0$ (check: $x * 0 = x$ ); the inverse of $x$ is $\varphi^{-1}\bigl((1-x)^{-1}\bigr) = 1 - \frac{1}{1-x} = \frac{x}{x - 1}$ (which is $\neq 1$ ). So $(E, *)$ is an abelian group.

Exercise 7.2 ★

Which of the following are groups?

$(\intoo{0}{+\infty}, \times)$ ;
$(\{-1, 0, 1\}, +)$ ;
$(\Q^*, \times)$ ;
the set of odd integers under addition.

Solution

Solution of Exercise 7.2.

Yes: product of positives is positive, identity $1$ , inverse $\frac 1x$ , associativity inherited from $\R^*$ .
No: not stable ( $1 + 1 = 2 \notin \{-1,0,1\}$ ).
Yes: the standard example.
No: not stable (odd $+$ odd $=$ even), and no identity ( $0$ is even).

Exercise 7.3 ★

Write the composition table of the symmetric group $\mathfrak{S}_3$ of $\{1,2,3\}$ (six bijections: identity, three transpositions, two $3$ -cycles), and exhibit two elements that do not commute.

Solution

Solution of Exercise 7.3.

Write $\mathrm{id}$ , the transpositions $\tau_{12}, \tau_{13}, \tau_{23}$ (swapping the two named points), and the cycles $c = (1\,2\,3)$ (i.e. $1 \mapsto 2 \mapsto 3 \mapsto 1$ ) and $c^2 = (1\,3\,2)$ . The table of $\sigma\rho$ (row $\sigma$ , column $\rho$ , apply $\rho$ first):

$\sigma\backslash\rho$	$\mathrm{id}$	$c$	$c^2$	$\tau_{12}$	$\tau_{13}$	$\tau_{23}$
$\mathrm{id}$	$\mathrm{id}$	$c$	$c^2$	$\tau_{12}$	$\tau_{13}$	$\tau_{23}$
$c$	$c$	$c^2$	$\mathrm{id}$	$\tau_{13}$	$\tau_{23}$	$\tau_{12}$
$c^2$	$c^2$	$\mathrm{id}$	$c$	$\tau_{23}$	$\tau_{12}$	$\tau_{13}$
$\tau_{12}$	$\tau_{12}$	$\tau_{23}$	$\tau_{13}$	$\mathrm{id}$	$c^2$	$c$
$\tau_{13}$	$\tau_{13}$	$\tau_{12}$	$\tau_{23}$	$c$	$\mathrm{id}$	$c^2$
$\tau_{23}$	$\tau_{23}$	$\tau_{13}$	$\tau_{12}$	$c^2$	$c$	$\mathrm{id}$

Non-commuting pair: $\tau_{12}\tau_{13} = c^2$ while $\tau_{13}\tau_{12} = c$ . (To check one entry: $\tau_{12}\tau_{13}$ sends $1 \xmapsto{\tau_{13}} 3 \xmapsto{\tau_{12}} 3$ , $3 \mapsto 1 \mapsto 2$ , $2 \mapsto 2 \mapsto 1$ : that is $1 \mapsto 3 \mapsto 2 \mapsto 1$ , the cycle $c^2 = (1\,3\,2)$ .)

Exercise 7.4 ★

Prove that $H = \{z \in \C^* : \abs z = 1\}$ is a subgroup of $(\C^*, \times)$ , and that $\R_+^*$ is another; is $H \cup \R_+^*$ a subgroup?

Solution

Solution of Exercise 7.4.

$H$ : $1 \in H$ ; for $z, w \in H$ , $\abs{zw^{-1}} = \abs z / \abs w = 1$ : the criterion applies. $\R_+^*$ : same, $\abs{xy^{-1}}$ replaced by positivity. Union: $\iu \in H$ and $2 \in \R_+^*$ , but $2\iu$ has modulus $2 \neq 1$ and is not a positive real: $2\iu \notin H \cup \R_+^*$ , so the union is not stable — not a subgroup (as predicted by Exercise 7.6, neither subgroup contains the other).

Exercise 7.5 ★★

Let $f \colon (\R, +) \to (\C^*, \times)$ , $\theta \mapsto \eu^{\iu\theta}$ . Prove that $f$ is a morphism, compute $\ker f$ and $\operatorname{im} f$ , and deduce from Proposition 7.11 that $f$ is not injective. Restrict the domain to make it injective on an interval as large as possible.

Solution

Solution of Exercise 7.5.

Morphism: $\eu^{\iu(\theta + \varphi)} = \eu^{\iu\theta}\eu^{\iu\varphi}$ (Theorem 3.7). Kernel: $\eu^{\iu\theta} = 1 \iff \theta \in 2\pi\Z$ , so $\ker f = 2\pi\Z \neq \{0\}$ : not injective. Image: every unit complex number is $\eu^{\iu\theta}$ for some $\theta$ (polar form), so $\operatorname{im} f = \mathbb{U}$ , the unit circle. The restriction of $f$ to a half-open interval of length $2\pi$ , such as $\intco{0}{2\pi}$ or $\intoc{-\pi}{\pi}$ , is injective (two angles with the same image differ by a multiple of $2\pi$ , and only one representative of each class fits in the interval); no interval of greater length works, since it contains two points at distance $2\pi$ .

Exercise 7.6 ★★

Let $H, K$ be subgroups of $G$ . Prove that $H \cap K$ is a subgroup, and that $H \cup K$ is a subgroup only when $H \subseteq K$ or $K \subseteq H$ . (If $h \in H \setminus K$ and $k \in K \setminus H$ , where can $hk$ live?)

Solution

Solution of Exercise 7.6.

Intersection: $e \in H \cap K$ , and $x, y \in H \cap K$ gives $xy^{-1}$ in both $H$ and $K$ . Union: if $H \subseteq K$ the union is $K$ , a subgroup (and symmetrically). Conversely, suppose neither inclusion holds: pick $h \in H \setminus K$ and $k \in K \setminus H$ , and suppose $H \cup K$ were a subgroup; then $hk \in H \cup K$ . If $hk \in H$ , then $k = h^{-1}(hk) \in H$ : contradiction. If $hk \in K$ , then $h = (hk)k^{-1} \in K$ : contradiction. So $H \cup K$ is not a subgroup.

Exercise 7.7 ★★

A group $G$ satisfies $x^2 = e$ for all $x \in G$ . Prove that $G$ is abelian. (Expand $(xy)^2$ .)

Solution

Solution of Exercise 7.7.

Note first that $x^2 = e$ means $x^{-1} = x$ for every $x$ . Then for $x, y \in G$ :

xy = (xy)^{-1} = y^{-1} x^{-1} = yx ,

using Proposition 7.5 (2). So $G$ is abelian.

Exercise 7.8 ★★

In $\Z/18\Z$ : list the units and find the inverse of $\overline 5$ ; solve $\overline 5\, x = \overline 7$ ; solve $\overline 6\, x = \overline 3$ and $\overline 6\, x = \overline{12}$ .

Solution

Solution of Exercise 7.8.

Units of $\Z/18\Z$ : classes coprime to $18 = 2 \times 3^2$ : $\overline 1, \overline 5, \overline 7, \overline{11}, \overline{13}, \overline{17}$ . Inverse of $\overline 5$ : $5 \times 11 = 55 = 3\times 18 + 1$ , so $\overline 5^{-1} = \overline{11}$ .

$\overline 5 x = \overline 7$ : multiply by $\overline{11}$ : $x = \overline{77} = \overline 5$ (since $77 = 4\times 18 + 5$ ). Unique solution.

$\overline 6 x = \overline 3$ : the equation $6x \equiv 3 \pmod{18}$ means $18 \mid 6x - 3$ . But $6x - 3 = 3(2x - 1)$ is odd, while $18$ is even: an even number cannot divide an odd one. No solution.

$\overline 6 x = \overline{12}$ : $6x \equiv 12 \pmod{18} \iff x \equiv 2 \pmod 3$ : solutions $x \in \{\overline 2, \overline 5, \overline 8, \overline{11}, \overline{14}, \overline{17}\}$ — six of them.

Exercise 7.9 ★★

Prove that the set $\Z[\sqrt 2] = \{a + b\sqrt 2 : a, b \in \Z\}$ is a ring (a subring of $\R$ ), and that $1 + \sqrt 2$ is a unit of it with infinitely many distinct powers — so $\Z[\sqrt 2]^\times$ is infinite, unlike $\Z^\times$ .

Solution

Solution of Exercise 7.9.

$\Z[\sqrt 2]$ contains $0$ and $1$ , and is stable under subtraction and product:

(a + b\sqrt 2)(c + d\sqrt 2) = (ac + 2bd) + (ad + bc)\sqrt 2 ,

so it is a subring of $\R$ (commutativity, associativity, distributivity are inherited). Unit: $(1 + \sqrt 2)(-1 + \sqrt 2) = 2 - 1 = 1$ , so $1 + \sqrt 2$ is invertible with inverse $\sqrt 2 - 1 \in \Z[\sqrt 2]$ . Its powers $(1 + \sqrt 2)^n$ are strictly increasing (the base is $> 1$ ), hence pairwise distinct, and each is a unit ( $\bigl((1+\sqrt2)^n\bigr)^{-1} = (\sqrt 2 - 1)^n$ ): the group of units is infinite.

Exercise 7.10 ★★★

(Boolean rings) Let $A$ be a ring in which $x^2 = x$ for every $x$ . Prove that $x + x = 0$ for all $x$ , and that $A$ is commutative. (Expand $(x+x)^2$ and $(x+y)^2$ .) Give an example of such a ring with $\mathcal{P}(E)$ , taking the symmetric difference as addition and intersection as multiplication.

Solution

Solution of Exercise 7.10.

$x + x = (x + x)^2 = x^2 + x^2 + x^2 + x^2 = 4x^2 = 4x$ — so $2x = 4x$ , giving $2x = 0$ , i.e. $x + x = 0$ (each element is its own additive inverse). Then

x + y = (x+y)^2 = x^2 + xy + yx + y^2 = x + xy + yx + y ,

so $xy + yx = 0$ , i.e. $xy = -yx = yx$ (using $-z = z$ ). Hence $A$ is commutative.

Example: on $\mathcal{P}(E)$ , define $A + B = (A \cup B) \setminus (A \cap B)$ (symmetric difference) and $A \times B = A \cap B$ . One checks: $(\mathcal{P}(E), +)$ is an abelian group with identity $\emptyset$ and each set its own inverse; $\cap$ is associative, commutative, with identity $E$ ; distributivity $A \cap (B + C) = (A \cap B) + (A \cap C)$ holds (an element lies in the left side iff it is in $A$ and in exactly one of $B, C$ ). And $A \cap A = A$ : every element is idempotent, as required.

Exercise 7.11 ★★★

Let $G$ be a group in which, for some fixed $n \geq 1$ , $(xy)^n = x^n y^n$ , $(xy)^{n+1} = x^{n+1}y^{n+1}$ and $(xy)^{n+2} = x^{n+2}y^{n+2}$ for all $x, y$ . Prove that $G$ is abelian. (From the three identities, derive first $y^n x = x y^n$ , then $y^{n+1} x = x y^{n+1}$ , and conclude.)

Solution

Solution of Exercise 7.11.

Write the hypothesis for $n$ and $n+1$ :

(xy)^{n+1} = x^{n+1} y^{n+1} \quad\text{and}\quad (xy)^{n+1} = (xy)(xy)^n = xy\,x^n y^n .

Equating: $x^{n+1} y^{n+1} = x\,y\,x^n\,y^n$ ; cancel $x$ on the left and $y^n$ on the right: $x^n y = y x^n$ . The same computation one degree higher ( $n+1$ and $n+2$ ) gives $x^{n+1} y = y x^{n+1}$ . Then

y\,x^{n+1} = x^{n+1} y = x\,(x^n y) = x\,y\,x^n ,

and cancelling $x^n$ on the right of $y x \cdot x^n = x y \cdot x^n$ : $yx = xy$ . So $G$ is abelian.

Exercise 7.12 ★★

Determine all group morphisms from $(\Z, +)$ to $(\Z, +)$ .
Prove that the only group morphism from $(\Q, +)$ to $(\Z, +)$ is the zero morphism. (For $x \in \Q$ and $n \in \N^*$ , compare $f(x)$ and $n\,f(x/n)$ .)

Solution

Solution of Exercise 7.12.

Let $f \colon \Z \to \Z$ be additive and $a = f(1)$ . By induction $f(k) = ka$ for $k \in \N$ , and $f(-k) = -f(k) = -ka$ : so $f$ is the multiplication by $a$ . Conversely every map $k \mapsto ak$ is a morphism: the morphisms $(\Z,+) \to (\Z,+)$ are exactly the multiplications by a fixed integer.
Let $f \colon \Q \to \Z$ be a morphism, $x \in \Q$ and $n \in \N^*$ . Then

$f(x) = f\Bigl(\underbrace{\tfrac xn + \dots + \tfrac xn}_{n}\Bigr) = n\,f\Bigl(\frac xn\Bigr) ,$

so the integer $f(x)$ is divisible by every $n \geq 1$ . The only such integer is $0$ : $f \equiv 0$ .

7.6 Problem: The symmetric group and the 8-puzzle

Problem 7.1

The group $\mathfrak S_n$ of permutations of $\intint1n$ is the oldest group in mathematics and still the most instructive. This problem builds its structure theory from scratch — cycles, generation by transpositions, the signature morphism $\varepsilon \colon \mathfrak S_n \to \{\pm1\}$ (whose existence is genuinely nontrivial), and the alternating group $\mathfrak A_n$ generated by $3$ -cycles — then cashes it in on a classical puzzle: in the $3 \times 3$ sliding-tile game, no sequence of moves can swap two tiles and leave everything else in place. Permutations act on $\intint1n$ ; products $\sigma\tau$ mean “apply $\tau$ first”; $[\,v_1, \dots, v_n]$ denotes the permutation sending $i$ to $v_i$ .

Part I — Cycles and transpositions.

Justify $\abs{\mathfrak S_n} = n!$ (Theorem 2.12). In $\mathfrak S_3$ , compute both products of $\sigma = [2, 3, 1]$ and $\tau = [1, 3, 2]$ , and conclude that $\mathfrak S_3$ is not abelian.
A $k$ -cycle $(a_1\ a_2\ \dots\ a_k)$ ( $k \geq 2$ , the $a_i$ pairwise distinct) sends $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ and fixes everything else; its support is $\{a_1, \dots, a_k\}$ . Prove that two cycles with disjoint supports commute.
Prove that every $\sigma \in \mathfrak S_n$ is a product of cycles with pairwise disjoint supports, and that this decomposition is unique up to the order of the factors. (Consider, for each $i$ , the sequence $i, \sigma(i), \sigma^2(i), \dots$ : it must return to $i$ ; the resulting orbits partition $\intint1n$ , and $\sigma$ acts on each as a cycle.)
Decompose $\sigma = [4, 1, 5, 2, 3, 7, 8, 6] \in \mathfrak S_8$ into disjoint cycles. Defining the order of $\sigma$ as in Definition 7.14, prove that the order of a product of disjoint cycles is the lcm of their lengths, and compute the order of this $\sigma$ .
Prove the telescoping identity

$(a_1\ a_2\ \dots\ a_k) = (a_1\ a_k)(a_1\ a_{k-1})\cdots(a_1\ a_2) ,$

and conclude that every permutation is a product of transpositions. Write the $\sigma$ of question 4 as such a product.
Show further that the adjacent transpositions $(i\ \ i{+}1)$ suffice: for $a < b$ ,

$(a\ b) = (a\ \ a{+}1)(a{+}1\ \ a{+}2)\cdots(b{-}1\ \ b) \cdots(a{+}1\ \ a{+}2)(a\ \ a{+}1),$

a product of $2(b - a) - 1$ adjacent transpositions — an odd number (this parity will matter twice below).

Part II — The signature exists. For $\sigma \in \mathfrak S_n$ , let

N(\sigma) = \#\bigl\{(i, j) : i < j,\ \sigma(i) > \sigma(j)\bigr\}

be its number of inversions, and set $\varepsilon(\sigma) = (-1)^{N(\sigma)}$ .

Compute $N$ and $\varepsilon$ for the identity, for a transposition $(i\ \ i{+}1)$ , and for $[2, 3, 1]$ .
Prove that for every $\sigma$ and every adjacent transposition $\tau = (i\ \ i{+}1)$ : $N(\sigma\tau) = N(\sigma) \pm 1$ . (Composing with $\tau$ on the right swaps the values in positions $i$ and $i + 1$ ; exactly one pair changes its inversion status.)
Deduce, using question 6, that for any transposition $\tau$ , $\varepsilon(\sigma\tau) = -\varepsilon(\sigma)$ ; conclude that if $\sigma$ is a product of $p$ transpositions, then $\varepsilon(\sigma) = (-1)^p$ — in particular the parity of $p$ depends only on $\sigma$ , not on the chosen factorization — and that $\varepsilon \colon \mathfrak S_n \to \{\pm 1\}$ is a group morphism.
Show that a $k$ -cycle has signature $(-1)^{k-1}$ , and that in general $\varepsilon(\sigma) = (-1)^{n - c(\sigma)}$ , where $c(\sigma)$ is the number of orbits of $\sigma$ (fixed points included).
The alternating group is $\mathfrak A_n = \ker\varepsilon$ . Justify that it is a subgroup, and prove $\abs{\mathfrak A_n} = \frac{n!}2$ for $n \geq 2$ . (Fix a transposition $\tau_0$ and consider $\sigma \mapsto \sigma\tau_0$ .)
Consistency check on $\sigma = [4, 1, 5, 2, 3, 7, 8, 6]$ : compute $\varepsilon(\sigma)$ three ways — by counting inversions, from the cycle type via question 10, and from your transposition count in question 5.

Part III — $\mathfrak A_n$ is generated by $3$ -cycles.

Let $a, b, c, d$ be pairwise distinct. Verify the two identities

$(a\ b)(a\ c) = (a\ c\ b), \qquad (a\ b)(c\ d) = (a\ c\ b)(a\ c\ d) .$
Prove that for $n \geq 3$ , every element of $\mathfrak A_n$ is a product of $3$ -cycles. (An even permutation is a product of an even number of transpositions; absorb them two at a time.)
Write $(1\ 2)(3\ 4)$ and the $5$ -cycle $(1\ 2\ 3\ 4\ 5)$ explicitly as products of $3$ -cycles.
Prove the conjugation formula: for every $\sigma \in \mathfrak S_n$ ,

$\sigma\,(a_1\ \dots\ a_k)\,\sigma^{-1} = \bigl(\sigma(a_1)\ \dots\ \sigma(a_k)\bigr) .$

Part IV — The 8-puzzle. Tiles $1, \dots, 8$ slide in a $3 \times 3$ frame with one empty cell; a move slides a tile adjacent to the empty cell into it. Number the cells $1, \dots, 9$ (row by row; the solved position has tile $i$ in cell $i$ and the empty cell at cell $9$ ). Treat the empty cell as a ninth tile, so a position is a permutation $\sigma \in \mathfrak S_9$ (tile $\sigma(i)$ sits in cell $i$ ).

Show that a move replaces $\sigma$ by $\sigma \circ \tau$ where $\tau$ is the transposition of the two cells involved; deduce that each move flips $\varepsilon(\sigma)$ .
Let $d(\sigma)$ be the taxicab distance (rows plus columns) between the empty cell’s current cell and its home cell $9$ . Show that each move changes $d$ by $\pm1$ , so each move also flips $(-1)^{d(\sigma)}$ . Conclude that

$I(\sigma) = \varepsilon(\sigma)\cdot(-1)^{d(\sigma)}$

is invariant under every move.
Prove the puzzle’s classical impossibility: the position that swaps tiles $7$ and $8$ and leaves everything else (including the empty cell) in place cannot be reached from the solved position.
We admit the converse (its proof is an instructive but lengthy induction): every position with $I = +1$ is reachable. Deduce that exactly half of the $8!$ positions with the empty cell at home are solvable, i.e. $\frac{8!}2 = 20\,160$ .
Deduce from question 20 that the reachable tile arrangements with the empty cell at home form exactly the subgroup $\mathfrak A_8 \leq \mathfrak S_8$ .
Applications of the invariant: can one reach (a) the position where tiles $1, 2, 3$ are cyclically permuted and everything else, empty cell included, is at home? (b) the position where tile $5$ and the empty cell have exchanged places and all other tiles are at home? Justify both answers with $I$ .

Part V — Synthesis.

Prove that for $n \geq 3$ the only group morphisms $f \colon \mathfrak S_n \to \{\pm 1\}$ are the constant morphism and $\varepsilon$ . (Using question 16 and commutativity of $\{\pm1\}$ , show $f$ takes the same value on all transpositions.)
Where exactly did the problem use: (i) the morphism concept and Proposition 7.11; (ii) the counting principles of Chapter 2; (iii) the well-definedness issue that questions 8–9 resolve? One sentence each.
Synthesis, in a short paragraph: one parity function, proved well defined once, simultaneously organizes the internal structure of $\mathfrak S_n$ (the subgroup $\mathfrak A_n$ ), decides a physical puzzle, and — through the formula $\det = \sum_\sigma \varepsilon(\sigma)\cdots$ — will define determinants in Chapter 22. Comment on the recurring pattern: invariants turn “try all sequences of moves” into one computation.

Solution

Solution of Problem 7.1.

1. A permutation is a bijection of $\intint1n$ , i.e. an $n$ -arrangement of $n$ objects: there are $n!$ of them (Theorem 2.12). With $\sigma = [2,3,1]$ , $\tau = [1,3,2]$ : $\sigma\tau$ sends $1 \mapsto 1 \mapsto 2$ , $2 \mapsto 3 \mapsto 1$ , $3 \mapsto 2 \mapsto 3$ : $\sigma\tau = [2,1,3]$ ; and $\tau\sigma$ sends $1 \mapsto 2 \mapsto 3$ , $2 \mapsto 3 \mapsto 2$ , $3 \mapsto 1 \mapsto 1$ : $\tau\sigma = [3,2,1] \neq \sigma\tau$ .

2. Let $\gamma, \gamma'$ have disjoint supports $S, S'$ . For $x \in S$ : $\gamma'(x) = x$ and $\gamma(x) \in S$ , so $\gamma\gamma'(x) = \gamma(x) = \gamma'\gamma(x)$ . Symmetrically for $x \in S'$ ; and both sides fix every $x \notin S \cup S'$ . So $\gamma\gamma' = \gamma'\gamma$ .

3. For $i \in \intint1n$ , the values $i, \sigma(i), \sigma^2(i), \dots$ live in a finite set, so $\sigma^a(i) = \sigma^b(i)$ for some $a < b$ ; injectivity gives $\sigma^{b-a}(i) = i$ : the sequence returns to $i$ . Call orbit of $i$ the set $\{i, \sigma(i), \dots, \sigma^{k-1}(i)\}$ with $k \geq 1$ minimal such that $\sigma^k(i) = i$ . Two orbits meeting in one point coincide (both are the forward $\sigma$ -images of that point), so the orbits partition $\intint1n$ ; $\sigma$ acts on each orbit of size $k \geq 2$ as the $k$ -cycle $(i\ \sigma(i)\ \cdots\ \sigma^{k-1}(i))$ and fixes the singletons. The product of these disjoint cycles agrees with $\sigma$ everywhere. Uniqueness: in any decomposition into disjoint cycles, the cycle through $i$ must be $(i\ \sigma(i)\ \cdots)$ — the cycles are forced to be the orbits with their induced action.

4. Following the orbits: $1 \to 4 \to 2 \to 1$ , $3 \to 5 \to 3$ , $6 \to 7 \to 8 \to 6$ :

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

If $\sigma = \gamma_1\cdots\gamma_r$ with disjoint cycles of lengths $k_1, \dots, k_r$ , commutation (question 2) gives $\sigma^m = \gamma_1^m\cdots\gamma_r^m$ , and since the supports are disjoint, $\sigma^m = \mathrm{id}$ iff each $\gamma_i^m = \mathrm{id}$ iff $k_i \mid m$ for all $i$ (a $k$ -cycle has order $k$ : $\gamma^m$ sends $a_1$ to $a_{1 + (m \bmod k)}$ ). The least such $m$ is $\operatorname{lcm}(k_1, \dots, k_r)$ . Here: $\operatorname{lcm}(3, 2, 3) = 6$ .

5. Apply the right-hand side to each point, rightmost factor first. $a_1 \mapsto a_2$ by $(a_1\ a_2)$ , then every later factor fixes $a_2$ : net $a_1 \mapsto a_2$ . For $2 \leq i < k$ : $a_i$ is untouched until $(a_1\ a_i)$ sends it to $a_1$ , and the very next factor $(a_1\ a_{i+1})$ sends $a_1$ to $a_{i+1}$ , after which nothing moves it: net $a_i \mapsto a_{i+1}$ . Finally $a_k$ is fixed by all factors but the leftmost, which sends it to $a_1$ . This is exactly the cycle. Since every permutation is a product of cycles (question 3), it is a product of transpositions. For question 4’s $\sigma$ :

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

five transpositions.

6. Induction on $b - a$ . For $b = a + 1$ the identity is trivial ( $1 = 2\cdot1 - 1$ factor). For $b > a + 1$ , verify directly that $(a\ b) = (a\ \ a{+}1)\,(a{+}1\ \ b)\,(a\ \ a{+}1)$ : the right side sends $a \mapsto a{+}1 \mapsto b \mapsto b$ , $b \mapsto b \mapsto a{+}1 \mapsto a$ , $a{+}1 \mapsto a \mapsto a \mapsto a{+}1$ , and fixes the rest. By induction $(a{+}1\ \ b)$ is a palindromic product of $2(b - a - 1) - 1$ adjacent transpositions, so $(a\ b)$ is one of $2(b - a) - 1$ : an odd number.

7. $N(\mathrm{id}) = 0$ , $\varepsilon = +1$ . For $(i\ \ i{+}1)$ , the only inverted pair is $(i, i+1)$ : $N = 1$ , $\varepsilon = -1$ . For $[2, 3, 1]$ : the inverted pairs are $(1, 3)$ (values $2 > 1$ ) and $(2, 3)$ (values $3 > 1$ ): $N = 2$ , $\varepsilon = +1$ .

8. The value lists of $\sigma$ and $\sigma\tau$ differ only by the swap of positions $i$ and $i + 1$ . For a pair of positions not involving $i, i+1$ , nothing changes. For $k < i$ , the two pairs $(k, i)$ and $(k, i+1)$ exchange their inversion statuses (the same two values are compared with $\sigma(k)$ , in the other order of positions): their total contribution is unchanged; likewise for $k > i + 1$ . The one remaining pair $(i, i+1)$ flips its status. Hence $N(\sigma\tau) = N(\sigma) \pm 1$ .

9. Let $\tau = (a\ b)$ be any transposition: by question 6 it is a product of an odd number of adjacent transpositions, so right-multiplying by $\tau$ changes $N$ by an odd total (question 8, applied repeatedly): $\varepsilon(\sigma \tau) = -\varepsilon(\sigma)$ . Now if $\sigma = \tau_1\cdots \tau_p$ (transpositions), build it up from the identity by $p$ right-multiplications: $\varepsilon(\sigma) = (-1)^p\varepsilon(\mathrm{id}) = (-1)^p$ . Since $\varepsilon(\sigma)$ is defined by inversions — independently of any factorization — the parity of $p$ is an invariant of $\sigma$ . Morphism: writing $\sigma$ with $p$ and $\sigma'$ with $q$ transpositions, $\sigma\sigma'$ uses $p + q$ of them: $\varepsilon(\sigma\sigma') = (-1)^{p+q} = \varepsilon(\sigma)\varepsilon(\sigma')$ .

10. A $k$ -cycle is a product of $k - 1$ transpositions (question 5): $\varepsilon = (-1)^{k-1}$ . For general $\sigma$ with orbits of sizes $k_1, \dots, k_r$ ( $k_i \geq 2$ ) plus $f$ fixed points, $c(\sigma) = r + f$ and $n = k_1 + \dots + k_r + f$ , so

\varepsilon(\sigma) = \prod_{i=1}^r (-1)^{k_i - 1} = (-1)^{\sum_i k_i - r} = (-1)^{n - f - r} = (-1)^{n - c(\sigma)} .

11. $\mathfrak A_n = \ker\varepsilon$ is a subgroup as the kernel of a morphism (Definition 7.10). Fix a transposition $\tau_0$ (exists for $n \geq 2$ ). The map $\sigma \mapsto \sigma\tau_0$ is a bijection of $\mathfrak S_n$ (its own inverse) exchanging $\mathfrak A_n$ with the set of odd permutations (question 9). The two sets partition $\mathfrak S_n$ and have equal size: $\abs{\mathfrak A_n} = \frac{n!}2$ .

12. Inversions of $[4, 1, 5, 2, 3, 7, 8, 6]$ : from value $4$ : over $1, 2, 3$ : three; from $5$ : over $2, 3$ : two; from $7$ : over $6$ : one; from $8$ : over $6$ : one. $N = 7$ , $\varepsilon = -1$ . Cycle type: $c = 3$ orbits, $n = 8$ : $\varepsilon = (-1)^{8-3} = -1$ . Transposition count: five transpositions in question 5: $(-1)^5 = -1$ . All three agree.

13. $(a\ b)(a\ c)$ (rightmost first): $a \mapsto c \mapsto c$ ; $c \mapsto a \mapsto b$ ; $b \mapsto b \mapsto a$ : the $3$ -cycle $(a\ c\ b)$ . And $(a\ c\ b)(a\ c\ d)$ : $a \mapsto c \mapsto b$ ; $b \mapsto b \mapsto a$ ; $c \mapsto d \mapsto d$ ; $d \mapsto a \mapsto c$ : that is $(a\ b)(c\ d)$ , as claimed.

14. Let $\sigma \in \mathfrak A_n$ : by question 9, $\sigma = \tau_1\cdots\tau_{2m}$ with an even number of transpositions. Group them in consecutive pairs $\tau_{2i-1}\tau_{2i}$ : if the two are equal, the pair is the identity and disappears; if they share exactly one point, the first identity of question 13 writes the pair as one $3$ -cycle; if they are disjoint, the second identity writes it as two $3$ -cycles. Hence $\sigma$ is a product of $3$ -cycles (or the identity, an empty product — and for $n \geq 3$ also $(1\ 2\ 3)^3$ ).

15. $(1\ 2)(3\ 4) = (1\ 3\ 2)(1\ 3\ 4)$ (question 13 with $a{=}1, b{=}2, c{=}3, d{=}4$ ). For the $5$ -cycle: by question 5, $(1\ 2\ 3\ 4\ 5) = (1\ 5)(1\ 4)(1\ 3)(1\ 2)$ , and pairing: $(1\ 5)(1\ 4) = (1\ 4\ 5)$ , $(1\ 3)(1\ 2) = (1\ 2\ 3)$ :

(1\ 2\ 3\ 4\ 5) = (1\ 4\ 5)(1\ 2\ 3) .

(Check on $3$ : $(1\ 2\ 3)$ sends $3 \to 1$ , then $(1\ 4\ 5)$ sends $1 \to 4$ : net $3 \to 4$ , correct.)

16. Apply both sides to an arbitrary point. For $i = \sigma(a_j)$ : the left side gives $\sigma\bigl((a_1\ \dots\ a_k)(a_j)\bigr) = \sigma(a_{j+1})$ (indices mod $k$ ), which is what the right side does to $\sigma(a_j)$ . For $i$ not of this form: $\sigma^{-1}(i)$ is outside the support, so the left side fixes $i$ , and so does the right side. Equal everywhere.

17. Sliding the tile of cell $c'$ into the empty cell $c$ swaps the contents of cells $c$ and $c'$ (tile $9$ , the blank, moves to $c'$ ). If tile $\sigma(i)$ sat in cell $i$ , the new position is $\sigma' = \sigma \circ (c\ c')$ : same contents except that cells $c, c'$ read each other’s former contents. By question 9, $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

18. A move sends the empty cell to an adjacent cell: its row or its column changes by exactly $1$ , so the taxicab distance $d$ to cell $9$ changes by $\pm1$ , and $(-1)^d$ flips. Since each move flips both $\varepsilon(\sigma)$ and $(-1)^{d(\sigma)}$ , their product $I(\sigma)$ is unchanged by every move: an invariant.

19. The solved position has $\varepsilon = +1$ , $d = 0$ : $I = +1$ . The target (tiles $7, 8$ swapped, blank home) is the transposition of the contents of cells $7$ and $8$ : $\varepsilon = -1$ , $d = 0$ : $I = -1$ . Since $I$ is invariant and the two values differ, no sequence of moves joins them.

20. A position with the blank at home is a permutation of the $8$ tiles among cells $1, \dots, 8$ , i.e. an element of $\mathfrak S_8$ ; it has $d = 0$ , so $I = \varepsilon(\sigma)$ . Reachable forces $I = +1$ , i.e. $\sigma \in \mathfrak A_8$ ; the admitted converse says all of $\mathfrak A_8$ is reached. Count: $\abs{\mathfrak A_8} = \frac{8!}2 = 20\,160$ (question 11).

21. By question 20 the reachable blank-at-home arrangements form exactly $\mathfrak A_8$ — in particular a subgroup of $\mathfrak S_8$ : composing two solvable scrambles, or inverting one, stays solvable, which is far from obvious by pure puzzle reasoning.

22. (a) A $3$ -cycle of tiles with blank home: $\varepsilon = +1$ (question 10), $d = 0$ , so $I = +1$ : reachable (by the admitted converse) — one can cycle three tiles. (b) Tile $5$ and the blank exchanged: the position is the transposition of the contents of cells $5$ and $9$ , so $\varepsilon = -1$ ; the blank sits at the center, at taxicab distance $d = 2$ from home, so $(-1)^d = +1$ and $I = -1$ : unreachable. One cannot simply “park the blank in the middle” leaving the tiles otherwise sorted.

23. Let $f \colon \mathfrak S_n \to \{\pm1\}$ be a morphism. For any two transpositions $\tau, \tau'$ , question 16 provides $\sigma$ with $\sigma\tau\sigma^{-1} = \tau'$ (map the two moved points onto the two others; $n \geq 3$ guarantees room to do so, though even $n = 2$ is trivial here). Then $f(\tau') = f(\sigma)f(\tau)f(\sigma)^{-1} = f(\tau)$ since $\{\pm1\}$ is abelian: $f$ is constant on transpositions. If that constant is $+1$ , then $f = 1$ on all products of transpositions, i.e. everywhere (question 5). If it is $-1$ , then $f(\sigma) = (-1)^p = \varepsilon(\sigma)$ on a product of $p$ transpositions. So $f \in \{1, \varepsilon\}$ .

24. (i) The morphism property of $\varepsilon$ and the kernel machinery gave $\mathfrak A_n$ its subgroup structure and its size, and Proposition 7.11-style reasoning runs through questions 11 and 21. (ii) Counting: $\abs{\mathfrak S_n} = n!$ , the halving argument of question 11, and the count $20\,160$ of question 20 are Chapter 2 at work. (iii) Questions 8–9 resolve a genuine well-definedness problem — “the parity of the number of transpositions” presupposes that this parity does not depend on the factorization, exactly as $\Z/n\Z$ ’s operations required representative-independence in Definition 7.24.

25. The signature is a single $\{\pm1\}$ -valued computation, proved once to be well defined, and it does three jobs at once: internally, it cuts $\mathfrak S_n$ in half and isolates $\mathfrak A_n$ with its $3$ -cycle generators; externally, it decides in one line a question (“can these two tiles be swapped?”) that naive search could never settle, since no finite list of failed move sequences proves impossibility; and structurally, it is the alternating-sign engine inside the formula $\det A = \sum_\sigma \varepsilon(\sigma)\, a_{1\sigma(1)}\cdots a_{n\sigma(n)}$ of Chapter 22. The pattern — find a quantity conserved by every elementary move, compute it at the start and at the target — is the mathematician’s standard weapon against “is it possible?” questions, and it will return whenever a group acts on a set of states.

7.1 Laws of composition

7.2 Groups

7.3 Rings and fields

7.4 The ring Z/nZ\Z/n\ZZ/nZ

7.5 Exercises

7.6 Problem: The symmetric group and the 8-puzzle

7.4 The ring $\Z/n\Z$