Proof of Lemma 1.2.11

We need to show \(\sigma_1(\sigma_2(l)) = \sigma_2(\sigma_1(l))\) for all \(l \in [n]\). If \(l \notin \{i_1, \ldots, i_m, j_1, \dots, j_k\}\), Then \(\sigma_1(l) = l = \sigma_2(l)\), so

If \(l \in \{j_1, \dots, j_k\}\), then \(\sigma_2(l) \in \{j_1, \dots, j_k\}\) and hence, since the subsets are disjoint, \(l\) and \(\sigma_2(l)\) are not in the set \(\{i_1 , i_2 , \dots i_m\}\). It follows that \(\sigma_1\) preserves \(l\) and \(\sigma_2(l)\), and thus

The case when \(l \in \{i_1, \dots, i_m\}\) is analogous.

Proof of Theorem 1.2.12

Fix a permutation \(\sigma\). The key idea is to look at the orbits of \(\sigma\): for each \(x \in [n]\), its orbit by \(\sigma\) is the subset of \([n]\) of the form

Notice that the orbits of two elements \(x\) and \(y\) are either the same orbit, which happens precisely when \(y \in O_x\), or disjoint. Since \([n]\) is a finite set, and \(\sigma\) is a bijection of \(\sigma\), we will eventually have \(\sigma^i(x) = \sigma^j(x)\) for some \(j > i\), but then

Thus we can find the smallest positive integer \(n_x\) such that \(\sigma^{n_x}(x)=x\). Now for each \(x \in [n]\), we consider the cycle

Now let \(S\) be a set of indices for the distinct \(\tau_x\), where note that we are not including the \(\tau_x\) that are \(1\)-cycles. We claim that we can factor \(\sigma\) as

To show this, consider any \(x \in [n]\). It must be of the form \(\sigma^j(i)\) for some \(i \in S\), given that our choice of \(S\) was exhaustive. On the right hand side, only \(\tau_i\) moves \(x\), and indeed by definition of \(\tau_i\) we have

This proves that

As for uniqueness, note that if \(\sigma = \tau_1 \cdots \tau_s\) is a product of disjoint cycles, then each \(x \in [n]\) is moved by at most one of the cycles \(\tau_i\), since the cycles are all disjoint. Fix \(i\) such that \(\tau_i\) moves \(x\). We claim that

This will show that our product of disjoint cycles giving \(\sigma\) is the same (unique) product we constructed above. To do this, note that we do know that there is some integer \(s\) such that \(\tau_x^s(x) = e\), and

Thus we need only to prove that

for all integers \(k \geqslant 1\). Now by the Theorem, disjoint cycles commute, and thus for each integer \(k \geqslant 1\) we have

But \(\tau_j\) fixes \(x\) whenever \(j \neq i\), so

We conclude that the integer \(n_x\) we defined before is the length of the cycle \(\tau_i\), and that

Thus this decomposition of \(\sigma\) as a product of disjoint cycles is the same decomposition we described above.

Proof of Corollary 1.2.18

Given any permutation, we can decompose it as a product of cycles by the Theorem. Thus it suffices to show that each cycle can be written as a product of permutations. For a cycle \((i_1 \, i_2 \, \cdots \, i_p)\), one can show that

which we leave as an exercise.

Proof of Theorem 1.2.22

Suppose that \(\sigma\) is a permutation that can be written as a production of transpositions \(\beta_i\) and \(\lambda_j\) in two ways,

where \(s\) is even and \(t\) is odd. As we noted in Exercise 1.2.21, every transposition is its own inverse, so we conclude that

which is a product of \(s+t\) transpositions. This is an odd number, so it suffices to show that it is not possible to write the identity as a product of an odd number of transpositions.

Suppose the identity can be written as the product \((a_1 b_1) \cdots (a_k b_k)\), where each \(a_i \neq b_i\). A single transposition \emph{cannot} be the identity, and thus \(k \neq 1\). So assume, for the sake of an argument by induction, that for a fixed \(k\), we know that every product of fewer than \(k\) transpositions that equals the identity must use an even number of transpositions. Since \(2\) is even, we might as well assume \(k \geqslant 3\). Now note that since \(k > 1\), and our product is the identity, then some transposition \((a_i b_i)\) with \(i > 1\) must move \(a_1\); otherwise, \(b_1\) would be sent to \(a_1\), and our product would not be the identity.

Of all the possible ways we can write the identity as a product of \(k\) many transpositions \((a_1 b_1) \cdots (a_k b_k)\) with \(a_1 = a\) and \(b_1 = b\) fixed, choose one where the number \(N\) of times that \(a_1\) appears in one of the transpositions is smallest. The two rules in Exercise 1.2.21 allow us to rewrite the overall product without changing the number of transpositions in such a way that the transposition \((a_2 b_2)\) moves \(a_1\), meaning \(a_2 = a_1\) or \(b_2=a_1\). So let us assume that our product of transpositions has already been put in this form. Note also that \((a_i b_i) = (b_i a_i)\), so we might as well assume without loss of generality that \(a_2 = a_1\).

Case 1: When \(b_1 = b_2\), our product is

but \((a_1 b_1) (a_1 b_1)\) is the identity, so we can rewrite our product using only \(k-2\) transpositions. By induction hypothesis, \(k-2\) is even, and thus \(k\) is even.

Case 2: When \(b_1 \neq b_2\), we can use Exercise 1.2.21 to write

Notice here that it matters that \(a_1\), \(b_1\), and \(b_2\) are all distinct, so that we can apply Exercise 1.2.21. So our product, which equals the identity, is

The advantage of this shuffling is that while we have only changed the first two transpositions, we have decreased the number \(N\) of transpositions that move \(a_1\). But this contradicts our choice of \(N\) to be smallest possible.

Proof of Theorem 1.3.12

First, we show that \(D_n\) has order at most \(2n\). Any element \(\sigma \in D_n\) takes the polygon \(P_n\) to itself, and must in particular send vertices to vertices and preserve adjacencies, meaning that any two adjacent vertices remain adjacent after applying \(\sigma\). Fix two adjacent vertices \(A\) and \(B\). By Lemma 1.3.5, the location of every other point \(P\) on the polygon after applying \(\sigma\) is completely determined by the locations of \(\sigma(A)\) and \(\sigma(B)\). There are \(n\) distinct possibilities for \(\sigma(A)\), since it must be one of the \(n\) vertices of the polygon. But once \(\sigma(A)\) is fixed, \(\sigma(B)\) must be a vertex adjacent to \(\sigma(B)\), so there are at most \(2\) possibilities for \(\sigma(B)\). This gives us at most \(2n\) elements in \(D_n\).

Now we need only to present \(2n\) distinct elements in \(D_n\). We have described \(n\) reflections and \(n\) rotations for \(D_n\); we need only to see that they are all distinct. First, note that the only rotation that fixes any vertices of \(P_n\) is the identity. Moreover, if we label the vertices of \(P_n\) in order with \(1, 2, \ldots, n\), say by starting in a fixed vertex and going counterclockwise through each adjacent vertex, then the rotation by an angle of \(\frac{2 \pi i}{n}\) sends \(V_{1}\) to \(V_{i+1}\) for each \(i \lt n \), showing these \(n\) rotations are distinct. Now when \(n\) is odd, each of the \(n\) reflections fixes exactly one vertex, and so they are all distinct and disjoint from the rotations. Finally, when \(n\) is even, we have two kinds of reflections to consider. The reflections through a line connecting opposite vertices have exactly two fixed vertices, and are completely determined by which two vertices are fixed; since rotations have no fixed points, none of these matches any of the rotations we have already considered. The other reflections, the ones through the midpoint of two opposite sides, are completely determined by (one of) the two pairs of adjacent vertices that they switch. No rotation switches two adjacent vertices, and thus these give us brand new elements of \(D_n\).

In both cases, we have a total of \(2n\) distinct elements of \(D_n\) given by the \(n\) rotations and the \(n\) reflections.

Proof of Lemma 1.3.16

First, we claim that \(rs\) is a reflection. To see this, observe that \(s(V_1) = V_1\), so

and

This shows that \(rs\) must be a reflection, since it reverses orientation. Reflections have order \(2\), so \(rsrs = (rs)^2 = \mathrm{id}\) and hence \(srs = r^{-1}.\)

Proof of Theorem 1.3.19

Let \(\alpha\) be an arbitrary symmetry of \(P_n\). Note \(\alpha\) must fix the origin, since it is the center of mass of \(P_n\), and it must send each vertex to a vertex because the vertices are the points on \(P_n\) at largest distance from the origin. Thus \(\alpha(V_1) = V_ j\) for some \(1 \leqslant j \leqslant n\) and therefore the element \(r^{-j}\alpha\) fixes \(V_1\) and the origin. The only elements that fix \(V_1\) are the identity and \(s\). Hence either \(r^{-j}\alpha = \mathrm{id}\) or \(r^{-j}\alpha = s\). We conclude that \(\alpha = r^j\) or \(\alpha = r^js\).

Notice that we have shown that \(D_n\) has exactly \(2n\) elements, and that there are \(2n\) distinct expressions of the form \(r^j\) or \(r^js\) for \(0 \leqslant j \leqslant n-1\). Thus each element of \(D_n\) can be written in this form in a unique way.

Proof of Theorem 1.3.22

Theorem 1.3.19 shows that \(\{r,s\}\) is a set of generators for \(D_n\). Moreover, we also know that the relations listed above \(r^n = 1, s^2 = 1, srs^{-1} = r^{-1}\) hold; the first two are easy to check, and the last one is Lemma 1.3.16. The only concern we need to deal with is that we may not have discovered all the relations of \(D_n\); or rather, we need to check that we have found enough relations so that any other valid relation follows as a consequence of the ones listed.

Let

Assume that \(D_n\) has more relations than \(X_{2n}\) does. Then \(D_n\) would be a group of cardinality strictly smaller than \(X_{2n}\), meaning that \(|D_n|<|X_{2n}|\). This will become more clear once we properly define presentations. We will show below that in fact \(|X_{2n}|\leqslant 2n=|D_n|\), thus obtaining a contradiction.

Now we show that \(X_{2n}\) has at most \(2n\) elements using just the information contained in the presentation. By definition, since \(r\) and \(s\) generated \(X_{2n}\) then every element \(x\in X_{2n}\) can be written as

for some \(j\) and (possibly negative) integers \(m_1, \dots, m_j, n_1, \dots, m_j\).Note that, \(m_1\) could be \(0\), so that expressions beginning with a power of \(s\) are included in this list. As a consequence of the last relation, we have

and its not hard to see that this implies

for all \(m\). Thus, we can slide an \(s\) past a power of \(r\), at the cost of changing the sign of the power. Doing this repeatedly gives that we can rewrite \(x\) as

By the first relation, \(r^n = 1\), from which it follows that \(r^a = r^b\) if \(a\) and \(b\) are congruent modulo \(n\). Thus we may assume \(0 \leqslant M \leqslant n-1.\) Likewise, we may assume \(0 \leqslant N \leqslant 1\). This gives a total of at most \(2n\) elements, and we conclude that \(X_{2n}\) must in fact be \(D_n.\)

Proof of Claim 1.4.2

By using the property \(f(xy)=f(x)f(y)\) as well as associativity of multiplication in \(\mathrm{GL}_2(\mathbb{C})\) (marked by \(*\)) we obtain

Since \(f\) is injective and \(f((xy)z)=f(x(yz))\), we deduce \((xy)z=x(yz)\).

Proof of Lemma 1.5.7

By definition, \[ f(e_G)f(e_G) = f(e_Ge_G) = f(e_G). \] Multiplying both sides by \(f(e_G)^{-1}\), we get \[ f(e_G) = e_H. \]

Now given any \(x \in G\), we have \[ f(x^{-1}) f(x) = f(x^{-1}x) = f(e) = e, \] and thus \(f(x^{-1}) = f(x)^{-1}\).

Proof of Lemma 1.5.12

First, note that \(e_G \in \ker f\) by Lemma 1.5.7. If \(f\) is injective, then \(e_G\) must be the only element that \(f\) sends to \(e_H\), and thus \(\ker(f) = \{ e_G \}\).

Now suppose \(\ker(f) = \{e_G\}\). If \(f(g) = f(h)\) for some \(g,h \in G\), then \[ f(h^{-1}g) = f(h^{-1})f(g) = f(h)^{-1}f(g) = e_H. \] But then \(h^{-1}g \in \ker(f)\), so we conclude that \(h^{-1}g = e_G\), and thus \(g = h\).

Proof of Lemma 1.5.14

(\(\Rightarrow\)) A function \(f: X \to Y\) between two sets is bijective if and only if it has an inverse, meaning that there is a function \(g: Y \to X\) such that \(f \circ g = \mathrm{id}_Y\) and \(g \circ f = \mathrm{id}_X\). Our definition of group isomorphism implies that this must hold for any isomorphism (and more!), as we noted in Remark 1.5.4.

(\(\Leftarrow\)) If \(f\) is bijective homomorphism, then as a function it has a set-theoretic two-sided inverse \(g\), as remarked in Remark 1.5.4. But we need to show that this inverse \(g\) is actually a homomorphism. For any \(x,y \in H\), we have

Since \(f\) is injective, we must have \(g(xy) = g(x)g(y)\). Thus \(g\) is a homomorphism, and \(f\) is an isomorphism.

Proof of Theorem 1.5.17

Let \(f\!:G\to H\) be any group isomorphism.

1. Since \(f\) is a bijection by Remark 1.5.4, we conclude that \(|G|=|H|\).
2. We wish to show that \(\{|x| \ | \ x\in G\}= \{|y| \ | \ y\in H\}\). (\(\subseteq\)) follows from Exercise 1.5.15: given any \(x\in G\), we have \(|x| = |f(x)|\), which is the order of an element in \(H\). (\(\supseteq\)) follows from the previous statement applied to the group isomorphism \(f^{-1}\): given any \(y\in H\), we have \(f^{-1}(y)\in G\) and \(|y| = |f^{-1}(y)|\) is the order of an element of \(G\).
3. For any \(y_1,y_2\in H\) there exist some \(x_1, x_2\in G\) such that \(f(x_i)=y_i\). Then we have \[ y_1y_2=f(x_1)f(x_2)=f(x_1x_2)\stackrel{*}{=}f(x_2x_1)=f(x_2)f(x_1)=y_2y_1, \] where \(*\) indicates the place where we used that \(G\) is abelian.
4. Exercise. The idea is to show \(f\) induces an isomorphism \(\mathcal{Z}(G)\cong \mathcal{Z}(H)\).
5. Exercise. Show that if \(S\) generates \(G\) then \(f(S)=\{f(s) \ | \ s\in S\}\) generates \(H\).\qedhere