Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

🔗

Section 15.2 Cosets and Factor Groups

🔗
Consider the group [Z12;+12]. As we saw in the previous section, we can picture its cyclic properties with the string art of Figure 15.1.3. Here we will be interested in the non-generators, like 3. The solid lines in Figure 15.2.1 show that only one-third of the tacks have been reached by starting at zero and jumping to every third tack. The numbers of these tacks correspond to ⟨3⟩={0,3,6,9}.
described in detail following the image
“String art” cosets
🔗
Figure 15.2.1. “String art” cosets
🔗
What happens if you start at one of the unused tacks and again jump to every third tack? The two broken paths on Figure 15.2.1 show that identical squares are produced. The tacks are thus partitioned into very similar subsets. The subsets of Z12 that they correspond to are {0,3,6,9}, {1,4,7,10}, and {2,5,8,11}. These subsets are called cosets. In particular, they are called cosets of the subgroup {0,3,6,9}. We will see that under certain conditions, cosets of a subgroup can form a group of their own. Before pursuing this example any further we will examine the general situation.
🔗

Definition 15.2.2. Coset.

🔗
🔗
If [G;∗] is a group, H≤G and a∈G, the left coset of H generated by a is
a∗H={a∗h|h∈H}
🔗
and the right coset of H generated by a is
H∗a={h∗a|h∈H}.
🔗

Note 15.2.3.

🔗
  1. H itself is both a left and right coset since e∗H=H∗e=H.
  2. If G is abelian, a∗H=H∗a and the left-right distinction for cosets can be dropped. We will normally use left coset notation in that situation.
🔗

Definition 15.2.4. Coset Representative.

🔗
Any element of a coset is called a representative of that coset.
🔗
One might wonder whether a is in any way a special representative of a∗H since it seems to define the coset. It is not, as we shall see.
🔗

Remark 15.2.5. A Duality Principle.

🔗
A duality principle can be formulated concerning cosets because left and right cosets are defined in such similar ways. Any theorem about left and right cosets will yield a second theorem when “left” and “right” are exchanged for “right” and “left.”

Proof.

In light of the remark above, we need only prove the first part of this theorem. Suppose that x∈a∗H. We need only find a way of expressing x as “b times an element of H.” Then we will have proven that a∗H⊆b∗H. By the definition of a∗H, since b and x are in a∗H, there exist h1 and h2 in H such that b=a∗h1 and x=a∗h2. Given these two equations, a=bh1−1 and
x=a∗h2=(b∗h1−1)∗h2=b∗(h1−1∗h2)
Since h1,h2∈H, h1−1∗h2∈H, and we are done with this part of the proof. In order to show that b∗H⊆a∗H, one can follow essentially the same steps, which we will let the reader fill in.

Example 15.2.7.

In Figure 15.2.1, you can start at either 1 or 7 and obtain the same path by taking jumps of three tacks in each step. Thus,
1+12{0,3,6,9}=7+12{0,3,6,9}={1,4,7,10}.
🔗
The set of left (or right) cosets of a subgroup partition a group in a special way:

Proof.

That every element of G belongs to a left coset is clear because a∈a∗H for all a∈G. If a∗H and b∗H are left cosets, we will prove that they are either equal or disjoint. If a∗H and b∗H are not disjoint, a∗H∩b∗H is nonempty and some element c∈G belongs to the intersection. Then by Theorem 15.2.6, c∈a∗H⇒a∗H=c∗H and c∈b∗H⇒b∗H=c∗H. Hence a∗H=b∗H.
We complete the proof by showing that each left coset has the same cardinality as H. To do this, we simply observe that if a∈G, ρ:H→a∗H defined by ρ(h)=a∗h is a bijection and hence |H|=|a∗H|. We will leave the proof of this statement to the reader.
🔗
The function ρ has a nice interpretation in terms of our opening example. If a∈Z12, the graph of {0,3,6,9} is rotated (30a)∘ to coincide with one of the three cosets of {0,3,6,9}.

Proof.

This follows from the partitioning of G into equal sized sets, one of which is H.

Example 15.2.10.

The set of integer multiples of four, 4Z, is a subgroup of [Z;+]. Four distinct cosets of 4Z partition the integers. They are 4Z, 1+4Z, 2+4Z, and 3+4Z, where, for example, 1+4Z={1+4k|k∈Z}. 4Z can also be written 0+4Z.
🔗

Convention 15.2.11. Distinguished Representatives.

🔗
Although we have seen that any representative can describe a coset, it is often convenient to select a distinguished representative from each coset. The advantage to doing this is that there is a unique name for each coset in terms of its distinguished representative. In numeric examples such as the one above, the distinguished representative is usually the smallest nonnegative representative. Remember, this is purely a convenience and there is absolutely nothing wrong in writing −203+4Z, 5+4Z, or 621+4Z in place of 1+4Z because −203,5,621∈1+4Z.
🔗
Before completing the main thrust of this section, we will make note of a significant implication of Theorem 15.2.8. Since a finite group is divided into cosets of a common size by any subgroup, we can conclude:
🔗
One immediate implication of Lagrange’s Theorem is that if p is prime, Zp has no proper subgroups.
🔗
We will now describe the operation on cosets which will, under certain circumstances, result in a group. For most of this section, we will assume that G is an abelian group. This is one sufficient (but not necessary) condition that guarantees that the set of left cosets will form a group.
🔗

Definition 15.2.13. Operation on Cosets.

🔗
🔗
Let C and D be left cosets of H, a subgroup of G with representatives c and d, respectively. Then
C⊗D=(c∗H)⊗(d∗H)=(c∗d)∗H
🔗
The operation ⊗ is called the operation induced on left cosets by ∗.
🔗
In Theorem 15.2.18, later in this section, we will prove that if G is an abelian group, ⊗ is indeed an operation. In practice, if the group G is an additive group, the symbol ⊗ is replaced by +, as in the following example.

Example 15.2.14. Computing with cosets of 4Z.

Consider the cosets described in Example 15.2.10. For brevity, we rename 0+4Z, 1+4Z, 2+4Z, and 3+4Z with the symbols 0¯, 1¯, 2¯, and 3¯. Let’s do a typical calculation, 1¯+3¯. We will see that the result is always going to be 0¯ , no matter what representatives we select. For example, 9∈1¯, 7∈3¯, and 9+7=16∈0¯. Our choice of the representatives 1¯ and 3¯ were completely arbitrary.
🔗
🔗
In general, C⊗D can be computed in many ways, and so it is necessary to show that the choice of representatives does not affect the result. When the result we get for C⊗D is always independent of our choice of representatives, we say that “⊗ is well defined.” Addition of cosets is a well-defined operation on the left cosets of 4Z and is summarized in the following table. Do you notice anything familiar?
⊗0¯1¯2¯3¯0¯0¯1¯2¯3¯1¯1¯2¯3¯0¯2¯2¯3¯0¯1¯3¯3¯0¯1¯2¯

Example 15.2.15. Cosets of the integers in the group of Real numbers.

Consider the group of real numbers, [R;+], and its subgroup of integers, Z. Every element of R/Z has the same cardinality as Z. Let s,t∈R. s∈t+Z if s can be written t+n for some n∈Z. Hence s and t belong to the same coset if they differ by an integer. (See Exercise 15.2.6 for a generalization of this fact.)
Now consider the coset 0.25+Z. Real numbers that differ by an integer from 0.25 are 1.25,2.25,3.25,… and −0.75,−1.75,−2.75,…. If any real number is selected, there exists a representative of its coset that is greater than or equal to 0 and less than 1. We will call that representative the distinguished representative of the coset. For example, 43.125 belongs to the coset represented by 0.125; −6.382+Z has 0.618 as its distinguished representative. The operation on R/Z is commonly called addition modulo 1. A few typical calculations in R/Z are
(0.1+Z)+(0.48+Z)=0.58+Z(0.7+Z)+(0.31+Z)=0.01+Z−(0.41+Z)=−0.41+Z=0.59+Zand in general, −(a+Z)=(1−a)+Z.

Example 15.2.16. Cosets in a Direct Product.

Consider F=(Z4×Z2)/H, where H={(0,0),(0,1)}. Since Z4×Z2 is of order 8, each element of F is a coset containing two ordered pairs. We will leave it to the reader to verify that the four distinct cosets are (0,0)+H, (1,0)+H, (2,0)+H and (3,0)+H. The reader can also verify that F is isomorphic to Z4 , since F is cyclic. An educated guess should give you a generator.

Example 15.2.17.

Consider the group Z24=Z2×Z2×Z2×Z2 . Let H be ⟨(1,0,1,0)⟩, the cyclic subgroup of Z24 generate by (1,0,1,0). Since
(1,0,1,0)+(1,0,1,0)=(1+21,0+20,1+21,0+20)=(0,0,0,0)
the order of H is 2 and , Z24/H has |Z24/H|=|Z24||H|=162=8 elements. A typical coset is
C=(0,1,1,1)+H={(0,1,1,1),(1,1,0,1)}
Note that since 2(0,1,1,1)=(0,0,0,0), 2C=C⊗C=H, the identity for the operation on Z24/H. The orders of non-identity elements of this factor group are all 2, and it can be shown that the factor group is isomorphic to Z23.

Proof.

Suppose that a, b, and a′, b′. are two choices for representatives of cosets C and D. That is to say that a,a′∈C, b,b′∈D. We will show that a∗b and a′∗b′ are representatives of the same coset. Theorem 15.2.61 implies that C=a∗H and D=b∗H, thus we have a′∈a∗H and b′∈b∗H. Then there exists h1,h2∈H such that a′=a∗h1 and b′=b∗h2 and so
a′∗b′=(a∗h1)∗(b∗h2)=(a∗b)∗(h1∗h2)
by various group properties and the assumption that G is abelian, which lets us reverse the order in which b and h1 appear in the chain of equalities. This last expression for a′∗b′ implies that a′∗b′∈(a∗b)∗H since h1∗h2∈H because H is a subgroup of G. Thus, we get the same coset for both pairs of representatives.

Proof.

Let C1,C2, and C3 be the left cosets with representatives r1, r2, and r3, respectively. The values of C1⊗(C2⊗C3) and (C1 ⊗C2)⊗C3 are determined by r1∗(r2∗r3) and (r1∗r2)∗r3, respectively. By the associativity of ∗ in G, these two group elements are equal and so the two coset expressions must be equal. Therefore, the induced operation is associative. As for the identity and inverse properties, there is no surprise. The identity coset is H, or e∗H, the coset that contains G’s identity. If C is a coset with representative a; that is, if C=a∗H, then C−1 is a−1∗H.
(a∗H)⊗(a−1∗H)=(a∗a−1)∗H=e∗H= identity coset.
🔗

Definition 15.2.20. Factor Group.

🔗
Let G be a group and H≤G. If the set of left cosets of H forms a group, then that group is called the factor group of “G modulo H.” It is denoted G/H.
🔗

Note 15.2.21.

🔗
If G is abelian, then every subgroup of G yields a factor group. We will delay further consideration of the non-abelian case to Section 15.4.
🔗

Remark 15.2.22. On Notation.

🔗
It is customary to use the same symbol for the operation of G/H as for the operation on G. The reason we used distinct symbols in this section was to make the distinction clear between the two operations.
🔗

Exercises Exercises

🔗

1.

🔗
Consider Z10 and the subsets of Z10, {0,1,2,3,4} and {5,6,7,8,9}. Why is the operation induced on these subsets by modulo 10 addition not well defined?
Answer.
An example of a valid correct answer: Call the subsets A and B respectively. If we choose 0∈A and 5∈B we get 0+105=5∈B. On the other hand, if we choose 3∈A and 8∈B, we get 3+108=1∈A. Therefore, the induced operation is not well defined on {A,B}.
🔗

2.

🔗
Can you think of a group G, with a subgroup H such that |H|=6 and |G/H|=6? Is your answer unique?
🔗

3.

🔗
🔗
For each group and subgroup, what is G/H isomorphic to?
  1. G=Z4×Z2 and H=⟨(2,0)⟩. Compare to Example 15.2.16.
  2. G=[C;+] and H=R.
  3. G = Z20 and H=⟨8⟩.
Answer.
  1. The four distinct cosets in G/H are H={(0,0),(2,0)}, (1,0)+H={(1,0),(3,0)}, (0,1)+H={(0,1),(2,1)}, and (1,1)+H={(1,1),(3,1)}. None of these cosets generates G/H; therefore G/H is not cyclic. Hence G/H must be isomorphic to Z2×Z2.
  2. The factor group is isomorphic to [R;+]. Each coset of R is a line in the complex plane that is parallel to the x-axis: τ:C/R→R, where T({a+bi∣a∈R})=b is an isomorphism.
  3. ⟨8⟩={0,4,8,12,16}⇒ |Z20/⟨8⟩|=4. The four cosets are: 0¯, 1¯, 2¯, and 3¯. 1 generates all four cosets. The factor group is isomorphic to [Z4;+4] because 1¯ is a generator.
🔗

4.

🔗
🔗
For each group and subgroup, what is G/H isomorphic to?
  1. G=Z×Z and H={(a,a)|a∈Z}.
  2. G=[R∗;⋅] and H={1,−1}.
  3. G=Z25 and H=⟨(1,1,1,1,1)⟩.
🔗

5.

🔗
Assume that G is a group, H≤G, and a,b∈G. Prove that a∗H=b∗H if and only if b−1∗a∈H.
Answer.
a∗H=b∗H⇔a∈bH⇔a=b∗h for some h∈H⇔b−1∗a=h for some h∈H⇔b−1∗a∈H
🔗

6.

🔗
  1. Real addition modulo r, r>0, can be described as the operation induced on cosets of ⟨r⟩ by ordinary addition. Describe a system of distinguished representatives for the elements of R/⟨r⟩.
  2. Consider the trigonometric function sine. Given that sin⁡(x+2πk)=sin⁡x for all x∈R and k∈Z, show how the distinguished representatives of R/⟨2π⟩ can be useful in developing an algorithm for calculating the sine of a number.
🔗

7.

🔗
Complete the proof of Theorem 15.2.8 by proving that if a∈G, ρ:H→a∗H defined by ρ(h)=a∗h is a bijection.
You have attempted 1 of 1 activities on this page.
PrevTopNext