Group Theory

Prerequisites: Basic Concepts of Abstract Algebra, Permutations and Arrangements

Introduction

Group theory mainly studies the algebraic structure of groups.

To understand the structure of groups, some fundamental tools are needed, including subgroups, group homomorphisms, and group actions. In competitive programming, the groups involved are primarily number-theoretic groups (such as the multiplicative group of integers modulo \(n\), \((\mathbf Z/n\mathbf Z)^\times\)) and permutation groups. This article will focus on introducing related concepts. For parts of group theory not covered here, such as the structure theory of finite groups and the linear representation theory of groups, interested readers should refer to specialized textbooks.

Notation

When no ambiguity arises, this article may write \(g\cdot h\) as \(gh\), and may also denote the group \((G,\cdot)\) simply as \(G\).

Understanding abstract algebra cannot be separated from examples. As an example to understand the following concepts, consider the spatial symmetry group \(D_6\) of an equilateral triangle.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle

As shown in the figure, for a given equilateral triangle, there are six distinct operations that map it onto itself.

Here, \(r\) denotes clockwise rotation, and \(s\) denotes reflection across the line from vertex \(1\) to the center of the triangle. Operations are composed from right to left, i.e., \(sr\) means first rotate (\(r\)) then reflect (\(s\)). Two operations are different if and only if the positions of the triangle's vertices differ after applying the two operations.

Notation	Operation	Order	Permutation Representation
\(e\)	Identity transformation, i.e., do nothing	1	\((1)\)
\(r\)	Rotate clockwise by \(120^\circ\)	3	\((123)\)
\(r^2\)	Rotate clockwise by \(240^\circ\)	3	\((132)\)
\(s\)	Reflect across the line from \(1\) to the center	2	\((23)\)
\(sr\)	Rotate by \(120^\circ\), then reflect	2	\((13)\)
\(sr^2\)	Rotate by \(240^\circ\), then reflect	2	\((12)\)

It is easy to verify that these operations indeed form a group. For example, the identity element of this group is \(e\), and the inverse of \(sr\) is itself. Moreover, the group \(D_6\) is not abelian; for instance, one can directly verify that \(rs=sr^{-1}\).

The operations recorded in the table are not the only symmetric operations corresponding to that notation. For example, "reflect across the line from vertex \(2\) to the center" is also a symmetric operation of the triangle. It is not in the table, but its effect is the same as the operation "rotate by \(120^\circ\), then reflect". Concepts such as "order" and "permutation representation" in the table will be explained later.

Subgroups

To understand the structure of a given group, one can first analyze its substructures. The substructures of a group are those subsets that themselves form a group under the same operation. This leads to the following definition.

Subgroup

For a group \((G,\cdot)\) and a subset \(H\subseteq G\), if \((H,\cdot)\) is also a group, then the subset \(H\) is called a subgroup of \(G\), denoted \(H\le G\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In \(D_6\), it is easy to verify that its subgroups are \(\{e\}\), \(\{e,s\}\), \(\{e,sr\}\), \(\{e,sr^2\}\), \(\{e,r,r^2\}\), and \(D_6\) itself, totaling six. Except for \(D_6\), the structures of these subgroups are simpler and contain partial information about the original group.

To determine whether a given subset \(H\subseteq G\) is a subgroup, it is not necessary to verify all group axioms: associativity holds naturally; for a subset to be a subgroup, it suffices to ensure it is closed under the binary operation, contains the identity element, and is closed under taking inverses. In fact, these conditions can be summarized together.

Theorem (Subgroup Criterion)

A subset \(H\) of a group \(G\) is a subgroup if and only if for all elements \(g,h \in H\), we have \(g^{-1}h\in H\).

Subgroup Generated by a Subset

In general, given a subset \(S\) of a group \(G\), starting from the elements in \(S\) and repeatedly performing multiplication and taking inverses finitely many times, the set of all possible results forms a subgroup of \(G\). This is called the subgroup generated by the subset \(S\).

Subgroup Generated by a Subset

For a group \(G\) and its nonempty subset \(S\subseteq G\), if \(H\) is the smallest (by inclusion) subgroup of \(G\) containing \(S\), then the subgroup \(H\) is called the subgroup generated by the subset \(S\), denoted \(\langle S\rangle\). In particular, if \(S=\{x\}\) is a singleton set, then \(\langle S\rangle\) is also denoted \(\langle x\rangle\), called the cyclic subgroup of the powers of the element \(x\).

It can be proved that given such a subset \(S\), such a subgroup always exists: \(\langle S\rangle\) can be constructed as the intersection of all subgroups of \(G\) containing \(S\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In the group \(D_6\), selecting the rotation operation \(r\) and repeatedly applying it and its inverse yields the subgroup \(\{e,r,r^2\}\). It can be denoted as \(\langle r\rangle\). All nontrivial subgroups of \(D_6\) can be generated by selecting some operation.

Some subsets generate the entire group. Such subsets are particularly special and are called generating sets of the group.

Generating Set of a Group

If a subset \(S\subseteq G\) of a group \((G,\cdot)\) satisfies \(\langle S\rangle=G\), then \(S\) is called a generating set of \(G\). The elements in the generating set \(S\) are called generators.

The group itself is a trivial generating set. More interestingly, generating sets can be much smaller than the group itself.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

It can be verified that \(D_6=\langle s,r\rangle\), meaning any symmetric operation of an equilateral triangle can be obtained by composing rotations and reflections.

Cyclic Groups

The structure of a group generated by a single element is very simple. Such groups are called cyclic groups.

Cyclic Group

For a group \(G\), if there exists \(x\in G\) such that \(G=\langle x\rangle\), then \(G\) is called a cyclic group.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

All nontrivial subgroups of \(D_6\) and \(\{e\}\) are cyclic groups.

It can be proved that the structure of a cyclic group is uniquely determined by its size. If the cyclic group is infinite, it must have the same group structure as the additive group of integers \((\mathbf Z,+)\), denoted \(C_\infty\) or \(\mathbf Z\); otherwise, if the number of elements is \(n\in\mathbf N_+\), it must have the same group structure as the additive group of integers modulo \(n\), \((\mathbf Z/n\mathbf Z,+)\), denoted \(C_n\) or \(\mathbf Z_n\). A rigorous statement of this conclusion requires the concept of group isomorphism introduced later, which precisely describes when two groups have the same structure.

Classification Theorem of Cyclic Groups

A finite cyclic group \(G\) of size \(n\) is isomorphic to \(C_n\); an infinite cyclic group \(G\) is isomorphic to \(C_\infty\).

Proof

Given a cyclic group \(G=\langle x\rangle\), it can always be written as \(G=\{x^n:n\in\mathbf Z\}\). If \(G\) is finite, then there exist natural numbers \(n<m\) such that \(x^n=x^m\). By the cancellation law, we get \(x^{m-n}=e\). At this point, take the smallest positive integer \(n\in\mathbf N_+\) such that \(x^n=e\). Then the sequence \(\{x^k\}\) will be a cycle of length \(n\), and the elements within a cycle are distinct (otherwise it would violate the minimality of \(n\)). Now, the mapping \(x^k\mapsto\bar k\) provides an isomorphism \(G\rightarrow\mathbf Z/n\mathbf Z\), i.e., \(G\cong C_n\). Conversely, if \(G\) is infinite, then the elements of \(G\) are all distinct, and the mapping \(x^k\mapsto k\) provides an isomorphism \(G\rightarrow\mathbf Z\), i.e., \(G\cong C_\infty\).

All cyclic groups are abelian. The example \(D_6\) in this article shows that even if all nontrivial subgroups of a group are cyclic, the group itself may not be abelian.

Order

The order of a group is the number of its elements. The order of a given element in a group is the order of the cyclic subgroup it generates. This leads to the following definitions:

Order of a Group

The order of a group \(G\) is its number of elements, denoted \(|G|\). The order of an infinite group is also infinite.

Order of an Element

The order of an element \(x\in G\) in a group \(G\) is the smallest positive integer \(n\) such that \(x^n=e\), denoted \(|x|\); if such \(n\) does not exist, the order of the element \(x\) is said to be infinite, denoted \(|x|=\infty\).

The order of an element always divides the order of the group; in fact, it will be proved later that the order of an element always divides the order of the group. However, the order of the group is not always the maximum order of its elements; for example, \(D_6\) is a group of order 6, but the maximum order of its elements is 3. The order of the group is also not necessarily the least common multiple of the orders of all elements; for example, the Klein four-group¹ \(V_4\) has order 4, but it contains only elements of order 1 and 2.

Theorem

In a finite cyclic group \(C_n=\langle x\rangle\), the order of the element \(x^k\) is

\[ \frac{n}{\gcd(k,n)}. \]

In particular, the number of generators of \(C_n\) is \(\varphi(n)\), where \(\varphi(\cdot)\) is the Euler totient function.

As an application of the above discussion, note that the order of the multiplicative group of integers modulo \(n\) is \(\varphi(n)\). The order of any element \(a\) in this group divides \(\varphi(n)\), so we must have \(a^{\varphi(n)}=1\). This is Euler's theorem, because the elements of this group are precisely those coprime to \(n\).

Cosets

The structure of elements outside a subgroup in a group is not chaotic.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

Observe the subgroup \(\langle r\rangle\) in \(D_6\). The remaining elements \(\{s,sr,sr^2\}\) have a structure very similar to \(\langle r\rangle\): each operation in it can be obtained by composing \(s\) with an operation from \(\langle r\rangle\). Similarly, consider the subgroup \(\langle s\rangle\). Then the remaining elements of the group can be divided into two classes: \(\{r,sr\}\) and \(\{r^2,sr^2\}\), which can be obtained by composing elements from \(\langle s\rangle\) with \(r\) and \(r^2\), respectively. This phenomenon is general.

Given a subgroup, its cosets can be defined.

Coset

Let \(G\) be a group and \(H\le G\) a subgroup. The left coset and right coset of \(H\) containing \(g\) are defined as the sets

\[ \begin{aligned} gH &= \{gh:h\in H\},\\ Hg &= \{hg:h\in H\}. \end{aligned} \]

Elements in a coset are called representative elements of the coset.

The subgroup itself is also one of its cosets. Given a subgroup, the set of all cosets forms a partition of the group, i.e., the group is the disjoint union of all cosets. A partition can always be viewed as the equivalence classes of some equivalence relation. For the partition into left cosets, this equivalence relation is \(g_1\sim g_2\) if and only if \(g_1^{-1}g_2\in H\); for the partition into right cosets, it is \(g_1\sim g_2\) if and only if \(g_1g_2^{-1}\in H\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In the language of cosets, the above examples show that \(D_6\) can be partitioned into \(\langle r\rangle\cup s\langle r\rangle\) and \(\langle s\rangle\cup \langle s\rangle r \cup \langle s\rangle r^2\), respectively. The former partitions the group into left cosets, the latter into right cosets. Note that the choice of representative is not special; for example, one can verify \(s\langle r\rangle=sr\langle r\rangle\). Any element in a coset can serve as a representative for that coset.

Different cosets of the same subgroup all have the same size, equal to the size of the subgroup. Since the set of all cosets of a given subgroup forms a partition of the group, the order of a finite group must be an integer multiple of the order of the subgroup. This is called Lagrange's theorem.

Lagrange's Theorem

For a finite group \(G\) and its subgroup \(H\le G\), we have \(|G|=[G:H]|H|\), where \([G:H]\) denotes the number of left (or right) cosets of \(H\) in \(G\), called the index of \(H\) in \(G\).

Proof

Consider the map \(h\mapsto gh\) given by left multiplication by \(g\). It and the map \(h\mapsto g^{-1}h\) are inverses of each other, so they are both bijections. This shows that \(|H|=|gH|\) always holds.

Note that the order of an element is the order of the cyclic subgroup it generates, so the order of an element must also divide the order of the group.

Normal Subgroup

In general, the left and right cosets of a given subgroup are not the same.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In the group \(D_6\), \(\langle s\rangle r=\{r,sr\}\), but \(r\langle s\rangle=\{r,sr^2\}\). However, if we consider the subgroup \(\langle r\rangle\), then the left and right cosets are always the same, because in this case the group has only two cosets, and the subgroup as one coset must coincide.

Whether left and right cosets are the same reflects properties of the corresponding subgroup.

Normal Subgroup

Let \(N\le G\) be a subgroup of a group \(G\). If for all \(h\in N\) and \(g\in G\), we have \(ghg^{-1}\in N\), i.e., for all \(g\in G\), \(gNg^{-1}\subseteq N\), then \(N\) is called a normal subgroup of \(G\), denoted \(N\trianglelefteq G\).

The condition in this definition is equivalent to \(gN=Ng\) always holding. A group \(G\) always has trivial normal subgroups: \(\langle e\rangle\) and \(G\) itself.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In the group \(D_6\), \(\langle s\rangle\) is not a normal subgroup, while \(\langle r\rangle\) is a normal subgroup.

Quotient Group

Normal subgroups are a very important class of subgroups, one reason being that quotient groups can be defined based on them.

For a group \(G\) and its normal subgroup \(N\trianglelefteq G\), consider the set of all cosets

\[ G/N = \{gN:g\in G\}. \]

Here, left and right cosets coincide, so no distinction is needed. Starting from the operation of \(G\), we can define a binary operation \(\circ\) on \(G/N\) satisfying

\[ g_1N\circ g_2N=(g_1g_2)N. \]

It can be proved that the result of the operation is independent of the choice of representatives². Then \((G/N,\circ)\) indeed has a group structure; it is called the quotient group of \(G\) modulo \(N\). The quotient group \(G/N\) is not a subgroup of \(G\); each of its elements is a subset of \(G\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

In the group \(D_6\), the meaning of the quotient group \(G/\langle r\rangle\) is quite clear. It essentially ignores the rotation angle in these symmetric operations and only focuses on whether the triangle is flipped. Composing two operations that both flip the triangle is equivalent to not flipping the original triangle; however, if one operation flips the triangle and the other does not, the composition necessarily flips the triangle. The presence or absence of flipping also has a group structure. Algebraically, ignoring the details of rotation and only considering the presence of flipping from the group \(D_6\) corresponds to taking the quotient group \(D_6/\langle r\rangle\) by modding out \(\langle r\rangle\). These arguments do not apply to the subgroup \(\langle s\rangle\), because if we ignore the presence of flipping, the degree of rotation cannot be clearly determined. This is why \(G/\langle s\rangle\) does not have the structure of a quotient group.

Quotient groups of a group can simplify complex groups, allowing one to understand the structure of the original group by observing part of its structure. This is also why quotient groups are called factor groups. Groups that contain no normal subgroups other than the trivial ones are called simple groups; these groups cannot be simplified into smaller groups. Like prime numbers, they are the building blocks of more complex group structures.

Group Homomorphisms

The second method to understand the structure of a given group is to compare the structures of two groups.

To compare the structures of two groups, one needs to construct a map between them. However, such a map cannot be arbitrary; it must preserve the group structure, meaning the group operation should be consistent before and after the mapping. Such maps are called group homomorphisms.

Group Homomorphism

Let \(\varphi:G\rightarrow H\) be a map from a group \((G,\cdot)\) to a group \((H,\odot)\). If \(\varphi\) preserves the group operation, i.e., \(\varphi(g_1\cdot g_2)=\varphi(g_1)\odot\varphi(g_2)\) for all \(g_1,g_2\in G\), then \(\varphi\) is called a homomorphism from \(G\) to \(H\).

A group homomorphism necessarily maps the identity element to the identity element and inverses to inverses.

Notation

In the following, if no ambiguity arises, the notation for the operations in groups \(G\) and \(H\) will not be distinguished, and for simplicity, these notations will be omitted.

Group Isomorphism

For a homomorphism \(\varphi:G\rightarrow H\) from \(G\) to \(H\), a natural question is to what extent this homomorphism reflects that the structures of \(G\) and \(H\) are the same. To this end, consider the image \(\varphi(G)\) of \(G\) under \(\varphi\), which maps the structure of \(G\) into \(H\). On one hand, \(\varphi(G)\) is a subgroup of \(H\); but if \(\varphi\) is not surjective, \(\varphi(G)\) is not the same as \(H\). On the other hand, \(\varphi\) may not be injective; if \(\varphi\) is not injective, then \(\varphi(G)\) only reflects part of the structure of \(G\). Only when \(\varphi\) is a bijection are the structures of \(G\) and \(H\) completely identical. This special kind of group homomorphism is called a group isomorphism.

Group Isomorphism

Let \(\varphi:G\rightarrow H\) be a homomorphism from \(G\) to \(H\). If \(\varphi\) is a bijection, then \(\varphi\) is called an isomorphism between \(G\) and \(H\), denoted \(G\cong H\).

Two isomorphic groups have completely identical structures. If one is only concerned with group structure, two isomorphic groups need not be distinguished. The classification theorem for cyclic groups given earlier is stated up to isomorphism.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

Returning to the earlier example, each symmetric operation of the equilateral triangle uniquely corresponds to a permutation operation on the set of vertices. The set of all permutations on the vertex set also forms a group, namely \(S_3\). It is easy to verify that the resulting map \(\varphi:D_6\rightarrow S_3\) is a group homomorphism; moreover, it is also a group isomorphism. So, \(D_6\cong S_3\). In fact, a group of order 6 is either isomorphic to \(C_6\) or to \(S_3\) (proof given later).

Classifying the structure of finite groups of a given order is an important research topic in group theory, but it is beyond the scope of this article.

Kernel of a Homomorphism

For a general homomorphism, one can further discuss how much information about the group structure is lost in the homomorphism. Continuing with the notation above. We know \(\varphi(G)\) is a subgroup of \(H\). Now the key question is the relationship between \(\varphi(G)\) and \(G\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

Consider the map \(\varphi: D_6 \rightarrow C_2 = \langle x\rangle\) defined as follows:

\[ \varphi(e)=\varphi(r)=\varphi(r^2)=e,\ \varphi(s)=\varphi(sr)=\varphi(sr^2)=x. \]

It is easy to verify that \(\varphi\) is a group homomorphism; it is surjective but not injective. Its meaning is clear: it maps each symmetric operation of the group to whether it flips the triangle. Such a homomorphism compresses the information in \(D_6\) about the rotation angle. For example, if there is no flip, any rotation maps to the identity element in \(C_2\).

This example suggests using the preimage of \(\{e\}\) to measure the structural information lost in the homomorphism. This leads to the following definition.

Kernel of a Homomorphism

Let \(\varphi:G\rightarrow H\) be a homomorphism from \(G\) to \(H\). The kernel of \(\varphi\) is \(\ker\varphi=\{g\in G:\varphi(g)=e\}\), where \(e\) is the identity element of \(H\).

Fundamental Theorem of Homomorphisms

The kernel \(\ker\varphi\) indeed characterizes the structural information lost in the group homomorphism. The precise statement of this conclusion is the fundamental theorem of group homomorphisms (also known as the first isomorphism theorem).

Fundamental Theorem of Homomorphisms (First Isomorphism Theorem)

Let \(\varphi:G\rightarrow H\) be a homomorphism from \(G\) to \(H\). Then \(\ker\varphi\trianglelefteq G\), and \(G/\ker\varphi\cong\varphi(G)\le H\).

Proof

First, \(N=\ker\varphi\) is a normal subgroup because for any \(h\in N\), \(\varphi(ghg^{-1})=\varphi(g)\varphi(h)\varphi(g)^{-1}=\varphi(g)\varphi(g)^{-1}=e\), i.e., \(ghg^{-1}\in\ker\varphi\). Then consider the map \(\Phi:G/N\rightarrow\varphi(G)\) defined by \(\Phi(gN)=\varphi(g)\). The map is well-defined because if \(g_1N=g_2N\), then \(g_1^{-1}g_2\in N\), so \(\varphi(g_1^{-1}g_2)=e\), i.e., \(\varphi(g_1)=\varphi(g_2)\). \(\Phi\) is clearly surjective; it is also injective because \(\ker\Phi=\{gN:\varphi(g)=e\}=\{N\}\). Hence, \(\Phi\) is a group isomorphism. Finally, \(\varphi(g_1)\varphi(g_2)^{-1}=\varphi(g_1g_2^{-1})\in\varphi(G)\), so by the subgroup criterion, \(\varphi(G)\) must be a subgroup.

Corollary

A homomorphism \(\varphi:G\rightarrow H\) is injective if and only if \(\ker\varphi=\{e\}\). In this case, \(G\) is isomorphic to a subgroup of \(H\), i.e., \(G\cong\varphi(G)\le H\).

That is, the kernel of a homomorphism \(\varphi\) is a normal subgroup of \(G\), and the quotient group \(G/\ker\varphi\) obtained by modding out \(\ker\varphi\) is isomorphic to the image \(\varphi(G)\), which is a subgroup of \(H\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

The kernel of the group homomorphism \(\varphi: D_6 \rightarrow C_2\) given above is \(\langle r\rangle\). Earlier, when discussing normal subgroups, we already noted that \(D_6/\langle r\rangle\) is indeed isomorphic to \(C_2\).

Natural Homomorphism

This conclusion is not surprising. This is because when constructing the homomorphism \(\varphi: D_6 \rightarrow C_2\), we were essentially using the geometric meaning of the quotient group \(D_6/\langle r\rangle\). This phenomenon is not rare. In fact, for every quotient group, one can construct a group homomorphism such that the image is isomorphic to the given quotient group.

Natural Homomorphism

For a group \(G\) and its normal subgroup \(N\trianglelefteq G\), the map \(\pi: G\rightarrow G/N\) given by \(\pi(g)=gN\) is a surjective homomorphism from \(G\) to \(G/N\), called the natural homomorphism or natural map from \(G\) to the quotient group \(G/N\).

This conclusion also shows that for any given normal subgroup of a group, one can find a corresponding group homomorphism whose kernel is precisely that normal subgroup. The fundamental theorem of homomorphisms earlier shows that the kernel of any homomorphism is a normal subgroup. Hence, normal subgroups and kernels of homomorphisms are two sides of the same coin.

Using the concept of the natural map, the fundamental theorem of homomorphisms essentially says the following commutative diagram holds.

Here, all arrows are group homomorphisms, \(N=\ker\varphi\) is the kernel of \(\varphi\), and \(\varphi(G)\) is the image of \(\varphi\). These maps are: \(\pi:g\mapsto gN\) is the natural map (surjective homomorphism) from \(G\) to \(G/N\); \(\Phi:gN\mapsto\varphi(g)\) is an isomorphism; and \(\iota\) is the inclusion map (injective homomorphism). The commutative diagram means that the composition of maps along the two different paths from \(G\) to \(H\) yields the same result, i.e., \(\varphi=\iota\circ\Phi\circ\pi\). The diagram clearly shows that the information lost in the homomorphism \(\varphi\) is reflected in \(\pi\) and \(\iota\).

Isomorphism Theorems for Groups

Powerful tools for understanding group structure are the isomorphism theorems for groups. The first isomorphism theorem has already been given. For completeness, other common isomorphism theorems are presented here.

The second isomorphism theorem involves the concept of the product of subgroups.

Product of Subsets

For a group \(G\) and its subsets \(A,B\subseteq G\), the product of subsets \(A\) and \(B\) is the subset \(AB=\{ab:a\in A,b\in B\}\).

The product of subgroups is not always a subgroup. For example, the product of subgroups \(A=\langle s\rangle\) and \(B=\langle sr\rangle\) of \(D_6\) is \(AB=\{e,s,r,sr\}\), which is not a subgroup of \(G\) because \((sr)s=r^2\notin AB\). In fact, counterexamples of the form \(a\in A\), \(b\in B\), but \(ba\notin AB\) are the fundamental reason why the product is not a subgroup. In this regard, we have the following theorem.

Theorem

For a group \(G\) and its subgroups \(A,B\le G\), the product \(AB\) is a subgroup if and only if \(AB=BA\).

Proof

If \(AB\) is a subgroup, then necessarily \(ba=(a^{-1}b^{-1})^{-1}\in AB\) for any \(a\in A\) and \(b\in B\), so \(BA\subseteq AB\). Conversely, if \(AB=BA\), then for any \(a_1,a_2\in A\) and \(b_1,b_2\in B\), we have \((a_1b_1)(a_2b_2)^{-1}=a_1b_1b_2^{-1}a_2^{-1}\in a_1BA=a_1AB=AB\). Then by the subgroup criterion, \(AB\) must be a subgroup.

The second isomorphism theorem (also known as the diamond isomorphism theorem) gives a simpler sufficient condition for the product of subgroups to be a subgroup and further determines its structure.

Second Isomorphism Theorem

Let \(G\) be a group and \(A,B\le G\) subgroups such that \(A\le N_G(B)\). Then \(AB\le G\), \(B\trianglelefteq AB\), \(A\cap B\trianglelefteq A\), and \(AB/B\cong A/(A\cap B)\). Here, \(N_G(B)\) is the normalizer of \(B\). In particular, a sufficient condition for \(A\le N_G(B)\) is \(B\trianglelefteq G\).

Proof

Since \(A\le N_G(B)\), we have \(aBa^{-1}=B\) for all \(a\in A\), i.e., \(aB=Ba\). Therefore, \(AB=BA\), so by the above theorem, \(AB\) is a subgroup. The subgroup \(B\), as a subgroup of \(AB\), has identical left and right cosets, so \(B\trianglelefteq AB\).

Consider the map \(\varphi:A\rightarrow AB/B\) defined by \(\varphi(a)=aB\). It is surjective, and its kernel \(\ker\varphi=\{a\in A:aB=B\}=A\cap B\). Applying the fundamental theorem of homomorphisms yields the result.

The third isomorphism theorem gives the correspondence between normal subgroups and quotient groups of a quotient group and those of the original group. It justifies the idea of further decomposing quotient groups.

Third Isomorphism Theorem

Let \(G\) be a group with normal subgroups \(H,K\trianglelefteq G\) such that \(H\le K\). Then \(K/H\trianglelefteq G/H\), and \((G/H)/(K/H)\cong G/K\).

Proof

Consider the map \(\varphi:G/H\rightarrow G/K\) defined by \(\varphi(gH)=gK\). It is a surjective group homomorphism, and \(\ker\varphi=\{gH:g\in K\}=K/H\). Applying the fundamental theorem of homomorphisms yields the result.

This result can be generalized to the fourth isomorphism theorem, also called the correspondence theorem, which further gives the correspondence between the subgroup lattice of a group and that of its quotient group.

Correspondence Theorem

Let \(G\) be a group with a normal subgroup \(N\trianglelefteq G\). Then there is a bijection \(\varphi:\mathcal H\rightarrow\mathcal S\) between the set of all subgroups of \(G\) containing \(N\), \(\mathcal H=\{H:N\subseteq H\subseteq G\}\), and the set of all subgroups of the quotient group \(G/N\), \(\mathcal S=\{S:S\le G/N\}\). It maps \(H\in\mathcal H\) to \(H/N\in\mathcal S\). This bijection preserves subgroup inclusion, and normal subgroups of \(G\) are mapped to normal subgroups of \(G/N\).

On the Content of Isomorphism Theorems

Different textbooks may vary in the content and names of the isomorphism theorems. The version chosen here is a common one. Wikipedia summarizes the differences in content and names among common textbooks.

Group Actions

The third method to understand the structure of a given group is to examine its action on a set.

For example, the spatial symmetry group of an equilateral triangle studied in this article is defined through the action of group elements (symmetric operations) on the triangle. Similarly, the symmetric group \(S_M\) can be defined by the action of its elements on the set \(M\). Here, an action means that each group element corresponds to a permutation on the set.

Group Action on a Set

For a group \(G\), a set \(X\), and a map \(G\times X\rightarrow X\), denote the image of \((g,x)\) under this map as \(g\cdot x\). If this map satisfies \(g_1\cdot(g_2\cdot x)=(g_1g_2)\cdot x\) and \(e\cdot x=x\) for all \(g_1,g_2\in G\) and \(x\in X\), then the map is called a group action of \(G\) on \(X\).

Left Action and Right Action

The definition of group action adopted here is sometimes⁴ called a left action because in the notation \(g\cdot x\), the group element is written to the left of the set element. Correspondingly, when composing group elements \(g_1g_2\) acting on the set, \(g_2\) acts first, then \(g_1\). Of course, one can similarly define a right action, denoted \(x\cdot g\). In that case, the order of composition of group elements is reversed compared to left action, i.e., \(x\cdot (g_1g_2)=(x\cdot g_1)\cdot g_2\). The two differ only in notation, not in essence, so this article defaults to left action notation.

For a group action satisfying the above definition, we naturally have the following construction:

\[ \begin{aligned} \varphi:{\color{Maroon}{G}}\rightarrow {\color{Orchid}{S_X}}&\\ {\color{Maroon}{g}}\mapsto {\color{Orchid}{\varphi_g}}&: {\color{RoyalBlue}{X}}\rightarrow{\color{YellowGreen}{X}}\\ &\quad {\color{RoyalBlue}{x}}\mapsto {\color{YellowGreen}{g\cdot x}}. \end{aligned} \]

This map assigns to each element \(g\) in \(G\) a permutation \(\varphi_g\) on \(X\), where \(\varphi_g\) maps \(x\) to \(g\cdot x\).

By definition, the identity element \(e\) corresponds to the identity map \(\varphi_e\) on \(X\), and the map \(\varphi_g\) corresponding to \(g\) and the map \(\varphi_{g^{-1}}\) corresponding to its inverse \(g^{-1}\) are inverses of each other (which also shows why \(\varphi_g\) is always a bijection). It can be verified that \(\varphi_{g_1g_2}=\varphi_{g_1}\varphi_{g_2}\), i.e., \(\varphi\) is a group homomorphism from \(G\) to \(S_X\).

This group homomorphism \(\varphi\) is called the permutation representation of the group action; it maps \(G\) into some permutation group.

Permutation Group

If a group \(G\) is a subgroup of some symmetric group, then \(G\) is called a permutation group.

The kernel of this homomorphism is also called the kernel of the group action. If this kernel is trivial, i.e., the homomorphism is injective, then the group action is called faithful, meaning the permutation representation faithfully reflects the group structure. In this case, \(G\) is isomorphic to the permutation group obtained from the permutation representation.

Notation

In the following, for simplicity, the \(\cdot\) notation in group actions will be omitted.

Orbit

A group action is a binary map. Fixing a group element \(g\) yields a permutation \(\varphi_g\) on the set. Fixing a set element \(x\) yields all possible results of the group acting on that element.

Orbit

For a group action of \(G\) on \(X\) and \(x\in X\), the orbit of \(x\) under the action of \(G\) is the subset \(Gx=\{gx:g\in G\}\).

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

For example, consider the action of the subgroup \(\langle s\rangle\le D_6\) on the vertex set of the equilateral triangle. The orbit of vertex \(1\) is \(\{1\}\), while the orbit of vertices \(2\) and \(3\) is \(\{2,3\}\). However, the action of the subgroup \(\langle r\rangle\le D_6\) on the vertex set has only one orbit: the entire vertex set.

It is easy to prove that under the action of \(G\), the set of all orbits of \(X\) forms a partition of \(X\), denoted \(X/G\). However, unlike cosets, these orbits are not necessarily of equal size.

Stabilizer

Under a group action, the length of the orbit of an element in the set depends on how many group elements correspond to permutations that fix it.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

For example, the reason the orbit of vertex \(1\) under the action of \(\langle s\rangle\le D_6\) has length one is that all group elements map vertex \(1\) to itself; the orbit of vertex \(2\) has length two because only the identity \(e\) maps vertex \(2\) to itself.

This inspires the following definition.

Stabilizer

For a group action of \(G\) on \(X\) and \(x\in X\), the stabilizer of \(x\) in \(G\) is the subgroup \(G_x=\{g\in G:gx=x\}\).

The kernel of a group action is the intersection of the stabilizers of all elements in the set.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

Consider the group action of \(D_6\) on the vertex set. The stabilizer of vertex \(1\) is \(\{e,s\}=\langle s\rangle\), a subgroup of \(D_6\). Since \(D_6\) can be partitioned into left cosets \(\langle s\rangle\), \(r\langle s\rangle\), and \(r^2\langle s\rangle\), it is easy to see that each left coset acts on vertex \(1\) in the same way.

This example shows that elements in an orbit correspond one-to-one with left cosets of the stabilizer. This implies the following result.

Theorem

For a group action of \(G\) on \(X\), the stabilizer \(G_x\) of an element \(x\in X\) is a subgroup of \(G\), and there is a bijection between the left cosets of \(G_x\) and the orbit \(Gx\).

Proof

Verify that the map \(gG_x\mapsto gx\) is a well-defined bijection.

Using Lagrange's theorem, we can relate the orbit length to the number of cosets of the stabilizer. This is the orbit-stabilizer theorem.

Orbit-Stabilizer Theorem

For a finite group \(G\) acting on a set \(X\) and \(x\in X\), we have \(|Gx|=[G:G_x]=|G|/|G_x|\).

One can verify this conclusion in the above example.

Burnside's Lemma

This lemma gives a formula for the number of orbits of a group action.

Burnside's Lemma

For a group action of \(G\) on \(X\), the number of orbits equals the average number of fixed points of the permutations corresponding to each group element, i.e.,

\[ |X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|. \]

Here, \(X^g=\{x\in X:gx=x\}\) is the set of fixed points of the permutation corresponding to \(g\in G\).

Proof

The proof of this theorem is quite concise. Note that the number of orbits can be written as

\[ |X/G|=\sum_{o\in X/G}1=\sum_{x\in X}\frac{1}{|Gx|}=\frac1{|G|}\sum_{x\in X}|G_x|. \]

The last equality follows from the above corollary; the right-hand side differs from what we want to prove only by a Fubini theorem, because both sums count the set \(\{(g,x)\in G\times X:gx=x\}\), with the right-hand side summing over \(g\) first and the desired formula summing over \(x\) first.

This theorem has many uses in combinatorics for counting "essentially distinct" objects. More examples and discussion can be found in Pólya enumeration.

Cayley's Theorem

To study group structure using group actions, one needs to choose a suitable set. In fact, the group itself is such a set. Therefore, we next consider two common group actions of a group on itself and use them to analyze group structure.

The first such action is the left multiplication action of a group on itself. Its permutation representation is as follows.

\[ \begin{aligned} \varphi:G\rightarrow S_G&\\ g\mapsto \varphi_g&: G\rightarrow G\\ &\quad x\mapsto gx \end{aligned} \]

The left multiplication action of a group is always faithful because groups satisfy the cancellation law. So, by the fundamental theorem of homomorphisms, \(G\) can be embedded into the symmetric group \(S_G\). This means every group is isomorphic to some permutation group³.

Cayley's Theorem

A group \(G\) is isomorphic to a subgroup of the symmetric group \(S_G\).

This group action has only one orbit, and the stabilizer of each element is \(\{e\}\).

Conjugation Action

The second action of a group on itself is called conjugation. Its permutation representation is as follows.

\[ \begin{aligned} \varphi:G\rightarrow S_G&\\ g\mapsto \varphi_g&: G\rightarrow G\\ &\quad x\mapsto gxg^{-1} \end{aligned} \]

Under the conjugation action of a group, orbits and stabilizers have special names.

Conjugacy Class

For a group \(G\) and \(g\in G\), the conjugacy class of \(g\) in \(G\) is the orbit of \(g\) under the conjugation action. If elements \(g\) and \(h\) are in the same conjugacy class, they are said to be conjugate.

Centralizer

For a group \(G\) and \(a\in G\), the centralizer of \(a\) in \(G\) is \(C_G(a)=\{g\in G:ga=ag\}\).

Center

For a group \(G\), the center of \(G\) is \(Z(G)=\cap_{a\in G}C_G(a)=\{g\in G:\forall a\in G(ga=ag)\}\).

The center of a group is the set of elements that commute with all elements of the group; because it is the kernel of the group action, it is necessarily a normal subgroup. The size of the center indicates how far the group is from being abelian. The centralizer of a given element is the set of all elements that commute with that element; it is the largest subgroup whose center includes it, which is the origin of its name; also, because it is the stabilizer of an element under the conjugation action, it is a subgroup. Conjugacy classes are generally not subgroups.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

Returning to \(D_6\), its center is \(\{e\}\neq G\), showing it is not abelian. The centralizer \(C_G(r)\) of \(r\) is \(\langle r\rangle\), and the centralizer \(C_G(s)\) of \(s\) is \(\langle s\rangle\). In general, for all \(g\in G\), we always have \(\langle g\rangle\le C_G(g)\). The conjugacy classes of \(D_6\) are three: \(\{e\},\{r,r^2\},\{s,sr,sr^2\}\). It is easy to see that conjugate elements have the same order⁵.

A group is partitioned into several conjugacy classes under conjugation. Thus, we can write the class equation.

Class Equation

For a group \(G\), let \(\{\mathcal K_i\}_{i=1}^r\) be all conjugacy classes of size greater than one, and let \(g_i\) be a representative of \(\mathcal K_i\). Then

\[ |G|=|Z(G)|+\sum_{i=1}^r[G:C_G(g_i)]. \]

It can be used to analyze group structure, for example, to prove the Sylow theorems below.

Normalizer and Centralizer

In fact, the power set of a group can also be an object of group action. Here we focus on the conjugation action of a group on its set of all subsets \(X=\mathcal P(G)\). Its permutation representation is as follows.

\[ \begin{aligned} \varphi:G\rightarrow S_X&\\ g\mapsto \varphi_g&: X\rightarrow X\\ &\quad S\mapsto gSg^{-1} = \{gsg^{-1}:s\in S\} \end{aligned} \]

Under this conjugation action, we can similarly define conjugacy classes of subsets of the group. Its kernel is still the center of the group. Its stabilizer is called the normalizer.

Normalizer

For a group \(G\) and a subset \(S\subseteq G\), the normalizer of \(S\) in \(G\) is \(N_G(S)=\{g\in G:gSg^{-1}=S\}\).

The normalizer is the stabilizer of \(S\) under the conjugation action, so it is necessarily a subgroup of \(G\); the normalizer of \(S\) is the largest subgroup in which \(S\) is contained as a normal subgroup, which is the origin of the name. In particular, for a singleton \(\{a\}\), \(N_G(\{a\})=C_G(a)\).

The centralizer can also be generalized similarly to subsets.

Centralizer

For a group \(G\) and a subset \(S\subseteq G\), the centralizer of \(S\) in \(G\) is \(C_G(S)=\{g\in G:\forall s\in S(gsg^{-1}=s)\}\).

The centralizer is actually the kernel of the conjugation action of \(N_G(S)\) on \(S\). So we necessarily have \(C_G(S)\trianglelefteq N_G(S)\le G\), so by transitivity of subgroups, the centralizer is also a subgroup. In particular, the center of the group \(Z(G)=C_G(G)\trianglelefteq N_G(G)=G\) is necessarily a normal subgroup.

Sylow Theorems

Further analysis of the conjugation action on finite groups yields the Sylow theorems. They are powerful tools for handling the structure of finite groups and can quickly yield the structure of many small-order groups.

\(p\)‑group

For a group \(G\), if there exists a prime \(p\) and a positive integer \(\alpha\) such that \(|G|=p^\alpha\), then \(G\) is called a \(p\)‑group.

On the Definition of \(p\)‑group

There is another definition of \(p\)‑group: a group where the order of every element is a power of a prime. These two definitions are equivalent for finite groups; however, the second definition also applies to infinite groups. Also, regarding the definition of \(p\)‑group, different literature may differ on whether \(\{e\}\) is considered a \(p\)‑group; readers should be aware when reading.

\(p\)‑subgroup

For a group \(G\) and a subgroup \(P\le G\), if \(P\) itself is a \(p\)‑group, then \(P\) is called a \(p\)‑subgroup.

Cauchy's Theorem

If a prime \(p\) divides the order of a group \(G\), then there exists an element of order \(p\).

Cauchy's theorem guarantees the existence of \(p\)‑subgroups. In fact, through more detailed analysis, a stronger conclusion can be obtained: the existence of Sylow \(p\)‑subgroups.

Sylow \(p\)‑subgroup

For a group \(G\) and a subgroup \(P\le G\), if \(|G|=p^\alpha m\) with \(p\perp m\) and \(|P|=p^\alpha\), then \(P\) is called a Sylow \(p\)‑subgroup.

That is, a Sylow \(p\)‑subgroup is a maximal \(p\)‑subgroup. The Sylow theorems assert the existence of Sylow \(p\)‑subgroups, providing a partial converse to Lagrange's theorem.

Sylow Theorems

Let the order \(|G|\) of a finite group \(G\) be expressed as \(p^\alpha m\), where \(p\) is a prime and \(p\) does not divide \(m\). Then:

1. Sylow \(p\)‑subgroups exist;
2. For a Sylow \(p\)‑subgroup \(P\) and a \(p\)‑subgroup \(Q\) of \(G\), there exists \(g\in G\) such that \(Q\le gPg^{-1}\); in particular, all Sylow \(p\)‑subgroups are conjugate;
3. The number \(n_p\) of Sylow \(p\)‑subgroups in \(G\) satisfies \(n_p\equiv 1\pmod p\), \(n_p\mid m\), and \(n_p=[G:N_G(P)]\), where \(P\) is any Sylow \(p\)‑subgroup.

Proof

To prove part 1, induct on \(|G|\). Consider the class equation

\[ |G|=|Z(G)|+\sum_{i=1}^r[G:C_G(g_i)]. \]

If \(p\mid|Z(G)|\), then take any \(p\)‑order subgroup \(N\le Z(G)\) of the center. Then necessarily \(N\trianglelefteq Z(G)\trianglelefteq G\), so \(G/N\) is a smaller group. By the induction hypothesis, it has a Sylow \(p\)‑subgroup \(P/N\). Then the preimage \(P\) under the natural homomorphism is a Sylow \(p\)‑subgroup of the original group \(G\). Thus, we only need to consider the case where \(p\) does not divide \(|Z(G)|\). In this case, we can take \(g_i\in G\) such that \(p\) does not divide \([G:C_G(g_i)]\). Hence, all powers of \(p\) in \(|G|\) appear in \(|C_G(g_i)|\). Again by the induction hypothesis, \(|C_G(g_i)|\) has a Sylow \(p\)‑subgroup \(P\), which is precisely a Sylow \(p\)‑subgroup of the original group \(G\).

To prove parts 2 and 3, let \(\mathcal S=\{gPg^{-1}:g\in G\}\) be the conjugacy class of a Sylow \(p\)‑subgroup \(P\) of \(G\), and consider the conjugation action of \(G\) on \(\mathcal S\) restricted to some \(p\)‑subgroup \(Q\). The set \(\mathcal S\) can be partitioned into orbits under this action. Suppose there are \(r\) orbits, with representatives \(P_i\). Then we have the identity

\[ |\mathcal S|=\sum_{i=1}^r[Q:Q\cap N_G(P_i)]. \]

Here, \(Q\cap N_G(P_i)\) is the stabilizer of \(P_i\) under the above group action. Let \(H=Q\cap N_G(P_i)\). Clearly \(H\le N_G(P_i)\), so by the second isomorphism theorem, \(P_iH/P_i\cong H/(P_i\cap H)\). Thus, \(|P_iH|=|P_i||H|/|P_i\cap H|\). The right-hand side is a power of \(p\), so the left-hand side must also be a power of \(p\), and we must have \(|P_i|\le |P_iH|\). But \(P_i\) is already the subgroup of \(G\) with the largest power of \(p\), so \(P_i=P_iH\). Substituting into the earlier isomorphism gives \(H=P_i\cap H=Q\cap P_i\). Here we used the obvious relation \(P_i\le N_G(P_i)\). Thus, the stabilizer \(Q\cap N_G(P_i)\) is actually \(Q\cap P_i\). So the above equation can be written as

\[ |\mathcal S|=\sum_{i=1}^r[Q:Q\cap P_i]. \]

This equality holds for all \(p\)‑subgroups \(Q\).

Naturally, a Sylow \(p\)‑subgroup \(P\) is also a \(p\)‑subgroup. Substituting \(P\) for \(Q\) in the above, the right-hand side has exactly one term of size \(1\), and the rest are multiples of \(p\). Therefore, the size \(|\mathcal S|\) of the conjugacy class of a Sylow \(p\)‑subgroup \(P\) must be congruent to \(1\) modulo \(p\). Also, since this formula holds for any \(p\)‑subgroup \(Q\), there must exist \(g\in G\) such that \(Q\le gPg^{-1}\); otherwise, for all \(P_i\) in the above equation, \(|Q\cap P_i|<|Q|\), contradicting \(|\mathcal S|\equiv 1\pmod p\). If we now consider \(Q\) to be a Sylow \(p\)‑subgroup different from \(P\), then necessarily \(Q=gPg^{-1}\) for some \(g\in G\), i.e., all Sylow \(p\)‑subgroups are conjugate. Hence, the number \(n_p\) of Sylow \(p\)‑subgroups is \(|\mathcal S|\), which must satisfy \(n_p\equiv 1\pmod p\). Finally, note that \(n_p=|\mathcal S|=[G:N_G(P)]\) and \(P\le N_G(P)\), so \(n_p\mid m\). This completes the proof of parts 2 and 3.

Application: Up to isomorphism, the only groups of order 6 are \(C_6\) and \(S_3\)

Let \(G\) have order 6. By Sylow theorems, it has a Sylow \(2\)‑subgroup, and their number satisfies \(n_2\equiv 1\pmod 2\) and \(n_2\mid 3\), so there are two cases: \(n_2=1\) or \(n_2=3\). Similarly, one can show \(G\) has exactly one Sylow \(3\)‑subgroup, i.e., \(n_3=1\).

For \(n_2=1\), we find \(G\) has a Sylow \(2\)‑subgroup, hence an element of order 2; it also has a Sylow \(3\)‑subgroup, hence two elements of order 3. \(G\) also has an identity element. The remaining elements, by Lagrange's theorem, must have orders dividing 6. They cannot be new elements of order 2 or 3, otherwise new Sylow \(p\)‑subgroups different from the previous ones would appear; so the remaining element must be of order 6. The existence of an element with the same order as the group means \(G\) is cyclic, so \(G\cong C_6\).

For \(n_2=3\), \(G\) has three conjugate Sylow \(3\)‑subgroups. Consider the conjugation action of \(G\) on these three Sylow \(3\)‑subgroups. For any Sylow \(3\)‑subgroup \(P\), by Sylow theorems, \(|N_G(P)|=2\); but also \(P\le N_G(P)\), so \(P=N_G(P)\). Therefore, the intersection of the normalizers of these three Sylow \(3\)‑subgroups, i.e., the kernel of this conjugation action, is trivial. So the action is faithful, embedding \(G\) into the permutation group \(S_3\) on these three Sylow \(3\)‑subgroups. But since \(|G|=|S_3|\), we must have \(G\cong S_3\).

Finitely Generated Abelian Groups

After mastering the basic tools for analyzing group structure, we now focus on discussing the structure of a particular class of groups.

As mentioned in the introduction, abelian groups have simpler structure compared to other groups because their elements commute. Particularly simple are those abelian groups that can be generated by finitely many elements.

Finitely Generated

A group \(G\) is said to be finitely generated if it has a finite generating set.

The classification theorem in this section shows that finitely generated abelian groups can be viewed as simple combinations of finitely many cyclic groups. Groups involved in competitive programming are mostly finite. Finite abelian groups are necessarily finitely generated, so this conclusion always applies.

Direct Product

Previous analysis of groups focused on how to decompose a group into smaller groups; conversely, one can discuss how to combine two groups into a larger group. Among all possible ways of combination, the direct product of groups is the simplest.

The basic idea of the direct product of groups is: given two groups \(G\) and \(H\), consider their Cartesian product \(G\times H\). The operation on pairs \((g,h)\) is defined componentwise, with the components independent. The result is clearly a larger group, and the original two groups can be trivially embedded into the new group.

Direct Product

The direct product of groups \((G,\cdot_G)\) and \((H,\cdot_H)\) is the group \((G\times H,\cdot)\), where the binary operation \(\cdot:(G\times H)\times(G\times H)\rightarrow G\times H\) is defined by \((g_1,h_1)\cdot(g_2,h_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2)\). The direct product of \(G\) and \(H\) is denoted \(G\times H\).

For the direct product \(G\times H\), we trivially have embedding maps \(g\mapsto(g,e_H)\) and \(h\mapsto(e_G,h)\). Conversely, the maps \((g,h)\mapsto g\) and \((g,h)\mapsto h\) are group homomorphisms, whose kernels are \(\{e_G\}\times H\) and \(G\times\{e_H\}\), respectively. These kernels are precisely the images of the above embedding maps, and their intersection is trivial, i.e., \(\{(e_G,e_H)\}\). So, the direct product \(G\times H\) contains two subgroups, both normal, with trivial intersection, and their product is \(G\times H\) itself.

This analysis actually gives a necessary and sufficient condition for a group to be the direct product of two of its subgroups.

Theorem

For a group \(G\) and its subgroups \(H_1,H_2\le G\), we have \(G\cong H_1\times H_2\) if and only if \(H_1,H_2\trianglelefteq G\), \(H_1\cap H_2=\{e\}\), and \(G=H_1H_2\).

Proof

The necessity of these conditions has been discussed in the main text; here we prove sufficiency. Consider the map \(\varphi:G\rightarrow H_1\times H_2\) defined by \(h_1h_2\mapsto(h_1,h_2)\). \(\varphi\) is well-defined because for any \(h_1,k_1\in H_1\) and \(h_2,k_2\in H_2\), if \(h_1h_2=k_1k_2\), then \(h_1=k_1\) and \(h_2=k_2\); this is because \(k_1^{-1}h_1=k_2h_2^{-1}\in H_1\cap H_2=\{e\}\). To show \(\varphi\) is a group homomorphism, we need to show \((h_1h_2)(k_1k_2)=h_1k_1h_2k_2\), which is equivalent to \(k_1\) and \(h_2\) commuting, i.e., \(k_1h_2k_1^{-1}h_2^{-1}=e\). To prove this, note that \(k_1h_2k_1^{-1}h_2^{-1}=(k_1h_2k_1^{-1})h_2^{-1}\in (k_1H_2k_1^{-1})H_2=H_2\), and similarly \(k_1(h_2k_1^{-1}h_2^{-1})\in H_1\), so \(k_1h_2k_1^{-1}h_2^{-1}\in H_1\cap H_2=\{e\}\). This proves \(\varphi\) is a homomorphism. It is clearly a bijection, hence an isomorphism, i.e., \(G\cong H_1\times H_2\).

In a direct product, elements from the two direct factors necessarily commute because \(hg=(e_G,h)(g,e_H)=(g,h)=gh\). So, if both direct factors are abelian, the direct product is also abelian.

Not all groups can be written as the direct product of two nontrivial subgroups.

Example: The spatial symmetry group \(D_6\) of an equilateral triangle (continued)

For example, \(D_6=\langle r,s\rangle\) is not isomorphic to \(\langle r\rangle\times\langle s\rangle\), because as the direct product of two cyclic groups, the latter is necessarily abelian.

The following classification theorem states that every finitely generated abelian group can be written as the direct product of finitely many cyclic groups.

Classification Theorem

For finitely generated abelian groups, we have the following classification theorem, called the fundamental theorem of finitely generated abelian groups.

Fundamental Theorem of Finitely Generated Abelian Groups

For a finitely generated abelian group \(G\), there exist an integer \(r\ge0\) and integers \(n_1,\cdots,n_s\ge 2\) such that

\[ G\cong C_\infty^r\times C_{n_1}\times\cdots\times C_{n_s}. \]

In particular, \(r\) is uniquely determined and is called the rank of \(G\), and

• One can choose integers \(n_1,\cdots,n_s\) satisfying \(n_1\ge2,\ n_1|n_2,\ \cdots,\ n_{s-1}|n_s\); in this case, the integers \(n_1,\cdots,n_s\) are uniquely determined, and the factors \(C_{n_i}\) are called the invariant factors of \(G\);
• Alternatively, one can choose integers \(n_1,\cdots,n_s\) to be prime powers; in this case, these prime powers are also uniquely determined, and the factors \(C_{n_i}\) are called the elementary divisors of \(G\).

The theorem first asserts that a finitely generated abelian group is always the direct product of finitely many cyclic groups.

Proof

We give a simple formal proof⁶; a deeper proof should refer to the structure theorem for finitely generated modules over a principal ideal domain⁷. In the proof, for simplicity, additive notation will be used instead of the general multiplicative notation for groups, with \(0\) representing the identity and \(mx\) representing the \(m\)‑th power of \(x\).

Suppose \(G\) can be generated by at least \(k\) elements. The proof proceeds by induction on \(k\). The case \(k=1\) is trivial. For \(k>1\), take a generating tuple \(\langle x_1,x_2,\cdots,x_k\rangle\) of \(G\) such that \(x_1\) has the smallest possible order. We want to show \(G=\langle x_1\rangle\times\langle x_2,\cdots,x_k\rangle\). The latter, by the induction hypothesis, can be decomposed as a direct product of \((k-1)\) cyclic groups, completing the induction step.

By the characterization of direct products, if the direct product decomposition fails, there must exist a relation \(m_1x_1+m_2x_2+\cdots+m_kx_k=0\) with \(m_1x_1\neq 0\). For negative coefficients \(m_i\), we can replace \(x_i\) with its inverse \(-x_i\), so all coefficients \(m_i\) can be taken as nonnegative integers. Moreover, we can take \(0< m_1 <|x_1|\). If we then take \(d=\gcd(m_1,m_2,\cdots,m_k)\) and \(c_i=m_i/d\), then \(y_1=c_1x_1+c_2x_2+\cdots+c_kx_k\) satisfies \(dy_1=0\), so \(|y_1|\le d\le m_1< |x_1|\), i.e., \(y_1\) is an element of smaller order than \(x_1\).

Next, we prove that \(y_1\) can be extended to a generating set of \(G\). That is, there exist elements \(y_2,\cdots,y_k\in G\) such that \(G=\langle y_1,y_2,\cdots,y_k\rangle\). The only known condition is that \(y_1\) itself can be written as \(c_1x_1+c_2x_2+\cdots+c_kx_k\), where the coefficients \(c_i\) are natural numbers with greatest common divisor 1. Assume the coefficients are (non-strictly) decreasing. Then \(y_1\) can also be written as \((c_1-c_2)x_1+c_2(x_1+x_2)+\cdots+c_kx_k\). Comparing with the previous condition, the coefficients are still all natural numbers with gcd 1, and \(G=\langle x_1,x_1+x_2,x_3,\cdots,x_k\rangle\), but the sum of all coefficients has decreased by \(c_2\). If \(c_2=0\), then necessarily \(c_1=1\), and the conclusion is trivial; otherwise, the sum of coefficients strictly decreases. This means that by inducting on the sum of coefficients, we can prove that such a \(y_1\) can always be extended to a generating set of \(G\).

Consequently, we have found a generator \(y_1\) of smaller order than \(x_1\), contradicting the choice of \(x_1\). Hence, the direct product decomposition must hold, and by induction the desired conclusion follows.

Of course, cyclic groups may be infinite or finite; they correspond to the \(C_\infty\) part and the \(C_{n_i}\) part in the decomposition, respectively. Then the theorem gives the structure of finite cyclic groups \(C_n\). The elementary divisor decomposition part of the theorem relies on the following observation.

Lemma

If \(m\) and \(n\) are coprime, then \(C_{mn}\cong C_m\times C_n\).

Proof

Let \(x\) and \(y\) be generators of \(C_m\) and \(C_n\), respectively. Since \((m,n)=1\), we have \(|(x,y)|=mn=|C_m\times C_n|\). So \((x,y)\) is a generator of \(C_m\times C_n\), i.e., \(C_m\times C_n=\langle(x,y)\rangle\). Hence, it is a cyclic group of order \(mn\), necessarily isomorphic to \(C_{mn}\).

Given a cyclic group \(C_{n}\), if by the fundamental theorem of arithmetic \(n=p_1^{r_1}\cdots p_k^{r_k}\), then repeatedly applying the lemma proves \(C_n=C_{p_1^{r_1}}\times\cdots\times C_{p_k^{r_k}}\). After these two steps of decomposition, we essentially obtain the elementary divisor decomposition in the theorem. Then, using the lemma to reassemble these prime-power cyclic groups so that their orders satisfy the required conditions yields the invariant factor decomposition in the theorem. The uniqueness in the theorem can be proved by induction.

Example: Classification of Abelian Groups of Order 24

As an example, the theorem tells us that all abelian groups of order 24 are of three types, listed below.

Invariant Factor Decomposition	Elementary Divisor Decomposition
\(C_{24}\)	\(C_{3}\times C_{8}\)
\(C_{2}\times C_{12}\)	\(C_2\times C_{3}\times C_4\)
\(C_2\times C_2\times C_6\)	\(C_2\times C_2\times C_2\times C_3\)

References and Notes

• Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3^rd Edition, John Wiley & Sons, Inc.
• Milne, J.S. (2021) Group Theory.
• Group (mathematics) - Wikipedia
• Group theory - Wikipedia
• Group - Wolfram MathWorld
• Visual Group Theory

---

1. This group can be represented as the permutation group \(\{(1),(12)(34),(13)(24),(14)(23)\}\), or written as \(C_2\times C_2\). ↩

2. For a general subgroup \(H\le G\), one can also try to define a similar operation on the set of all left (right) cosets. However, such an operation is well-defined if and only if \(H\) is a normal subgroup of \(G\). ↩

3. Cayley's theorem itself does not reflect much information about the group's structure because the group \(S_G\) is usually very large, and it is hard to say what definite properties a subgroup of size exactly \(|G|\) has. However, early group theory development focused mainly on permutation groups. So Cayley's theorem essentially says that all possible group structures are among these already well-studied objects. In practice, more refined tools are needed. ↩

4. For example, Group action - Wikipedia. ↩

5. More generally, conjugate elements in a permutation group necessarily have the same cycle type. ↩

6. See Milne, J.S. (2021) Group Theory, page 25. ↩

7. See Structure theorem for finitely generated modules over a principal ideal domain - Wikipedia. ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用