Symmetric Groups

The Symmetric Groups

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

Last updates: 7 December 2010

The symmetric groups Sm

Definition. Let 1,m denote the set 1,2,,m . A permutation of m is a bijective map σ: 1,m 1,m. The symmetric group, Sm, is the set of permutations of m with th operation of composition of functions.

HW: Show that the order of the symmetric group Sm is m!= mm-1 m-221.

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,ith entry equal to 1 for all i and all other entries equal to zero.
  4. As a function diagram consiting of two rows, of m dots each, such that the ith dot of the upper row is connected to the σ ith 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. We often leave out the cycles containing only one element when we write σ in cycle notation.

HW: Show that, in function diagram noation, 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.

The sign of a permutation

For each permutation σSm, let dσ denote the determinant of the matrix which represents the permutation σ. The map ϵ: Sm ±1 σ detσ is a homomorphism from the symmetric group Sm to the group μ2= ±1 .

Definition.

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

Conjugacy classes

Definition.

Example. A permutation σ can have several different representations in cycle notation. I 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.

Generators and relations

Definition. The simple transpositions in Sm are the elements si= i,i+1, 1im-1.

  1. Sm is generated by the simple transpositions si, 1im-1.
  2. The simple transpositions si, 1im-1, in Sm satsify the relations sisj= sjsi, if  i-j >1, sisi+1si= si+1sisi+1, 1im-2, si2 =1, 1im-1.

Definition.

HW: Show that the sign ϵsi of a simple transposition si in the symmetric group Si is -1.

Let σ be a permutation. Let 𝓁σ be the length of σ and let invσ be the set of inversions of the permutation σ. Then

  1. The sign of σ is ϵσ= -1 𝓁σ .
  2. Cardinvσ= 𝓁σ.
  3. The number of crossings in the function diagram of σ is 𝓁σ.

The symmetric group Sm has a presentation by the generators s1, s2, , sm-1 and relations sisj= sjsi, if  i-j >1, sisi+1si= si+1sisi+1, 1im-2, si2 =1, 1im-1.

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