Chapter 1 Groups

The cartesian product \(G\times H\) of two sets \(G\) and \(H\) is defined as the set \[ G\times H := \{(g,h) \mid g\in G, h\in H\}, \] consisting of all (ordered) pairs \((g,h)\) where \(g\in G\) and \(h\in H\). For example, \(\mathbb{R}^2 = \mathbb{R}\times \mathbb{R}\).

Definition 1.1

  1. A binary operation on a set \(G\) is a function \(G\times G\to G\) (from the cartesian product \(G\times G=\{(a,b)\mid a\in G, b\in G\}\) to \(G\)). We write \(a * b\) (or \(ab\), or \(a\circ b\), or \(a+b\)) for the image of the pair \((a,b)\in G\times G\) in \(G\) under this function.

  2. A group is a set \(G\) together with a binary operation \(G\times G\to G\), \((a,b)\mapsto a*b\) (which we usually refer to as “group operation”, or “group multiplication”, or just “multiplication”) such that the following axioms are satisfied:

    1. Associativity: For all \(a,b,c\in G\), we have \((a*b)*c = a*(b*c)\) in \(G\).

    2. Existence of the identity (or neutral) element: There exists \(e\in G\), such that for all \(a\in G\) we have \(e*a=a=a*e\).

    3. Existence of the right inverse: For every \(a\in G\) there exists \(b\in G\) such that \(a*b=e\).

  3. A group is called abelian (or commutative), if for all \(a,b\in G\) we have \(a*b=b*a\).

  4. A group is called finite if \(G\) has only finitely many elements; in this case its cardinality \(|G|\) is called the order of \(G\).

Example 1.2

  1. The usual addition \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\), \((m,n)\mapsto m+n\), defines a binary operation on \(\mathbb{N}\) (and so does multiplication), but subtraction does not, because for instance \(2-3=-1\not\in\mathbb{N}\).

  2. The sets \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}\) and \(\mathbb{C}\) together with addition as the binary operation are abelian groups. The sets \(\mathbb{Q}^*:=\mathbb{Q}\setminus\{0\}\), \(\mathbb{R}^*:=\mathbb{R}\setminus\{0\}\) and \(\mathbb{C}^*:=\mathbb{C}\setminus\{0\}\) together with multiplication as the binary operation are abelian groups.

  3. The set \(\mathbb{N}\) with addition is not a group, because, for example, there doesn’t exist a (right) inverse to \(1\in\mathbb{N}\). (In other words, the equation \(1+ ? =0\) has no solution in \(\mathbb{N}\).)

  4. For any \(n\in\mathbb{N}\), the set \(\mathbb{R}^n\) together with vector addition is a group. For any \(m,n\in\mathbb{N}\) the set \(M_{m\times n}(\mathbb{R})\) of real \(m\)–by–\(n\) matrices together with matrix addition is a group. For every \(n\in \mathbb{N}\), the set \(\mathrm{GL}_n(\mathbb{R})\) of invertible real \((n\times n)\)–matrices together with matrix multiplication is a group, called the general linear group. If \(n>1\), \(\mathrm{GL}_n(\mathbb{R})\) is not abelian: e.g. \[ \begin{pmatrix}1&1\\0&1\end{pmatrix}\cdot \begin{pmatrix}1&0\\1&1\end{pmatrix} = \begin{pmatrix}2&1\\1&1\end{pmatrix}, \quad \text{but} \quad \begin{pmatrix}1&0\\1&1\end{pmatrix}\cdot \begin{pmatrix}1&1\\0&1\end{pmatrix} = \begin{pmatrix}1&1\\1&2\end{pmatrix}. \]

Proposition 1.3 Let \(G\) be a group. Then:

  1. There exists precisely one identity element in \(G\).

  2. For every \(a\in G\) there exists precisely one right inverse (call it \(b\)) to \(a\), and this \(b\) is also a left inverse of \(a\) (meaning that we also have \(b*a=e\)). We write \(a^{-1}\) for this inverse of \(a\) (or \(-a\) if the group operation is “\(+\)”).

\(\)(a) Suppose \(e\) and \(e'\) are two identity elements in \(G\).
\(\implies\) \(e*e' = e\)  (because \(e'\) is an identity element)
   and \(e*e' = e'\)  (because \(e\) is an identity element)
\(\implies\) \(e=e'\).

\(\)(b) Let \(b\) be a right inverse of \(a\), and let \(c\) be a right inverse of \(b\).
\(\implies\) \(a*(b*c) = a*e\)  (because \(c\) is a right inverse of \(b\))
          \(= a\)  (because \(e\) is the identity element)
   and \(a*(b*c) = (a*b)*c\)  (by associativity)
          \(= e*c\)  (because \(b\) is a right inverse of \(a\))
          \(= c\)  (because \(e\) is the identity element)
\(\implies\) \(a=c\)
\(\implies\) \(b*a = b*c = e\).  (because \(c\) is a right inverse of \(b\))
In other words, \(b\) is also a left inverse of \(a\).
Suppose that \(b'\) is another right inverse of \(a\).
\(\implies\) \(b=b*e=b*(a*b')=(b*a)*b' = e*b' = b'\).
(These equalities hold by: definition of \(e\), definition of \(b'\), associativity, the fact we just proved, and by definition of \(e\), respectively.)

Proposition 1.4 Let \(G\) be a group.

  1. (Cancellation) If \(a,b,z\in G\) and \(a*z=b*z\) (or \(z*a=z*b\)), then \(a=b\).

  2. For all \(a\in G\) both the equation \(a*x=b\) and \(y*a=b\) have a unique solution in \(G\). (Another way to say this: for every \(a\in G\), both the map \(G\to G\), \(x\mapsto a*x\) (called left translation by \(a\)) and \(G\to G\), \(y\mapsto y*a\) (called right translation by \(a\)) are bijective.)

  3. For every \(a\in G\) we have \((a^{-1})^{-1}=a\).

  4. For all \(a,b\in G\) we have \((a*b)^{-1}=b^{-1}*a^{-1}\).

  5. (Exponential laws) For any \(m\in \mathbb{Z}\) and \(a\in G\), we define: \[ {\color{red}{a^m}} := \begin{cases} \underbrace{a*a*\cdots*a}_{m\text{ times}} & \text{if }m>0;\\ e & \text{if }m=0;\\ (a^{-1})^{|m|} & \text{if }m<0. \end{cases} \] (In additive notation, i.e. when the group operation is “+”, we write \(ma\) instead of \(a^m\).)
    Then for all \(m,n\in\mathbb{Z}\) and \(a\in G\) we have \(a^{m+n}=a^m * a^n\) and \(a^{mn}=(a^m)^n\).
    If \(a,b\in G\) commute (i.e. \(a*b=b*a\)), then for all \(m\in\mathbb{Z}\) we have \((a*b)^m = a^m*b^m\).

  1. Multiply both sides of the equation by \(z^{-1}\).

  2. Proof of the “another way”: Injectivity: use (a).
    Surjectivity: If \(b\in G\), then \(b*a^{-1}\) is mapped to \(b\) under the right translation by \(a\).

  3. Both \((a^{-1})^{-1}\) and \(a\) are solutions of the equation \(a^{-1}*x=e\) (see Proposition 1.3 (b)). Now apply (b).

  4. We have \((a*b)*(b^{-1}*a^{-1}) = a*(b*(b^{-1}*a^{-1})) = a*((b*b^{-1})*a^{-1})\) \(= a*(e*a^{-1})\) \(=a*a^{-1} = e\). \(\implies\) \(b^{-1}*a^{-1}\) is a right inverse to \(a*b\).

\(\)   (e) Left as an exercise.

Example 1.5

  1. The group table of a finite group \(G=\{a_1,a_2,\dots,a_n\}\) is a table like this: \[ \begin{array}{c|ccc} \ast & \cdots & a_j & \cdots \\ \hline \vdots & \ddots & \vdots & \\ a_i & \cdots & a_i*a_j & \cdots\\ \vdots & & \vdots & \end{array} \] The trivial group is the group with exactly one element, say \(e\). Its group table must be \[ \begin{array}{c|c} * & e \\ \hline e & e\end{array} \] Any group with two elements, say \(e\) and \(a\), is given by the group table: \[ \begin{array}{c|cc} * & e & a \\ \hline e & e & a \\ a & a & e\end{array} \] Any group with three elements, say \(e, a\) and \(b\), must have group table: \[ \begin{array}{c|ccc} * & e & a & b \\ \hline e & e & a & b \\ a & a & b & e \\ b & b & e & a\end{array} \] (Note that \(a*b=a\) would imply \(b=e\) by 1.4(a).) There are two “essentially different” groups of order 4.
    Note that Proposition 1.4(b) implies that group tables must satisfy “sudoku rules”, i.e. that every group element must appear in each row and each column exactly once. However, not every table obeying this rule is a group table of a group; for example the table below does not. Why? (Hint: what is \(a*a*b\)?) \[ \begin{array}{ccccc} e&a&b&c&d\\ a&e&c&d&b\\ b&c&d&e&a\\ c&d&a&b&e\\ d&b&e&a&c \end{array} \]

  2. Let \(m\in\mathbb{N}\) and define \(C_m\) \(:=\{\overline{0},\overline{1},\dots,\overline{m-1}\}\). Define a binary operation on the set \(C_m\) by: \[ \overline{x} \oplus \overline{y} := \begin{cases} \overline{x+y} & \text{if }x+y<m;\\ \overline{x+y-m} & \text{if }x+y\geq m. \end{cases} \] Then \(C_m\) together with \(\oplus\) is an abelian group called the cyclic group of order \(m\). (Caveat: these notes will use \(\oplus\) for the group operation on \(C_m\), to distinguish it from “\(+\)” between numbers. However it is very common to just use “\(+\)” for the operation on \(C_m\).)

Proof (that \(C_m\) is a group).
Associativity: Let \(x,y,z\in \{0,1,\dots,m-1\}\). Want to show \((\overline{x}\oplus\overline{y})\oplus\overline{z} = \overline{x} \oplus(\overline{y}\oplus\overline{z})\) in \(C_m\).

First case: Suppose that \(x+y+z<m\). Then also \(x+y<m\) and \(y+z<m\).
\(\implies\) LHS \(=\overline{x+y}\oplus\overline{z}\) \(=\overline{(x+y)+z}\) \(=\overline{x+(y+z)}\) \(=\overline{x}\oplus\overline{y+z}=\) RHS (using associativity of addition of integers).

Second case: Suppose \(m\leq x+y+z<2m\).
Subcase (i): Suppose \(x+y<m\).
\(\implies\) LHS \(=\overline{x+y}\oplus \overline{z}\) \(= \overline{x+y+z-m}\).
Subcase (ii): Suppose \(x+y \geq m\).
\(\implies\) LHS \(=\overline{x+y-m}\oplus\overline{z}\) \(= \overline{x+y+z-m}\).
Hence in both subcases we have LHS \(=\overline{x+y+z-m}\).
Similarly we obtain that also RHS \(=\overline{x+y+z-m} =\) LHS.

Third case: Suppose \(x+y+z\geq 2m\) \(\implies\) \(x+y\geq m\) and \(y+z\geq m\).
\(\implies\) LHS \(=\overline{x+y-m}\oplus\overline{z}\) \(=\overline{x+y+z-2m}\) (since \((x+y-m)+z \geq m\))
and RHS \(=\overline{x}\oplus\overline{y+z-m}\) \(=\overline{x+y+z-2m}\) (since \(x+(y+z-m)\geq m\)).
\(\implies\) LHS = RHS.

Identity element: \(\overline{0}\) is an identity element in \(C_m\), because for any \(\overline{x}\in C_m\) we have \(\overline{x}\oplus\overline{0}\) \(=\overline{x+0}\) \(=\overline{x}\) \(=\overline{0+x}\) \(=\overline{0}\oplus\overline{x}\).

Existence of right inverses: Let \(\overline{x}\in C_m\). If \(x\neq0\), then the inverse to \(\overline{x}\) is \(\overline{m-x}\in C_m\). If \(x=0\), then the inverse to \(\overline{x}=\overline{0}\) is \(\overline{0}\).  \(\square\)

  1. Let \(S\) be a set (such as \(S=\{1,2,\dots,n\}\) for some \(n\in\mathbb{N}\)) and let \(\mathrm{Sym}(S)\) denote the set of all bijective maps \(\pi : S\to S\), also called permutations of \(S\).
    For any \(\pi, \sigma\in \mathrm{Sym}(S)\), we denote \(\sigma\circ\pi\) their composition (as functions, so \((\sigma\circ\pi)(s) = \sigma(\pi(s))\) for all \(s\in S\)). This defines a binary operation on \(\mathrm{Sym}(S)\).
    Then \(\mathrm{Sym}(S)\) together with composition is a group, called the permutation group of \(S\) (or sometimes also the symmetric group of \(S\)).
    The identity element in \(\mathrm{Sym}(S)\) is the identity function (denoted \(\mathrm{id}_S\) or just \(\mathrm{id}\)), and the inverse of \(\pi\in\mathrm{Sym}(S)\) is the inverse function \(\pi^{-1}\) (as in Calculus I).
    If \(S=\{1,\dots,n\}\) for some \(n\in\mathbb{N}\), we write \(S_n\) for \(\mathrm{Sym}(S)\) and use the “table notation” to describe permutations \(\pi\in S_n\) as \(\left(\begin{smallmatrix}1&2&\cdots&n\\\pi(1)&\pi(2)&\cdots&\pi(n)\end{smallmatrix}\right)\). For example: \[\begin{align*} \begin{pmatrix}1&2&3&4\\3&1&2&4\end{pmatrix}^{-1} &= \begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}\quad\text{in }S_4,\\ \begin{pmatrix}1&2&3&4&5\\3&4&1&2&5\end{pmatrix}\circ \begin{pmatrix}1&2&3&4&5\\2&3&5&1&4\end{pmatrix} &= \begin{pmatrix}1&2&3&4&5\\4&1&5&3&2\end{pmatrix}\quad\text{in }S_5. \end{align*}\]

Definition 1.6 Let \(n\geq 1\) and \(s\leq n\). Let \(a_1, \dots, a_s\in\{1,\dots,n\}\) be pairwise distinct. The permutation \(\pi\in S_n\) such that \[\begin{gather*} \pi(a_1)=a_2,\quad \pi(a_2)=a_3,\quad \dots,\quad \pi(a_{s-1})=a_s,\quad \pi(a_s) = a_1,\\ \text{and}\quad \pi(a) = a \quad\text{ for }a\in\{1,\dots,n\}\setminus\{a_1,\dots,a_s\}, \end{gather*}\] is denoted by \(\langle a_1,\dots,a_s\rangle\). Any permutation of this form is called a cycle. If \(s=2\), it is called a transposition. The number \(s\) is called the length (or order) of the cycle.

For example, \(\langle 3,1,5,2\rangle=\begin{pmatrix}1&2&3&4&5&6\\5&3&1&4&2&6\end{pmatrix}\) in \(S_6\); and \(\langle 3,2\rangle = \begin{pmatrix}1&2&3&4\\1&3&2&4\end{pmatrix}\) in \(S_4\).

Proposition 1.7 Every permutation \(\sigma\in S_n\) is a composition of cycles.

Example 1.8

  1. Let \(\sigma=\left(\begin{array}{ccccccccccc}1&2&3&4&5&6&7&8&9&10&11\\ 2&5&6&9&1&4&10&11&3&7&8\end{array}\right)\in S_{11}\). Then \(\sigma = \langle 1,2,5\rangle\circ \langle 3,6,4,9\rangle \circ \langle 7,10\rangle\circ\langle 8,11\rangle\).

  2. Let \(\tau=\begin{pmatrix}1&2&3&4\\ 4&2&3&1\end{pmatrix}\in S_4\). Then \(\tau=\langle 1,4\rangle\).

General Recipe (which, with a bit of effort, can be turned into a proof of 1.7).
Denote by \(\sigma\in S_n\) the permutation that we want to write as a composition of cycles.
Start with some \(a\in\{1,\dots,n\}\) such that \(\sigma(a)\neq a\) (e.g. \(a:=1\)). (If there is no such \(a\) then \(\sigma=\mathrm{id}\) and we are done.)
Let \(m\in\mathbb{N}\), \(m>1\), be the smallest number such that \(\sigma^m(a)\in \{a,\sigma(a),\sigma^2(a),\dots,\sigma^{m-1}(a)\}\). (Actually then necessarily \(\sigma^m(a)=a\).)
Let \(\sigma_1\) be the cycle \(\sigma_1=\langle a,\sigma(a),\sigma^2(a),\dots,\sigma^{m-1}(a)\rangle\).
Now repeat the steps: take \(b\in\{1,\dots,n\}\setminus\{a,\sigma(a),\dots,\sigma^{m-1}(a)\}\) such that \(\sigma(b)\neq b\). Let \(l\in\mathbb{N}\), \(l>1\), be the smallest number such that \(\sigma^l(b)\in\{b,\sigma(b),\dots,\sigma^{l-1}(b)\}\). Let \(\sigma_2=\langle b,\sigma(b),\dots,\sigma^{l-1}(b)\rangle\).
Continuing in this way, we find a decomposition into cycles: \(\sigma=\sigma_1\circ \sigma_2\circ\cdots\).

Definition 1.9 Let \(n\geq 1\) and \(\sigma\in S_n\). We write \(\sigma=\sigma_1\circ\sigma_2\circ\cdots\) as a composition of cycles of lengths \(s_1,s_2,\dots\). Then the number \[ {\color{red}{\mathrm{sgn}(\sigma)}} := (-1)^{(s_1-1)+(s_2-1)+\cdots}\in\{\pm1\} \] is called the sign (or signum) of \(\sigma\).

For example, with \(\sigma\) as in 1.8(a), we have \(\mathrm{sgn}(\sigma)=(-1)^{2+3+1+1}=-1\).
We have \(\mathrm{sgn}(\mathrm{id})=1\), and if \(\tau\) is any transposition, then \(\mathrm{sgn}(\tau)=-1\).

Theorem 1.10

  1. The definition of \(\mathrm{sgn}(\sigma)\) does not depend on the chosen cycle decomposition of \(\sigma\).

  2. For all \(\sigma,\tau\in S_n\) we have \(\mathrm{sgn}(\sigma\circ\tau)=\mathrm{sgn}(\sigma)\cdot\mathrm{sgn}(\tau)\).

In Group Theory in Year 2. (But for one possible proof for (a), see also an optional problem on one of the Courseworks.)