Symmetric Groups

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

Definition. Let $\left[1,m\right]$ denote the set $\left\{1,2,\dots ,m\right\}$. A permutation of $m$ is a bijective map $σ: 1,m → 1,m.$ The symmetric group, ${S}_{m}$, is the set of permutations of $m$ with th operation of composition of functions.

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.$

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)\sigma \left(2\right)\dots \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 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 ${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(i2\right)={i}_{3},\dots ,\sigma \left({i}_{k-1}\right)={i}_{k},\sigma \left({i}_{k}\right)={i}_{1}.$ We often leave out the cycles containing only one element when we write $\sigma$ in cycle notation.

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

The sign of a permutation

For each permutation $\sigma \in {S}_{m},$ let $d\left(\sigma \right)$ denote the determinant of the matrix which represents the permutation $\sigma$. The map $ϵ: Sm → ±1 σ ↦ detσ$ is a homomorphism from the symmetric group ${S}_{m}$ to the group ${\mu }_{2}=\left\{±1\right\}.$

Definition.

• The sign homomorphism of the symmetric group ${S}_{m}$ is the homomorphism $ϵ: Sm → ±1 σ ↦ detσ$ where $det\left(\sigma \right)$ is the determinant of the matrix which reprepresents the permutation $\sigma$.
• The sign of a permutation $\sigma$ is the determinant $ϵ\left(\sigma \right)$ of the permutation matrix representing $\sigma$.
• A permutation $\sigma$ is even if $ϵ\left(\sigma \right)=+1$ and odd if $ϵ\left(\sigma \right)=-1.$

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$

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 whic sum to $m$, i.e. $λ1≥ λ2≥ ⋯≥ λk>0, and ∑ i=1 k λi =m.$ The elements of a partition $λ= λ1, λ2, …, λk$ are the parts of the partition $\lambda$. Sometimes we represent a partition $\lambda$ in the fom $\lambda =\left({1}^{{m}_{1}}{2}^{{m}_{2}}\cdots \right)$ if $\lambda$ has ${m}_{1}$ $1$'s, ${m}_{2}$ $2$'s and so on. We 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. 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 ${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.

Generators and relations

Definition. The simple transpositions in ${S}_{m}$ are the elements ${s}_{i}=\left(i,i+1\right),1\le i\le m-1.$

1. ${S}_{m}$ is generated by the simple transpositions ${s}_{i},$ $1\le i\le m-1.$
2. The simple transpositions ${s}_{i}$, $1\le i\le m-1$, in ${S}_{m}$ satsify the relations

Definition.

• A reduced word for $\sigma \in {S}_{m}$ is an expression $σ= si1 si2⋯ sip$ of $\sigma$ as a product of simple transpositions such that the number of factors is as small as possible.
• The length $𝓁\left(\sigma \right)$ of $\sigma$ is the number of factors in a reduced expression for the permutation $\sigma$.
• The set of inversions of $\sigma$ is the set $invσ= i,j∣ 1≤i σj .$

HW: Show that the sign $ϵ\left({s}_{i}\right)$ of a simple transposition ${s}_{i}$ in the symmetric group ${S}_{i}$ is $-1$.

Let $\sigma$ be a permutation. Let $𝓁\left(\sigma \right)$ be the length of $\sigma$ and let $inv\left(\sigma \right)$ be the set of inversions of the permutation $\sigma$. Then

1. The sign of $\sigma$ is $ϵ\left(\sigma \right)={\left(-1\right)}^{𝓁\left(\sigma \right)}.$
2. $Card\left(inv\left(\sigma \right)\right)=𝓁\left(\sigma \right).$
3. The number of crossings in the function diagram of $\sigma$ is $𝓁\left(\sigma \right).$

The symmetric group ${S}_{m}$ has a presentation by the generators ${s}_{1},{s}_{2},\dots ,{s}_{m-1}$ and relations

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)