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 $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 $$\sigma :\left[1,m\right]\to \left[1,m\right].$$ 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\times 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 $$\begin{array}{cccc}ϵ:& S_m& \to & \left\{\pm 1\right\}\\ & \sigma & \mapsto & det\left(\sigma \right)\end{array}$$ is a homomorphism from the symmetric group $S_m$ to the group ${\mu }_2=\left\{\pm 1\right\}.$

Definition.

• The sign homomorphism of the symmetric group $S_m$ is the homomorphism $$\begin{array}{cccc}ϵ:& S_m& \to & \left\{\pm 1\right\}\\ & \sigma & \mapsto & det\left(\sigma \right)\end{array}$$ 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$ $$\left(3\hspace{0.17em}6\hspace{0.17em}4\hspace{0.17em}1\hspace{0.17em}5\hspace{0.17em}2\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 6& 4& 1& 5& 2\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}3\hspace{0.17em}4\right)\left(2\hspace{0.17em}6\right)$$ $$\left(3,2,1\right)$$ $\tau$ $$\left(3\hspace{0.17em}5\hspace{0.17em}6\hspace{0.17em}2\hspace{0.17em}4\hspace{0.17em}1\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 5& 6& 2& 4& 1\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}3\hspace{0.17em}6\right)\left(2\hspace{0.17em}5\hspace{0.17em}4\right)$$ $$\left(3,3\right)$$ $\tau \sigma$ $$\left(6\hspace{0.17em}1\hspace{0.17em}2\hspace{0.17em}3\hspace{0.17em}4\hspace{0.17em}5\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 6& 1& 2& 3& 4& 5\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}6\hspace{0.17em}5\hspace{0.17em}4\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}1\right)$$ $$\left(6\right)$$ $\sigma \tau$ $$\left(4\hspace{0.17em}5\hspace{0.17em}2\hspace{0.17em}6\hspace{0.17em}1\hspace{0.17em}3\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 4& 5& 2& 6& 1& 3\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}4\hspace{0.17em}6\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}5\right)$$ $$\left(6\right)$$ ${\sigma }^{-1}$ $$\left(4\hspace{0.17em}6\hspace{0.17em}1\hspace{0.17em}3\hspace{0.17em}5\hspace{0.17em}2\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 4& 6& 1& 3& 5& 2\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}4\hspace{0.17em}3\right)\left(2\hspace{0.17em}3\right)$$ $$\left(3,2,1\right)$$ ${\tau }^{-1}$ $$\left(6\hspace{0.17em}4\hspace{0.17em}1\hspace{0.17em}5\hspace{0.17em}2\hspace{0.17em}3\right)$$ $$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 6& 4& 1& 5& 2& 3\end{array}\right)$$ $$\left(\begin{array}{cccccc}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\end{array}\right)$$ $$\left(1\hspace{0.17em}6\hspace{0.17em}3\right)\left(2\hspace{0.17em}4\hspace{0.17em}5\right)$$ $$\left(3,3\right)$$

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. $${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k>0,\text{and}\sum _{i=1}^k{\lambda }_i=m.$$ The elements of a partition $$\lambda =\left({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k\right)$$ 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 $$\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.$$
• 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, $$\begin{array}{c}\left(12345\right)\left(67\right)\left(89\right)\left(10\right),\left(51234\right)\left(67\right)\left(89\right),\left(45123\right)\left(67\right)\left(10\right),\\ \left(34512\right)\left(89\right)\left(67\right),\text{and}\left(34512\right)\left(10\right)\left(98\right)\left(67\right),\end{array}$$ all represent the same permutation in $S_{10}$, which, in two line notation, is given by $$\left(\begin{array}{cccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 2& 3& 4& 5& 1& 7& 6& 9& 8& 10\end{array}\right).$$

Example. If $\sigma$ in $S_9$ which is given, cylce notation, by $$\sigma =\left(1362\right)\left(587\right)\left(49\right)$$ and $\pi$ is the permutation in $S_9$ which is given, in $2$-line notation, by $$\left(\begin{array}{ccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9\\ 4& 6& 1& 3& 5& 9& 2& 8& 7\end{array}\right),$$ then $\pi \sigma {\pi }^{-1}$ is the permutation which is given, in cycle notation, by $$\pi \sigma {\pi }^{-1}=\left(4196\right)\left(582\right)\left(37\right)=\left(1964\right)\left(258\right)\left(37\right).$$

1. The conjugacy classes of $S_m$ are the sets $${𝒞}_{\lambda }=\left\{\text{permutations} \sigma \text{with cycle type} \lambda \right\},$$ 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 $$\left|{𝒞}_{\lambda }\right|=\frac{m!}{m_1!1^{m_1}{m}_2!2^{m_2}{m}_3!3^{m_3}\cdots }.$$

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 $${\gamma }_{\lambda }=\left(1,2,\dots ,{\lambda }_1\right)\left({\lambda }_1+1,{\lambda }_2+2,\dots ,{\lambda }_1+{\lambda }_2\right)\left({\lambda }_1+{\lambda }_2+1,\cdots \right)\cdots$$

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 $$m_1!1^{m_1}{m}_2!2^{m_2}\cdots .$$

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}45^0{6}^2\right)=\left(1^3{2}^2{3}^{3}46^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 $$\begin{array}{c}{s}_i{s}_j=s_j{s}_i,\text{if} \left|i-j\right|>1,\\ s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1},1\le i\le m-2,\\ s_i^2=1,1\le i\le m-1.\end{array}$$

Definition.

• A reduced word for $\sigma \in S_m$ is an expression $$\sigma =s_{i_1}{s}_{i_2}\cdots s_{i_p}$$ 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\left(\sigma \right)=\left\{\left(i,j\right)\mid 1\le i<j\le m,\sigma \left(i\right)>\sigma \left(j\right)\right\}.$$

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 $$\begin{array}{c}{s}_i{s}_j=s_j{s}_i,\text{if} \left|i-j\right|>1,\\ s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1},1\le i\le m-2,\\ s_i^2=1,1\le i\le m-1.\end{array}$$

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