Permutations and the symmetric group

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 17 August 2013

The symmetric groups Sm

Let m>0 .

There are several convenient ways of representing a permutation σ.

  1. Two line notation: where w(i) in the second line is below i in the first line. w= ( 1 2 3 4 5 6 4 1 6 2 5 3 ).
  2. Cycle notation: Where (i1, i2,, ir) indicates w(i1) = i2,   w(i2) = i3,   ,   w(ir-1) = ir,   w(ir) = i1. Cycles of length 1 are usually dropped from the notation. w= (142)(36)(5) =(142)(36).
  3. Matrix notation: where the w(i)th entry of the ith column is 1 and all other entries are 0. w= ( 010 000 000 100 000 001 100 000 000 010 001 000 ).
  4. Diagram notation: where the ith dot in the top row is connected to the w(i)th dot in the bottom row. w= .

HW: Show that Card( Sm)= m!.

Generators and relations

The symmetric group Sm has a presentation by the generators s1, s2, , sm-1 and relations si2 =1, for i{1,m-1} sisj= sjsi, if ji,i±1, and si si+1 si = si+1 si si+1, for i{1,m-2}

Proof.
There are three things to show:
  1. The simple transpositions in Sm satisfy the given relations.
  2. The simple transpositions generate Sm.
  3. The group given by generators s1, , sm-1 and relations as in the statement of the theorem has order n!.
  1. The following pictures show that the simple transpositions si= (i,i+1), for 1im-2 , satisfy the given relations. = = = = =
  2. The diagram of any permutation can be "stretched" to guarantee that no more than two edges cross at any given point. Then w can be written as a product of simple transpositions corresponding to these crossings. w= = = s1s3 s5s4 s5s3.
  3. Let Gm be the free group generated by symbols s1, s2,, sm-1 modulo the relations in the statement of the theorem. Let Gm-1 be the subgroup generated by s1, s2,, sn-2. We will show that
    1. Every element w Gm can be written in the form w= w1 sm-1 w2, with w1,w2 Gm-1 .
    2. Every element w Gm can be written in the form w= asm-1 sm-2 sk, for 1kn, and a Gm-1.

    1. Since sm-12 =1, every element wGm can be written in the form w= w1 sm-1 w2 sm-1 w3 sm-1 wl-1 sm-1 wl, where wj Gm-1. By induction, either w2 Gm-2 or w2= asm-2 b, where a,b Gm-2. In the first case w = w1sn-1 w2sn-1 w3sn-1 wl-1 sn-1 wl = w1w2 sn-1 sn-1 w3 sn-1 wl-1 sn-1 wl = w1w2 sn-1 w3 sn-1 wl-1 sn-1 wl, and in the second case w = w1 sn-1 w2 sn-1 w3 sn-1 wl-1 sn-1 wl = w1 sn-1a sn-2b sn-1 w3 sn-1 wl-1 sn-1 wl = w1a sn-1 sn-2 sn-1b w3 sn-1 wl-1 sn-1 wl = w1a sn-2 sn-1 sn-2b w3 sn-1 wl-1 sn-1 wl = w1 sn-1 w3 sn-1 wl-1 sn-1 wl where w1 = w1a sn-2 Gn-1 and w3 = sn-2b w3 Gn-1 . In either case the number of sn-1 factors in the expression of w has been reduced. The statement in (1) follows by induction.
    2. By (1) any element w Gm is either an element of Gm-1 or can be written in the form w=w1 sm-1 w2, with w1,w2 Gm-1 . In the first case w=w sm-1 sl with l=m and the statement is satisfied. If w= w1 sm-1 w2 then, by induction, w2=a sm-2 sm-3 sl , for some 1lm-2 and a Gm-2. So w=w1 sm-1a sm-2 sl = w1a sm-1 sl = w1 sn-1 sl, where w1 = w1a Gn-1 . Statement (2) follows.
    From (2) it follows that Card(Gm) Card(Gm-1) m, and, by induction, that Card(Gm) m!. Since Sm is a quotient of Gm and Card(Sm) = n! , then Gm Sm.

The sign of a permutation

Let w be a permutation in Sm.

A pair (i,j) is in inv(σ) if, in the function diagram of σ, the edges starting at positions i and j cross.

HW: Show that the sign of a simple transposition is det(si) =-1.

HW: Show that the sign of a permutation σ is equal to the determinant of the matrix which represents the permutation σ.

Let det(σ) denote the sign of the permutation σ. The function det: Sm {±1} σ det(σ) is a group homomorphism.

Conjugacy classes

Definition.

Example. A permutation σ can have several different representations in cycle notation. In cycle notation, 12345 67 89 10 , 51234 67 89 , 45123 67 10 , 34512 89 67 , and 34512 10 98 67 , all represent the same permutation in S10, which, in two line notation, is given by 1 2 3 4 5 6 7 8 9 10 2 3 4 5 1 7 6 9 8 10 .

Example. If σ in S9 which is given, cylce notation, by σ= 1362 587 49 and π is the permutation in S9 which is given, in 2-line notation, by 1 2 3 4 5 6 7 8 9 4 6 1 3 5 9 2 8 7 , then πσπ-1 is the permutation which is given, in cycle notation, by πσπ-1= 4 1 9 6 5 8 2 3 7 = 1964 258 37 .

  1. The conjugacy classes of Sm are the sets 𝒞λ = permutations σ  with cycle type λ , where λ is a partition of m.
  2. If λ= 1m1 2m2 then the size of the conjugacy class 𝒞λ is 𝒞λ = m! m1!1m1 m2!2m2 m3!3m3 .

The proof of Theorem (3.1) will use the following lemma.

Suppose that σSm has cycle type λ= λ1,λ2, and let γλ be the permutation Sm which is given, in cycle notation, by γλ= 1,2,,λ1 λ1+1, λ2+2,, λ1+λ2 λ1+λ2+1,

  1. Then σ is conjugate to γλ .
  2. If τSm is conjugate to σ then τ has cycle type λ.
  3. Suppose that λ= 1m1 2m2 . Then the order of the stabilizer of the permutation γλ, under the action of Sm on itself by conjugation, is m1!1m1 m2!2m2.

Example. The sequence λ= 66433322111 is a partition of 32 and can be represented in the form λ= 13 22 33 4 50 62 = 13 22 33 4 62 . The conjugacy class 𝒞λ in S32 had 32! 13 3! 22 2! 33 3! 4 62 2! elements.

Examples and exercises

There are several convenient ways of representing a permutation σ.

  1. As a two line array σ=( 1 2 3 m σ1 σ2 σ3 σm ).
  2. As a one line array σ=( σ(1) σ(2) σ(m) ) .
  3. As an m×m matrix which has the (σ(i), i)th entry equal to 1 for i{ 1,,m} and all other entries 0.
  4. As a function diagram consisting of two rows, of m dots each, such that the ithdot of the upper row is connected to the σ(i)th dot of the lower row.
  5. In cycle notation, as a collection of sequences ( i1, i2, , ik ) such that σ(i1) =i2, σ(i2) =i3, , σ(ik-1) =ik, σ(ik) =i1 . It is common to leave out the cycles containing only one element when writing σ in cycle notation.

Example.

Element 1-line 2-line Function Matrix Cycle Diagram Cycle Notation Type
σ 364152 1 2 3 4 5 6 3 6 4 1 5 2 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 134 26 3,2,1
τ 356241 1 2 3 4 5 6 3 5 6 2 4 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 136 254 3,3
τσ 612345 1 2 3 4 5 6 6 1 2 3 4 5 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 165 4321 6
στ 452613 1 2 3 4 5 6 4 5 2 6 1 3 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 146325 6
σ-1 461352 1 2 3 4 5 6 4 6 1 3 5 2 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 143 23 3,2,1
τ-1 641523 1 2 3 4 5 6 6 4 1 5 2 3 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 163 245 3,3

HW: Show that the order of the symmetric group Sm is m!= m(m-1) (m-2) 21 .

HW: Show that, in function diagram notation, the product τσ of two permutations τ and σ is given by placing the diagram of σ above the diagram of τ and connecting the bottom dots of σ to the top dots of τ.

HW: Show that, in function diagram notation, the identity permutation is represented by m vertical lines.

HW: Show that, in function diagram notation, σ-1 is represented by the diagram of σ flipped over.

HW: Show that, in matrix notation, the product τσ of two permutations τ and σ is given by matrix multiplication.

HW: Show that, in matrix notation, the identity permutation is the diagonal matrix with all 1's on the diagonal.

HW: Show that, in matrix notation, the matrix of σ-1 is the transpose of the matrix of σ.

HW: Show that the matrix of a permutation is always an orthogonal matrix.

References

[Bou] N. Bourbaki, Groupes et Alg├Ębres de Lie, Masson, Paris, 1990.

[GW1] F. Goodman and H. Wenzl, The Temperly-Lieb algebra at roots of unity, Pacific J. Math. 161 (1993), 307-334. MR1242201 (95c:16020)

page history

page history