Subgroups and cosets

Syllabus: In this section we define subgroups and cosets and also describe how to `generate' a group.

Definition 1.3.1   Let G be a group. The subset $H\subseteq G$ is called a subgroup of G, denoted by $H\le G$, if it is a group with its multiplication defined by the product in the ambient group G.

Lemma 1.3.2   Subgroup criterion  For a subset $\emptyset\ne H\subseteq G$ the following are equivalent:
(i): $H\le G$.
(ii): $h,h'\in H$ $\Rightarrow$ $h^{-1}\in H$ and $hh'\in H$.
(iii): $h,h'\in H\Rightarrow h^{-1}h'\in H$.

Proof: We prove the equivalence by showing ${\rm (i)} \Rightarrow {\rm (ii)}$, ${\rm (ii)} \Rightarrow {\rm (iii)}$ and finally ${\rm (iii)} \Rightarrow {\rm (i)}$.

${\rm (i)} \Rightarrow {\rm (ii)}$: If H is a group with multiplication given by the product in G, H must be multiplicatively closed. Moreover there is a neutral element $1_H \in H$. We want to show that 1_H= 1_G: the equation 1_H1_H=1_H, viewed as an equation inside G, yields $1_H = 1_H\cdot 1_H^{-1} = 1_G$. Now let $h\in H$ and h^-1_H be its inverse in the group H. Then

$$h^{-1}_H = h^{-1}_H \cdot 1_G = h^{-1}_H \cdot (h h^{-1}_G) = (h^{-1}_H h) \cdot h^{-1}_G = 1_G \cdot h^{-1}_G = h^{-1}_G.$$

Together with the fact that H is closed under multiplication we see that $h,h'\in H$ implies $h^{-1}\in H$ and $hh'\in H$.

${\rm (ii)} \Rightarrow {\rm (iii)}$: this is obvious.

${\rm (iii)} \Rightarrow {\rm (i)}$: Since H is not empty, there is at least one $h\in H$. Therefore, $1_G= h^{-1}h\in H$. Taking h':=1_G, we see that $h^{-1}\in H$ as well. Taking the h in (iii) to be h^-1 we see that $h,h'\in H$ implies $hh' = (h^{-1})^{-1} h'\in H$. Hence H is multiplicatively closed, contains a neutral element and the inverses of each member. The associative law is inherited from G, so H is a subgroup. $\diamond$

Notice that it is important in (ii) and (iii) to consider inverse elements: the natural numbers $\mathbb{N}$, viewed as an additive subset of the integers $\mathbb{Z}$ are additively closed: in fact if m and n are in $\mathbb{N}$, then so is their sum m+n. But $\mathbb{N}$ is not a subgroup of $\mathbb{Z}$, as negative numbers (the `inverses' of natural numbers with respect to addition) are not contained in $\mathbb{N}$.

If $U_i, i\in I$ is a family of subgroups, then so is the intersection $\cap_{i\in I} U_i$. If $\emptyset \ne S\subseteq G$ is an arbitrary subset, we can consider the family ${\cal S}:= \{H\le G\ \vert\ S\subseteq H\}$ of subgroups that contain S. As $G\in {\cal S}$, this family is nonempty and the intersection

$$\langle S\rangle := \langle s\ \vert\ s\in S\rangle := \cap_{H\in {\cal S}} \ H$$

is the smallest subgroup of G that contains S. It is called the subgroup of G, generated by S. A more explicit way to describe this group is the following (check this):

$$\langle S\rangle = \{ s_{i_1}^{z_{i_1}} s_{i_2}^{z_{i_2}} \cd... ...\ \ell\in \mathbb{N} ,\ s_{i_j}\in S,\ z_{i_j}\in \mathbb{Z}\}.$$

If $S=\{g\}$ with $g\in G$, then $\langle g \rangle = \{ g^i\ \vert\ i\in \mathbb{Z}\}$ is called the cyclic subgroup generated by g. If this is a finite group, its order $\vert\langle g\rangle\vert$ is called the order of the element g and denoted by |g|, o(g) or ${\rm ord}(g)$. Otherwise one says that g has infinite order ( $\vert g\vert=\infty$). If $G = \langle g\rangle$ for some $g\in G$, then G is called a cyclic group. A subgroup $G\le \Sigma_\Omega$ is called a permutation group on the set $\Omega$. Again $\vert\Omega\vert$ is then called the degree of G.

Lemma 1.3.3   Let G be a group. For any element $g\in G$ and $n\in \mathbb{N}$ the following are equivalent:
(i) $\vert g\vert = n < \infty$. (ii) $n= {\rm min}\ \{ m\in \mathbb{N}\ \vert\ g^m=1\}$.
(iii) $\forall z\in \mathbb{Z} :\ g^z=1 \iff n\ \vert\ z$ (n divides z).

If one of (i),(ii) or (iii) holds, then $g^ig^j \equiv g^k \iff k=i+j\ {\rm mod}\ n$.

Proof: Assume (i). Then $\vert\langle g \rangle\vert=n$ is finite and the elements $1,g,g^2,\cdots,g^i,\cdots$ can not be all different. Hence there is a smallest $0< j \in \mathbb{Z}$ with $j<i\in \mathbb{Z}$ such that g^j=gⁱ, which implies g^i-j:=gⁱ g^-j=1. So $n':= {\rm min}\ \{ m\in \mathbb{N}\ \vert\ g^m=1\}$ is a well defined element $0< n' \in \mathbb{Z}$. Now the elements $1,g,g^2,\cdots,g^{n'-1}$ are pairwise different. Moreover for $z\in \mathbb{Z}$ there is a unique $0\le i < n'$ with $z\equiv i\ {\rm mod}\ n'$, i.e. z=qn' + i. Hence g^z = (g^n')^q gⁱ = gⁱ and $\langle g \rangle = \{ 1,g,\cdots,g^{n'-1}\}$ and we conclude n'=n.
Assume (ii) and g^z=1 for the integer z. Dividing z by n with remainder, we get z=qn+r with $0\le r < n$ and 1=(gⁿ)^q g^r=g^r, which implies r=0, due to the definition of n. Hence n divides z.
Assume (iii). Again this implies that $\langle g \rangle = \{ g^i\ \vert\ 0\le i\le n-1\}$ has cardinality n.
The last remark is obvious. $\diamond$

If G is a finite group, then certainly all its elements have finite order. In particular, the inverse of an element $g\in G$ is a power of g itself. Therefore the above subgroup criterion 1.3.2 is simplified in this case:

Lemma 1.3.4   Subgroup criterion for finite groups  Let G be a finite group. For a subset $\emptyset\ne H\subseteq G$ the following are equivalent:
(i): $H\le G$.
(ii): $h,h'\in H$ $\Rightarrow$ $hh'\in H$.

Let G be a finite group generated by the subset S with $S=\{s_1,\cdots,s_t\}$. How can we produce a complete list of all elements in G? We certainly know

• $\{1\}\cup S \subseteq G;$
• G is closed with respect to multiplication;
• G is the smallest multiplicatively closed subset which contains S.

From these observations we obtain the following obvious procedure to write down all elements of G in a list

Procedure 1:

The list will reach its final stage, when all products of elements of the list are members of the list. Since we only added products of elements of S, we arrive at the group generated by S. The drawback is that this method is not very efficient. We have to check |G|² pairs (g,h) with one multiplication and one containment test each time. Even if we use the information $1\cdot x=x\cdot 1=x$, we still have (|G|-1)² pairs to consider. But we can improve the performance of the procedure by taking into account that each element $g\in G$ is of the form

$$g= s_{i_1}\cdot s_{i_2} \cdots s_{i_k},$$

therefore it suffices to consider right multiplications of list elements by elements of S:

Procedure 2:

Now we only need to check $\vert G\vert\times \vert S\vert$ pairs, which is a good save if |S| << |G|.

Example 1.3.5   Let $x:=(12),\ y:=(123) \in \Sigma_3$, $S:= \{x,y\}$ and $G:= \langle S\rangle$ the subgroup of $\Sigma_3$ generated by S. Check that the above algorithm builds up the list of elements as follows:

${\rm list}_{(0)}:= [1,x,y]$, ${\rm list}_{(1)}:= [1,x,y,yx]$, ${\rm list}_{(2)}:= [1,x,y,yx,xy]$,

${\rm list}_{(3)}:= [1,x,y,yx,xy,xyx]$ with yx= (23), xy = (13) and xyx=(132).

To further improve the procedure we need some more structural information on the group and therefore some more theory:

For any two subsets A,B of the group G we define its complex product

$$AB:= \{ab\ \vert\ a\in A, b\in B\}$$

and $A^{-1}:= \{a\in G\ \vert\ a^{-1}\in A\}$. Let $H\le G$ and $B:= \{b\}$. Then one writes Hb instead of $H\{b\}$ and calls this subset the right H coset of b. Similarly the left coset

$$bH := \{bh\ \vert\ h\in H\}$$

is defined. It is easy to see that

$$Hb = Hb' \iff b'b^{-1}\in H \iff Hb\cap Hb'\ne \emptyset.$$

So the right cosets can be interpreted as the equivalence classes of the equivalence relation on G

$$g\sim_H g'\iff g'g^{-1}\in H.$$

Example 1.3.6   Let $G:= \langle x,y\rangle = \Sigma_3$ with x=(12) and y=(123) as above. Then for $A:=\{(12),(13)\}$, $B:=\{(12),(123)\}$ and $C:=\{ (12),(123), (13)\}$, we get

$$AB = \{(),(13),(132),(23)\} \ne BA = \{(), (123), (23), (12) \}.$$

Notice that $C\cdot (13) = \{(123), (12), ()\}\ne C$, with $\emptyset \ne C\cap C\cdot (13)$. This can only happen, because C is not a subgroup. The set $H:=\{(), (12)\}$ is a subgroup of order 2 and

$$G = H \uplus H\cdot (23) \uplus H\cdot (123).$$

The set of these right H - cosets is usually denoted by $H\backslash G$. (A confusion with the notation for the difference set $H\backslash G$ is unlikely, as this difference is always empty.) The set $\{ gH\ \vert\ g\in G\}$ is denoted by $G\ /\ H$.

The cardinality $\vert\{ Hg\ \vert\ g\in G\}\vert$ of the set of these classes is called the index of H in G and denoted by [G:H]. For any two right cosets Hg, Hg' the map

$$\cdot g^{-1}g':\ Hg \to Hg',\ hg \mapsto hg\cdot g^{-1}g'$$

is a bijection, hence |Hg|=|H| for all $g\in G$. A subset ${\cal R}\subseteq G$ is called a system of representatives for the right (left) cosets of H in G or a right (left) transversal of H in G if it contains precisely one element of each coset, in other words if $\vert{\cal R}\cap Hg\vert=1$ ( $\vert{\cal R}\cap (gH)\vert=1$ )for each $g\in G$. In particular we have $\vert{\cal R}\vert = [G:H]$.

In the example above we had $G = \Sigma_3 = H \uplus H\cdot (23) \uplus H\cdot (123)$ with the subgroup $H=\{(), (12)\}$ and the right transversal ${\cal R} = \{ (), (23), (123)\}$.

If ${\cal R}$ is such a transversal, we can write G as the disjoint union

$$G= \uplus_{g\in {\cal R}} \ Hg.$$

An immediate consequence of this is

Lemma 1.3.7 (Lagrange)   If G is a finite group with subgroup H, then

$$\vert G\vert = \vert H\vert\cdot [G:H].$$

Remark 1.3.8   (i): If G is a finite group and $g\in G$, then |g| divides |G|, because it is the order of the subgroup $\langle g\rangle \le G$. In particular 1.3.3 implies that g^|G| = 1 for all $g\in G$. For an arbitrary group the number

$${\rm exp}(G):= {\rm min}\ \{ m\in \mathbb{N}\ \vert\ g^m=1 \ \forall\in G\}$$

(with ${\rm exp}(G)=\infty$ possible) is called the exponent of G. It is easy to see that ${\rm exp}(G)$ divides |G| if G is finite. The infinite cartesian product $C_2^{\mathbb{N} }$ with componentwise multiplication is an infinite group with finite exponent.

(ii): In the situation $G = (\mathbb{Z} _p^*, \cdot)$, the multiplicative group of nonzero elements of the finite field with p elements (p a prime number), Lagrange's theorem implies Fermat's `little theorem':

$$n^{p-1} \equiv 1\ {\rm mod}\ p,\ \forall n\in \mathbb{N}\ {\rm with}\ p\not \vert\ n.$$

Lemma 1.3.9   Let $H\le G$ be a subgroup and $g\in G$. Then the following are equivalent:
(i): Hg is also a left coset of H (i.e. Hg = xH for some $x\in G$).
(ii): Hg=gH.
(iii): Hg^-1=g^-1H.
(iv): H^g:= g^-1Hg = H.
In particular the set $N_G(H):= \{g\in G\ \vert\ Hg=gH\}$ is a subgroup of G (called the normalizer in G of H) and the set

$$N_G(H)/H:= \{ Hg\ \vert\ g\in N_G(H)\}$$

is a group under the complex product.

Proof: `(i) $\Rightarrow$ (ii)': g=xh' for some $h'\in H$. This implies $x^{-1}g\in H$, hence xH=x(x<sup>-1</sup>gH)=gH=Hg.
`(ii) $\Rightarrow$ (iii)': Hg^-1 = (gH)^-1 = (Hg)^-1 = g^-1H.
`(iii) $\Rightarrow$ (iv)': Follows from multiplication by g from the right.
`(iv) $\Rightarrow$ (i)': Follows from multiplication by g from the left.
If $g,h\in N_G(H)$, then Ng^-1h=g^-1Nh=g^-1hN and $g^{-1}h\in N_G(H)$, so this is a subgroup of G. The complex product AB for subsets $A,B\subseteq G$ defines an associative multiplication on the power set 2^G of G. If $g,h\in N_G(H)$ then Ng Nh= NNgh=Ngh, and Ng Ng^-1 = Ngg^-1= N =NN. This shows that N_G(H)/H is a group with neutral element N. $\diamond$

Definition 1.3.10   A subgroup $N\le G$ is called normal or invariant (written $N\triangleleft G$), if N_G(N)=G or, in other words, if

$$\forall g\in G:\ g^{-1}Ng := \{ g^{-1}ng \ \vert\ n\in N\} = N.$$

The corresponding group of cosets (with complex product)

$$G/N:= \{ Ng=gN\ \vert\ g\in G\}$$

is called the factor group of G by N.

In practice a group G often occurs as a system of symmetries of a certain structured set $\Omega$ and one can get a `representation' of G as a subgroup of $\Sigma_\Omega$. We illustrate this with the following examples:

Example 1.3.11   We consider a square S and choose H to be the set of all those rotations in the two dimensional plane that map S onto itself as a whole. As set $\Omega$ we take the set ${\bf 4}:=\{1,2,3,4\}$ which will be identified with the corners of S as shown below:

From this we see immediately that $H=\langle h\rangle$ with $h:= (1,2,3,4)\in \Sigma_4$ is cyclic of order 4.
Now we let G be the set of all distance preserving symmetries of S. This includes reflections at the symmetry axes a, b, c and d.

The reflections at a and c can be identified with the transpositions $r_a:= (2,4),\ r_c:=(1,3)$ and the reflections at b and d are $r_b:= (1,2)(3,4),\ r_d:=(1,4)(2,3)$. Each element $1\ne g\in G$ either has no (pointwise) fixed symmetry axis and thus is a rotation in H, or it has exactly one symmetry axis and thus is one of the elements r_a,r_b,r_c or r_d. We conclude that |G|=8. Hence H is a subgroup of G with index [G:H]=2. It is easy to see, that any subgroup of index 2 is normal (check this!), so $H\triangleleft G$ and $G= \langle (1,2,3,4), (1,3)\rangle.$ We can calculate directly

(1,3) (1,2,3,4) (1,3) = (1,4,3,2) = (1,2,3,4)^-1,

which completely determines the multiplication of elements in G. (This group is called D₈, the `dihedral group' of order 8.)
The set ${\cal R} := \{ 1, (1,3)\}$ is a right transversal of H in G and

$$G= H \uplus H (1,3) = H \uplus (1,3) H$$

is the corresponding coset decomposition. In particular G/H is a group with two elements

$$G/H = \{H, H(1,3)\}.$$

Now we consider the subgroup $U:= \langle (1,3)\rangle$. We see that
$U (1,2,3,4) = \{(1,2,3,4),\ (1,4)(2,3)\};$
$U (1,3)(2,4) = U (2,4) = \{(1,3)(2,4),\ (2,4)\};$
$U (1,4,3,2) = \{(1,4,3,2),\ (1,2)(3,4)\}.$
Hence the decomposition of G into right cosets of U is given by

$$G= U \uplus U (1,2,3,4) \uplus U (1,3)(2,4) \uplus U (1,4,3,2).$$

From this we immediately obtain the decomposition into left cosets, by observing that (Ug)^-1 = g^-1U:

$$G= U \uplus (1,4,3,2) U \uplus (1,3)(2,4) U \uplus (1,2,3,4) U.$$

Notice that the right cosets U (1,2,3,4) and U (1,4,3,2) are not left cosets of U, hence $N_G(U)=\langle (1,3), (2,4) \rangle.$ Notice also that ${\cal R}:= \{ 1,\ (1,2,3,4),\ (1,3)(2,4),\ (1,4,3,2)\}$ as well as ${\cal R}':= \{ (1,3),\ (1,4)(2,3),\ (2,4),\ (1,2)(3,4)\}$ are two different right transversals of U in G. Now let's check, using MAPLE, that our calculation have been correct:

c1:=[[1,2,3,4]]; t1:=[[1,3]];



H:= permgroup(4,c1);

grouporder(H);

isabelian(H);

G:=permgroup(4,t1,c1);

grouporder(G);

mulperms(t1,mulperms(c1,t1));

isabelian(G);

cosets(G,H);



The cosets - function returns as set of representatives for right cosets of H in G.

T:=permgroup(4,t1);

cosets(G,T);



The output is different from what we computed by hand: firstly the order is arbitrary, secondly representatives of cosets are not unique. They can only differ by a factor of T. (Check that this is indeed the case here!)