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

Let $m\in {\mathbb{Z}}_{>0}$.

• A permutation of $m$ is a bijective function $\sigma :\{1,2,\dots ,m\}\to \{1,2,\dots ,m\}$
• 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=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 4& 1& 6& 2& 5& 3\end{array}\right).$$
2. Cycle notation: Where $(i_1,i_2,\dots ,i_r)$ indicates $w\left(i_1\right)=i_2, w\left(i_2\right)=i_3, \dots , w\left(i_{r-1}\right)=i_r, w\left(i_r\right)=i_1.$ Cycles of length 1 are usually dropped from the notation. $$w=\left(142\right)\left(36\right)\left(5\right)=\left(142\right)\left(36\right).$$
3. Matrix notation: where the $w\left(i\right)$th entry of the $ith$ column is 1 and all other entries are 0. $$w=\left(\begin{array}{cccccc}0& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 0\end{array}\right).$$
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=\begin{array}{c} \end{array}.$$

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

Generators and relations

• The transpositions in $S_m$ are the permutations $s_{ij}=(i,j)$, in cycle notation, for $i,j\in \{1,\dots ,m\}$ with $i<j$. $$\text{PICTURE OF A TRANSPOSITION}$$
• The simple transpositions are $$s_i=(i,i+1)=\begin{array}{c} i i+1 ⋯ ⋯ \end{array},\text{for}i\in \{1,\dots ,m-1\}.$$
• A reduced word for $\sigma \in S_m$ is an expression of $\sigma$ as a product of simple transpositions $$\sigma =s_{i_1}{s}_{i_2}\cdots s_{i_{\ell }}\text{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 $$\begin{array}{cc}{s}_i^2=1,& \text{for}i\in \{1,\dots m-1\}\hfill \\ s_i{s}_j=s_j{s}_i,& \text{if}j\ne i,i\pm 1,\text{and}\hfill \\ s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1},& \text{for}i\in \{1,\dots m-2\}\hfill \end{array}$$

		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=(i,i+1),$ for $1\le i\le m-2$, satisfy the given relations. $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$ $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$ $$\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}$$ 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=\begin{array}{c} \end{array}=\begin{array}{c} \end{array}=s_1{s}_3{s}_5{s}_4{s}_5{s}_3.$$ 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=w_1{s}_{m-1}{w}_2{s}_{m-1}{w}_3{s}_{m-1}\cdots w_{l-1}{s}_{m-1}{w}_l,\text{where}{w}_j\in G_{m-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 $$\begin{array}{rcl}w& =& w_1{s}_{n-1}{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{w}_2{s}_{n-1}{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l,\end{array}$$ and in the second case $$\begin{array}{rcl}w& =& w_1{s}_{n-1}{w}_2{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1{s}_{n-1}a{s}_{n-2}b{s}_{n-1}{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_{1}a{s}_{n-1}{s}_{n-2}{s}_{n-1}b{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_{1}a{s}_{n-2}{s}_{n-1}{s}_{n-2}b{w}_3{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\\ & =& w_1^{\prime }{s}_{n-1}{w}_3^{\prime }{s}_{n-1}\cdots w_{l-1}{s}_{n-1}{w}_l\end{array}$$ 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=w_1{s}_{m-1}a{s}_{m-2}\cdots s_l=w_{1}a{s}_{m-1}\cdots s_l=w_1^{\prime }{s}_{n-1}\cdots s_l,$$ 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 $$\mathrm{inv}\left(\sigma \right)=\left\{\right(i,j\left)\right|i,j\in \{1,\dots ,m\},i<j\text{and}\sigma \left(i\right)>\sigma \left(j\right)\}.$$
• The length of $\sigma$ is $\ell \left(\sigma \right)=\mathrm{Card}\left(\mathrm{inv}\right(\sigma \left)\right)$
• The sign of $\sigma$ is $\det \left(\sigma \right)={\left(-1\right)}^{𝓁\left(\sigma \right)}$.
• The permutation $\sigma$ is even if $\det \left(\sigma \right)=1$ and odd if $\det \left(\sigma \right)=-1$.

A pair $(i,j)$ 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 $\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 $\det \left(\sigma \right)$ denote the sign of the permutation $\sigma$. The function $$\begin{array}{cccc}\det :& S_m& \to & \{\pm 1\}\\ & \sigma & \mapsto & det\left(\sigma \right)\end{array}\text{<em>is a group homomorphism.</em>}$$

Conjugacy classes

Definition.

• A partition $\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)$ of $m$ is a weakly decreasing sequence of positive integers which sum to $m$, i.e. $${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k>0\text{and}{\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k=m.$$ The elements of a partition $$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)$$ are the parts of the partition $\lambda$. Sometimes a partition $\lambda$ is represented in the form $\lambda =(1^{m_1}{2}^{m_2}\cdots )$ 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 $(i_1,i_2,\dots ,i_k)$ 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. In 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.

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 \right(1\left)\sigma \right(2)\dots \sigma (m\left)\right)$.
3. As an $m\times m$ matrix which has the ${\left(\sigma \right(i),i)}^{th}$ entry equal to $1$ for $i\in \{1,\dots ,m\}$ 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 $(i_1,i_2,\dots ,i_k)$ 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$ $$\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)$$

HW: Show that the order of the symmetric group $S_m$ is $m!=m(m-1)(m-2)\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)

page history