Notes on the symmetric group

1 Computations in the symmetric group

Recall that, given a set X, the set SX of all bijections from X to itself (or,
more briefly, permutations of X) is group under function composition. In
particular, for each n ∈ N, the symmetric group Sn is the group of per-
mutations of the set {1, . . . , n}, with the group operation equal to function
composition. Thus Sn is a group with n! elements, and it is not abelian if
n ≥ 3. If X is a finite set with #(X) = n, then any labeling of the elements
of X as x1 , . . . , xn defines an isomorphism from SX to Sn (see the homework
for a more precise statement). We will write elements of Sn using Greek let-
ters σ, τ, ρ, . . . , we denote the identity function by 1, and we just use the
multiplication symbol · or juxtaposition to denote composition (instead of
the symbol ◦). Recall however that functions work from right to left: thus
στ (i) = σ(τ (i)), in other words evaluate first τ at i, and then evaluate σ on
this. We say that σ moves i if σ(i) 6= i, and that σ fixes i if σ(i) = i.
There are many interesting subgroups of Sn . For example, the subset
Hn defined by
Hn = {σ ∈ Sn : σ(n) = n}
is easily checked to be a subgroup of Sn isomorphic to Sn−1 (see the home-
work for a generalization of this). If n = n1 + n2 for two positive integers
n1 , n2 then the subset

H = {σ ∈ Sn : σ({1, . . . , n1 }) = {1, . . . , n1 }}

is also a subgroup of Sn . Note that, if σ ∈ H, then automatically

σ({n1 + 1, . . . , n2 }) = {n1 + 1, . . . , n2 },

and in fact it is easy to check that H is isomorphic to Sn1 × Sn2 . There

are many other subgroups of Sn . For example, the dihedral group Dn , the
group of symmetries of a regular n-gon in the plane, is (isomorphic to) a
subgroup of Sn by looking at the permutation of the vertices of the n-gon.

1
Note that #(Dn ) = 2n, and hence that Dn is a proper subgroup of Sn if
n ≥ 4. We shall see (Cayley’s theorem) that, if G is a finite group, then
there exists an n such that G is isomorphic to a subgroup of Sn (and in
fact one can take n = #(G)). Thus the groups Sn are as complicated as all
possible finite groups.
To describe a function σ : {1, . . . , n} → {1, . . . , n}, not necessarily a per-
mutation, we can give a table of its values, recording i and then σ(i), as
follows:
i 1 2 ... n
σ(i) σ(1) σ(2) . . . σ(n)
Of course, we could describe the same information by a 2 × n matrix:
 
1 2 ... n
.
σ(1) σ(2) . . . σ(n)
The condition that σ is a permutation is then the statement that the integers
1, . . . , n each occur exactly once in the second row of the matrix. For
example, if σ is given by the matrix
 
1 2 3 4 5 6 7 8
,
2 4 8 1 5 7 3 6
then σ(1) = 2 and σ(5) = 5.
This notation is however cumbersome and not well suited to calculation.
We describe a much more efficient way to write down elements of Sn by
first writing down some special ones, called cycles, and then showing that
very element of Sn can be factored into a product of cycles, in an essentially
unique way if we are careful.
Definition 1.1. Let {a1 , . . . , ak } be a subset of {1, . . . , n} with exactly k
elements; equivalently, a1 , . . . , ak are distinct. We denote by (a1 , . . . , ak ) the
following element of Sn :
(a1 , . . . , ak )(ai ) = ai+1 , if i < k;
(a1 , . . . , ak )(ak ) = a1 ;
(a1 , . . . , ak )(j) = j, if j 6= ai for any i.
We call (a1 , . . . , ak ) a k-cycle or cycle of length k. For k > 1, we define
the support Supp(a1 , . . . , ak ) to be the set {a1 , . . . , ak }. Note that, again
for k > 1, the k-cycle (a1 , . . . , ak ) moves i ⇐⇒ i ∈ Supp(a1 , . . . , ak ). Two
cycles (a1 , . . . , ak ) and (b1 , . . . , b` ) are disjoint if
Supp(a1 , . . . , ak ) ∩ Supp(b1 , . . . , b` ) = ∅,
i.e. the sets {a1 , . . . , ak } and {b1 , . . . , b` } are disjoint.

2
Remark 1.2. 1) A 1-cycle (a1 ) is the identity function 1, no matter what
a1 is. For this reason, we will generally only consider cycles of length at
least 2. If σ = (a1 , . . . , ak ) with k ≥ 2, then σ is never the identity, since
σ(a1 ) = a2 6= a1 .
2) A 2-cycle (a1 , a2 ) is also called a transposition. It is the unique permu-
tation of {1, . . . , n} which switches a1 and a2 and leaves all other elements
alone.
3) From the description in 2), it is clear that (a1 , a2 ) = (a2 , a1 ). But for
k ≥ 3, the order of the elements a1 , . . . , ak is important: for example σ1 =
(1, 3, 2) 6= σ2 = (1, 2, 3), because σ1 (1) = 3 but σ2 (1) = 2.
4) However, there are a few ways to change the order without changing the
element of Sn : clearly

(a1 , a2 , . . . , ak ) = (a2 , a3 , . . . , ak , a1 ) = (a3 , a4 , . . . , ak , a1 , a2 ) = · · ·

= (ak , a1 , . . . , ak−2 , ak−1 ).

In other words, you can start the cycle anywhere, at ai , say, but then you
have to list the elements in order: the next one must be ai+1 , and so on, with
the understanding that once you reach ak , the next one has to be a1 , then
a2 , and then so on up to ai−1 . Clearly, this the only way you can change
the order. By convention, we often start with the smallest ai . Of course,
after that, there is no constraint on the sizes of the consecutive members of
the cycle.
5) It is easy to see that the inverse (a1 , a2 , . . . , ak )−1 = (ak , ak−1 , . . . , a1 ). In
other words, the inverse of the k-cycle (a1 , a2 , . . . , ak ) is the k-cycle where the
elements are written in the opposite order. In particular, for a transposition
(a1 , a2 ), (a1 , a2 )−1 = (a2 , a1 ) = (a1 , a2 ), i.e. a transposition has order 2.
6) Generalizing the last line of 5), it is easy to see that the order of a
k-cycle σ = (a1 , a2 , . . . , ak ) is exactly k. In fact, σ(ai ) = ai+1 , so that
σ r (ai ) = ai+r , with the understanding that the addition i + r is to be taken
mod k, but using the representatives 1, . . . , k for addition mod k instead of
the more usual ones (in this course) of 0, . . . , k − 1. In particular, we see
that σ r (ai ) = ai for all i ⇐⇒ r is a multiple of k, and since σ r (j) = j for
j 6= ai , we see that k is the smallest positive integer r such that σ r = 1.
Note however that, if σ is a k-cycle, its powers σ r need not be k-cycles.
For example,
(1, 2, 3, 4)2 = (1, 3)(2, 4),
and (1, 3)(2, 4) is not a k-cycle for any k.

3
7) Suppose that σ1 = (a1 , . . . , ak ) and σ2 = (b1 , . . . , b` ) are two disjoint cy-
cles. Then it is easy to see that σ1 σ2 = σ2 σ1 , i.e. “disjoint cycles commute.”
To check this we have to check that, for all j ∈ {1, . . . , n}, σ1 σ2 (j) = σ2 σ1 (j).
First, if j = ai for some i, then σ1 (ai ) = ai+1 (with our usual conventions
on adding mod k) but σ2 (ai ) = ai since ai 6= br for any r. For the same
reason, σ2 (ai+1 ) = ai+1 . Thus, for all i with 1 ≤ i ≤ k,

σ1 σ2 (ai ) = σ1 (σ2 (ai )) = σ1 (ai ) = ai+1 ,

whereas

σ2 σ1 (ai ) = σ2 (σ1 (ai )) = σ2 (ai+1 ) = ai+1 = σ1 σ2 (ai ).

Similarly, σ1 σ2 (br ) = br+1 = σ2 σ1 (br ) for all r, 1 ≤ r ≤ `. Finally, if j is not

an ai or a br for any i, r, then

σ1 σ2 (j) = σ1 (σ2 (j)) = σ1 (j) = j,

and similarly σ2 σ1 (j) = j. Thus, for all possible j ∈ {1, . . . , n}, σ1 σ2 (j) =
σ2 σ1 (j), hence σ1 σ2 = σ2 σ1 .
Note that non-disjoint cycles might or might not commute. For example,

(1, 2)(1, 3) = (1, 3, 2) 6= (1, 2, 3) = (1, 3)(1, 2),

whereas

(1, 2, 3, 4, 5)(1, 3, 5, 2, 4) = (1, 4, 2, 5, 3) = (1, 3, 5, 2, 4)(1, 2, 3, 4, 5).

8) Finally, we have the beautiful formula: if σ ∈ Sn is an arbitrary element

(not necessarily a k-cycle), and (a1 , . . . , ak ) is a k-cycle, then

σ · (a1 , . . . , ak ) · σ −1 = (σ(a1 ), . . . , σ(ak )).

In other words, σ · (a1 , . . . , ak ) · σ −1 is again a k-cycle, but it is the k-cycle

where the elements a1 , . . . , ak have been “renamed” by σ.
To prove this formula, it suffices to check that

σ · (a1 , . . . , ak ) · σ −1 (j) = (σ(a1 ), . . . , σ(ak ))(j)

for every j ∈ {1, . . . , n}. First, if j is of the form σ(ai ) for some i, then by
definition (σ(a1 ), . . . , σ(ak ))(σ(ai )) = σ(ai+1 ), with the usual remark that if
i = k then we interpret k + 1 as 1. On the other hand,

σ · (a1 , . . . , ak ) · σ −1 (σ(ai )) = σ · (a1 , . . . , ak )(σ −1 (σ(ai ))

= σ · (a1 , . . . , ak )(ai ) = σ((a1 , . . . , ak )(ai )) = σ(ai+1 ).

4
Thus both sides agree if j = σ(ai ) for some i. On the other hand, if j 6= σ(ai )
for any i, then (σ(a1 ), . . . , σ(ak ))(j) = j. But j 6= σ(ai ) ⇐⇒ σ −1 (j) 6= ai ,
so

σ · (a1 , . . . , ak ) · σ −1 (j) = σ · (a1 , . . . , ak )(σ −1 (j))

= σ((a1 , . . . , ak )(σ −1 (j))) = σ(σ −1 (j)) = j.

Hence σ·(a1 , . . . , ak )·σ −1 (j) = (σ(a1 ), . . . , σ(ak ))(j) for every j ∈ {1, . . . , n},
proving the formula.

In the discussion above, we have seen numerous computations with cy-

cles, and in particular examples where the product of two cycles either is
or is not again a cycle. More generally, we have the following factorization
result for elements of Sn :

Theorem 1.3. Let σ ∈ Sn , σ 6= 1. Then σ is a product of disjoint cycles

of lengths at least 2. Moreover, the terms in the product are unique up to
order.

Remark 1.4. 1) Just as with factoring natural numbers into primes, a

single cycle is a “product” of cycles (it is a product of one cycle).
2) We could also allow 1 in this framework, with the convention that 1 is
the empty product, i.e. the “product” of no cycles.
3) Since disjoint cycles commute, we can always change the order in a prod-
uct of disjoint cycles and the answer will be the same. However, the theorem
says that is the only ambiguity possible.

Example 1.5. For the group S4 , the only possibilities for products of dis-
joint cycles are: 1) the identity 1; 2) a transposition, i.e. a 2-cycle; 3) a
3-cycle; 4) a 4-cycle; 5) a product of two disjoint 2-cycles.  There is just
4
one identity 1. The number of transpositions is = 6. For a 3-cycle
2
(a1 , a2 , a3 ), there are 4 choice for a1 , then 3 choices for a2 , then 2 choices for
a3 , giving a total of 4 · 3 · 2 = 24 choices for the ordered triple (a1 , a2 , a3 ).
However, as an element of S4 , (a1 , a2 , a3 ) = (a2 , a3 , a1 ) = (a3 , a1 , a2 ), so the
total number of different elements of S4 which are 3-cycles is 24/3 = 8. Like-
wise, the total number of 4-cycles, viewed as elements of S4 , is 4·3·2·1/4 = 6.
Finally, to count the number of products (a, b)(c, d) of two disjoint 2-cycles,
note that, as above, there are 6 choices for (a, b). The choice of (a, b) then
determines c and d since {c, d} = {1, 2, 3, 4} − {a, b}. But since (a, b)(c, d) =
(c, d)(a, b), we should divide the total number by 2, to get 6/2 = 3 elements

5
of S4 which can be written as a product of two disjoint 2-cycles. As a check,
adding up the various possibilities gives 1 + 6 + 8 + 6 + 3 = 24, as expected.
In this notation, D4 is the subgroup of S4 given by
D4 = {1, (1, 2, 3, 4), (1, 3)(2, 4), (1, 4, 3, 2), (2, 4), (1, 3), (1, 2)(3, 4), (1, 4)(2, 3)}.
The proof of the theorem gives a procedure which is far easier to under-
stand and implement in practice than it is to explain in the abstract. For
example, suppose we are given a concrete permutation corresponding to a
2 × n matrix, for example
 
1 2 3 4 5 6 7 8 9
σ= ,
3 6 5 7 1 4 9 8 2
here is how to write σ as a product of disjoint cycles of lengths at least 2:
beginning with 1, we see that σ(1) = 3, σ(3) = 5, σ(5) = 1, so we have
returned to where we started. Write down the cycle (1, 3, 5). Searching for
elements not in the support of (1, 3, 5), we see that the first such is 2. Then
σ(2) = 6, σ(6) = 4, σ(4) = 7, σ(7) = 9, σ(9) = 2 so that we are again where
we started. Write down the cycle (2, 6, 4, 7, 9). Search again for elements
not in the support of (1, 3, 5) or (2, 6, 4, 7, 9). The only remaining element
is 8, and σ(8) = 8. As we omit 1-cycles, we are left with the factorization
σ = (1, 3, 5)(2, 6, 4, 7, 9) = (2, 6, 4, 7, 9)(1, 3, 5).
To describe this procedure in general, we introduce a new idea.
Definition 1.6. Let σ ∈ Sn . We define a relation ∼σ on {1, . . . , n} as
follows: for i, j ∈ {1, . . . , n}, i ∼σ j if there exists an r ∈ Z such that
σ r (i) = j. The orbit of i under σ is the set
Oσ (i) = {σ r (i) : r ∈ Z}.
Before giving examples, we note the following:
Proposition 1.7. The relation ∼σ is an equivalence relation and the equiv-
alence class [i] of i for ∼σ is the orbit Oσ (i).
Proof. Clearly i = σ 0 (i), so that i ∼σ i. Hence ∼σ is reflexive. If i ∼σ j, then
by definition there exists an r ∈ Z such that σ r (i) = j. Thus i = σ −r (j),
so that j ∼σ i and ∼σ is symmetric. To see that it is transitive, suppose
that i ∼σ j and j ∼σ k. Thus there exist r, s ∈ Z such that σ r (i) = j and
σ s (j) = k. Then σ r+s (i) = σ s (σ r (i)) = σ s (j) = k. Thus i ∼σ k and so ∼σ
is transitive, hence an equivalence relation. By definition, the equivalence
class [i] is Oσ (i).

6
 By general facts about equivalence relations, the orbits Oσ (i) partition
{1, . . . , n} into disjoint subsets, in the sense that every integer j ∈ {1, . . . , n}
is in exactly one orbit Oσ (i). Note that Oσ (i) = {i} ⇐⇒ σ fixes i. For
example, the identity permutation has the n orbits {1}, {2}, . . . , {n}. A k-
cycle (a1 , . . . , ak ) with k ≥ 2 has one orbit {a1 , . . . , ak } with k elements, and
the remaining orbits are one element orbits {i} for the i ∈ {1, . . . , n} such
that i 6= ar for any r. There are then n − k one element orbits and one orbit
with k elements, for a total of n − k + 1 orbits. For another example, given
the σ ∈ S9 described above, σ = (1, 3, 5)(2, 6, 4, 7, 9), the orbits of σ are
{1, 3, 5}, {2, 4, 6, 7, 9}, and {8}. More generally, if σ is a product of disjoint
cycles ρ1 · · · ρ` of lengths at least 2, then the orbits Oσ (i) are the supports of
the cycles ρi in addition to one element orbits for each i ∈ {1, . . . , n} which
is not in the support of any ρi .
Note that, while σ determines the orbits, the orbits do not completely
determine σ. For example, σ 0 = (1, 5, 3)(2, 9, 7, 6, 4) has the same set of
orbits as σ. On the other hand, the orbits do determine the “shape” of σ, in
other words they tell us in this case that σ is a product of a disjoint 3-cycle
and a 5-cycle, and they tell us that the support of the 3-cycle is {1, 3, 5} and
the support of the 5-cycle is {2, 4, 6, 7, 9}.
Let us make two remarks about the equivalence relation ∼σ above. First,
since Sn is finite, every element σ has finite order, say σ d = 1 with d > 0.
Then σ d−1 = σ −1 , so we can write every negative power of σ as a positive
power as well. Thus
Oσ (i) = {σ r (i) : r ∈ N}.
Second, given i ∈ {1, . . . , n}, the orbit of i is the set {i, σ(i), σ 2 (i), . . . } by
the above discussion. Inductively, set a1 = i and define ak+1 = σ(ak ), so that
ak = σ k−1 (i). Thus the orbit Oσ (i) is just {a1 , a2 , . . . }, with σ(ak ) = ak+1 .
Note that the set {a1 , a2 , . . . } is finite, so there have to exist r, s ≥ 1 with
r 6= s and ar = as . Let k ∈ N be the smallest integer ≥ 1 such that ak+1 = a`
for some ` with 1 ≤ ` ≤ k, i.e. ak+1 is the first term in the sequence which
is equal to a previous term. Equivalently, k is the largest positive integer
such that a1 , . . . , ak are all distinct. We claim that ak+1 = a1 = i, in other
words that the sequence starts to repeat only when we come back to the
starting point a1 = i. For suppose that ak+1 = a` with 1 ≤ ` ≤ k. Then
σ k (i) = σ `−1 (i), so that σ k−`+1 (i) = i. Hence ak−`+2 = a1 , in other words
there is a repetition at stage k − ` + 2. Since k + 1 was the smallest positive
integer greater than 1 for which some repetition occurs, k − ` + 2 ≥ k + 1, so
that ` ≤ 1. But also ` ≥ 1, so that ` = 1 and ak+1 = a1 , as claimed. Once
we have ak+1 = a1 , i.e. σ k (i) = i, then ak+2 = σ(i) = a2 , ak+3 = a3 , . . . . In

7
general, given r ∈ Z, writing r = kq + ` with 0 ≤ ` ≤ k − 1, it follows that
σ r (i) = σ ` (σ kq (i)) = σ ` ((σ k )q (i)) = σ ` (i) = a`+1 ,
where 1 ≤ ` + 1 ≤ k, and hence that
Oσ (i) = {i, σ(i), σ 2 (i), . . . , σ k−1 (i)} = {a1 , . . . , ak }.
Using the above, let us show that an arbitrary σ ∈ Sn can be factored
into a product of disjoint cycles as in the statement of Theorem 1.3. First,
given i ∈ {1, . . . , n}, either σ(i) = i, which happens ⇐⇒ Oσ (i) = {i}, or
Oσ (i) has at least 2 elements. In this second case, write Oσ (i) = {a1 , . . . , ak }
as above, where k = #(Oσ (i)) and σ(aj ) = aj+1 for 1 ≤ j ≤ k − 1 and
σ(ak ) = a1 . Thus, if ρ is the k-cycle (a1 , . . . , ak ), then ρ(aj ) = aj+1 = σ(aj )
for all aj , and ρ(r) = r if r ∈ / {a1 , . . . , ak } = Oσ (i) = Supp ρ.
Now list the orbits of σ as O1 , . . . , ON , say, where O1 , . . . , OM are the
orbits with at least two elements and OM +1 , . . . , ON are the one-element
orbits. For each orbit Or with r ≤ M , we have found a cycle ρr of length at
least 2, with Supp ρr = Or , ρr (i) = σ(i) if i ∈ Or , and ρr (i) = i if i ∈ / Or .
Then the cycles ρ1 , . . . , ρM are disjoint, and by inspection σ = ρ1 · · · ρM .
This proves that σ is a product of disjoint cycles, and the uniqueness up to
order is easy to check from the construction. 
The proof shows the following:
Corollary 1.8. Let σ ∈ Sn , and suppose that the orbits of σ are O1 , . . . , ON ,
where #(Oi ) = ki ≥ 2 if i ≤ M and #(Oi ) = 1 if i > M . Then
σ = ρ1 · · · ρM ,
where each ρi is a ki -cycle, Supp ρi = Oi , and hence, if i 6= j, ρi and ρj are
disjoint.

2 The sign of a permutation

We now look for further ways to factor elements of Sn , not in general
uniquely. First, we note that the k-cycle (1, . . . , k) is a product of transpo-
sitions:
(1, . . . , k) = (1, k)(1, k − 1) · · · (1, 3)(1, 2),
since the right hand side sends 1 to 2, 2 to 1 and then to 3, 3 to 1 and then
to 4, and so on, and finally k to 1. There is nothing special about choosing
the cycle (1, . . . , k): if a1 , . . . , ak are k distinct elements of {1, . . . , n}, then
(a1 , . . . , ak ) = (a1 , ak )(a1 , ak−1 ) · · · (a1 , a3 )(a1 , a2 ).

8
Hence every k-cycle is a product of k − 1 transpositions. Since every per-
mutation σ ∈ Sn is a product of k-cycles and every k-cycle is a product of
transpositions, we conclude:

Theorem 2.1. Every element σ ∈ Sn is a product of transpositions.

Intuitively, to permute a set with n elements,

  it is enough to successively
n
switch two at a time. This says that the transpositions (i, j) with i < j
2
generate the group Sn . In fact, as in the homework, Sn can be generated by
2 elements, although in many ways the most natural generating set is given
by the n − 1 elements (1, 2), (2, 3), . . . , (n − 1, n).
It is easy to see that there is in general no way to write a permutation
uniquely as a product of transpositions. For example, we can always insert
the identity which is a product (i, j)(i, j) of a transposition with itself. For
another example, corresponding to the fact that (1, 2, 3) = (2, 3, 1) = (3, 1, 2)
and the above recipe for writing a 3-cycle as a product of transpositions, we
have
(1, 3)(1, 2) = (1, 2)(2, 3) = (2, 3)(1, 3).
If this product is taking place in Sn , n ≥ 5, then we have many more ways
of writing (1, 2, 3) as a product of transpositions, for example (1, 2, 3) =
(4, 5)(1, 3)(2, 4)(2, 4)(1, 2)(4, 5).
Despite the lack of uniqueness, there is one feature that all of the ways
of writing a permutation as a product of transpositions have in common:

Theorem 2.2. Let σ ∈ Sn , and suppose that σ = τ1 · · · τk = ρ1 · · · ρ` , where

the τi and ρj are all transpositions. Then k ≡ ` (mod 2). In other words,
a given element σ of Sn can be written as an even number of transpositions
or as an odd number of transpositions, but not both.

Thus every element of Sn has a well-defined parity, i.e. is either even or

odd, depending on whether it can be written as an even number of trans-
positions or as an odd number of transpositions. We will describe three
different proofs of the theorem; each one is instructive.
First Proof. Consider the positive integer
Y
Nn = (j − i),
1≤i<j≤n

the product of all differences of pairs of distinct positive integers between 1

and n, where we always take the positive difference. Here the exact value

9
of Nn is not important (exercise: show that Nn = (n − 1)!(n − 2)! · · · 2!1!);
clearly, Nn is just a large positive integer, and the main point is that it is
Y σ ∈ Sn , consider what happens when
nonzero since no factor is zero. Given
we consider instead the product (σ(j)−σ(i)). This is again a product
1≤i<j≤n
of all possible differences of pairs of distinct positive integers between 1 and
n, but since σ mixes up the order we don’t always subtract the smaller of the
pair from the larger. Thus, there exists a sign, i.e. there exists an element
ε(σ) ∈ {±1}, such that
Y Y
(σ(j) − σ(i)) = ε(σ)Nn = ε(σ) (j − i).
1≤i<j≤n 1≤i<j≤n

Note that ε(σ) just depends on σ, not on how σ is expressed as a product

of transpositions. The two main facts we need about ε(σ) are
1. For all σ1 , σ2 ∈ Sn , ε(σ1 σ2 ) = ε(σ1 )ε(σ2 ) (i.e. ε is multiplicative); and

2. If τ = (a, b) is a transposition, then ε(τ ) = −1.

Assuming (1) and (2), let us finish the proof. If σ = τ1 · · · τk is a product of
transpositions, then using (1) repeatedly and then (2), we see that

ε(σ) = ε(τ1 · · · τk ) = ε(τ1 ) · · · (τk ) = (−1)k .

Hence ε(σ) = 1 if σ is a product of an even number of transpositions

and ε(σ) = −1 if σ is a product of an even number of transpositions.
In particular, if also σ = ρ1 · · · ρ` where the ρi are transpositions, then
ε(σ) = (−1)` = (−1)k , and hence k ≡ ` (mod 2).
We will not write down the proof of (1); it follows from carefully looking
at how ε(σ) is defined. However, we will prove (2). Suppose that τ = (a, b)
is a transposition, where we may assume that a < b. We examine for which
pairs i < j, 1 ≤ i < j ≤ n, the difference τ (j) − τ (i) is negative. Note that,
if neither i nor j is a or b, then τ (j) − τ (i) = j − i > 0. Thus we may assume
that at least one of i, j is either a or b. For the moment, we assume that
(i, j) 6= (a, b), i.e. either j = a or i = b, but not both. If j = a, then i < a,
hence i 6= b, and
τ (a) − τ (i) = b − i > a − i > 0.
Thus the difference of the pairs a − i don’t change sign. Similarly, if i = b
and j > b, then τ (j) − τ (b) = j − a > j − b > 0. So the only possible sign
changes come from differences j −a, with j > a, or b−i with i < b. Consider
first the case of j − a. If j > b, then τ (j) − τ (a) = j − b > 0. If b > j > a,

10
then τ (j) − τ (a) = j − b < 0, and there are b − a − 1 such j, so these
contribute a factor of (−1)b−a−1 . Likewise, when we look at the difference
b − i, then τ (b) − τ (i) = a − i. The sign is unchanged if i < a but becomes
negative if a < i < b. Again, there are b − a − 1 such i, so these contribute
another factor of (−1)b−a−1 which cancels out the first factor of (−1)b−a−1 .
The only remaining pair of integers that we have not yet considered is the
pair where i = a and j = b. Here τ (b) − τ (a) = a − b = −(b − a), so there
is one remaining factor of −1 which is not canceled out. Thus, the total
number of sign changes is
ε(τ ) = (−1)b−a−1 (−1)b−a−1 (−1) = −1.
Finally, we note a fact which is useful in Modern Algebra II: it didn’t
matter that we chose the integers between 1 and n and looked at their
differences. We could have started with any sequence t1 , . . . , tn of, say,
real
Ynumbers such that the ti are all distinct and looked at the product
(ti −tj ). Comparing this product with the product where we permute
1≤i<j≤n
Y
the pairs, i.e. (tσ(i) − tσ(j) ), the above analysis shows that
1≤i<j≤n
Y Y
(tσ(i) − tσ(j) ) = ε(σ) (ti − tj ),
1≤i<j≤n 1≤i<j≤n

where ε(σ) ∈ {±1} is the sign factor introduced above.

Second Proof. This proof uses basic properties of determinants, which are
closely connected with permutations and signs, so one has to be careful
not to make a circular argument. For σ ∈ Sn , we will define ε(σ) ∈ {±1}
which has the properties (1) and (2) from the first proof, thus showing
that, if σ = τ1 · · · τk is a product of k transpositions, then ε(σ) = (−1)k ;
the argument then concludes as in the first proof. To define ε(σ), we first
associate to σ an n × n matrix P (σ). Recall from linear algebra that an
n × n matrix P (σ) is the same thing as a linear map Rn → Rn , which we
also denote by P (σ), and that such a linear map is specified by its values
on the standard basis e1 , . . . , en ; in fact, the value P (σ)(ei ), written as a
column vector, is the ith column of P (σ). So define P (σ)(ei ) = eσ(i) . Then
P (σ) is a permutation matrix: each row and each column have the property
that all of the entries except for one of them are 0, and the nonzero entry is
1. Clearly P (1) = I. A calculation shows that
P (σ1 σ2 )(ei ) = eσ1 σ2 (i) ;
P (σ1 )P (σ2 )(ei ) = P (σ1 )(eσ2 (i) ) = eσ1 σ2 (i) .

11
Hence P (σ1 σ2 ) and P (σ1 )P (σ2 ) have the same value on each basis vector,
hence on all vectors, and thus P (σ1 σ2 ) = P (σ1 )P (σ2 ). Now, to convert
the matrix P (σ) to a number, we have the determinant det. Define ε(σ) =
det P (σ). As it stands, ε(σ) is just a real number. However, using the
multiplicative property of the determinant, for all σ1 , σ2 ∈ Sn , we have

ε(σ1 σ2 ) = det(P (σ1 σ2 )) = det(P (σ1 )P (σ2 )) = det P (σ1 ) det P (σ2 ) = ε(σ1 )ε(σ2 ).

Clearly ε(1) = det I = 1. Moreover, if τ = (i, j) is a transposition, then

P (τ ) is obtained from I by switching the ith and j th columns of I. Another
well-known property of the determinant says that, in this case, det P (τ ) =
− det I = −1. Putting this together, we see that, if σ = τ1 · · · τk is a product
of transpositions, then, as in the first proof,

ε(σ) = ε(τ1 · · · τk ) = ε(τ1 ) · · · ε(τk ) = (−1)k ,

and hence k is either always even or always odd.

Third Proof. In this proof, we don’t define the function ε directly, but just
use information about the orbits of σ to see that σ cannot simultaneously
be the product of an even and an odd number of transpositions. For any
σ ∈ Sn , define N (σ) to be the number of orbits of σ, including the one-
element orbits. For example, as we saw earlier, if σ is an r-cycle, then
N (σ) = n − r + 1. The main point of the third proof is then:

Claim 2.3. If σ ∈ Sn is a product of k transpositions, i.e. σ = τ1 · · · τk

where each τi is a transposition, then

N (σ) ≡ n − k (mod 2).

To see that Claim 2.3 implies the theorem, suppose that σ = τ1 · · · τk =

ρ1 · · · ρ` , where the τi and ρj are transpositions. Then we have both that
N (σ) ≡ n−k (mod 2) and that N (σ) ≡ n−` (mod 2), hence k ≡ ` (mod 2).

Proof of Claim 2.3. We prove Claim 2.3 by induction on k. If k = 1, then σ

is a transposition, hence a 2-cycle, and hence N (σ) = n−2+1 = n−1 by the
discussion before the statement of the claim, so the congruence in the claim
is in fact an equality. By induction, suppose that the claim is true for all
products of k transpositions, and consider a product of k + 1 transpositions,
say σ = τ1 · · · τk τk+1 . If we set ρ = τ1 · · · τk , then by the inductive hypothesis
N (ρ) ≡ n−k (mod 2), and we must show that N (ρτk+1 ) ≡ n−k−1 (mod 2).
Clearly, it is enough (since 1 ≡ −1 (mod 2)) to show the following:

12
Claim 2.4. If ρ ∈ Sn and τ ∈ Sn is a transposition, then

N (ρτ ) ≡ N (ρ) + 1 (mod 2).

In fact, N (ρτ ) = N (ρ) ± 1.

Proof of Claim 2.4. Label the orbits of ρ (including the one-element orbits)
as O1 , . . . , ON , where N = N (ρ). As usual, we can assume that O1 , . . . , OM
have at least two elements and that OM +1 , . . . , ON are the one-element
orbits. We must show that ρτ has N ± 1 orbits. Since τ is a transposition,
we can write τ = (a, b) for some a, b ∈ {1, . . . , n}, a 6= b.
Case I. There is some orbit Oi of ρ, necessarily with at least two elements,
such that a, b ∈ Oi . In this case, we claim that N (ρτ ) = N (ρ) + 1. For
each j ≤ M , let Oj correspond to the kj -cycle µj , so that ρ = µ1 · · · µM ,
where the µj are disjoint and hence commute. For the cycle µi , we know
that a, b ∈ Supp µi = Oi , and a, b are not in the support of any µj , j 6= i.
Then (a, b) commutes with all of the µj , j 6= i, and hence

ρτ = µ1 · · · µM τ = µ1 · · · (µi τ ) · · · µM .

If we write µi = (i1 , . . . , iki ), then one of the ir , say it , is a, and another,

say is , is b, and after switching a and b we can assume that t < s. Thus we
can write µi = (i1 , . . . , it−1 , a, it+1 , . . . , is−1 , b, is+1 , . . . , iki ). Of course, it is
possible that t = 1 and s = 2, say. Now consider the product

µi τ = (i1 , . . . , it−1 , a, it+1 , . . . , is−1 , b, is+1 , . . . , iki )(a, b).

We see that a is sent to is+1 , is+1 is sent to is+2 , . . . , iki −1 to iki , iki to
i1 ,. . . , and finally it−1 is sent back to a. As for b, it is sent to it+1 , it+1 is
sent to it+2 , . . . , and finally is−1 is sent back to b. In other words,

µi τ = (i1 , . . . , it−1 , a, it+1 , . . . , is−1 , b, is+1 , . . . , iki )(a, b)

= (a, is+1 , . . . , iki , i1 , . . . , it−1 )(b, it+1 , . . . , is−1 ) = µ0 µ00 ,

say, where µ0 and µ00 are two cycles, disjoint from each other and from all
of the other µj and the remaining one-element orbits. (Note: it is possible
that one or both of µ0 , µ00 is a one-cycle. How could this happen?) It follows
that the orbits of ρτ are the Oj for j 6= i together with the two new orbits
O0 , O00 coming from µ0 and µ00 . Counting them, we see that there are N + 1
orbits in all, hence N (ρτ ) = N (ρ) + 1.
Case II. In this case, we assume that a and b are in different orbits, say
a ∈ Oi and b ∈ Oj with i 6= j. We let µi , µj be the corresponding cycles.

13
Note that it is possible that either Oi or Oj is a one-element orbit, in which
case we will simply define µi or µj to be the corresponding one-cycle (in
particular, as an element of Sn , it would then be the identity). Then

ρτ = µ1 · · · µM τ = µ1 · · · (µi µj τ ) · · · µM ,

where we have simply moved the µi and µj next to each other since all of the
µi commute. In this case, we claim that N (ρτ ) = N (ρ) − 1. Write as before
µi = (i1 , . . . , it−1 , a, it+1 , . . . , iki ) and µj = (`1 , . . . , `s−1 , b, `s+1 , . . . , `kj ). A
calculation similar to that in Case I shows that

µi µj τ = (i1 , . . . , it−1 , a, it+1 , . . . , iki )(`1 , . . . , `s−1 , b, `s+1 , . . . , `kj )(a, b)

= (a, `s+1 , . . . , `kj , `1 , . . . , `s−1 , b, it+1 , . . . , iki , i1 , . . . , it−1 ) = µ,

say. Thus the orbits of ρτ are the Ok for k 6= i, j together with O = Supp µ.
Counting these up, we see that there are N − 1 orbits in all, hence N (ρτ ) =
N (ρ) − 1.

Definition 2.5. If σ ∈ Sn , we define ε(σ) = 1, if σ is a product of an even

number of transpositions, and ε(σ) = −1, if σ is a product of an odd number
of transpositions. Likewise, we define σ to be even if σ is a product of an
even number of transpositions (i.e. ε(σ) = 1) and odd if σ is a product of an
odd number of transpositions (i.e. ε(σ) = −1). The content of the previous
theorem is then that ε is well-defined. Finally we define An , the alternating
group, to be the subset of Sn consisting of even permutations.

Lemma 2.6. Let σ1 and σ2 be elements of Sn . If σ1 and σ2 are both even or

both odd, then the product σ1 σ2 is even. If one of σ1 , σ2 is even and the other
is odd, then the product σ1 σ2 is odd. Equivalently, ε(σ1 σ2 ) = ε(σ1 )ε(σ2 ).

Proof. Suppose that σ1 can be written as a product τ1 · · · τk of k transposi-

tions and that σ2 can be written as a product ρ1 · · · ρ` of ` transpositions.
Then σ1 σ2 = τ1 · · · τk ρ1 · · · ρ` is a product of k + ` transpositions. (Confus-
ingly, for the product σ1 σ2 we take the sum of the numbers of transposi-
tions.) From this, the proof of the lemma is clear: if k and ` are both even
or both odd, then k + ` is even, and if one of k, ` is even and the other is
odd, then k + ` is odd.

Corollary 2.7. An is a subgroup of Sn .

Proof. If σ1 , σ2 ∈ An , then σ1 and σ2 are both even, hence σ1 σ2 is even,

hence σ1 σ2 ∈ An and An is closed under taking products. The element 1 is

14
even, i.e. 1 ∈ An , either formally (1 is the product of 0 transpositions and
0 is even) or by writing 1 = (a, b)(a, b), which is possible as long as n ≥ 2.
Finally, if σ ∈ An , then σ = τ1 · · · τk is the product of k transpositions,
where k is even. Then

σ −1 = (τ1 · · · τk )−1 = τk−1 · · · τ1−1 = τk · · · τ1 ,

i.e. σ −1 is the product of the k transpositions τ1 , . . . , τk in the opposite

order. In particular, σ −1 is the product of an even number of transpositions,
hence σ −1 ∈ An . Thus An is a subgroup of Sn .

Example 2.8. First note that, as we have already seen, a k-cycle is a

product of k − 1 transpositions if k ≥ 1 (and a 1-cycle is a product of two
transpositions). Thus a k-cycle is is even if k is odd and odd if k is even.
Hence we can determine the parity of any product of cycles (whether or not
they are disjoint). This gives the following description of the subgroups An
for small n: A1 = S1 = {1}. A2 = {1}. A3 consists of 1 together with the
two different 3-cycles in S3 : A3 = {1, (1, 2, 3), (1, 3, 2)}. A4 consists of 1, the
8 3-cycles, and the 3 products of two disjoint 2-cycles. Hence #(A4 ) = 12 =
1 1
2 #(S4 ), and in hindsight we also see that #(A2 ) = 1 = 2 #(S2 ) and that
1
#(A3 ) = 3 = 2 #(S3 ). This is not a coincidence:

Proposition 2.9. For n ≥ 2, #(An ) = 12 #(Sn ) = n!/2.

Proof. Since every element of Sn is either even or odd, Sn is the disjoint

union of An , the set of even permutations, and Sn − An , the set of odd
permutations. We will find a bijection from An to Sn − An . This will imply
that #(An ) = #(Sn − An ), hence

#(Sn ) = #(An ) + #(Sn − An ) = 2#(An ),

hence #(An ) = 21 #(Sn ).

To find a bijection from An to Sn − An , choose an odd permutation ρ.
For example, we can take ρ = (1, 2). Note that this is only possible for
n ≥ 2, since for n = 1 S1 = {1} and every permutation is trivially even.
Then define a function f : An → Sn − An by the rule:

f (σ) = ρ · σ,

the product of σ with the fixed odd permutation ρ. If σ ∈ An , then σ is

even and hence ρσ is odd, so that f is really a function from An to Sn − An .
To show that f is a bijection, it is enough to find an inverse function, i.e. a

15
function g : Sn − An → An such that f ◦ g and g ◦ f are both the identity
(on their respective domains). Define g : Sn − An → An by the rule:

g(σ) = ρ−1 σ.

If ρ is odd, then ρ−1 is odd, hence, if σ is also odd, then ρ−1 σ is even.
Thus g is really a function from Sn − An to An . Finally, if σ ∈ An , then
g ◦ f (σ) = ρ−1 ρσ = σ, and if σ ∈ Sn − An , then f ◦ g(σ) = ρρ−1 σ = σ. Thus
f ◦ g = IdSn −An and g ◦ f = IdAn , so that g = f −1 and f is a bijection.

The group An is a group of fundamental importance, for reasons which

will gradually emerge this semester, and will play a major role in Modern
Algebra II as well.

16