Quantum Information Methods for Many-Body Physics · Notes Sec. 2.2.1
Permutations label the symmetry that organizes every Haar average. This lesson introduces the essential properties we need, and only those: how to write and compose permutations, how they decompose into cycles, and how many of them have a given number of cycles.
A permutation is a reordering of a finite set of elements. We consider permutations of \(\{1,2,\dots,\kk\}\) and denote them by Greek letters such as \(\pi,\sigma,\tau\). The set of all permutations of \(\kk\) elements forms a group under composition, the symmetric group \(\SG_\kk\).
Given \(\sigma\in\SG_\kk\) and \(x\in\{1,\dots,\kk\}\), we write \(\sigma(x)\) for the image of \(x\). In two-line notation the first row lists the elements and the second their images:
\[ \sigma=\begin{pmatrix} 1 & 2 & \dots & \kk \\ \sigma(1) & \sigma(2) & \dots & \sigma(\kk)\end{pmatrix}. \]The group operation in \(\SG_\kk\) is the composition of permutations,
Composition is applied from right to left: \(\tau\) acts first, followed by \(\sigma\).
Take \(\sigma=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}\) and \(\tau=\begin{pmatrix}1&2&3&4\\4&2&3&1\end{pmatrix}\). To compute \(\tau\cdot\sigma\), apply \(\sigma\) first and then \(\tau\):
\[ \begin{aligned} \sigma(1)&=3,& \tau(3)&=3, & \sigma(2)&=1,& \tau(1)&=4,\\ \sigma(3)&=4,& \tau(4)&=1, & \sigma(4)&=2,& \tau(2)&=2, \end{aligned}\qquad\Longrightarrow\qquad \tau\cdot\sigma=\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}. \]For \(\kk\ge3\) the symmetric group is non-abelian: the order of composition matters, and in general \(\sigma\cdot\tau\neq\tau\cdot\sigma\).
The identity \(\iota\) leaves all elements unchanged, \(\iota\cdot\sigma=\sigma=\sigma\cdot\iota\). Every \(\sigma\in\SG_\kk\) has an inverse with \(\sigma\cdot\sigma^{-1}=\iota=\sigma^{-1}\cdot\sigma\). To compute it, apply the rule
\[ \sigma^{-1}(\sigma(i))=\iota(i)=i,\qquad i\in\{1,\dots,\kk\}. \]For \(\sigma=\begin{pmatrix}1&2&3&4&5\\3&5&1&2&4\end{pmatrix}\) we read \(\sigma(1)=3\Rightarrow\sigma^{-1}(3)=1\), \(\sigma(2)=5\Rightarrow\sigma^{-1}(5)=2\), \(\sigma(3)=1\Rightarrow\sigma^{-1}(1)=3\), \(\sigma(4)=2\Rightarrow\sigma^{-1}(2)=4\), \(\sigma(5)=4\Rightarrow\sigma^{-1}(4)=5\). Reordering by the argument,
\[ \sigma^{-1}=\begin{pmatrix}1&2&3&4&5\\3&4&1&5&2\end{pmatrix}. \]Any permutation is a product of disjoint cycles, unique up to the order in which the cycles are written. This motivates the cycle notation
\[ \sigma=(a_1\,a_2\,\dots\,a_{j_1})(a_{j_1+1}\,\dots\,a_{j_2})\cdots(a_{j_{r-1}+1}\,\dots\,a_{j_r}), \]where every element appears exactly once and \(r=\#(\sigma)\) is the number of disjoint cycles. To find the decomposition, follow the permutation until you return to the start:
For \(\tau=\begin{pmatrix}1&2&3&4&5\\4&5&3&1&2\end{pmatrix}\): starting at \(1\), \(1\mapsto4\mapsto1\) gives \((1\;4)\); the next unvisited element is \(2\), with \(2\mapsto5\mapsto2\), giving \((2\;5)\); finally \(3\mapsto3\) is a fixed point \((3)\). Hence
\[ \tau=(1\;4)(2\;5)(3)=(2\;5)(1\;4)(3)=(3)(1\;4)(2\;5). \]When \(\kk\) is clear from the context, 1-cycles (fixed points) are usually omitted, \(\tau=(1\;4)(2\;5)\), and the identity is written \(\iota=()\), shorthand for \((1)(2)\cdots(\kk)\).
For \(\tau=\begin{pmatrix}1&2&3&4&5&6\\5&4&1&6&3&2\end{pmatrix}\) and \(\sigma=\begin{pmatrix}1&2&3&4&5&6\\5&2&6&4&1&3\end{pmatrix}\) one finds \(\tau=(1\;5\;3)(2\;4\;6)\) and \(\sigma=(1\;5)(3\;6)\), shorthand for \((1\;5)(3\;6)(2)(4)\). Thus \(\lambda(\tau)=(3,3)\) and \(\lambda(\sigma)=(2,2,1,1)\).
Transpositions (swaps) exchange exactly two elements and leave all others unchanged:
\[ (i\;j)=\begin{pmatrix} 1 & \dots & i & \dots & j & \dots & \kk \\ 1 & \dots & j & \dots & i & \dots & \kk\end{pmatrix}. \]Any permutation can be written as a product of transpositions, but, unlike the decomposition into disjoint cycles, not uniquely. This makes transpositions unsuitable for labeling permutations, yet very useful in algebraic manipulations. The number of transpositions in any representation is always odd or always even, which defines the sign
The sign is central in the construction of representations of \(\SG_\kk\) and in multilinear algebra, in particular in the definition of the determinant.
The group \(\SG_\kk\) embeds into \(\SG_{\kk+1}\): every permutation of \(\kk\) elements is a permutation of \(\kk+1\) elements that fixes the last one. More precisely,
\[ \SG_{\kk+1}=\SG_\kk\sqcup\big\{(j\;\,\kk{+}1)\cdot\sigma\;:\;\sigma\in\SG_\kk,\ j=1,\dots,\kk\big\}, \]a disjoint union whose second part composes an element of \(\SG_\kk\) with a transposition that swaps \(\kk+1\) with one of the first \(\kk\) elements. This recursive structure proves many properties by induction on \(\kk\).
Proof. For \(\kk=1\), \(\SG_1=\{\iota\}\), so \(|\SG_1|=1=1!\). Assume \(|\SG_\kk|=\kk!\). In the decomposition above there are \(\kk\) choices of \(j\) and \(\kk!\) choices of \(\sigma\), so \(|\SG_{\kk+1}|=\kk!+\kk\cdot\kk!=(\kk+1)\,\kk!=(\kk+1)!\). □
The permutations \(\sigma_1=(1\;2\;3)(5\;6)\), \(\sigma_2=(2\;4\;6\;1)\) and \(\sigma_3=(1\;2)(3\;4)(5\;6)\) of six elements have different cycle structures but all exactly three cycles: counting cycles is a coarser classification than the cycle structure. In many computations of this course we need the number of permutations in \(\SG_\kk\) with a fixed number of cycles \(r=\#(\sigma)\): the unsigned Stirling numbers of the first kind \(c(\kk,r)\), which satisfy
They form a triangle analogous to Pascal's:
| \(\kk\backslash r\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | 1 | |||
| 3 | 2 | 3 | 1 | ||
| 4 | 6 | 11 | 6 | 1 | |
| 5 | 24 | 50 | 35 | 10 | 1 |
PracticeQuBite units 1–3 drill two-line notation, composition, cycles, sign, Stirling numbers and conjugation, with fresh exercises every time.
Practice on QuBite