## Permutations and the symmetric group

Last update: 17 August 2013

## The symmetric groups ${S}_{m}$

Let $m\in {ℤ}_{>0}$.

• A permutation of $m$ is a bijective function $\sigma :\left\{1,2,\dots ,m\right\}\to \left\{1,2,\dots ,m\right\}$
• The symmetric group ${S}_{m}$ is the set of permutations of $m$ with the operation of composition of functions.

There are several convenient ways of representing a permutation $\sigma$.

1. Two line notation: where $w\left(i\right)$ 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 $\left({i}_{1},{i}_{2},\dots ,{i}_{r}\right)$ indicates Cycles of length 1 are usually dropped from the notation. $w= (142)(36)(5) =(142)(36).$
3. Matrix notation: where the $w\left(i\right)$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 $i$th dot in the top row is connected to the $w\left(i\right)$th dot in the bottom row. $w= .$

HW: Show that $\mathrm{Card}\left({S}_{m}\right)=m!$.

## Generators and relations

• The transpositions in ${S}_{m}$ are the permutations ${s}_{ij}=\left(i,j\right)$, in cycle notation, for $i,j\in \left\{1,\dots ,m\right\}$ with $i. $PICTURE OF A TRANSPOSITION$
• The simple transpositions are $si =(i,i+1) = i i+1 ⋯ ⋯ , for i∈{1,…, m-1}.$
• A reduced word for $\sigma \in {S}_{m}$ is an expression of $\sigma$ as a product of simple transpositions $σ= si1 si2⋯ siℓ such that the number of factors is as small as possible.$
• The length $\ell \left(\sigma \right)$ of $\sigma$ is the number of factors in a reduced expression for the permutation $\sigma$.

The symmetric group ${S}_{m}$ has a presentation by the generators ${s}_{1},{s}_{2},\dots ,{s}_{m-1}$ and relations $si2 =1, for i∈{1,…m-1} sisj= sjsi, if j≠i,i±1, and si si+1 si = si+1 si si+1, for i∈{1,…m-2}$

 Proof. There are three things to show: The simple transpositions in ${S}_{m}$ satisfy the given relations. The simple transpositions generate ${S}_{m}$. The group given by generators ${s}_{1},\dots ,{s}_{m-1}$ and relations as in the statement of the theorem has order $\le n!.$ The following pictures show that the simple transpositions ${s}_{i}=\left(i,i+1\right),$ for $1\le i\le m-2$, satisfy the given relations. $=$ $= =$ $= =$ 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.$ Let ${G}_{m}$ be the free group generated by symbols ${s}_{1},{s}_{2},\dots ,{s}_{m-1}$ modulo the relations in the statement of the theorem. Let ${G}_{m-1}$ be the subgroup generated by ${s}_{1},{s}_{2},\dots ,{s}_{n-2}$. We will show that Every element $w\in {G}_{m}$ can be written in the form $w={w}_{1}{s}_{m-1}{w}_{2},$ with ${w}_{1},{w}_{2}\in {G}_{m-1}$. Every element $w\in {G}_{m}$ can be written in the form $w=a{s}_{m-1}{s}_{m-2}\cdots {s}_{k},$ for $1\le k\le n,$ and $a\in {G}_{m-1}.$ Since ${s}_{m-1}^{2}=1$, every element $w\in {G}_{m}$ 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 ${w}_{2}\in {G}_{m-2}$ or ${w}_{2}=a{s}_{m-2}b$, where $a,b\in {G}_{m-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 ${w}_{1}^{\prime }={w}_{1}a{s}_{n-2}\in {G}_{n-1}$ and ${w}_{3}^{\prime }={s}_{n-2}b{w}_{3}\in {G}_{n-1}.$ In either case the number of ${s}_{n-1}$ factors in the expression of $w$ has been reduced. The statement in (1) follows by induction. By (1) any element $w\in {G}_{m}$ is either an element of ${G}_{m-1}$ or can be written in the form $w={w}_{1}{s}_{m-1}{w}_{2},$ with ${w}_{1},{w}_{2}\in {G}_{m-1}$. In the first case $w=w{s}_{m-1}\cdots {s}_{l}$ with $l=m$ and the statement is satisfied. If $w={w}_{1}{s}_{m-1}{w}_{2}$ then, by induction, ${w}_{2}=a{s}_{m-2}{s}_{m-3}\cdots {s}_{l}$, for some $1\le l\le m-2$ and $a\in {G}_{m-2}$. So $w=w1 sm-1a sm-2 ⋯sl = w1a sm-1 ⋯sl = w1′ sn-1 ⋯sl,$ where ${w}_{1}^{\prime }={w}_{1}a\in {G}_{n-1}.$ Statement (2) follows. From (2) it follows that $\mathrm{Card}\left({G}_{m}\right)\le \mathrm{Card}\left({G}_{m-1}\right)\cdot m,$ and, by induction, that $\mathrm{Card}\left({G}_{m}\right)\le m!.$ Since ${S}_{m}$ is a quotient of ${G}_{m}$ and $\mathrm{Card}\left({S}_{m}\right)=n!$, then ${G}_{m}\cong {S}_{m}$. $\square$

## The sign of a permutation

Let $w$ be a permutation in ${S}_{m}$.

• The set of inversions of $\sigma$ is the set $inv(σ)= { (i,j) | i,j∈{1, …,m}, i σ(j) } .$
• The length of $\sigma$ is $\ell \left(\sigma \right)=\mathrm{Card}\left(\mathrm{inv}\left(\sigma \right)\right)$
• The sign of $\sigma$ is $\mathrm{det}\left(\sigma \right)={\left(-1\right)}^{𝓁\left(\sigma \right)}$.
• The permutation $\sigma$ is even if $\mathrm{det}\left(\sigma \right)=1$ and odd if $\mathrm{det}\left(\sigma \right)=-1$.
A pair $\left(i,j\right)$ is in $\mathrm{inv}\left(\sigma \right)$ if, in the function diagram of $\sigma$, the edges starting at positions $i$ and $j$ cross.

HW: Show that the sign of a simple transposition is $\mathrm{det}\left({s}_{i}\right)=-1$.

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

Let $\mathrm{det}\left(\sigma \right)$ denote the sign of the permutation $\sigma$. The function $det: Sm → {±1} σ ↦ det(σ) is a group homomorphism.$

## Conjugacy classes

Definition.

• A partition $\lambda =\left({\lambda }_{1},{\lambda }_{2},\dots ,{\lambda }_{k}\right)$ of $m$ is a weakly decreasing sequence of positive integers which sum to $m$, i.e. $λ1≥ λ2≥ ⋯≥ λk>0 and λ1+ λ2+ ⋯+ λk=m.$ The elements of a partition $λ=( λ1, λ2, …, λk )$ are the parts of the partition $\lambda$. Sometimes a partition $\lambda$ is represented in the form $\lambda =\left({1}^{{m}_{1}}{2}^{{m}_{2}}\cdots \right)$ if $\lambda$ has ${m}_{1}$ $1$'s, ${m}_{2}$ $2$'s and so on. Write $\lambda ⊢m$ if $\lambda$ is a partition of $m$.
• The cycles of a permutation $\sigma$ are the ordered sequences $\left({i}_{1},{i}_{2},\dots ,{i}_{k}\right)$ such that $σ(i1) =i2, σ(i2)= i3, …, σ(ik-1) =ik, σ(ik)= i1.$
• The cycle type $\tau \left(\sigma \right)$ of a permutation $\sigma \in {S}_{m}$ is the partition of $m$ determined by the sizes of the cycles of $\sigma$.

Example. A permutation $\sigma$ 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 ${S}_{10}$, 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 $\sigma$ in ${S}_{9}$ which is given, cylce notation, by $σ= 1362 587 49$ and $\pi$ is the permutation in ${S}_{9}$ 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 $\pi \sigma {\pi }^{-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 ${S}_{m}$ are the sets where $\lambda$ is a partition of $m$.
2. If $\lambda =\left({1}^{{m}_{1}}{2}^{{m}_{2}}\cdots \right)$ then the size of the conjugacy class ${𝒞}_{\lambda }$ is $𝒞λ = m! m1!1m1 m2!2m2 m3!3m3 ⋯ .$

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

Suppose that $\sigma \in {S}_{m}$ has cycle type $\lambda =\left({\lambda }_{1},{\lambda }_{2},\dots \right)$ and let ${\gamma }_{\lambda }$ be the permutation ${S}_{m}$ which is given, in cycle notation, by $γλ= 1,2,…,λ1 λ1+1, λ2+2,…, λ1+λ2 λ1+λ2+1,⋯ ⋯$

1. Then $\sigma$ is conjugate to ${\gamma }_{\lambda }$ .
2. If $\tau \in {S}_{m}$ is conjugate to $\sigma$ then $\tau$ has cycle type $\lambda$.
3. Suppose that $\lambda =\left({1}^{{m}_{1}}{2}^{{m}_{2}}\cdots \right).$ Then the order of the stabilizer of the permutation ${\gamma }_{\lambda }$, under the action of ${S}_{m}$ on itself by conjugation, is $m1!1m1 m2!2m2⋯.$

Example. The sequence $\lambda =\left(66433322111\right)$ is a partition of $32$ and can be represented in the form $\lambda =\left({1}^{3}{2}^{2}{3}^{3}4{5}^{0}{6}^{2}\right)=\left({1}^{3}{2}^{2}{3}^{3}4{6}^{2}\right).$ The conjugacy class ${𝒞}_{\lambda }$ in ${S}_{32}$ had $\frac{32!}{{1}^{3}\cdot 3!\cdot {2}^{2}\cdot 2!\cdot {3}^{3}\cdot 3!\cdot 4\cdot {6}^{2}\cdot 2!}$ elements.

## Examples and exercises

There are several convenient ways of representing a permutation $\sigma$.

1. As a two line array $\sigma =\left(\begin{array}{ccccc}1& 2& 3& \dots & m\\ \sigma \left(1\right)& \sigma \left(2\right)& \sigma \left(3\right)& \dots & \sigma \left(m\right)\end{array}\right).$
2. As a one line array $\sigma =\left(\sigma \left(1\right)\phantom{\rule{0.5em}{0ex}}\sigma \left(2\right)\phantom{\rule{0.5em}{0ex}}\dots \phantom{\rule{0.5em}{0ex}}\sigma \left(m\right)\right)$.
3. As an $m×m$ matrix which has the ${\left(\sigma \left(i\right),i\right)}^{th}$ entry equal to $1$ for $i\in \left\{1,\dots ,m\right\}$ and all other entries 0.
4. As a function diagram consisting of two rows, of $m$ dots each, such that the ${i}^{th}$dot of the upper row is connected to the $\sigma {\left(i\right)}^{th}$ dot of the lower row.
5. In cycle notation, as a collection of sequences $\left({i}_{1},{i}_{2},\dots ,{i}_{k}\right)$ such that $\sigma \left({i}_{1}\right)={i}_{2},\sigma \left({i}_{2}\right)={i}_{3},\dots ,\sigma \left({i}_{k-1}\right)={i}_{k},\sigma \left({i}_{k}\right)={i}_{1}$. It is common to leave out the cycles containing only one element when writing $\sigma$ in cycle notation.

Example.

Element $1$-line $2$-line Function Matrix Cycle Diagram Cycle Notation Type
$\sigma$ $3 6 4 1 5 2$ $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$ $1 3 4 2 6$ $3,2,1$
$\tau$ $3 5 6 2 4 1$ $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$ $1 3 6 2 5 4$ $3,3$
$\tau \sigma$ $6 1 2 3 4 5$ $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$ $1 6 5 4 3 2 1$ $6$
$\sigma \tau$ $4 5 2 6 1 3$ $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$ $1 4 6 3 2 5$ $6$
${\sigma }^{-1}$ $4 6 1 3 5 2$ $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$ $1 4 3 2 3$ $3,2,1$
${\tau }^{-1}$ $6 4 1 5 2 3$ $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$ $1 6 3 2 4 5$ $3,3$

HW: Show that the order of the symmetric group ${S}_{m}$ is $m!=m\left(m-1\right)\left(m-2\right)\cdots 2\cdot 1$.

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

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

HW: Show that, in function diagram notation, ${\sigma }^{-1}$ is represented by the diagram of $\sigma$ flipped over.

HW: Show that, in matrix notation, the product $\tau \sigma$ of two permutations $\tau$ and $\sigma$ 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 ${\sigma }^{-1}$ is the transpose of the matrix of $\sigma$.

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)