1. Groups of Transformations and Permutations
, the set of invertible 2-by-2 matrices with real entries, can be made into a group by considering the matrix multiplication operation as the binary operation on . Matrix multiplication is associative; the identity matrix serves as the group identity; every invertible matrix is, well, invertible. In this manner, is a group of matrices.
Recall, however, that every matrix defines a linear transformation. In the case of , every defines a linear transformation given by the formula , where represents the matrix-vector multiplication. In other words, every element of the group transforms 2-vectors to some other 2-vectors. From this angle, is a group of transformations on .
Similarly, then, we can define the group of invertible -by- matrices with entries in a field and consider it a group of transformations on , the space of -vectors with entries in . Generalizing even further, we define the general linear group on a vector space over a field , denoted by , to be the group of all invertible linear transformations with function composition as the group operation. Each element of takes vectors in and transforms them into other vectors in . In other words, is a group of transformations on .
But what is a “group of transformations”, really? Every group we have discussed above has one thing in common: each group comes with some set on which each element of can be thought of as a function . The most general group of this kind is the symmetric group on a nonempty set , which is the collection of all bijections . We require the functions to be bijections, so that with respect to the function composition operation is a bona fide group. Note that the general linear group is a subgroup of , the symmetric group on the vector space .
Being a bijection, an arbitrary element of the symmetric group transforms each element of in a way that preserves . Indeed, if we let act on the elements of , then we end up with , relabeled. In this sense, the elements of are called permutations on , and subgroups of permutation groups on .
2. Cayley’s Theorem; Basic Definitions and Examples
Let us now consider an abstract group . Unlike or , the group does not come equipped with an obvious set on which the elements of can act as permutations. What we do have is a binary operation on , which takes two elements of and outputs one element of . This is to say that, by fixing one of the two input parameters, the group operation can be thought of as a function on . We formalize this observation as follows:
Theorem 2.1 (Cayley). Every group is isomorphic to a permutation group on .
Proof. Given a , we define the left regular representation by setting for each . We note that is a bijection, as is the inverse of .
Let us now define a left-multiplication map by declaring for each . We fix and observe that
for all . From this, it follows that . Since and were arbitrary, we conclude that is a group homomorphism.
It remains to show that is injective, whence is isomorphic to , a subgroup of . To this end, we fix and suppose that . This, in particular, implies that
Since the inverse element of a fixed group element is unique, we conclude that . This completes the proof of Cayley’s theorem.
We glean from Cayley’s theorem an important idea: we can make an abstract group act on a set by identifying with a permutation group on .
Definition 2.2. Let be a group. A permutation representation of is a group homomorphism into the symmetric group on some set . Given a nonempty set , we say that acts on if there exists a permutation representation ; in this case, is referred to as a -set. If, in addition, is injective, then we say that acts faithfully on .
Given a permutation representation , we often write
to denote . This is the left action notation, which we shall use throughout this post. Also prevalent in the literature is the right action notation, which employs
to denote . We will not use the right action notation in this post.
Here is a simple exercise to get you used to the left action notation.
Exercise 2.3. If acts on , then the following holds:
(1) for all .
(2) for all and .
Conversely, if (1) and (2) holds, then the mapping given by the formula is a permutation representation.
We shall therefore use the left action notation and the permutation representation notation interchangeably. In construcitn a group action, we often define a map and check that it is a permutation representation, or define a dot operation and check that properties (1) and (2) hold. If a group action arises from restricting an already-extant functions on a smaller domain , then we must also check that the range of is a subset of : see Example 2.10.
Let us now study several examples of group actions. There is no need to peruse all of these on the first read: take a look at a few, move on to Section 3, come back whenever certain examples are cited.
Example 2.4. Let be a nonempty set. The symmetric group acts faithfully on via the identity representation that sends each to itself. If is a subgroup of , then the canonical injection map that sends each to itself is an injective permutation representation of on . Therefore, acts faithfully on .
Now, if is a set that contains as a subset, then we can define an injective group homomorphism by setting
In other words, we identify with the subgroup of permutations on that permutes and fixes . It now follows that acts faithfully on . Moreover, is an injective group homomorphism, whence acts faithfully on . We summarize the chain of permutation representations as follows:
Example 2.5. In general, if acts on , then every subgroup of acts on . To see this, we take a permutation representaiton and precompose it with the canonical injection map , obtaining another permutation representation . Note that if the action of on is faithful, then so is induced action of on .
Even more generally, if acts on , and if is a group homomorphism from another group into , then acts on .
Example 2.6. The general linear group is a subgroup of the symmetric group , and so acts faithfully on .
Example 2.7 (Linear groups). We introduce a few important subgroups of . Since is a subgroup of the symmetric group , Example 2.4 implies that all such subgroups act faithfully on . The special linear group is the subgroup consisting of matrices of determinant 1. The orthogonal group is the subgroup consisting of matrices such that , where denotes the matrix transpose operation and the -by- identity matrix. The special orthogonal group is the subgroup .
If , then we typically write and to denote and , respectively. Both and act faithfully on .
If , then we define the unitary group to be the group of matrices such that , where denotes the conjugate transpose operation. The special unitary group is the subgroup . Both and act faithfully on .
Example 2.8 (Isometry groups, orthogonal groups, and symmetry groups). Let denote the usual Euclidean norm of . An isometry on is a function such that for all . We note that isometries are always injective. Indeed, if for some , then , whence .
The key fact is as follows; see, for example, Theorem 6.2.3 in M. Artin’s Algebra for a proof.
Theorem 2.8.1. If is an isometry, then there exists an such that for all .
Since the mapping is a bijection, we see that every isometry on is an element of , the symmetric group on . It follows from Example 2.4 that any group of isometries on acts faithfully on . Note also that Theorem 2.8.1 implies that is, in fact, the group of all isometries on such that .
Let us now fix a subset of . An isometry is said to be a symmetry of if . Since is a restriction of an injective function, it must be injective. The surjectivity is guaranteed by defintion, and so we conclude that a symmetry of is a permutation on . Therefore, any group of symmetries of is a subgroup of , whence by Example 2.4 it acts faithfully on . In particular, the symmetry group of , which we define below, acts faithfully on :
Definition 2.8.2. Let . The symmetry group of is the group of all symmetries of .
For example, is the symmetry group of the -sphere
To see this, we first fix . is invertible, and so the mapping is injective on . Moreover, for each , we see that
whence is an element of such that . It follows that the mapping is a symmetry of . We conclude that the symmetry group of includes .
To show the reverse inclusion, we fix a symmetry of and show that for some . It suffices to show that , for then the desired result follows from Theorem 2.8.1.
To this end, we suppose for a contradiction that and let . Since
we see that . Now, Theorem 2.8.1 implies that
which contradicts the assumption that is a symmetry of . It now follows that is the symmetry group of .
Example 2.9 (Dihedral groups). We have already discussed dihedral groups as abstract groups in my blog post on generators and relations. Here we give an alternate definition that brings forth the geometric nature of the groups. Consider , the orthogonal group of degree 2. We have seen in Example 2.8 that is the symmetry group of the unit circle . The typical elements of are the rotation matrices
and the reflection matrices
Note that . Since
represents reflection with respect to the axis. Consequently, can be thought of as reflection with respect to an appropriate axis of reflection determined by the rotation matrix .
An important fact about rotation matrices and reflection matrices in is as follows; see, for example, Section 2.1 of Grove & Benson, Finite Reflection Groups for a proof.
Theorem 2.9.1. is generated by .
We now define the dihedral group of degree , denoted by , to be the subgroup of generated by and . Every element of is a symmetry of the regular -gon whose vertices are precisely the elements of the following set:
By Theorem 2.9.1, every symmetry of is a finite product of rotation matrices and . Since the symmetry group of cannot contain rotation matrices other than , we see that every symmetry of must be a finite product of and . The relation now implies that all such products can be written in the form for some . All such isometries are already included in the dihedral group, and so we conclude that is the symmetry group of . In particular, it follows from Example 2.8 that acts faithfully on .
Example 2.10 (Actions of dihedral groups on other sets). Recall , the dihedral group of degree , from Example 2.9. We think of as a subgroup of , so that each element of is a 2-by-2 matrix. For all , we define . The set
is a subset of , the unit circle in . Let us define a -action on by setting for each and every . To check that this is indeed a group action, we must check that the mapping is a bijection on . This can be checked explicitly, using rotation matrices and reflection matrices introduced in Example 2.9. can now be thought of as a subgroup of , whence Example 2.4 implies that acts faithfully on .
Let us now assume that is even, and consider the following collection of two-element sets:
The -action on given by setting is likewise a group action. Note, however, that rotation by fixes all elements of . It follows that this -action is not faithful.
Example 2.11 (Regular actions). Recall from the proof of Cayley’s theorem that the left-multiplication map with respect to is the map . The mapping that sends each to the corresponding left-multiplication map is a permutation representation, called the left regular representation.
Analogously, we define the right-multiplication map with respect to to be the map . The map that sends each to the corresponding right-multiplication map is a permutation representation, called the right regular representation.
We note that acts faithfully on itself in both cases.
Example 2.12 (Regular action on cosets). Let be a group and be a subgroup of . We define , the collection of all left cosets. We define a -action on by setting . This is indeed a group action, as and
for all .
Example 2.13 (Conjugation on elements). Combining the left-multiplication map and the right-multiplication maps from Example 2.10, we obtain a very important permutation representation. We define the conjugation representation of a group to be the map defined by the formula . Since , we see at once that each is a permutation on . Observe that , and that
It follows that is a permutation representation. The resulting action is referred to as the conjugation action. In light of this, we call the conjugation of by .
The conjugation action is not necessarily faithful. For example, if is abelian, then regardless of the choice of .
Example 2.14 (Conjugation on subgroups). Let be a group, and let be the collection of all subgroups of . We claim that the conjugate subgroup of an arbitrary subgroup of is also a subgroup of , regardless of our choice of . To see this, we fix . Since , the identity element is in . If , then
as . Therefore, is closed under group operation. Finally, if , then
as . We conclude that . Let us now define a mapping by setting for each and every . Observe that is a permutation on , as is the inverse of . Moreover,
and so is a permutation representation. Similarly as in Example 2.13, the action induced by is not necessarily faithful. For example, if , then for all and .
3. Counting Principles
Let us now turn to the abstract theory of group actions; some applications of the theory presented in this section can be found in Section 4. The two fundamental objects associated with a group action are as follows:
Definition 3.1. Let act on , and fix . The -orbit of is
The stabilizer, or theisotropy subgroup, of is
We remark that is a subset of , and that is a subgroup of . Example 3.2. Pick a group and let act on itself by conjugation (see Example 2.13). The orbit of is the conjugacy class of
and the stabilizer of is the centralizer
Example 3.3. Pick a group and let act on the collection of all subgroups by conjugation (see Example 2.14). The orbit of is the collection of all conjugates
and the stabilizer of is the normalizer
Exercise 3.4. Write down orbits and stabilizers for actions introduced in Example 2.9, Example 2.10, Example 2.11, and Example 2.12.
How are the orbit and the stabilizer of a point related? Observe that the coset can be rewriten as follows, by making the substitution :
Therefore, there is a one-to-one correspondence between the cosets and the points of the form . Now, the collection of all points of the form is precisely the stabilizer . We therefore conjecture that equals the number of cosets . This turns out to be true:
Theorem 3.5 (Orbit-stabilizer theorem). Let a group act on a set . For each fixed , we have the formula
Proof. Let denote the left coset space of . We define a function by setting . Let us first check that is well-defined. Indeed, if , then , and so . Therefore, , whence . It follows that is well-defined.
We claim that is bijective. If , then , and so . This implies that , whence . It follows that is injective. Moreover, for all , and so is surjective. We conclude that .
The orbit-stabilizer theorem is a counting principle, in the sense that many combinatorial results about finite groups can be derived as simple corollaries. Below, we establish a few.
Corollary 3.6. Let a finite group act on . For each , we have the identity . In particular, divides .
Proof. We apply Lagrange’s theorem and the orbit-stabilizer theorem to obtain the following:
Diving through by , we obtain the desired result.
Corollary 3.7. Let be a finite group. For each , the number of conjugates of equals .
Proof. Apply the orbit-stabilizer theorem to Example 3.2.
Corollary 3.8. Let be a finite group. For each , the number of conjugate subgroups of equals .
Proof. Apply the orbit-stabilizer theorem to Example 3.3.
As alluded to above, each of the three corollaries give rise to useful combinatorial results in group theory. Let us first establish a combinatorial restriction on the size of . For this, we need the following result:
Theorem 3.9 (Orbit decomposition theorem). Let a group act on a set . The collection forms a partition of .
Proof. Suppose that and fix . Find such that . It now follows that for all , whence . Similarly, we see that for all , and so . We conclude that .
The following combinatorial principle now is an immediate corollary of what we have established thus far.
Corollary 3.10. Let a finite group act on a finite set . Let be a subset of consisting of one representative from each set in the partition formed by the orbits (see Theorem 3.9). Then
Proof. The first equality is an immediate consequence of Theorem 3.9. The second equality follows from the orbit-stabilizer theorem (Theorem 3.5). The third equality follows from Corollary 3.6. When a group acts on itself, then Corollary 3.10 becomes a statement about the cardinality of the group itself. Let us carefully translate Corollary 3.10 in the context of conjugation action. For this, we need the following result:
Corollary 3.11. The conjugacy classes of a group form a partition of .
Proof. From Example 3.2, we know that the orbits of the conjugation action of on itself are precisely the conjugacy classes. The orbit decomposition theorem (Theorem 3.9) now furnishes the desired result.
We are now ready to adapt Corollary 3.9 to describe groups acting on themselves by conjugation.
Theorem 3.12 (Conjugacy class equation). Let be a finite group. Let be a subset of consisting of one representative from each set in the partition formed by the conjugacy classes (see Corollary 3.11). Then
where is the center of .
Proof. The first equality follows from Corollary 3.10 and Corollary 3.7. The second equality follows from the fact that the conjugacy class of each element in the center is a singleton set.
The class equation, combined with Corollary 3.8, allows us to establish powerful converses to Lagrange’s theorem, which we establish in the next section. We conclude by establishing a combinatorial restriction on the size of .
Theorem 3.12 (Burnside’s lemma). Let a finite group act on a finite set . Let be a subset of consisting of one representative from each set in the partition formed by the orbits (see Theorem 3.9). Then
where denotes the number of elements of fixed by the action of .
Proof. We first observe that
as there are -many orbits in the equivalence class of furnished by the orbit decomposition theorem (Theorem 3.9). For each and every , we define
We now invoke the orbit-stabilizer theorem (Corollary 3.6) to deduce that
as was to be shown.
4. Sylow’s theorems
While Lagrange’s theorem imposes restrictions on the orders of subgroups and elements of a group, it does not guarantee the existence of a subgroup or an element of a certain order.
Example 4.1. Consider the alternating group , which is of order 12. We show that has no subgroup of order 6. To this end, we shall make use of the following preliminary result:
Lemma 4.2. Every subgroup of a group of index 2 is normal in .
We assume for now that the lemma holds. Suppose for a contradiction that is a subgroup of of order 6, which must be a normal subgroup of by the lemma. The conjugacy classes of are as follows:
Since is normal, must be a union of conjugacy classes. Since must be a subset of , this implies that we ought to be able to write as a sum of 1 and the cardinalities of conjugacy classes. This is impossible, and so we conclude that has no subgroup of order 6.
It now suffices to establish the lemma. Let be a group and let be a subgroup of index 2. Note that the two left cosets of are itself and for an arbitrary . Fix and . If , then . We therefore suppose that . If , then , and so . This, in particular, implies that , whence , a contradiction. It follows that , as was to be shown.
See Brennan and MacHale, “Variations on a Theme: Definitely Has no Subgroup of Order Six!” for alternate proofs.
When, then, could we establish a converse to Lagrange’s theorem? The solution is intimately tied to the study of -groups, which we now define.
Definition 4.3. Let be a prime number. A group is said to be a -group if each element of is of order for some integer that depends on the element.
The problem of finding a nontrivial -subgroup of a group is equivalent to finding an element of of order . Indeed, if is an element of order , then the cyclic subgroup is a nontrivial -subgroup of . Conversely, if is a nontrivial -subgroup of , then we can find a non-identity element of order . In this case, is an element of order .
Now, in order for a finite group to have a -subgroup, the order of must be divisible by . The following result shows that the converse holds.
Theorem 4.4 (Cauchy, 1845). Every finite group whose order is divisible by a prime number contains an element of order .
Proof. We first prove the theorem for abelian groups. We shall proceed by induction on . If , then is a group of prime order, hence cyclic; it follows that contains an element of order .
Fix and suppose that every abelian group of order for each contains an element of order . Let be a non-identity element of . If is divisible by , then some power of is of order . If not, then is an abelian group of order for some , whence it contains an element of order . Now, the canonical projection is a homomorphism, and so the order of must be divisible by , order of . It follows that some power of must be . By induction, every Aelian group whose order is divisible by contains an element of order .
We now lift the assumption that is abelian. Once again, we proceed by induction on . The case is established above. Fix and suppose that every group of order for some contains an element of order . Let . If , then , the number of conjugates of , is larger than , and so . By induction, must contain an element of order , whence so must . We may therefore assume that whenever . Lagrange’s theorem now implies that whenever . We now invoke the conjugacy class equation (Theorem 3.12):
Since and all are divisible by , it follows that is divisible by . But is abelian, and so must contain an element of order . It follows that contains an element of order .
Cauchy’s theorem provides a convenient equivalence characterization of finite -groups:
Corollary 4.5. A finite group is a -group if and only if the order of is a power of .
Proof. If , then Lagrange’s theorem implies that is a -group. If is divisible by some other prime , then Cauchy’s theorem implies that contains an element of order , and so is not a -group.
The main result of this section is a substantial strengthening of Cauchy’s theorem, due to Sylow.
Definition 4.6. A Sylow -subgroup of a group is a maximal -subgroup. In other words, if is a Sylow -subgroup of , then no other -subgroup of properly contains .
Sylow’s theorems concern the existence and various other properties of Sylow -subgroups of finite groups whose orders are divisible by .
Theorem 4.7 (Sylow, 1872). Let be a finite group of order , where is a prime number and is an integer relatively prime to . The following holds:
First Sylow theorem. contains a Sylow -subgroup of order .
Second Sylow theorem. All Sylow -subgroups are conjugates of one another. In other words, if and are Sylow -subgroups of , then there exists a such that . This, in particular, implies that all Sylow -subgroups are isomorphic to one another.
Third Sylow theorem. Let denote the number of Sylow -subgroups of . We have the following combinatorial restrictions on :
- divides ;
Before we prove the Sylow theorems, we make a few observations. Firstly, the second Sylow theorem, in conjunction with the third Sylow theorem and Corollary 4.5, implies that has a normal subgroup of order if and only if . The third Sylow theorem provides two combinatorial restrictions on , which can be exploited in various clever ways to determine . Secondly, the second Sylow theorem, in conjunction with the first Sylow theorem, implies that every Sylow -subgroup of is of order . In other words, maximality in subgroup inclusion automatically implies maximality in order. Thirdly, the maximality observation, combined with the second Sylow theorem, implies the following structure theorem:
Corollary 4.8 (Frattini’s argument). Let be a finite group and a normal subgroup of . If is a Sylow -subgroup of for some prime , then
Proof of Corollary. Fix . Since is normal in , we see that . Now, , and so is a Sylow -subgroup of by maximality. The second Sylow theorem therefore furnishes such that , so that . It follows that . Since was arbitrary, the factorization establishes the desired identity.
Let us now turn to the proof of the Sylow theorems, which are taken from Rotman, An Introduction to the Theory of Groups. As in the statement of the theorem, we assume that . We shall make use of the following lemma:
Lemma 4.9. Let be a Sylow -subgroup of a finite group . The following holds: (1) is relatively prime to ; (2) If is of order for some and , then .
Proof of lemma. (1) If is divisible by , then Cauchy’s theorem (Theorem 4.4) furnishes an element of order . Therefore, is a subgroup of of order .
Let be the canonical projection map and set . If , then , and so . It follows that . Moreover, the first isomorphism theorem, in conjunction with Lagrange’s theorem, implies that
whence by Corollary 4.5 is a -subgroup of containing . This contradicts the maximality of , and so we conclude that fails to be divisible by .
(2) Note that is of order . Since , we see that , and so . If , then , and so . By Lagrange’s theorem, must be divisible by , and this contradicts (1).
Proof of the Second and Third Sylow theorems. Let denote the collection of all conjugates of in , where . Taking a cue from Example 2.14, we define the conjugation action of on as follows: for each . It is routine to check that is a group homomorphism from to : a simple modification of the argument in Example 2.14 suffices.
Let be an arbitrary Sylow -subgroup of . is a subgroup of , and so acts on by conjugation (Example 2.5). By the orbit-stabilizer theorem (Corollary 3.6), the size of each orbit divides , whence by Corollary 4.5 each is a power of .
If for some , then for all . In this case, we must have by Lemma 4.9(2). Since is a -group by Corollary 4.5, the maximality of implies that , and so . Now, if we take to be , then we must have for all , and so for some whenever . By the orbit decomposition theorem (Theorem 3.9), is the disjoint union of distinct orbits, whence equals 1 plus a sum of powers of . In other words, .
Now, we assume for a contradiction that is a Sylow -subgroup of not included in . We have shown above that whenever . Therefore, we must have for some for all . This, in particular, implies that , contradicting the 1-mod-p relation. Therefore, all Sylow -subgroups are conjugates of one another. This, in particular, implies that , whence .
We now invoke the orbit-stabilizer theorem to the conjugation action of on the set of all subgroups of to deduce that (Corollary 3.8). Lagrange’s theorem implies that divides . This completes the proof of the second and third Sylow theorems.
Proof of the first Sylow theorem. Cauchy’s theorem (Theorem 4.4) implies that has a subgroup of order , which is a -subgroup of . This, in particular, shows that has a Sylow -subgroup . Indeed, if is a non-Sylow -subgroup of , then, by definition, there exists a -subgroup of that properly contains . Since is finite, this process must terminate in finitely many steps, and we obtain a Sylow -subgroup .
We claim that is relatively prime to . Since Corollary 4.5 implies that must be a power of , the claim, in conjunction with Lagrange’s theorem, implies that and , as was to be shown. To prove the claim, we shall make use of the following lemma:
Lemma 4.9. If is a finite group and , then .
Proof of lemma. This is an immediate consequence of the fact that cosets of a subgroup partition a group into equal-sized equivalence classes. We let , , and and invoke the lemma to show that both and are relatively prime to . We apply the orbit-stabilizer theorem to the conjugation action of on the set of all subgroups of to deduce that (Corollary 3.8). The third Sylow theorem implies that that , whence is relatively prime to .
As for , we first note that , so that It follows from Lemma 4.9(1) that is relatively prime to . This concludes the proof of the first Sylow theorem.
The Sylow theorems play an important role in the classification of finite groups. We give examples of classification results in the next blog post, wherein we study semidirect products and the extension problem.