# Jordan-Holder Decomposition

A group which has no proper normal subgroups is called a
*simple* group.

**Example:** Cyclic groups of prime order are simple. Simple groups
of composite order are "rare" according to the book.

A proper normal subgroup \(A\) is called a
*maximum normal subgroup*
of \(G\) if \(A \triangleleft H \triangleleft G\) implies \(H = G\) or \(H = A\).
Note \(A\) is a maximum invariant normal subgroup if and only if \(G/A\) is
a simple group, because \(H/A\) is a normal subgroup of \(G/A\).

If \(G\) is not simple, let \(A\) a maximum normal subgroup in \(G\). Now
if \(A\) is not simple, let \(A_1\) be a maximum normal subgroup. Continuing
in this fashion we can construct a sequence, called a *composition
series* as follows.

where \(G/A, A/A_1, A_1/A_2,...,A_r\) are all simple nontrivial groups, which
are called the *composition quotient groups*. The orders
of the composition quotient groups are called the *composition
indices*.

**Jordan-Holder Theorem:** In any two composition series for a group \(G\),
the composition quotient groups are isomorphic in pairs, though may occur
in different orders in the sequences.

**Proof:**
Trivially the theorem is true if \(|G| =2\).
Next assume the theorem has been proved
for groups of order less than \(|G|\).
If \(G\) is simple then the theorem is again trivially true, otherwise
let two composition series be

and

Then if \(A = B\), by inductive assumption the composition quotient groups \(A/A_1, A_1/A_2 ,...,A_r\) and \(G/B, B/B_1, B_1 / B_2 ,..., B_s\) are isomorphic in pairs, and we have \(G/A = G/B\) hence the theorem is true in this case.

Otherwise \(A \ne B\). Consider the group \(A B\). This contains \(A\) and \(B\) which are distinct and maximal in \(G\), thus we must have \(A B = G\). Let \(D = A \cap B\). By the first isomorphism theorem we have \(G/A \cong B/D\) and \(G/B \cong A / D\). Note \(G/A, G/B\) are simple, hence \(B/D\), \(A/D\) are also simple which implies \(D\) is in fact a maximum normal subgroup in \(A\) and \(B\).

Now let \(D\triangleright D_1 \triangleright ... \triangleright D_t \triangleright \{1\}\) be a composition series for \(D\).

Consider the quotient groups

and

By inductive assumption, the theorem is true for the group \(A\) and hence the above sequences are isomorphic in pairs, and in fact \(t = r\).

Similarly

is isomorphic in pairs to the sequence

(and \(s = r\)).

But since the sequences

and

are clearly isomorphic in pairs, we have proved the theorem.

**Example:** The alternating group \(A_n\) is a maximum normal subgroup
of \(S_n\). We have already seen \(A_n\) is normal in \(S_n\)
since it is of index 2. But the fact that it is of index 2 implies
\(S_n / A_n\) is simple and hence \(A_n\) is maximal.

For \(n=3\), we have the composition series

since the composition indices are the primes \(2,3\).

For \(n=4\), recall that the group \(V=\{1,(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)\}\) is normal in \(A_4\), and note every element in \(V\) besides the identity generates a group of order \(2\) of index \(2\) (implying it is normal in \(V\)) thus we have the the composition series

with composition indices \(2,3,2,2\).

**Example:** Consider the cyclic group of order 6, and let \(a\) be a
generator. Then we have the composition series

with composition indices \(2, 3\). Note the composition quotient groups are isomorphic to those of \(S_3\), hence knowing the composition quotient groups is not enough to reconstruct the original group.

A group \(G\) is said to be *soluble* if all the composition
indices of \(G\) are prime.
For instance, all the groups in the above examples are soluble.
Note a group \(G\) is soluble if it contains a normal subgroup \(H\) with
both \(G/H, H\) soluble. This is because given the series

and

with prime composition indices, we have \(\frac{G_{i-1} /H}{G_i / H} \cong G_{i-1} / G_i\) (where we set \(G_0 = G\) by applying the third isomorphism theorem. Hence we can construct the series with prime composition indices

**Lemma:** If a normal subgroup \(H\) of \(A_n\) for \(n \ge 3\)
contains a cycle of degree \(3\) then \(H = A_n\).

**Proof:** Without loss of generality let \((1 2 3) \in H\).
For \(n = 3\), \((1 2 3)\) generates \(A_3\) and there is nothing to prove.
For \(n \gt 3\), since \(H\) is normal, it must also
contain \(s^{-1} (1 2 3) s\) for any even permutation \(s\). Set
\(s = (3 2 k)\) for \(k \gt 3\).
Then we have that \(H\) contains \((1 k 2)\), and hence also
its square which is \((1 2 k)\).
Recall these cycles generate \(A_n\).

**Theorem:** \(A_n\) is simple for \(n \gt 4\).

**Proof:** Suppose \(H\) is a normal subgroup of \(A_n\).
Suppose \(h\in H\) is a permutation of the form
\((a_1 a_2 ... a_m) h'\)
where \(m \gt 3\) and \(h'\) does not act on \(a_1,...,a_m\).
Then the permutation \(s = (a_1 a_2 a_3)\) commutes
with all the cycles of \(h\) except the first, Now \(s\) is even hence
\(h_1 = s^{-1}h s = (s^{-1} (a_1 ... a_m) s h') \in H\), thus

is contained in \(H\). Since this is a cycle of degree 3, by the above lemma we have \(H=A_n\). So if \(H\) is to be a proper subgroup, its elements cannot contain cycles longer than 3.

Now suppose \(H\) contains an element containing two 3-cycles. Without loss of generality, suppose \((1 2 3)(4 5 6)h' \in H\) where \(h'\) does not act on \(1,2,3,4,5,6\). Set \(s = (2 3 4)\), so that it is an even permutation commuting with \(h'\). Then set \(h_1 = s^{-1} h s = (1 3 4)(2 5 6)h' \in H\), which gives

which is a cycle of length greater than 3.

Now suppose \(H\) contains an element containing exactly one 3-cycle, say \(h = (1 2 3) h'\), and \(h'\) consists of 2-cycles implying \(h'^2 = 1\). Then \(h^2 = (1 3 2)\), so by the above lemma \(H = A_n\).

Lastly suppose \(H\) consists only of permutations that are products of disjoint transpositions. For \(n=4\) this leads to the four-group \(V\) in the above example. For \(n\gt 4\), suppose \(h = (1 2)(3 4)h' \in H\). Then set \(s = (2 3 4)\), and we have

thus

Now take \(t = (1 4 5)\), and we have

We conclude that \(h_3 h_2^{-1} = (4 5)(2 3)(1 4)( 2 3) = (4 5)(1 4) = (1 4 5) \in H\), hence \(H = A_n\) by the lemma.

**Corollary:** \(A_n\) is the only subgroup of order \(\frac{1}{2}n!\)
in \(S_n\) when \(n \gt 4\).

**Proof:**
Any subgroup \(H\) of index 2 is necessarily normal
in \(S_n\), thus \(D = A_n \cap H\) is normal in \(A_n\). By the Theorem
we have \(D = \{1\}\) or \(D = \{A_n\}\). Since \(H\) contains more than one
even permutation (because
either half or all of a group of permutations
are even) we must have \(D = A_n\), implying \(H = A_n\).

It can be easily verified that the statement of the corollary is also true for \(n \le 4\)

**Corollary:** \(S_n\) is not soluble for \(n \gt 4\).

**Proof:** By the theorem, the composition series for \(S_n\) is
\(S_n \triangleright A_n \triangleright \{1\}\) and its composition
indices are \(2, \frac{1}{2}n!\), the latter of which is not prime.

*blynn@cs.stanford.edu*💡