Cosets
A subgroup is one piece of a group. If we slide it along by multiplying every element by the same g, what do the slid copies look like, and how do they fit together?
Where you are 4 in Cosets and quotients
Why this exists
The integers split into the classes [0]_n, [1]_n, \dots, [n - 1]_n of Relations, equivalence classes and partitions, and each class [a]_n = \{a + kn : k \in \mathbb{Z}\} is the subgroup n\mathbb{Z} moved over by a. The solutions of a consistent linear system Ax = b are one particular solution plus every vector of the kernel (Kernel): the subgroup \ker A of \mathbb{R}^n, moved over. Both pictures are one construction. Given a subgroup H of a group G (Subgroups), multiply all of H by a fixed element g. The copies so made never overlap unless they coincide, they cover G, and they all have the size of H.
Definition
Let G be a group, H \le G and g \in G. The left coset of H containing g is
and the right coset is Hg = \{hg : h \in H\}. The element g is a representative: it lies in both, as g = ge = eg. In an additive group the left coset is written a + H = \{a + h : h \in H\}; additive groups here are abelian, so left and right agree.
The set of left cosets of H in G is written G/H. The index of H in G, written [G : H], is the number of left cosets, which may be infinite. Theorem 5 shows that counting right cosets gives the same number.
Throughout, H \le G, and for a, b \in G we write
In additive notation, a \sim b says b - a \in H. For H = n\mathbb{Z} in \mathbb{Z} that is n \mid b - a, congruence modulo n (Congruence modulo n and its arithmetic), so the cosets a + n\mathbb{Z} are exactly the classes [a]_n.
Intuition
Multiplying on the left by g is a bijection of G onto itself (it is undone by multiplying by g^{-1}), so it carries H to a copy gH of the same size. Two copies either coincide or miss each other entirely, because “lying in the same coset” is an equivalence relation. So a subgroup cuts its group into blocks of one size, as in the first figure below.
In a group that is not abelian, sliding on the left and sliding on the right can give different blocks (Example 4). The two partitions still have the same number of blocks.
Results
Throughout, G is a group and H \le G.
Theorem 1 (left cosets are classes). The relation \sim is an equivalence relation on G, and the class of a is aH. Consequently the left cosets of H partition G: every element of G lies in exactly one left coset.
Lemma 2 (equal cosets). For a, b \in G the following are equivalent: (i) aH = bH; (ii) b \in aH; (iii) a^{-1}b \in H; (iv) aH \cap bH \ne \varnothing. In particular, aH = H if and only if a \in H.
Theorem 3 (right cosets are classes). The relation \approx is an equivalence relation on G, and the class of a is Ha. So the right cosets of H partition G, and Ha = Hb if and only if ab^{-1} \in H, if and only if a \in Hb.
Theorem 4 (equal size). For each g \in G, the maps H \to gH, h \mapsto gh, and H \to Hg, h \mapsto hg, are bijections. So every left coset and every right coset of H has the same size as H; if H is finite, |gH| = |Hg| = |H|.
Theorem 5 (as many left as right). The rule gH \mapsto Hg^{-1} is a well-defined bijection from the set of left cosets of H onto the set of right cosets. So the number of right cosets of H is also [G : H].
Theorem 6 (abelian groups). If G is abelian, then gH = Hg for every g \in G.
Why it is true
Proof of Theorem 1. Reflexive: a^{-1}a = e \in H. Symmetric: if a^{-1}b \in H, then its inverse (a^{-1}b)^{-1} = b^{-1}a lies in H (Binary operations and the group axioms, Theorem 3), so b \sim a. Transitive: if a^{-1}b \in H and b^{-1}c \in H, their product a^{-1}bb^{-1}c = a^{-1}c lies in H. By symmetry the class of a is \{b \in G : a^{-1}b \in H\}. If a^{-1}b = h \in H, then b = ah \in aH; conversely, b = ah gives a^{-1}b = h \in H. So the class of a is aH. The classes of an equivalence relation partition the set (Relations, equivalence classes and partitions, Theorem 3). \square
Proof of Lemma 2. By Theorem 1, aH = [a] and bH = [b] are classes of \sim. (i) implies (ii), since b = be \in bH. (ii) and (iii) are equivalent, since b = ah exactly when a^{-1}b = h. (iii) says a \sim b, which gives [a] = [b] (Relations, equivalence classes and partitions, Theorem 1), that is, (i). (i) implies (iv), as a \in aH. Finally, two classes are equal or disjoint (Theorem 2 there), so (iv) implies (i). For the last sentence take b = e: aH = eH = H if and only if a^{-1} \in H, if and only if a \in H, as H is closed under inverses. \square
Proof of Theorem 3. Reflexive: aa^{-1} = e \in H. Symmetric: (ab^{-1})^{-1} = ba^{-1}. Transitive: (ab^{-1})(bc^{-1}) = ac^{-1}. The class of a is \{b : ba^{-1} \in H\} = \{b : b = ha \text{ for some } h \in H\} = Ha. Two classes are equal exactly when their representatives are related, so Ha = Hb if and only if ab^{-1} \in H, and ab^{-1} = h is the same as a = hb. \square
Proof of Theorem 4. The map h \mapsto gh is onto gH by the definition of gH. It is one to one: gh_1 = gh_2 gives h_1 = h_2 by left cancellation (Binary operations and the group axioms, Corollary 5). The map h \mapsto hg is handled the same way with right cancellation. A bijection between two sets shows they have the same size (One-to-one, onto and bijective functions). \square
Proof of Theorem 5. Well defined: if aH = bH, then a^{-1}b \in H by Lemma 2. Now a^{-1}(b^{-1})^{-1} = a^{-1}b, so a^{-1} \approx b^{-1} and Ha^{-1} = Hb^{-1} by Theorem 3. One to one: reading the same chain backward, Ha^{-1} = Hb^{-1} gives a^{-1}(b^{-1})^{-1} = a^{-1}b \in H, so aH = bH. Onto: the right coset Hg is the image of g^{-1}H, since (g^{-1})^{-1} = g. \square
Proof of Theorem 6. gh = hg for every h \in H, so \{gh : h \in H\} = \{hg : h \in H\}. \square
Worked examples
Cosets in the units mod 13
Let G = \mathbb{Z}_{13}^\times and H = \{1, 3, 9\}. Show that H \le G, list the cosets of H, and decide whether 5 and 6 lie in one coset, and whether 2 and 4 do.
SolutionMod 13, 3 \cdot 3 = 9, 3 \cdot 9 = 27 \equiv 1 and 9 \cdot 9 = 81 \equiv 3, so H is closed, and it is a subgroup by the finite test (Subgroups, Theorem 5). As G is abelian, left and right cosets agree (Theorem 6). Start with H = 1H. The element 2 is not in it, so 2H is a new coset:
The smallest element not yet used is 4, and 4H = \{4, 12, 36\} = \{4, 10, 12\}. Next is 7, and 7H = \{7, 21, 63\} = \{7, 8, 11\}. These four cosets hold all twelve elements, so by Theorem 1 there are no others, and [G : H] = 4.
Both 5 and 6 lie in 2H, so they share a coset. Lemma 2 confirms this without the list: 5^{-1} = 8, since 5 \cdot 8 = 40 \equiv 1, and 5^{-1} \cdot 6 = 48 \equiv 9 \in H. For 2 and 4: 2^{-1} = 7, and 7 \cdot 4 = 28 \equiv 2 \notin H, so 2H \ne 4H. Every coset has many names: 6H = \{6, 18, 54\} = \{6, 5, 2\} = 2H.
Circles and rays
In \mathbb{C}^\times, describe the cosets of the circle group S^1 = \{z : |z| = 1\} and of the positive reals \mathbb{R}_{>0}, both subgroups (Subgroups, Example 1). Which coset of each contains -3 + 3i?
SolutionWe claim zS^1 = \{w \in \mathbb{C}^\times : |w| = |z|\}. If w = zu with |u| = 1, then |w| = |z||u| = |z|, because moduli multiply (Polar form of a complex number). Conversely, if |w| = |z|, then u = z^{-1}w has |u| = |w|/|z| = 1 and w = zu \in zS^1. So the cosets of S^1 are the circles centered at 0, one for each radius r > 0, and [\mathbb{C}^\times : S^1] is infinite.
Likewise z\mathbb{R}_{>0} = \{tz : t > 0\} is the open ray from 0 through z, the points with the same argument as z. Writing w = r \operatorname{cis} \theta in polar form, the circle of radius r and the ray at angle \theta meet only at w: each circle crosses each ray once.
For -3 + 3i: \displaystyle |-3 + 3i| = \sqrt{18} = 3\sqrt{2}, so its S^1-coset is the circle \displaystyle |w| = 3\sqrt{2}. Its argument is \displaystyle \frac{3\pi}{4}, so its \mathbb{R}_{>0}-coset is the ray at angle \displaystyle \frac{3\pi}{4}, which also contains -1 + i and -50 + 50i.
Parallel lines in the plane
Let H = \{(x, y) \in \mathbb{R}^2 : x - 2y = 0\}, a subgroup of (\mathbb{R}^2, +). Show that the coset (a, b) + H is the line x - 2y = a - 2b. Then show that (1, -1), (3, 0) and (5, 1) name the same coset, and that it is the solution set of x - 2y = 3.
SolutionH is the kernel of the 1 \times 2 matrix \begin{pmatrix} 1 & -2 \end{pmatrix}, so it is a subspace, and in particular a subgroup under addition. By the definition, (x, y) lies in (a, b) + H exactly when (x - a, y - b) \in H, that is, when (x - a) - 2(y - b) = 0, or x - 2y = a - 2b. So the cosets are the lines of slope \displaystyle \frac{1}{2}, one for each value of c = x - 2y, and H is the one through the origin.
For the three points, x - 2y equals 1 + 2 = 3, 3 - 0 = 3 and 5 - 2 = 3. In the language of Lemma 2, (3, 0) - (1, -1) = (2, 1) lies in H because 2 - 2 \cdot 1 = 0. All three name the coset x - 2y = 3, the solution set of that equation. The point (0, 2) gives the coset x - 2y = -4, a different line, disjoint from the first as Theorem 1 requires.
Left and right cosets that differ
In \operatorname{GL}_2(\mathbb{Z}_2) (Integers mod n, symmetries and matrices as groups, Example 5) let
Find the left and the right cosets of H = \{I_2, J\}, and show that the rule gH \mapsto Hg is not well defined.
SolutionJ^2 = I_2, so H is closed and is a subgroup. With arithmetic mod 2,
and in the same way YJ = P and JY = Q. So the left cosets are
and the right cosets are H, HX = \{X, P\} and HY = \{Y, Q\}. Each family partitions the six elements into three pairs, as Theorems 1 and 3 promise, but the pairs differ: XH \ne HX. Both families have three members, so [G : H] = 3, as Theorem 5 requires.
Now XH = QH, since Q \in XH. If gH \mapsto Hg were a function, then HX = HQ. But JQ = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = Y, so HQ = \{Q, Y\}, while HX = \{X, P\}. The inverse in Theorem 5 is what repairs this: X^{-1} = X and Q^{-1} = (YX)^{-1} = X^{-1}Y^{-1} = XY = P, and indeed HX^{-1} = \{X, P\} = HP = HQ^{-1}, as JP = X.
Where two cosets meet
Let H, K \le G. Prove that a left coset of H and a left coset of K are either disjoint or meet in a left coset of H \cap K.
SolutionProof. Here H \cap K \le G (Subgroups, Theorem 6). Suppose aH \cap bK \ne \varnothing and pick x in it. Then x \in aH and x \in xH, so aH \cap xH \ne \varnothing and aH = xH by Lemma 2; likewise bK = xK. It remains to show xH \cap xK = x(H \cap K). If y \in x(H \cap K), then y = xk with k in both H and K, so y lies in xH and in xK. Conversely, if y = xh = xk with h \in H and k \in K, left cancellation gives h = k, which lies in H \cap K, and y = xh \in x(H \cap K). So aH \cap bK = x(H \cap K). \square
For instance, in \mathbb{Z}_{18} take H = \{0, 6, 12\} and K = \{0, 9\}. Then H \cap K = \{0\}, and (1 + H) \cap (4 + K) = \{1, 7, 13\} \cap \{4, 13\} = \{13\}, the coset 13 + \{0\}.
Correcting a flipped bit
Omar sends telemetry to Layla over a noisy link in blocks of five bits. Strings of five bits, added place by place mod 2, form an abelian group G of 32 elements, in which every element is its own inverse. Omar sends only the four strings of
Show that H \le G, and that if at most one bit is flipped on the way, Layla can recover what Omar sent. Decode the received string \mathtt{10111}.
Solution\mathtt{11100} + \mathtt{00111} = \mathtt{11011}, and each element added to itself gives \mathtt{00000}, so H is closed and is a subgroup by the finite test. If Omar sends c \in H and the line adds an error string f (a \mathtt{1} wherever a bit flips), Layla receives r = c + f. Then r - f = c \in H, so r and f lie in the same coset r + H.
The weight of a string is its number of \mathtt{1}s. The six strings of weight 0 or 1 lie in six different cosets: two of them differ by a string of weight 1 or 2, while the nonzero members of H have weights 3, 3 and 4, so by Lemma 2 no two share a coset. Hence if at most one bit flipped, f is the unique string of weight at most 1 in r + H, and Layla recovers c = r + f. (By Theorems 1 and 4 the 32 strings fall into cosets of 4, so there are 8 cosets; the remaining two contain no string of weight below 2.)
For r = \mathtt{10111}, adding each element of H gives
Its only member of weight at most 1 is \mathtt{10000}, so the first bit flipped and Omar sent \mathtt{10111} + \mathtt{10000} = \mathtt{00111}, which is in H.
Boundaries
- The subset must be a subgroup. For S = \{0, 1\} \subseteq \mathbb{Z}, the translates 0 + S = \{0, 1\} and 1 + S = \{1, 2\} overlap without being equal; the proof of Theorem 1 used e \in H, inverses and closure.
- Only one coset is a subgroup. gH contains e only when gH = H (Exercise 12).
- Left and right may differ. Example 4 shows XH \ne HX, and that gH \mapsto Hg is not a function. The subgroups whose left and right cosets agree are the Normal subgroups.
- Products of cosets need not be cosets. In Example 4, the products uv with u \in XH and v \in YH are P, Y, J and I_2: four elements, while every coset there has two. When a product of cosets is a coset is the question of Quotient groups.
- Infinite index. A finite subgroup may have infinitely many cosets: \{1, -1\} in \mathbb{R}^\times has the cosets \{x, -x\}, one per x > 0.
Where this goes next
For a finite group, Theorems 1 and 4 cut G into [G : H] blocks of |H| elements each; counting them is Lagrange's theorem. Asking when gH = Hg for all g leads to Normal subgroups, and for those the cosets multiply, giving the Quotient groups. Examples 2 and 3 and Exercise 16 show cosets of a kernel as the sets on which a map is constant; Homomorphisms and kernels makes this exact. In a group action, the points of an orbit match the left cosets of a stabilizer.
Exercises
Listing cosets
- List the cosets of H = \{0, 4, 8\} in \mathbb{Z}_{12} and give [\mathbb{Z}_{12} : H].
- List the cosets of H = \{1, 10\} in \mathbb{Z}_{11}^\times.
- In \mathbb{Z}_{16}^\times = \{1, 3, 5, 7, 9, 11, 13, 15\}, list the cosets of \{1, 9\} and of K = \{1, 7, 9, 15\}.
- With X, Y, J, P, Q as in Example 4, find the left and the right cosets in \operatorname{GL}_2(\mathbb{Z}_2) of H = \{I_2, X\} and of K = \{I_2, P, Q\}.
Deciding and describing
- In \mathbb{C}^\times: (a) do 3 + 4i and -5 lie in one coset of S^1? (b) Do 1 + i and 3 + 3i lie in one coset of \mathbb{R}_{>0}? (c) In one coset of S^1?
- Let \mu_4 = \{1, i, -1, -i\} \le \mathbb{C}^\times. List (2 + i)\mu_4, show that z and w lie in one coset of \mu_4 exactly when z^4 = w^4, and decide whether 1 + 2i lies in (2 + i)\mu_4.
- In \mathbb{R}^2 let H = \{(t, -3t) : t \in \mathbb{R}\}. Write the coset (2, 5) + H as a line px + qy = c, and decide which of (4, -1), (0, 11), (-1, 13) lie on it.
- Write the solution set of x + y + z = 6, x - y = 2 in \mathbb{R}^3 as a coset p + \ker A.
- Show that A, B \in \operatorname{GL}_2(\mathbb{R}) lie in one left coset of \operatorname{SL}_2(\mathbb{R}) exactly when \det A = \det B. Which two of A = \begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}, B = \begin{pmatrix} 1 & 7 \\ 0 & 5 \end{pmatrix}, C = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} share a coset? Find A^{-1}B.
- Find each index: (a) [\mathbb{Z} : 6\mathbb{Z}]; (b) [\mathbb{Z}_{24} : H] with H = \{0, 3, 6, \dots, 21\}; (c) [\mathbb{R}^\times : \mathbb{R}_{>0}]; (d) [\mathbb{Z}_{16}^\times : \{1, 15\}].
- With Omar’s code from Example 6, Layla receives \mathtt{11110} and later \mathtt{01101}. Decode each, or explain why it cannot be decoded.
Proofs
- Let H \le G and g \in G. Prove that gH \le G if and only if g \in H.
- Prove that if [G : H] = 2, then gH = Hg for every g \in G.
- Let H \le G. Prove that if a left coset aH equals some right coset Hb, then aH = Ha.
- Let H \le K \le G. Prove that every left coset of K is a union of left cosets of H.
- Let A be a real m \times n matrix and b \in \mathbb{R}^m. Prove that the solution set of Ax = b is empty or a coset of \ker A in \mathbb{R}^n, and that u, v \in \mathbb{R}^n lie in one coset of \ker A if and only if Au = Av.
- Let H \le G and a \in G. Prove that \{x^{-1} : x \in aH\} = Ha^{-1}, and explain how this gives a second proof that the rule of Theorem 5 is well defined.
Answers
- \{0, 4, 8\}, \{1, 5, 9\}, \{2, 6, 10\}, \{3, 7, 11\}, as a + H = \{a, a + 4, a + 8\}; so [\mathbb{Z}_{12} : H] = 4.
- Since 10 \equiv -1, aH = \{a, 11 - a\}: the cosets are \{1, 10\}, \{2, 9\}, \{3, 8\}, \{4, 7\}, \{5, 6\}.
- For \{1, 9\}: 3 \cdot 9 = 27 \equiv 11, 5 \cdot 9 = 45 \equiv 13, 7 \cdot 9 = 63 \equiv 15, giving \{1, 9\}, \{3, 11\}, \{5, 13\}, \{7, 15\}. For K: K itself and 3K = \{3, 21, 27, 45\} = \{3, 5, 11, 13\}, two cosets.
- For H = \{I_2, X\}: YX = Q and JX = P, so the left cosets are H, \{Y, Q\}, \{J, P\}; XY = P and XJ = Q, so the right cosets are H, \{Y, P\}, \{J, Q\}. For K: XP = X^2Y = Y and XQ = XYX = PX = J, so the left cosets are K and \{X, Y, J\}; PX = J and QX = YX^2 = Y, so the right cosets are K and \{X, J, Y\}, the same two sets.
- (a) Yes: |3 + 4i| = 5 = |-5| (Example 2). (b) Yes: (1 + i)^{-1}(3 + 3i) = 3 > 0. (c) No: \displaystyle |1 + i| = \sqrt{2} but \displaystyle |3 + 3i| = 3\sqrt{2}.
- (2 + i)\mu_4 = \{2 + i, -1 + 2i, -2 - i, 1 - 2i\}, the corners of a square centered at 0. By Lemma 2, w \in z\mu_4 if and only if z^{-1}w \in \mu_4, and \mu_4 is exactly the set of roots of u^4 = 1, so this says (z^{-1}w)^4 = 1, that is, w^4 = z^4. As (2 + i)^4 = (3 + 4i)^2 = -7 + 24i and (1 + 2i)^4 = (-3 + 4i)^2 = -7 - 24i, the number 1 + 2i is not in the coset.
- (x, y) is in it exactly when (x - 2, y - 5) = (t, -3t) for some t, that is, 3(x - 2) + (y - 5) = 0: the line 3x + y = 11. (4, -1) gives 11 and (0, 11) gives 11, so both lie on it; (-1, 13) gives 10 and does not.
- \ker A for A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & -1 & 0 \end{pmatrix}: x = y and z = -2x, so \ker A = \{t(1, 1, -2) : t \in \mathbb{R}\}. A particular solution is (4, 2, 0), as 4 + 2 = 6 and 4 - 2 = 2. The solution set is (4, 2, 0) + \{t(1, 1, -2) : t \in \mathbb{R}\} (Exercise 16).
- By Lemma 2, A and B share a coset exactly when A^{-1}B \in \operatorname{SL}_2(\mathbb{R}), and \det(A^{-1}B) = \det B / \det A (Properties of determinants: row operations, products, transposes), which is 1 exactly when \det A = \det B. Here \det A = 5, \det B = 5, \det C = -2: A and B share a coset. \displaystyle A^{-1}B = \frac{1}{5}\begin{pmatrix} 4 & 23 \\ -3 & -11 \end{pmatrix}, of determinant \displaystyle \frac{-44 + 69}{25} = 1.
- (a) 6: the cosets are the classes [0]_6, \dots, [5]_6. (b) 3: the cosets are H, 1 + H, 2 + H, the integers 0 to 23 sorted by remainder mod 3. (c) 2: \mathbb{R}_{>0} and (-1)\mathbb{R}_{>0}, the negative reals. (d) 4: \{1, 15\}, \{3, 13\}, \{5, 11\}, \{7, 9\}, as 15 \equiv -1.
- \mathtt{11110} + H = \{\mathtt{11110}, \mathtt{00010}, \mathtt{11001}, \mathtt{00101}\} has the single weight-1 member \mathtt{00010}, so Omar sent \mathtt{11110} + \mathtt{00010} = \mathtt{11100}. And \mathtt{01101} + H = \{\mathtt{01101}, \mathtt{10001}, \mathtt{01010}, \mathtt{10110}\} has no member of weight below 2, so at least two bits flipped; it holds two strings of weight 2, so the error is detected but cannot be corrected.
- Proof. If g \in H, then gH = H by Lemma 2, a subgroup. Conversely, if gH \le G, then e \in gH, so e = gh for some h \in H; hence g = h^{-1} \in H. \square
- Proof. By Theorem 1 the two left cosets are disjoint and cover G; one is H, so the other is G \setminus H. By Theorem 5 there are also two right cosets, one of them H = He, so the other is G \setminus H. If g \in H, then gH = H = Hg by Lemma 2 and Theorem 3. If g \notin H, then gH \ne H and Hg \ne H, so gH = G \setminus H = Hg. \square
- Proof. a = ae \in aH = Hb, so a \in Hb, and Theorem 3 gives Ha = Hb. Hence aH = Hb = Ha. \square
- Proof. Let gK be a left coset of K and x \in gK. Then xK = gK by Lemma 2 (for K), and xH \subseteq xK because H \subseteq K. So x \in xH \subseteq gK for each x \in gK, and gK = \bigcup_{x \in gK} xH. \square
- Proof. \ker A is a subspace of \mathbb{R}^n (Kernel), so a subgroup under addition. If Ax = b has a solution p, then for every x, Ax = b if and only if A(x - p) = Ax - Ap = 0, if and only if x - p \in \ker A, if and only if x \in p + \ker A; so the solution set is the coset p + \ker A. If there is no solution, the set is empty. And u, v lie in one coset exactly when v - u \in \ker A (Lemma 2, additively), that is, Av - Au = 0. \square
- Proof. Each x \in aH is ah with h \in H, and x^{-1} = h^{-1}a^{-1} (Binary operations and the group axioms, Theorem 3). As h runs over H, so does h^{-1}: it lies in H, and every k \in H is (k^{-1})^{-1}. So \{x^{-1} : x \in aH\} = \{ka^{-1} : k \in H\} = Ha^{-1}. \square Hence Hg^{-1} is the set of inverses of the elements of gH, which depends only on the set gH and not on the representative g; that is exactly well-definedness.