Definition 10.1. Left Equivalence Modulo \(H\).
Assume \(G\) is a group and \(H \leq G\text{.}\) For all \(a,b \in G\text{,}\) we say \(a\) is left equivalent to \(b\) modulo \(H\) if \(a^{-1}b \in H\) and write \(a \equiv_\ell b \pmod{H}\text{.}\)
Chapter 10 Cosets and the Theorem of Lagrange
When we defined The Integers Modulo \(n\), we constructed an equivalence relation
\begin{equation*}
a \equiv b \iff \exists k \in \Z, -a + b = kn\text{.}
\end{equation*}
The set of all possible multiples of \(n\) is precisely the subgroup, \(n\Z \leq \Z\text{,}\) generated by the element \(n\text{.}\) This realization allows us to extend the relation to arbitrary subgroups.
Section 10.1 Left Cosets
Proposition 10.2. Left Equivalence Modulo \(H\) is an Equivalence Relation.
Assume \(G\) is a group and \(H \leq G\text{.}\) Left equivalence modulo \(H\) is an equivalence relation on \(G\text{.}\)
Proof.
Assume \(G\) is a group and \(H \leq G\text{.}\)
- Reflexive:
- Symmetric
- Let \(a,b \in G\) be given. Assume \(a \equiv_\ell b \pmod{H}\text{.}\) There exists \(h \in H\) such that \(a^{-1}b = h\text{.}\) Since \(H\) is a subgroup of \(G\)\begin{equation*} b^{-1} a = \left(a^{-1} b\right)^{-1} = h^{-1} \in H \end{equation*}implies \(b \equiv_\ell a \pmod{H}\text{.}\)
- Transitive
- Let \(a,b,c \in G\) be given. Assume \(a \equiv_\ell b \pmod{H}\) and \(b \equiv_\ell c \pmod{H}\text{.}\) There exist elements \(h_1, h_2 \in H\) that satisfy\begin{equation*} a^{-1} b = h_1 \quad\text{and}\quad b^{-1}c = h_2\text{.} \end{equation*}Since \(H \leq G\text{,}\)\begin{align*} a^{-1} c \amp= a^{-1} \left(bb^{-1}\right) c\\ \amp = \left(a^{-1} b\right) \left(b^{-1}c\right)\\ \amp = h_1 h_2 \in H \end{align*}implies \(a \equiv_\ell c \pmod{H}\text{.}\)
Therefore the relation
\begin{equation*}
a \equiv_\ell b \pmod{H} \iff a^{-1}b \in H
\end{equation*}
is an equivalence relation on \(G\text{.}\)
Definition 10.3. Left Coset.
Assume \(G\) is a group and \(H \leq G\text{.}\) For each element \(g \in G\text{,}\) define the left coset of \(H\) in \(G\) represented by \(g\) to be the left equivalence class of \(g\) modulo \(H\text{,}\)
\begin{equation*}
[g] = \left\{g^\prime \in G \;\middle\vert\; g \equiv_\ell g^\prime \pmod{H}\right\}\text{.}
\end{equation*}
Following the path laid out by \(\Z/n\Z\text{,}\) we are interested in studying the equivalence classes of these relations. We start with a familiar example from linear algebra. Our geometric intuition will help inform our expectations for the algebraic situation.
Example 10.4. Translation of Subspaces.
Consider the matrix transformation \(T \colon \R^4 \to \R^3\) defined by the \(3 \times 4\) matrix
\begin{equation*}
A = \begin{bmatrix}
1 \amp 3 \amp -1 \amp 2 \\
-2 \amp 0 \amp -4 \amp 2 \\
1 \amp 2 \amp 0 \amp 1
\end{bmatrix}
\sim
\begin{bmatrix}
1 \amp 0 \amp 2 \amp -1 \\
0 \amp 1 \amp -1 \amp 1 \\
0 \amp 0 \amp 0 \amp 0
\end{bmatrix}
\end{equation*}
Recall that \(\R^4\) and \(\R^3\) are both groups under addition and for vectors \(\mathbf{v}, \mathbf{w} \in \R^4\)
\begin{equation*}
T(\mathbf{v} + \mathbf{w}) = A(\mathbf{v} + \mathbf{w}) = A\mathbf{v} + A \mathbf{w} + T(\mathbf{v}) + T(\mathbf{w}).
\end{equation*}
This tells us \(T\) is a morphism of additive groups.
If \(x_1, x_2, x_3, x_4\) are the names of the coordinates for \(\R^4\text{,}\) then the reduced row echelon form of \(A\) tells us the kernel is the subspace of \(\R^4\) cut out by the equations
\begin{align*}
x_1 + 2x_3 - x_4 = 0 \amp\iff x_1 = -2x_3 + x_4\\
x_2 - x_3 + x_4 = 0 \amp\iff x_2 = x_3 - x_4
\end{align*}
and so the kernel is the plane
\begin{align*}
K \amp= \operatorname{Span}\left\{
\mathbf{k}_1 = \begin{bmatrix}-2\\1\\1\\0\end{bmatrix},
\mathbf{k}_2 = \begin{bmatrix}1\\-1\\0\\1\end{bmatrix}\right\} \\
\amp = \left\{x\mathbf{k}_2 + y \mathbf{k}_2 \;\middle\vert\; (x,y) \in \R^2\right\} \cong \R^2.
\end{align*}
To understand the left equivalence classes modulo \(K\) in \(\R^4\text{,}\) consider the point \((1,2,3,4)\text{.}\) If we take the vector
\begin{equation*}
\mathbf{b} = \begin{bmatrix}1\\2\\3\\4\end{bmatrix},
\end{equation*}
then the equivalence class of \(\mathbf{b}\) modulo \(K\) is precisely the set of vectors \(\mathbf{v} \in \R^4\) that satisfy
\begin{align*}
-\mathbf{b} + \mathbf{v}\in K \amp \iff -\mathbf{b} + \mathbf{v} = x\mathbf{k}_1 + y\mathbf{k}_2,\, \text{for some}\ (x,y) \in \R^2\\
\amp \iff \mathbf{v} = \mathbf{b} + x\mathbf{k}_1 + y\mathbf{k}_2.
\end{align*}
Hence the equivalence class of \(\mathbf{b}\) modulo \(K\) is simply the plane parallel to \(K\) that contains the point \((1,2,3,4)\)
\begin{equation*}
\left\{\mathbf{b} + x\mathbf{k}_2 + y\mathbf{k}_2 \;\middle\vert\; (x,y) \in \R^2\right\}.
\end{equation*}
In general, the left equivalence class of \(\mathbf{b} \in \R^4\) modulo \(K\) is simply the plane parallel to \(K\) that contains the vector \(\mathbf{b}\text{.}\) Since the elements of this set are all of the form \(\mathbf{b} + \mathbf{k}\text{,}\) where \(\mathbf{k} \in K\text{,}\) it is often convenient to use the shorthand \(\mathbf{b} + K\) for the equivalence class of \(\mathbf{b}\) modulo \(K\text{.}\)
Following our geometric intuition, we make the following definition.
Definition 10.5. Left Translate.
Assume \(G\) is a group and \(H \leq G\text{.}\) For all \(g \in G\text{,}\) the left translate of \(H\) by \(g\) is the set
\begin{equation*}
gH = \left\{gh \;\middle\vert\; h \in H\right\}\text{.}
\end{equation*}
Proposition 10.6.
Proof.
Let \(g \in G\) be given and assume \(g^\prime \in [g]\text{.}\) Since \(g \equiv_\ell g^\prime \pmod{H}\text{,}\) there exists \(h \in H\) such that \(g^{-1}g^\prime = h\) and thus \(g^\prime = gh \in gH\text{.}\) Hence \([g] \subseteq gH\text{.}\)
For the reverse inclusion, let \(g^\prime = g h \in g H\) be given. Since \(g^{-1}g^\prime = h \in H\text{,}\) \(g^\prime \equiv_\ell g \pmod{H}\) implies \(g^\prime \in [g]\text{.}\) Hence \(gH \subseteq [g]\text{.}\) Therefore \([g] = gH\text{.}\)
Remark 10.7.
Definition 10.8. Left Coset Space.
Assume \(G\) is a group and \(H \leq G\text{.}\) We call the quotient of \(G\) by left equivalence modulo \(H\) the left coset space
\begin{equation*}
G/H = \left\{gH \;\middle\vert\; g \in G\right\}\text{.}
\end{equation*}
Definition 10.9. Canonical Projection to the Quotient.
Assume \(G\) is a group. If \(H \leq G\text{,}\) then the morphism of sets
\begin{align*}
\pi \colon G \amp\to G/H\\
x \amp\mapsto xH
\end{align*}
is called the canonical projection to the quotient.
Proposition 10.10.
Assume \(G\) is a group and \(H \leq G\text{.}\) For every \(g \in G\text{,}\) the cardinality of \(g H\) is equal to the order of \(H\text{.}\)
Proof.
Let \(g \in G\) be given. For every \(h \in H\text{,}\) \(gh \in gH\text{.}\) This defines a morphism of sets
\begin{align*}
f_g \colon H \amp\to g H\\
x \amp \mapsto gx
\end{align*}
Similarly, we observe that for every \(gh \in gH\text{,}\) \(g^{-1}(gh) = h \in H\) and so we obtain a mapping
\begin{align*}
f_{g^{-1}} \colon gH \amp\to H\\
x \amp\mapsto g^{-1}x
\end{align*}
It suffices to prove these two functions are inverses of one another.
Let \(h \in H\) be given and compute
\begin{equation*}
f_{g^{-1}} \circ f_g(h) = f_{g^{-1}}(gh) = g^{-1}g h = h\text{.}
\end{equation*}
Hence \(f_{g^{-1}} \circ f_g = \id_H\text{.}\)
Similarly, let \(gh \in gH\) be given and compute
\begin{equation*}
f_g \circ f_{g^{-1}} (gh) = f_g(g^{-1}gh) = f_g(h) = gh\text{.}
\end{equation*}
Hence \(f_g \circ f_{g^{-1}} = \id_{gH}\text{.}\) Therefore for every \(g \in G\text{,}\) \(f_g \colon H \to gH\) is a bijection and thus \(H\) and \(gH\) have the same cardinality.
Proposition 10.11.
Assume \(G\) is a group and \(H \leq G\text{.}\) If \(h \in H\text{,}\) then \(h H = H\text{.}\) In particular, \(1_G H = H\) because \(H\) is a subgroup of \(G\text{.}\)
Proof.
Let \(h \in H\) be given. Since \(H\) is closed under the binary operation on \(G\text{,}\) it follows that
\begin{equation*}
hH = \left\{hx \;\middle\vert\; x \in H\right\} \subseteq H.
\end{equation*}
For the reverse inclusion, let \(a \in H\) be given. Then \(h^{-1}a \in H\) implies
\begin{equation*}
a = \left(hh^{-1}\right)a = h\left(h^{-1}a\right) \in hH\text{.}
\end{equation*}
Hence \(H \subseteq hH\text{.}\) Therefore \(H = hH.\)
Section 10.2 Right Cosets
In defining the relation \(a \equiv_\ell b \pmod{H}\text{,}\) we made the choice to place the inverse of \(b\) on the left-hand side. We could just as well have defined the relation
\begin{equation*}
a \equiv_r b \pmod{H} \iff ab^{-1} \in H\text{.}
\end{equation*}
In doing so, the results above translate directly, mutatis mutandis. We provide the definitions for the right cosets, right translates and right coset space, but leave the relevant results as an exercise for the reader.
Definition 10.12. Right Coset.
Assume \(G\) is a group and \(H \leq G\text{.}\) For each element \(g \in G\text{,}\) define the right coset of \(H\) in \(G\) represented by \(g\) to be the right equivalence class of \(g\) modulo \(H\text{,}\)
\begin{equation*}
[g] = \left\{g^\prime \in G \;\middle\vert\; g \equiv_r g^\prime \pmod{H}\right\}\text{.}
\end{equation*}
We call \(Hg\) the right coset of \(H\) in \(G\) represented by \(g\text{.}\)
Definition 10.13. Right Translate.
Assume \(G\) is a group and \(H \leq G\text{.}\) For each element \(g \in G\text{,}\) define the right translate of \(H\) by \(g\) to be the set
\begin{equation*}
Hg = \left\{hg \;\middle\vert\; h \in H\right\}\text{.}
\end{equation*}
Definition 10.14. Right Coset Space.
Assume \(G\) is a group and \(H \leq G\text{.}\) We call the quotient of \(G\) by right equivalence modulo \(H\) the right coset space
\begin{equation*}
H \backslash G = \left\{Hg \;\middle\vert\; g \in G\right\}\text{.}
\end{equation*}
Definition 10.15. Canonical Projection to the Quotient.
Assume \(G\) is a group. If \(H \leq G\text{,}\) then the morphism of sets
\begin{align*}
\pi \colon G \amp\to G/H\\
x \amp\mapsto xH
\end{align*}
is called the canonical projection to the quotient.
Section 10.3 Lagrange’s Theorem
Definition 10.16. Index.
Assume \(G\) is a group and \(H \leq G\text{.}\) The index of \(H\) in \(G\) is defined to be the number of distinct left cosets of \(H\) in \(G\text{.}\) We denote the index by \(\abs{G : H}\text{.}\)
Remark 10.17.
Note that we could just as well have defined the index to be the number of distinct right cosets of \(H\) in \(G\text{.}\) The following proposition shows this is immaterial.
Proposition 10.18.
Assume \(G\) is a group and \(H \leq G\text{.}\) The number of distinct right cosets of \(H\) in \(G\) is equal to \(\abs{G : H}\text{.}\)
Proof.
Let \(g \in G\) be given. Define the morphisms of sets
\begin{align*}
\varphi(g) \colon gH \amp\to Hg^{-1} \amp \psi(g) \colon H g \amp\to g^{-1} H \\
gh \amp\mapsto h^{-1}g^{-1} \amp hg \amp\mapsto g^{-1}h^{-1}
\end{align*}
For all \(h \in H\text{,}\)
\begin{align*}
\psi\left(g^{-1}\right) \circ \varphi(g)(g h)
\amp= \psi\left(g^{-1}\right)\left(h^{-1}g^{-1}\right)
= gh,\,\text{and}\\
\varphi(g) \circ \psi\left(g^{-1}\right)\left(hg^{-1}\right)
\amp= \varphi(g)\left(gh^{-1}\right)
= hg^{-1}.
\end{align*}
Hence for all \(g \in G\text{,}\) \(\varphi(g) \colon gH \to Hg^{-1}\) is a bijection with inverse \(\psi\left(g^{-1}\right)\text{.}\)
Let \(L = \left\{g H \;\middle\vert\; g \in G\right\}\) and \(R = \left\{H g \;\middle\vert\; g \in G\right\}\text{.}\) Define the morphisms of sets
\begin{align*}
\Phi \colon L \amp\to R \amp \psi \colon R \amp\to L\\
gH \amp \mapsto \varphi(g)(gH) \amp Hg \amp\mapsto \psi(g)(Hg)
\end{align*}
For all \(g \in G\text{,}\)
\begin{align*}
\Psi \circ \Phi(g H)
\amp= \Psi\left(\varphi(g)(gH)\right)
= \Psi\left(Hg^{-1}\right)
= \psi\left(g^{-1}\right)\left(Hg^{-1}\right)
= gH,\,\text{and}\\
\Phi \circ \Psi(H g)
\amp = \Phi\left(\psi(g)(Hg)\right)
= \Phi(g^{-1}H)
= \varphi\left(g^{-1}\right)\left(g^{-1}H\right)
= H g.
\end{align*}
Therefore \(\Phi\) is a bijection and \(\abs{G : H} = \abs{L} = \abs{R}\text{.}\)
Theorem 10.19. Lagrange’s Theorem.
Assume \(G\) is a finite group and \(H \leq G\text{.}\) The order of \(H\) divides the order of \(G\text{.}\) In particular,
\begin{equation*}
\abs{G} = \abs{G : H} \abs{H}.
\end{equation*}
Proof.
Let \(m = \abs{G : H}\) be the number of distinct cosets of \(H\) in \(G\text{.}\) Since left equivalence modulo \(H\) is an equivalence relation on \(G\text{,}\) there exist \(g_1, g_2, \ldots, g_m \in G\) such that \(g_1H,\, g_2H,\, \ldots,\, g_mH\) are the distinct equivalence classes for this relation. These cosets partition the set \(G\)
\begin{equation*}
G = \bigsqcup_{i = 1}^m g_i H.
\end{equation*}
Each coset has \(\abs{H}\) elements by Proposition 10.10, hence
\begin{equation*}
\abs{G} = \sum_{i = 1}^m \abs{g_i H} = \sum_{i=1}^m \abs{H} = m\abs{H} = \abs{G : H} \abs{H}.
\end{equation*}
Therefore the order of \(H\) divides the order of \(G\text{.}\)
Corollary 10.20. Groups of Prime Order are Cyclic.
Proof.
Since \(1 \lt p\text{,}\) there exists \(g \in G\) such that \(g \neq 1.\) By Lagrange’s Theorem, the order of \(\langle g \rangle\) is a divisor of \(p\text{.}\) Since \(g \neq 1\text{,}\) it follows that \(\langle g \rangle = G\text{.}\) Therefore \(G\) is cyclic and any non-identity element is a generator.
Theorem 10.21.
Assume \(G\) is a finite group. If \(K \leq H \leq G\text{,}\) then
\begin{equation*}
\abs{G : K} = \abs{G : H}\abs{H : K}
\end{equation*}
Proof.
Define the surjective function
\begin{align*}
\phi \colon G/K \amp\to G/H\\
xK \amp\mapsto xH
\end{align*}
To see this function is well-defined, assume
\begin{equation*}
x_1K = x_2K \iff x_1^{-1}x_2 \in K \leq H\text{.}
\end{equation*}
Hence \(\phi(x_1K) = x_1H = x_2H = \phi(x_2K)\text{.}\)
Since \(\phi\) is a function, we note that if \(y_1H \neq y_2H\text{,}\) then \(\phi^{-1}(y_1H) \cap \phi^{-1}(y_2H) = \emptyset\text{.}\) If \(y_1H, \ldots, y_rH\) are the distinct elements of \(G/H\text{,}\) then we can write
\begin{equation*}
G/K = \bigsqcup_{i=1}^r \phi^{-1}(y_iH)\text{.}
\end{equation*}
Hence it suffices to prove that for all \(yH \in G/H\text{,}\) there is a bijection \(H/K \to \phi^{-1}(yH)\text{,}\) for then
\begin{align*}
\abs{G : K} \amp= \abs{G/K}\\
\amp= \sum_{i=1}^r \abs{\phi^{-1}(y_iH)}\\
\amp= \sum_{i=1}^r \abs{H/K}\\
\amp= r\abs{H/K}\\
\amp= \abs{G:H}\abs{H:K}\text{.}
\end{align*}
Let \(yH \in G/H\) be given. Define the function
\begin{align*}
\psi \colon H/K \amp\to \phi^{-1}(yH)\\
xK \amp\mapsto (yx)K\text{.}
\end{align*}
To see this function is well-defined and injective it suffices to observe that
\begin{align*}
x_1K = x_2K \amp\iff x_1^{-1}x_2 \in K\\
\amp\iff x_1^{-1}(y^{-1}y)x_2 \in K\\
\amp\iff (yx_1)^{-1}(yx_2) \in K\\
\amp\iff (yx_1)K = (yx_2)K\\
\amp\iff \psi(x_1H) = \psi(x_2H)\text{.}
\end{align*}
To see that \(\psi\) is surjective, let \(xK \in \phi^{-1}(yH)\) be given. Observe that
\begin{equation*}
yH = \phi(xK) = xH \iff y^{-1}x \in H
\end{equation*}
implies
\begin{equation*}
\psi\left(y^{-1}xK\right) = \left(y\left(y^{-1}x\right)\right)H = xH\text{.}
\end{equation*}
Therefore \(\psi\) is a bijection and thus
\begin{equation*}
\abs{G:K} = \abs{G:H}\abs{H:K}\text{.}
\end{equation*}
Exercises 10.4 Exercises for Undergrads & Grads
1.
Assume \(G\) is a group and \(H \leq G\text{.}\) Prove the relation
\begin{equation*}
a \equiv_r b \pmod{H} \iff a b^{-1} \in H
\end{equation*}
is an equivalence relation on \(G\text{.}\)
Solution.
We must prove the relation is reflexive, symmetric, and transitive.
- Reflexive:
- For any element \(g \in G\text{,}\) \(g g^{-1} = e \in H\) implies \(g \equiv_r g \pmod{H}\text{.}\)
- Symmetric
- If \(a \equiv_r b \pmod{H}\text{,}\) then there exists an element \(h \in H\) that satisfies \(ab^{-1} = h\text{.}\) Since \(H\) is a subgroup of \(G\)\begin{equation*} b a^{-1} = \left(a b^{-1}\right)^{-1} = h^{-1} \in H \end{equation*}implies \(b \equiv_r a \pmod{H}\text{.}\)
- Transitive
- If \(a \equiv_r b \pmod{H}\) and \(b \equiv_r c \pmod{H}\text{,}\) then there exist elements \(h_1, h_2 \in H\) that satisfy\begin{equation*} a b^{-1} = h_1 \quad\text{and}\quad b c^{-1} = h_2. \end{equation*}Since \(H\) is a subgroup\begin{align*} a c^{-1} \amp= a e c^{-1}\\ \amp = a \left(b^{-1} b\right) c^{-1}\\ \amp = \left(a b^{-1}\right) \left(b c^{-1}\right)\\ \amp = h_1 h_2 \in H \end{align*}implies \(a \equiv_r c \pmod{H}\text{.}\)
Therefore the relation
\begin{equation*}
a \equiv_r b \pmod{H} \iff a b^{-1} \in H
\end{equation*}
is an equivalence relation on \(G\text{.}\)
2.
Assume \(G\) is a group and \(H \leq G\text{.}\) Prove that for all \(g \in G\text{,}\) the right coset of \(H\) in \(G\) represented by \(g\) is precisely the right translate of \(H\) by \(g\text{,}\) \([g] = Hg\text{.}\)
Solution.
Given an element \(g^\prime \equiv_r g \pmod{H}\) there exists \(h \in H\) that satisfies \(g^\prime g^{-1} = h\) and thus \(g^\prime = hg \in Hg.\) Hence \(\left\{g^\prime \in G \;\middle\vert\; g^\prime \equiv_r g \pmod{H}\right\} \subseteq H g \text{.}\)
For the reverse inclusion, consider the element \(g^\prime = hg \in Hg\text{.}\) Then \(g^\prime g^{-1} = h \in H\) implies \(g^\prime \equiv_r g \pmod{H}\) and so \(g^\prime \in [g]\text{.}\) Hence \(Hg \subseteq [g]\text{.}\) Therefore \([g] = Hg\text{.}\)
3.
Assume \(G\) is a group and \(H \leq G\text{.}\) Prove for all \(g \in G\text{,}\) the cardinality of \(Hg\) is equal to the order of \(H\text{.}\)
Solution.
Fix an element \(g \in G\text{.}\) For every element \(h \in H\text{,}\) we obtain an element \(h g \in H g\text{.}\) This defines a mapping \(f_g \colon H \to H g\text{.}\)
On the other hand, every element of \(H g\) has the form \(h g\) for some \(h \in H\text{.}\) If we multiply this element on the right by \(g^{-1}\text{,}\) then we obtain the element
\begin{equation*}
(h g) g^{-1} = h \left(g g^{-1}\right) = h e = h \in H.
\end{equation*}
This defines a mapping \(f_{g^{-1}} \colon H g \to H\text{.}\)
By construction, these two functions are inverses of one another:
\begin{align*}
f_{g^{-1}} \circ f_g(h)
\amp = f_{g^{-1}}(h g)
= (h g) g^{-1}
= h,\,\text{and}\\
f_g \circ f_{g^{-1}} (h g)
\amp = f_g\left((h g) g^{-1}\right)
= f_g(h)
= h g.
\end{align*}
Therefore \(f_g\) is a bijection for every \(g \in G\) and the result follows.
4.
Assume \(G\) is a group and \(H \leq G\text{.}\) Prove for all \(h \in H\text{,}\) \(Hh = H\text{.}\)
Solution.
Let \(h \in H\) be given. Since \(H\) is closed under multiplication it follows that
\begin{equation*}
Hh = \left\{xh \;\middle\vert\; x \in H\right\} \subseteq H.
\end{equation*}
For the reverse inclusion, let \(a \in H\) be given. Then \(ah^{-1} \in H\) implies
\begin{equation*}
a = a\left(h^{-1}h\right) = \left(ah^{-1}\right)h \in Hh
\end{equation*}
Hence \(H \subseteq Hh\text{.}\) Therefore \(H = hH.\)
