Let \(M\) be a monoid with identity \(e\), and define
\[ M^{\times} = \{u \in M : u \text{ is invertible}\}. \]Then \(M^{\times}\) is a group under the operation inherited from \(M\).
Proof: First, \(e \in M^{\times}\), since \(e*e = e\). Thus \(M^{\times}\) is nonempty. Associativity is inherited from \(M\). Let \(u, v \in M^{\times}\). We show that \(u*v\) is invertible. Using associativity,
\[ (u*v)*(v^{-1}*u^{-1}) = u*(v*v^{-1})*u^{-1} = u*e*u^{-1} = e, \]and similarly \((v^{-1}*u^{-1})*(u*v) = e\). Hence \(u*v \in M^{\times}\) and \((u*v)^{-1} = v^{-1}*u^{-1}\). Finally, if \(u \in M^{\times}\), then \(u^{-1} \in M^{\times}\) because \(u\) is an inverse of \(u^{-1}\). Thus the restricted operation satisfies all group axioms on \(M^{\times}\). ∎
Example: For the multiplicative matrix monoid \(M_{n}(F)\), \(M_{n}(F)^{\times} = GL_{n}(F)\).
Let \(G\) be a group and let \(a, x, y \in G\).
- If \(ax = ay\), then \(x = y\).
- If \(xa = ya\), then \(x = y\).
Proof: If \(ax = ay\), multiply both sides on the left by \(a^{-1}\). Then \(a^{-1}(ax) = a^{-1}(ay)\). Associativity and the inverse and identity laws give
\[ (a^{-1}a)x = (a^{-1}a)y, \quad ex = ey, \quad x = y. \]The proof of right cancellation is analogous but uses multiplication on the right by \(a^{-1}\): \((xa)a^{-1} = (ya)a^{-1} \Rightarrow x = y\). ∎
Let \(G\) be a group and let \(a, b \in G\).
- The equation \(ax = b\) has the unique solution \(x = a^{-1}b\).
- The equation \(ya = b\) has the unique solution \(y = ba^{-1}\).
Proof: If \(ax = b\), left multiplication by \(a^{-1}\) gives \(x = a^{-1}b\). Conversely,
\[ a(a^{-1}b) = (aa^{-1})b = eb = b, \]so this element is indeed a solution. If \(x_{1}, x_{2}\) are both solutions, then \(ax_{1} = b = ax_{2}\), and left cancellation gives \(x_{1} = x_{2}\). This proves existence and uniqueness. The second assertion is proved in the same way by right multiplication by \(a^{-1}\). ∎
For all \(x, y\) in a group \(G\),
\[ (xy)^{-1} = y^{-1}x^{-1}. \]Proof: We verify that \(y^{-1}x^{-1}\) is a two-sided inverse of \(xy\):
\[ (xy)(y^{-1}x^{-1}) = x(yy^{-1})x^{-1} = xex^{-1} = e \]and
\[ (y^{-1}x^{-1})(xy) = y^{-1}(x^{-1}x)y = y^{-1}ey = e. \]By uniqueness of inverses, it must equal \((xy)^{-1}\). ∎
Corollary: For every \(x \in G\), \((x^{-1})^{-1} = x\).
Proof: The equations \(x^{-1}x = e = xx^{-1}\) show that \(x\) is an inverse of \(x^{-1}\). By uniqueness of inverses, \((x^{-1})^{-1} = x\). ∎
A group \(G\) is cyclic if there exists an element \(g \in G\) such that
\[ G = \{g^{m} : m \in \mathbb{Z}\}. \]In that case we write \(G = \langle g \rangle\) and call \(g\) a generator of \(G\). For an additive group the notation means
\[ G = \{mg : m \in \mathbb{Z}\}. \]Thus \((\mathbb{Z}, +) = \langle 1 \rangle = \langle -1 \rangle\).
Let \(n \ge 1\) be an integer, and let \(\mathbb{Z}/n\mathbb{Z} = \{0, 1, 2, \dots, n-1\}\). Define a binary operation \(\oplus\) on \(\mathbb{Z}/n\mathbb{Z}\) by
\[ a \oplus b = \text{the unique element } r \in \{0, 1, \dots, n-1\} \text{ such that } r \equiv a+b \pmod n. \]Thus \(\oplus\) is addition modulo \(n\). For example, in \(\mathbb{Z}/5\mathbb{Z}\), \(3 \oplus 4 = 2\), since \(3+4 = 7 \equiv 2 \pmod 5\).
We verify that \((\mathbb{Z}/n\mathbb{Z}, \oplus)\) is an abelian group. First, \(\oplus\) is well defined: for every \(a, b \in \mathbb{Z}/n\mathbb{Z}\), the division algorithm guarantees that there exists a unique \(r \in \{0, 1, \dots, n-1\}\) such that \(a+b \equiv r \pmod n\). Hence \(a \oplus b \in \mathbb{Z}/n\mathbb{Z}\).
The operation is associative. Indeed, for \(a,b,c \in \mathbb{Z}/n\mathbb{Z}\),
\[ (a \oplus b) \oplus c \equiv (a+b)+c \equiv a+(b+c) \equiv a \oplus (b \oplus c) \pmod n. \]Both \((a \oplus b) \oplus c\) and \(a \oplus (b \oplus c)\) belong to \(\{0, 1, \dots, n-1\}\), and two elements of this set that are congruent modulo \(n\) must be equal. Therefore \((a \oplus b) \oplus c = a \oplus (b \oplus c)\).
The identity element is \(0\). Every element has an inverse. The inverse of \(0\) is \(0\). If \(1 \le a \le n-1\), then \(n-a \in \mathbb{Z}/n\mathbb{Z}\) and \(a \oplus (n-a) = 0\), because \(a+(n-a) = n \equiv 0 \pmod n\).
Finally, \(\oplus\) is commutative, since \(a \oplus b \equiv a+b = b+a \equiv b \oplus a \pmod n\), and hence \(a \oplus b = b \oplus a\). Therefore \((\mathbb{Z}/n\mathbb{Z}, \oplus)\) is an abelian group, called the group of integers modulo \(n\) under addition.
Every cyclic group is abelian.
Proof: Let \(G = \langle g \rangle\), and let \(x, y \in G\). By the definition of a cyclic group, there exist \(m, n \in \mathbb{Z}\) such that \(x = g^{m}\) and \(y = g^{n}\). Therefore
\[ xy = g^{m}g^{n} = g^{m+n} = g^{n+m} = g^{n}g^{m} = yx. \]Since \(x\) and \(y\) were arbitrary, \(G\) is abelian. ∎
Let
\[ V_{4} = \{(0,0), (1,0), (0,1), (1,1)\}, \]with componentwise addition modulo 2:
\[ (a,b) + (c,d) = ((a+c) \pmod 2, (b+d) \pmod 2). \]The operation is associative and commutative because addition modulo 2 is. The identity is \((0,0)\), and every element is its own inverse. Hence \(V_{4}\) is an abelian group. It is not cyclic: each nonidentity element \(x\) satisfies \(x+x = (0,0)\), so the subgroup generated by \(x\) contains only \((0,0)\) and \(x\), not all four elements.
Let \(F\) be a field.
The general linear group is
\[ GL_{n}(F) = \{A \in M_{n}(F) : \det A \ne 0\}, \]with matrix multiplication.
If \(A, B \in GL_{n}(F)\) then \(\det(AB) = \det(A)\det(B) \ne 0\), so \(AB \in GL_{n}(F)\). Matrix multiplication is associative, \(I_{n}\) lies in \(GL_{n}(F)\), and every \(A \in GL_{n}(F)\) has a matrix inverse \(A^{-1}\), which is again invertible. Thus \(GL_{n}(F)\) is a group.
In \(GL_{2}(\mathbb{R})\) let
\[ A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. \]Both determinants are 1, so \(A, B \in GL_{2}(\mathbb{R})\). Direct multiplication gives
\[ AB = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}, \quad BA = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}. \]Hence \(AB \ne BA\), so \(GL_{2}(\mathbb{R})\) is nonabelian.
The special linear group is
\[ SL_{n}(F) = \{A \in GL_{n}(F) : \det A = 1\}. \]This is itself a group. Indeed, if \(A, B \in SL_{n}(F)\) then \(\det(AB) = \det(A)\det(B) = 1\), so \(AB \in SL_{n}(F)\). Also \(I_{n} \in SL_{n}(F)\) and \(\det(A^{-1}) = \det(A)^{-1} = 1\), so \(A^{-1} \in SL_{n}(F)\).
Over \(\mathbb{R}\), define
\[ O_{n}(\mathbb{R}) = \{A \in GL_{n}(\mathbb{R}) : A^{T}A = I_{n}\}. \]If \(A, B \in O_{n}(\mathbb{R})\), then \((AB)^{T}(AB) = B^{T}A^{T}AB = B^{T}IB = I\), and \(A^{-1} = A^{T} \in O_{n}(\mathbb{R})\). Thus \(O_{n}(\mathbb{R})\) is a group. It is called the orthogonal group.
The set \(SO_{n}(\mathbb{R}) = \{A \in O_{n}(\mathbb{R}) : \det A = 1\}\) is also a group and is called the special orthogonal group.
Let
\[ I = \begin{pmatrix} i & 0 \\ 0 & -i \end{pmatrix}, \quad J = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}, \quad K = IJ = \begin{pmatrix} 0 & i \\ i & 0 \end{pmatrix}, \]where \(i^{2} = -1\) in \(\mathbb{C}\).
The quaternion group is
\[ Q_{8} = \{\pm I_{2}, \pm I, \pm J, \pm K\} \subseteq GL_{2}(\mathbb{C}), \]with matrix multiplication.
A direct calculation gives
\[ I^{2} = J^{2} = K^{2} = -I_{2}, \quad IJ = K, \quad JK = I, \quad KI = J, \]and reversing the order changes the sign:
\[ JI = -K, \quad KJ = -I, \quad IK = -J. \]These relations show that the set is closed under multiplication. Since the operation is matrix multiplication, it is associative. The identity is \(I_{2}\), and
\[ I^{-1} = -I, \quad J^{-1} = -J, \quad K^{-1} = -K, \]with the inverses of their negatives obtained similarly. Hence \(Q_{8}\) is a group. It is nonabelian because \(IJ = K\) but \(JI = -K\).
Usually, one writes the elements as \(\{\pm 1, \pm i, \pm j, \pm k\}\) and the relations as
\[ i^{2} = j^{2} = k^{2} = ijk = -1. \]Let \((G, *)\) and \((H, \circ)\) be groups. A function \(\varphi : G \longrightarrow H\) is a group homomorphism if, for all \(x, y \in G\),
\[ \varphi(x*y) = \varphi(x) \circ \varphi(y). \]When the operations are written multiplicatively, this becomes \(\varphi(xy) = \varphi(x)\varphi(y)\).
Let \(\varphi : G \rightarrow H\) be a group homomorphism. Then \(\varphi(e_{G}) = e_{H}\), \(\varphi(g^{-1}) = \varphi(g)^{-1}\) for every \(g \in G\), and
\[ \varphi(g^{m}) = \varphi(g)^{m} \]for every \(g \in G\) and every \(m \in \mathbb{Z}\).
Proof: First, \(\varphi(e_{G}) = \varphi(e_{G}e_{G}) = \varphi(e_{G})\varphi(e_{G})\). Multiplying on the left by \(\varphi(e_{G})^{-1}\) in \(H\) gives \(e_{H} = \varphi(e_{G})\).
Next, \(e_{H} = \varphi(e_{G}) = \varphi(gg^{-1}) = \varphi(g)\varphi(g^{-1})\). Thus \(\varphi(g^{-1})\) is an inverse of \(\varphi(g)\); by uniqueness of inverses, \(\varphi(g^{-1}) = \varphi(g)^{-1}\).
For \(m>0\), induction gives \(\varphi(g^{m}) = \varphi(g)^{m}\). The case \(m=0\) follows from the identity statement, and if \(m<0\), write \(m=-r\) with \(r>0\) and use
- Reduction modulo n: The map \(\varphi : \mathbb{Z} \longrightarrow \mathbb{Z}/n\mathbb{Z}\), \(\varphi(k) = k \pmod n\), is a homomorphism of additive groups because \[ \varphi(a+b) = (a+b) \pmod n = a \pmod n + b \pmod n = \varphi(a) + \varphi(b). \]
- Determinant: The map \(\det : GL_{n}(F) \longrightarrow F^{\times}\) is a group homomorphism because \(\det(AB) = \det(A)\det(B)\).
- Roots of unity: Let \(\mu_{n} = \{z \in \mathbb{C} : z^{n} = 1\}\). If \(z, w \in \mu_{n}\) then \((zw)^{n} = z^{n}w^{n} = 1\), so \(zw \in \mu_{n}\). Also \(1 \in \mu_{n}\), and \(z^{-1} \in \mu_{n}\) because \((z^{-1})^{n} = 1\). Thus \(\mu_{n}\) is a group under multiplication. Let \(\zeta = e^{2\pi i / n}\). Define \(\varphi : \mathbb{Z}/n\mathbb{Z} \longrightarrow \mu_{n}\), \(\varphi(k) = \zeta^{k}\). Then \(\varphi\) is a group homomorphism. Every \(n\)th root of unity is one of \(1, \zeta, \dots, \zeta^{n-1}\), and these are distinct, so \(\varphi\) is bijective.
A bijective group homomorphism \(\varphi : G \rightarrow H\) is an isomorphism. If such a map exists, we write \(G \cong H\) and say that \(G\) and \(H\) are isomorphic.
Thus the preceding roots-of-unity map proves \(\mathbb{Z}/n\mathbb{Z} \cong \mu_{n}\).
If \(\varphi : G \rightarrow H\) is an isomorphism, then the inverse function \(\varphi^{-1} : H \rightarrow G\) is also an isomorphism.
Proof: The inverse function exists and is bijective because \(\varphi\) is bijective. Let \(u, v \in H\). Because \(\varphi\) is surjective, choose \(x, y \in G\) with \(u = \varphi(x)\) and \(v = \varphi(y)\). Then \(uv = \varphi(x)\varphi(y) = \varphi(xy)\). Applying \(\varphi^{-1}\) gives
\[ \varphi^{-1}(uv) = xy = \varphi^{-1}(u)\varphi^{-1}(v). \]Therefore \(\varphi^{-1}\) is a homomorphism, hence an isomorphism. ∎
Let \(G\) be a group. A subset \(H \subseteq G\) is a subgroup of \(G\) if \(H\), equipped with the restriction of the group operation of \(G\), is itself a group. We write \(H \le G\).
Let \(G\) be a group and let \(H \subseteq G\) be nonempty. Then \(H \le G\) if and only if
\[ xy^{-1} \in H \]for all \(x, y \in H\).
Proof: Assume first that \(H \le G\). If \(x, y \in H\) then \(y^{-1} \in H\) because \(H\) is a group, and closure under multiplication gives \(xy^{-1} \in H\).
Conversely, suppose \(H\) is nonempty and satisfies the condition. Choose \(h \in H\). Setting \(x=y=h\) gives \(hh^{-1} = e \in H\). Now let \(y \in H\). Since \(e, y \in H\), the hypothesis gives \(ey^{-1} = y^{-1} \in H\). Finally, if \(x, y \in H\), we have just shown that \(y^{-1} \in H\). Applying the hypothesis to \(x\) and \(y^{-1}\) gives \(x(y^{-1})^{-1} = xy \in H\). Thus \(H\) contains the identity and is closed under products and inverses. Associativity is inherited from \(G\), so \(H \le G\). ∎
- For \(n \in \mathbb{Z}\), the set \(n\mathbb{Z} = \{nk : k \in \mathbb{Z}\}\) is a subgroup of \((\mathbb{Z}, +)\). It is nonempty because \(0 = n \cdot 0 \in n\mathbb{Z}\). If \(nx, ny \in n\mathbb{Z}\), then \(nx - ny = n(x-y) \in n\mathbb{Z}\). The additive version of the subgroup test therefore applies.
- The group \(SL_{n}(F)\) is a subgroup of \(GL_{n}(F)\). It is nonempty because \(I_{n} \in SL_{n}(F)\). If \(A, B \in SL_{n}(F)\), then \(\det(AB^{-1}) = \det(A)\det(B)^{-1} = 1\), so \(AB^{-1} \in SL_{n}(F)\). The subgroup test applies.
Let \(\{H_{i}\}_{i \in I}\) be a nonempty family of subgroups of a group \(G\). Then \(\bigcap_{i \in I} H_{i}\) is a subgroup of \(G\).
Proof: Each \(H_{i}\) contains \(e\), so the intersection is nonempty. If \(x, y \in \bigcap_{i \in I} H_{i}\), then \(x, y \in H_{i}\) for every \(i \in I\). Since each \(H_{i}\) is a subgroup, \(xy^{-1} \in H_{i}\) for every \(i\). Hence \(xy^{-1} \in \bigcap_{i \in I} H_{i}\). The subgroup test proves the claim. ∎
The union of two subgroups need not be a subgroup. For example, \(2\mathbb{Z} \cup 3\mathbb{Z}\) contains \(2\) and \(3\) but not \(2+3=5\).