551, Fall '00   A2a.  Cosets; Transitive Actions; Counting Principle   p. 1

Math 551 – Algebra – Fall 2000

A. Groups

2. Group Actions

The close connection between groups and permutations is captured in the fundamental idea of group actions. Groups are important because they act on things.

Definition. Let G be a group and Ω a set. A (group) action of G on Ω is a mapping

G × Ω → Ω, (g, ω) ↦ gω,

such that

1) 1ω = ω for all ω ∈ Ω;
2) g(hω) = (gh)ω for all g, h ∈ G and all ω ∈ Ω.

We could add the property:

3) gω = ω′ ⟺ g^{−1}ω′ = ω, but it is redundant. The second equation follows from the first by applying g^{−1} to both sides and using the above properties; the first follows from the second by applying g to both sides.

Notice that for fixed g ∈ G, there is the mapping ℓ_{g} : Ω → Ω given by ℓ_{g}(ω) = gω. The axioms are that ℓ_{1} = id_{Ω} and ℓ_{g}ℓ_{h} = ℓ_{gh}. In particular ℓ_{g}ℓ_{g^{−1}} = ℓ_{g^{−1}}ℓ_{g} = ℓ_{1} = id_{Ω}, and so

Each ℓ_{g} is a permutation of Ω, i.e. a bijection from Ω to Ω.

Some important examples of group actions follow.

Ex. A. Let G ≤ Σ_{Ω}. Then G acts on Ω via σω = σ(ω).

Ex. B. Let G be a group. Then G acts on itself via gh = gh. This is the “left regular” action of G. There is also a “right regular” action, defined by gh = hg^{−1}. (The “products” on the left are the results of the action of a group element g on a set element h; on the right, the products are from the multiplication in G.)

2a. Cosets; classification of transitive actions; counting principle

Ex. C. Let G be a group and H a subgroup of G. We define an equivalence relation ∼_{H} on G

as follows:

a ∼_{H} b ⟺ a^{−1}b ∈ H.

p. 2                  A2.    Group Actions                   551, Fall '00

The facts that 1 ∈ H, H is closed under inversion, and H is closed under multiplication translate directly into the reflexivity, symmetry and transitivity of ∼_{H}. (Check this!) The equivalence classes of G are called the left cosets of H in G, and the set of all left cosets of G is denoted G/H. It is a partition of G, as is the set of equivalence classes for any equivalence relation. The cardinality of G/H is the “index” of H in G and is written |G : H|. Thus by definition, |G : H| = |G/H|.

Lemma. The left coset of H containing the element a ∈ G is the set aH = {ah | h ∈ H}. Moreover |H| = |aH| for any a ∈ G.

Proof. If a ∼_{H} b, then b = a(a^{−1}b) ∈ aH. Conversely if b ∈ aH, then b = ah for some h ∈ H, and a^{−1}b = h, so a ∼_{H} b. Finally the mapping h ↦ ah is a bijection between H and aH. QED

Lagrange’s Theorem. If H ≤ G, then |G| = |H||G : H|. If G is finite, then |G : H| = |G|/|H|.

The first statement is actually true even if G is infinite, with cardinal multiplication. In any case for G finite, it is a trivial consequence of the previous lemma.

Corollary. If H ≤ G and G is finite, then |H| divides |G|.

Corollary. If g ∈ G and G is finite, then |g| divides |G|.

Corollary. A group of prime order is cyclic.

Proof. Let G have order p and choose g ∈ G with g ≠ 1. Then |g| > 1, so |g| = p by the previous corollary, and hence |⟨g⟩| = p. Therefore G = ⟨g⟩. QED

Given H, the equivalence relation ∼_{H} is “preserved” by the left regular action of G:

∀a, b ∈ G, a ∼_{H} b ⟺ ga ∼_{H} gb.

This is trivial as (ga)^{−1}(gb) = a^{−1}g^{−1}gb = a^{−1}b. Hence the left regular action of G must permute the equivalence classes, and thus induces an action of G on G/H, via

g(aH) = (ga)H.

Definition. A group action of G on Ω is transitive if and only if for every ω, ω′ ∈ Ω there exists g ∈ G such that gω = ω′.

Proposition. If H ≤ G, then the action of G on G/H defined above is transitive.

Proof. (g(g′)^{−1})g′H = gH. QED Theorem. (Classification of transitive actions) Suppose that G acts transitively on Ω. Let ω ∈ Ω and set G_{ω} = {g ∈ G | gω = ω}. Then

1) G_{ω} ≤ G.

2) There exists a bijection ϕ : G/G_{ω} → Ω such that ϕ(G_{ω}) = ω and for every g ∈ G

and Γ ∈ G/G_{ω},

ϕ(gΓ) = gϕ(Γ).

Thus the actions of G on G/G_{ω} and Ω are “isomorphic”.

Proof. If gω = ω = hω, then (gh)ω = g(hω) = gω = ω, and also g^{−1}ω = g^{−1}(gω) = (g^{−1}g)ω = 1ω = ω. This proves 1).

Define Φ : G → Ω by Φ(g) = gω. The transitive action of G on Ω implies that Φ is surjective. For any g, h ∈ G,

Φ(g) = Φ(h) ⟺ gω = hω ⟺ h^{−1}gω = ω ⟺ h^{−1}g ∈ G_{ω} ⟺ g ∼_{G_{ω}} h.

So the fibers of Φ are the left cosets of G_{ω}. Therefore Φ induces an injective mapping ϕ : G/G_{ω} → Ω such that ϕ(gG_{ω}) = Φ(g) = gω. Since Φ is surjective, so is ϕ, so ϕ is a bijection. Finally for any Γ = hG_{ω} ∈ G/G_{ω} we have

ϕ(gΓ) = ϕ(g(hG_{ω})) = ϕ((gh)G_{ω}) = (gh)ω = g(hω) = gϕ(hG_{ω}),

completing the proof.

Corollary. (The counting principle, transitive case) Let G act transitively on Ω. Then for any ω ∈ Ω,

|Ω| = |G : G_{ω}|.

Ex. C. Let I be a regular icosahedron and G = Aut(I), the group of all its symmetries. Then G acts on I, and in particular on the set Ω of the 12 vertices of I. The action is clearly transitive. The stabilizer G_{ω} of a particular vertex ω contains 5 rotations and 5 reflections, which permute the 5 faces containing ω in the manner D_{10} permutes the 5 vertices of a regular pentagon. Therefore |G| = |G_{ω}||I| = 10 · 12 = 120.

A corollary of the counting principle is that |G_{ω}| = |G_{ω′}| for any ω, ω′ ∈ Ω (in the case of transitive actions). In fact more is true: G_{ω} ≅ G_{ω′}. In fact more is true: G_{ω} and G_{ω′} are conjugate.

Definition. Let G be a group and g, x ∈ G. Then ^{g}x = gxg^{−1}. The elements x and y of G are conjugate in G if and only if y = ^{g}x for some g ∈ G.

Conjugation has the following important properties for all x, g, h ∈ G:

1) ^{1}x = x.
2) ^{g}(^{h}x) = ^{gh}x.

In other words, G acts on itself by conjugation. (The action is not transitive unless G = {1}, since ^{g}1 = 1 for all g ∈ G.) Moreover,

3) ^{g}(xy) = ^{g}x^{g}y for all g, x, y ∈ G. This is easily verified, and so for fixed g ∈ G,

the mapping

Int(g) : G → G defined by Int(g)(x) = ^{g}x

is an automorphism of G (we saw above that it is a bijection as a consequence of the group action properties). It is called the inner automorphism of G determined by g. Two elements, subsets or subgroups A, B of G are said to be conjugate in G if and only if Int(g)(A) = B for some g ∈ G. If A and B are subgroups, then the restriction Int(g)|A is a bijection between A and B which is multiplicative, and so is an isomorphism between A and B. In particular

Conjugate subgroups are isomorphic.

Conjugation gives lots of examples of transitive actions. Let X be a subset (such as a subgroup) of G and let Ω = {^{g}X | g ∈ G} be the set of all G-conjugates of X. Then G acts on Ω by conjugation: g ^{h}X = ^{gh}X. We define N_{G}(X) = {g ∈ G | ^{g}X = X}. This is the stabilizer in G of the element X ∈ Ω. Thus the counting principle yields:

Corollary. Let G be a group and X a subset of G. Then N_{G}(X) is a subgroup of G and the number of distinct G-conjugates of X is |G : N_{G}(X)|.

Taking X to be a singleton X = {x}, we see that N_{G}(X) is the set of all elements of G which commute with x. This is called C_{G}(x), the centralizer of x in G.

Corollary. Let G be a group and x ∈ G. Then C_{G}(x) is a subgroup of G and the number of distinct G-conjugates of x is |G : C_{G}(x)|.

Returning to a transitive action of G on Ω, let ω, ω′ ∈ Ω. Write ω′ = gω for some g ∈ G. Then for any h ∈ G,

hω′ = ω′ ⟺ hgω = gω ⟺ g^{−1}hgω = ω ⟺ g^{−1}hg ∈ G_{ω} ⟺ h ∈ gG_{ω}g^{−1}.

That is,

G_{gω} = ^{g}G_{ω}.

Now we consider not necessarily transitive actions. Let G act on Ω. Define a relation ≡ on Ω by

ω ≡ ω′ ⟺ ∃g ∈ G such that gω = ω′.

By properties 1), 2) and 3) in the definition of group action, this relation is reflexive, transitive and symmetric. So it is an equivalence relation. The equivalence classes are called orbits, more precisely the G-orbits on Ω. Notice that G acts transitively on each orbit.

551, Fall '00    A2b.  Class Equation; Groups of Prime Power Order    p. 5

Theorem. (Counting principle, general case) Let G act on Ω. Let the set of orbits be {Ω_{i} | i ∈ I} and choose for each i ∈ I an element ω_{i} ∈ Ω_{i}. Then

|Ω| = ∑_{i} |G : G_{ω_{i}}|.

Proof. |Ω| = ∑_{i} |Ω_{i}| = ∑_{i} |G : G_{ω_{i}}|, the first since the orbits partition Ω, and the second by the transitive case of the counting principle.

2b. Class equation of a finite group; actions of groups of prime power order

An interesting application is the “class equation” of a group. Let G be any group, and consider G to act on itself by conjugation. The action is certainly not transitive (unless G = 1), since {1} is an orbit. The orbits of this action are called the conjugacy classes of G. If C is a conjugacy class and x ∈ C then |C| = |G : C_{G}(x)| by the previous corollary. Thus if we choose a set of representatives {g_{i} | i ∈ I} for the conjugacy classes (i.e., a subset of G which consists of one element from each conjugacy class), the counting principle yields

|G| = ∑_{i∈I} |G : C_{G}(g_{i})|.

It is customary to separate out the terms in this sum which are equal to 1; i.e., those for which C_{G}(g_{i}) = G. This condition is equivalent to g_{i} not having any conjugates in G other than itself, which is equivalent to g_{i}x = xg_{i} for all x ∈ G. The center of G is defined by

Z(G) = {g ∈ G | gx = xg∀x ∈ G},

and so consists of the elements contributing 1 to the sum above. We have proved

Theorem. (The Class Equation) Let G be a finite group. Then

|G| = |Z(G)| + ∑_{j} |G : C_{G}(g_{j})|,

where the sum is over a set of representatives for all the conjugacy classes of G except those in Z(G), and thus |G : C_{G}(g_{j})| > 1 for each term in the sum.

Proposition. For any G, Z(G) ≤ G.

Proof. Left to reader. QED

The class equation has important consequences for finite groups; one cute one is the following:

Theorem. Let G be a group such that |G| is a positive power of a prime. Then Z(G) ≠ {1}.

Proof. Let p be the prime. In the class equation, |G| as well as each term |G : C_{G}(g_{j})| is a positive power of p, by Lagrange’s Theorem. Therefore |Z(G)| ≡ 0 mod p. Certainly 1 ∈ Z(G) so |Z(G)| ≥ p. QED

Before giving an application of this we observe that virtually the same argument proves the following:

Theorem. Let G be a finite group of order p^{a}, p a prime, and suppose that G acts on the finite set Ω. Define Fix_{Ω}(G) = {ω ∈ Ω | gω = ω ∀g ∈ G}. Then

| Fix_{Ω}(G)| ≡ |Ω| mod p.

QED

Now for an application:

Corollary. Let G be a group whose order is p^{2}, p a prime. Then G is abelian (and is isomorphic either to Z_{p} × Z_{p} or to Z_{p^{2}}).

Proof. We prove that G is abelian, i.e., Z(G) = G, and leave the rest as an exercise. Assume by way of contradiction that Z(G) < G. We can choose g ∈ Z(G) with g ≠ 1 by the theorem, and choose h ∈ G − Z(G). Then |⟨g⟩| = p and as ⟨g, h⟩ properly contains ⟨g⟩ and has order which divides p^{2},

G = ⟨g, h⟩.

But gh = hg and it quickly follows that any word in g and h commutes with any other, so that G is abelian. QED

2c. Sylow’s Theorem

Here is another interesting consequence, a “baby Sylow theorem”:

Theorem. Let G be a finite group, and let p be a prime divisor of |G|. Then G possesses an element of order p.

Proof. Define

Ω = {(g_{1}, g_{2}, …, g_{p}) | g_{i} ∈ G ∀i = 1, …, p and g_{1}g_{2} ⋯ g_{p} = 1}.

Notice that this condition is equivalent to

g_{p} = (g_{1} ⋯ g_{p−1})^{−1},

551, Fall '00                 A2c.    Sylow's Theorem                 p. 7

and so for each g_{1}, …, g_{p−1} ∈ G, there is a unique p-tuple in Ω starting with g_{1}, …, g_{p−1}. Therefore

|Ω| = |G|^{p−1}.

Now let H = ⟨h⟩ be a cyclic group of order p, and let H act on Ω by h^{i}(g_{1}, g_{2}, …, g_{p}) = (g_{i+1}, g_{i+2}, …, g_{i+p}), where we interpret subscripts as having been reduced to their residue modulo p in the range between 1 and p. It is easy to check that this defines an action of H on Ω. Therefore by the previous theorem,

Fix_{Ω}(H) ≡ |Ω| = |G|^{p−1} ≡ 0 mod p.

Notice that (1, 1, …, 1) is a fixed point of H, and so there exists another fixed point (z_{1}, z_{2}, …, z_{p}). Since this point is fixed, we have z_{1} = z_{2} = ⋯ = z_{p}. Therefore z_{1} ≠ 1, and the definition of Ω yields z_{1}^{p} = 1. QED

We can even almost prove the full version of Sylow’s Theorem. The proof we shall give is old—it is very close to Sylow’s original proof—and I think that it’s still the best.

Sylow’s Theorem. (unusual version) Let G be a finite group and let p be a prime. Let P(G) be the set of all subgroups of G whose cardinality is a power of p and which are maximal with this property with respect to inclusion. Then the following hold:

1) Write |G| = p^{m}b with p not dividing b. Then |P | = p^{m} for every P ∈ P(G).

2) Any two elements of P(G) are conjugate.

3) |P(G)| ≡ 1 mod p.

4) For any P ∈ P(G), |P(G)| = |G : N_{G}(P)|.

Here the criterion for a subgroup P to belong to P(G) is that |P | is a power of p, and whenever P ≤ Q ≤ G with |Q| also a power of p, then P = Q. Thus if a is the largest integer such that G has a subgroup of order p^{a}, then every subgroup of G of order p^{a} lies in P(G). It is possible a priori that some smaller subgroups also lie in P(G). But in any case, since G has subgroups whose order is a power of p (e.g., the trivial subgroup), it is obvious that

P(G) ≠ ∅.

Sylow’s Theorem. (usual version) Let G be a finite group, p a prime, and write |G| = p^{m}b with p not dividing b. Let Syl_{p}(G) be the set of subgroups of G of cardinality p^{m}. The the following hold:

1) Syl_{p}(G) is not empty.

2) Any two elements of Syl_{p}(G) are conjugate.

3) | Syl_{p}(G)| ≡ 1 mod p.

4) For any P ∈ Syl_{p}(G), | Syl_{p}(G)| = |G : N_{G}(P)|.

5) Any subgroup of G whose order is a power of p lies in some element of Syl_{p}(G).

Lemma. The unusual version implies the usual version.

Proof. The unusual 1) implies that P(G) ⊆ Syl_{p}(G). But also if P ∈ Syl_{p}(G) and P ≤ Q ≤ G with |Q| a power of p, then |Q| ≤ |P | by Lagrange’s Theorem so P = Q. Therefore

P(G) = Syl_{p}(G).

Now 1), 2), 3) and 4) are immediate. In 5), if R ≤ G with |R| a power of p, then there exist subgroups Q ≤ G such that R ≤ Q ≤ G and |Q| is a power of p (namely, R itself is such a subgroup). Choosing such a Q of largest order, we find that Q ∈ P(G). Hence Q ∈ Syl_{p}(G) and 5) holds. QED

We shall prove 2), 3) and 4) of the unusual version now. For 1) we need a teeny bit more; but we shall present the argument anyhow, and it will be valid once we have proved the necessary extra (the third isomorphism theorem).

First, if g ∈ G and P ∈ P(G), then ^{g}P ∈ P(G). For conjugation by g is an automorphism of G, so preserves the cardinality and inclusion relation among subgroups. So

G acts on P(G) by conjugation.

The following lemma will allow us to use the counting principle effectively.

Lemma. Let P ∈ P(G). Then Fix_{P(G)}(P) = {P }.

Proof. Of course ^{g}P = P for all g ∈ P as P is a subgroup of G. So P is a fixed point. Now let Q ∈ P(G) be such that ^{g}Q = Q for all g ∈ P. We must prove that Q = P. To do this it is enough to show that P Q = {xy | x ∈ P, y ∈ Q} is a subgroup of G whose order is a power of p. For then P ≤ P Q ≥ Q so by the definition of P(G), P = P Q = Q.

To see that P Q is a subgroup of G, notice that gQg^{−1} = Q for all g ∈ P, so gQ = Qg for all g ∈ P. Therefore P Q = QP. It follows that (P Q)(P Q) = P (QP)Q = P (P Q)Q = P P QQ = P Q and (P Q)^{−1} = Q^{−1}P^{−1} = QP = P Q, so P Q is indeed a subgroup. Moreover every element of P Q may be written xy, x ∈ P, y ∈ Q, and xy = x′y′ ⟺ x^{−1}x′ = y(y′)^{−1} ∈ P ∩ Q. So each element of h ∈ P ∩ Q gives a way to vary xy to another representation (xh)(h^{−1}y) of the same element. Consequently xy can be represented exactly |P ∩ Q| ways as a product of an element of P and one of Q, so

|P Q| = |P ||Q|/|P ∩ Q| = |P : P ∩ Q||Q|,

a power of p as required. QED

Exercise. For any subsets X and Y of a group G, define XY = {xy | x ∈ X, y ∈ Y }, and also define X^{−1} = {x^{−1} | x ∈ X}. Suppose now that X and Y are subgroups of G. Show that

1) XY ≤ G if and only if XY = Y X.
2) |XY | = |X||Y |/|X ∩ Y |.

Proof of 2). Let P and Q belong to P(G). Since G acts on P(G) there is an orbit O_{P} of G on P(G) containing P. If Q ∈ O_{P}, then P and Q are G-conjugate. So assume by way of contradiction that Q ∉ O_{P}.

Now G acts on O_{P}, so P and Q both do. Since O_{P} contains P but not Q, P has a unique fixed point on O_{P} but Q has none. Therefore

1 = | Fix_{O_{P}}(P)| ≡ |O_{P} | ≡ | Fix_{O_{P}}(Q)| = 0 mod p,

a contradiction.

Proof of 3). Since G acts on P(G), so does P. Then

|P(G)| ≡ | Fix_{P(G)}(P)| = 1 mod p

by the lemma.

Proof of 4). This is immediate from 2) and the transitive version of the counting principle.

Almost-Proof of 1). The proof is by induction on |G|. If |G| = 1, the result is trivially true! In general, choose P ∈ P(G); our task is to prove that |G : P | is not divisible by p. Now |G : N_{G}(P)| ≡ 1 mod p, and in particular |G : N_{G}(P)| is not divisible by p. Since P is maximal among subgroups of G of order a power of p, and P ≤ N_{G}(P), certainly P is maximal among subgroups of N_{G}(P) whose order is a power of p. Hence P ∈ P(N_{G}(P)). If N_{G}(P) ≠ G, then by induction, |N_{G}(P) : P | is not divisible by p. But |G : P | = |G : N_{G}(P)||N_{G}(P) : P | is then not divisible by p, as required. So we may assume that N_{G}(P) = G.

In terminology below, this means that P ◁ G. We can therefore form the group G/P, and assume that the order of this quotient group if divisible by p, and derive a contradiction to the maximality of P. By the little Sylow theorem above, G/P has a subgroup of order p. By the third isomorphism theorem below, this subgroup has the form R/P for some subgroup R ≤ G with P ≤ R. But then |R : P | = p, so |R| = p|P | and R ≥ P, contradicting the maximality of P. QED

This unassuming result is unmatched for power in all of finite group theory.

As an example of its use we show:

Proposition. There two isomorphism types of groups of cardinality 6, namely Z_{6} and Σ_{3}.

Proof. These two groups of order 6 are not isomorphic since Z_{6} is abelian and Σ_{3} is not. Now let G be any group of order 6. We must show that either G ≅ Z_{6} or G ≅ Σ_{3}.

Let P ∈ Syl_{3}(G). By Sylow’s theorem the number of Sylow 3-subgroups is |G : N_{G}(P)|, which divides |G : P | = 2 and is congruent to 1 mod 3. Therefore P is the unique Sylow 3-subgroup, so ^{g}P = P for all g ∈ G. We have P = ⟨x⟩ for some x ∈ G of order 3.

Likewise by Sylow’s Theorem there exists y ∈ G of order 2. Then ⟨x⟩ ∩ ⟨y⟩ is a subgroup whose order divides both 2 and 3, so ⟨x⟩ ∩ ⟨y⟩ = 1.

If xy = yx, then (xy)^{n} = x^{n}y^{n} can equal 1 only if x^{n} = y^{−n} ∈ ⟨x⟩ ∩ ⟨y⟩ = 1, which occurs only if n is divisible both by 3 and by 2, i.e., xy has order 6. In this case G = ⟨xy⟩ ≅ Z_{6}.

Suppose then that xy ≠ yx. Then yxy^{−1} ∈ ⟨x⟩ but yxy^{−1} ≠ x (and of course yxy^{−1} ≠ 1 as x ≠ 1). Therefore yxy^{−1} = x^{−1}. We therefore know that

x^{3} = 1, y^{2} = 1 and yxy^{−1} = x^{2} = x^{−1}.

But we showed above that the symmetry group D_{6} of an equilateral triangle a) has elements σ and τ satisfying the same relations and b) as a result of these relations and nothing else, can be shown to consist of the elements τ^{i}σ^{j}, 0 ≤ i ≤ 1, 0 ≤ j ≤ 2, and have a uniquely determined multiplication table. Therefore G ≅ D_{6}. In particular taking G = Σ_{3}, a noncyclic group of order 6, we have Σ_{3} ≅ D_{6}. QED

Corollary. Let G be a group of order pq, where p > q are primes. If p ≢ 1 mod q, then G ≅ Z_{pq}.

Proof. By Sylow’s Theorem the number of Sylow p-subgroups divides q and is congruent to 1 mod p, so is 1 as p > q. Likewise using the hypothesis that p ≢ 1 mod q we find that G has a unique Sylow q-subgroup. Let P and Q be these Sylow subgroups. Then ^{g}P = P for every g ∈ G and similarly for Q. In particular, for any x ∈ P and y ∈ Q we have

xyx^{−1}y^{−1} = ^{x}yy^{−1} ∈ Q and xyx^{−1}y^{−1} = x^{y}x^{−1} ∈ P.

But P ∩ Q = 1 by Lagrange’s Theorem (its order divides both p and q). Therefore xyx^{−1}y^{−1} = 1. This implies that xy = yx. Consequently, as in the previous corollary we find that xy has order pq, so G ≅ Z_{pq}. QED

2d. Finite Symmetric Groups

Examples illustrating the previous results can be found in the symmetric groups. We introduce some standard notation for them, beginning with the “product of cycles” notation for permutations. The notation

(1 2 3 5 7)(4 6)

for example refers to the permutation in Σ_{7} taking 1 to 2, 2 to 3, 3 to 5, 5 to 7, and 7 to 1, and interchanging 4 and 6. Such notation is possible for any permutation in any symmetric group. We shall prove this intuitively obvious fact since in doing so we pass by some other useful concepts.

Let g ∈ Σ_{Ω}. Let Ω_{1} be an orbit of ⟨g⟩ on Ω, and suppose that |Ω_{1}| = n. Then for any ω ∈ Ω_{1}, we have

Ω_{1} = {ω, gω, g^{2}ω, …, g^{n−1}ω}.

Proof. For any α ∈ Ω, α = g^{i}ω for some i, by transitivity. Moreover α = g^{j}ω if and only if g^{i−j} ∈ ⟨g⟩_{ω}. Now G_{ω} = ⟨g^{n}⟩ for some n, and we may assume that n is the least positive integer with this property. Then we may write α = g^{i}ω with 0 ≤ i < n, and different such i give different g’s.

551, Fall '00             A2d.    Finite Symmetric Groups             p. 11

Alternatively we may quote the classification of transitive actions, which says that there is a bijection Ω_{1} → ⟨g⟩/⟨g⟩_{ω} preserving the action of ⟨g⟩ and mapping ω to the trivial coset ⟨g⟩_{ω}. Writing G_{ω} = ⟨g^{n}⟩ with n again the least such positive integer, we see that 1, g, g^{2}, …, g^{n−1} represent the left cosets of ⟨g⟩. This implies the result. QED

We write g|Ω_{1} as the “n-cycle”

g|Ω_{1} = (ω gω, g^{2}ω, …, g^{n−1}ω).  2A

Definition. A permutation g ∈ Σ_{Ω} is a cycle if and only if ⟨g⟩ has one orbit Ω_{1} on which it acts by (2A), with n > 1, and g fixes every point of Ω − Ω_{1}.

Thus we do not consider the identity permutation to be a cycle.

We may use the same notation for the cycle g, with the convention that points of Ω omitted in this symbolism are fixed by g.

Definition. Two permutations g, g′ ∈ Σ_{Ω} are disjoint if and only if each point of Ω is fixed by at least one of them.

Lemma. If g and g′ are disjoint permutations then gg′ = g′g, and points in the support of g are moved by gg′ just as they are moved by g.

Proof. Left to reader. QED

Now we can prove

Theorem. Let g ∈ Σ_{Ω}, with Ω finite. Then there exist uniquely determined disjoint cycles g_{1}, …, g_{r} (except for their order) such that g = g_{1} … g_{r}.

Proof. Let Ω_{1}, …, Ω_{r} be the nontrivial orbits of ⟨g⟩ on Ω, and let g_{i} be the permutation which agrees with g on Ω_{i} and acts trivially on all other Ω_{j}. Then g_{i} is a cycle by the first lemma, the g_{i} are obviously disjoint and g = g_{1} … g_{r}. Conversely if g = h_{1} … h_{s}, disjoint cycles, and we let Ω′_{i} be the nontrivial orbit of h_{i} on Ω, then it is clear that the Ω′_{i} are the nontrivial orbits of g on Ω, so that by reordering we have r = s and Ω_{i} = Ω′_{i}. Then h_{i} = g|Ω_{i} = g_{i}. QED

Lemma. The order of an n-cycle is n. If g = g_{1} ⋯ g_{r} as in the previous theorem, with g_{i} being an n_{i}-cycle, then the order of g is the l.c.m. of n_{1}, …, n_{r}. QED

Theorem. Two elements of Σ_{Ω}, Ω finite, are conjugate in Σ_{Ω} if and only if they have the same cycle shape.

Proof. If hα = β, then ghg^{−1}(gα) = gβ. Hence if h = (α β ⋯)(γ δ ⋯) ⋯, then ghg^{−1} = (gα gβ ⋯ (gγ gδ ⋯) · · ·. So conjugate elements have the same cycle shape; conversely if two elements have the same cycle shape a permutation g exists carrying the points in one cycle shape to corresponding points in the other. QED Now of the 3! elements of Σ_{3}, there are 2 3-cycles, 3 2-cycles and 1 identity element.

Of the 4! = 24 elements of Σ_{4}, there are 6 4-cycles, 8 3-cycles, 6 2-cycles, 3 elements of the form (ab)(cd), and one identity element. The last four elements consitute the “Klein four-subgroup V = {1, (12)(34), (13)(24), (14)(23)}.

Of the 5! = 120 elements of Σ_{5}, there are 24 5-cycles, 30 4-cycles, 20 3-cycles, 10 2-cycles, 15 “Klein elements” (a b)(c d), and 20 elements (a b c)(d e) of order 6.

It is not possible systematically to enumerate the subgroups of Σ_{n}; if this were possible we would know all finite groups, by Cayley’s Theorem. However, there are very few subgroups of very small index. Taking Ω = {1, …, n}, we of course have the point-stabilizers (Σ_{Ω})_{ω}, ω ∈ Ω; clearly this is isomorphic to Σ_{Ω−{ω}} and its index is |Ω| = n. The only other subgroup of index ≤ n is the alternating group A_{Ω}.

2-cycles are also called “transpositions”.

Theorem. Let Ω be a finite set. Then every element g ∈ Σ_{Ω} is the product g = t_{1} ⋯ t_{r} of (not necessarily disjoint) transpositions. This decomposition is not unique, nor is r. However, the parity of r is uniquely determined by g, and accordingly g is called even or odd, and the sign ϵ_{g} of g is defined as −1 or 1.

Proof. (α_{1} α_{2} ⋯ α_{r})(α_{r} α_{r+1}) = (α_{1} α_{2} ⋯ α_{r} α_{r+1}). Hence an inductive argument shows that every cycle is the product of transpositions. But every element of Σ_{Ω} is the product of cycles, proving the first statement.

For the uniqueness, a representation of G = Σ_{Ω} is the most useful way to proceed. Say Ω = {1, …, n}. Let R = Z[x_{1}, …, x_{n}] be the polynomial ring in n (commuting) indeterminates x_{1}, …, x_{n}. The action of G on Ω yields an action of G on R:

For g ∈ G and p ∈ R, define (g · p)(x_{1}, …, x_{n}) = p(x_{g^{−1}1}, …, x_{g^{−1}n}).  2B

If we put q = g · p, notice that h · (g · p)(x_{1}, …) = (h · q)(x_{1}, …, x_{n}) = q(x_{h^{−1}1}, …) = p(x_{g^{−1}h^{−1}1}, …) = (hg) · p(x_{1}, …, x_{n}). (For i = h^{−1}1 gets replaced by g^{−1}i = g^{−1}h^{−1}1, etc.) Thus

h · (g · p) = (hg) · p,  2C

whence we really have an action. Moreover, the multiplication in R is respected by this action:

g · (pq) = (g · p)(g · q),  2D

where the products are in the ring R, i.e., ordinary multiplication of polynomials. This is clear from the definition of the action.

What has this to do with even and odd permutations? The polynomial ring R contains an element δ which “detects” evenness and oddness, namely

δ(x_{1}, …, x_{n}) = ∏_{i<j}(x_{i} − x_{j}).

The key point is that if t is a transposition, then

t · δ = −δ.  2E

Indeed t permutes and changes the signs of the factors of δ, and so t · δ = ±δ, where the sign is determined by whether the phenomenon i < j but ti > tj occurs an even or odd number of times. But if t interchanges k and l with k < l, then this phenomenon occurs only if i = k and j = l, or i = k and k < j < l, or j = l and k < i < l. This is an odd number of times, proving (2E).

Now (2C, D, E) imply that if g is the product of r transpositions, then

gδ = (−1)^{r}δ.

Thus we may define ϵ_{g} by gδ = ϵ_{g}δ, and the proof is complete. QED

Definition. A_{Ω} is the subgroup of Σ_{Ω} consisting of all even permutations.

Thus Σ_{Ω} = A_{Ω} ∪ A_{Ω}t for any transposition t, so

|Σ_{Ω} : A_{Ω}| = 2.

In particular A_{3} = ⟨(123)⟩ ≅ Z_{3}. Also A_{4} has order 12, and has four Sylow 3-subgroups (exhausting the set of 8 elements of order 3).

The alternating and symmetric groups are highly non-abelian. For instance, A_{4} has no subgroup of order 6. One way to see this is to use Sylow’s Theorem, and show that no elements of order 2 and 3 in A_{4} can generate a subgroup of order 6. Another is to assume that such a subgroup H exists, let P be a Sylow 3-subgroup of H. Then P is a Sylow 3-subgroup of A_{4}, and there are four of them, so |A_{4} : N_{A_{4}}(P)| = 4 = |A_{4} : P |, whence N_{G}(P) = P. On the other hand, |H : P | = 2 so by Sylow’s Theorem |H : N_{H}(P)| can only be 1, as it is 1 mod 3. Therefore H = N_{H}(P) ≤ N_{G}(P) = P, a contradiction.

A fundamental fact about the alternating groups A_{n} is that they are simple for n ≥ 5, and that the only nontrivial normal subgroup of Σ_{n} for n ≥ 5 is A_{n}. This will have to wait for the next section.