228 CHAPTER 9. SOME ITEMS WHICH RESEMBLE LINEAR ALGEBRA

In other words, the sign of the permutation(1 2 · · · ni1 i2 · · · in

)

equals sgn(i1, · · · , in) defined earlier in Lemma 8.1.1.Note that from the fact that the determinant is well defined and its properties, the sign of

a permutation is 1 if and only if the permutation is produced by an even number of switchesand that the number of switches used to produce a given permutation must be either evenor odd. Of course a switch is a permutation itself and this is called a transposition. Notealso that all these matrices are orthogonal matrices so to take the inverse, it suffices to takea transpose, the inverse also being a permutation matrix.

The resulting group consisting of the permutations of In is called Sn. An important ideais the notion of a cycle. Let σ be a permutation, a one to one and onto function defined onIn. A cycle is of the form(

k,σ (k) ,σ2 (k) ,σ3 (k) , · · · ,σm−1 (k)), σ

m (k) = k.

The last condition must hold for some m because In is finite. Then a cycle can be consideredas a permutation as follows. Let (i1, i2, · · · , im) be a cycle. Then define σ by σ (i1) =i2,σ (i2) = i3, · · · ,σ (im) = i1, and if k /∈ {i1, i2, · · · , im} , then σ (k) = k.

Note that if you have two cycles, (i1, i2, · · · , im) ,( j1, j2, · · · , jm) which are disjoint inthe sense that

{i1, i2, · · · , im}∩{ j1, j2, · · · , jm}= /0,

then they commute. It is then clear that every permutation can be represented in a uniqueway by disjoint cycles. Start with 1 and form the cycle determined by 1. Then start with thesmallest k ∈ In which was not included and begin a cycle starting with this. Continue thisway. Use the convention that (k) is just the identity sending k to k and all other indices tothemselves. This representation is unique up to order of the cycles which does not matterbecause they commute. Note that a transposition can be written as (a,b), a→ b and b→ a.

A cycle can be written as a product of non disjoint transpositions.

(i1, i2, · · · , im) = (im−1, im) · · ·(i3, im)(i2, im)(i1, im)

Thus if m is odd, the permutation has sign 1 and if m is even, the permutation has sign −1.Also, it is clear the inverse of the above permutation is (i1, i2, · · · , im)−1 = (im, · · · , i2, i1) .For example, (1,2,3) = (2,3)(1,3).

Definition 9.4.35 An is the subgroup of Sn such that for σ ∈ An, σ is the product of aneven number of transpositions. It is called the alternating group.

Since each transposition switches a pair of columns in the above permutation matrix,the sign of the determinant which is the sign of the permutation is always 1 for permutationsin An. This is another way to describe An, those permutations with sign 1. If n = 1, thereis only one permutation and it is the identity so A1 = identity. If n = 2, you would havetwo permutations, the identity and the transposition (1,2). Thus A2 = identity. It might beuseful to think of the identity map as having zero transpositions.

The following important result is useful in describing An.