6.2: Symmetric Groups
- Page ID
- 84821
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Definition: Symmetric Group
When \(A=\{1,2,\ldots, n\}\) (\(n\in \mathbb{Z}^+\)), we call \(S_A\) the symmetric group on \(n\) letters and denote it by \(S_n\text{.}\)
(We can, in fact, define \(S_0\text{,}\) the set of all permutations on the empty set. One can show, using the fact that a function is a relation on a Cartesian product of sets, that \(S_0\) is the trivial group. However, this will not be relevant in this text.)
Remark
Throughout this course, if we are discussing a group \(S_n\text{,}\) you should assume \(n\in \mathbb{Z}^+\text{.}\)
It is important for us to be able to easily describe specific elements of \(S_n\text{.}\) It would be cumbersome to describe, for instance, an element of \(S_3\) by saying it swaps \(1\) and \(2\) and fixes \(3\text{;}\) imagine how much more cumbersome it could be to describe an element of, say, \(S_{100}\text{!}\) One can somewhat concisely describe a permutation \(\sigma\) of \(S_n\) by listing out the elements \(1,2,\ldots,n\) and writing the element \(\sigma(i)\) below each \(i\) for \(i=1,2,\ldots, n\text{.}\) For instance, if \(\sigma\) sends \(1\) to \(2\text{,}\) we'd write the number \(2\) below the number \(1\text{.}\) The convention is to enclose these two rows of numbers in a single set of parentheses, as in the following example.
Example \(\PageIndex{1}\)
We can denote the element \(\sigma\) of \(S_3\) that swaps \(1\) and \(2\) and fixes \(3\) by
\begin{equation*} \sigma = \begin{pmatrix}1& 2& 3\\ 2& 1& 3 \end{pmatrix}, \end{equation*}
and the element \(\tau\) of \(S_3\) that sends \(1\) to \(3\text{,}\) \(2\) to \(1\text{,}\) and \(3\) to \(2\) by
\begin{equation*} \tau =\begin{pmatrix}1& 2&3\\ 3& 1& 2 \end{pmatrix}. \end{equation*}
Then
\begin{equation*} \sigma\tau = \begin{pmatrix}1& 2& 3\\ 3& 2&1 \end{pmatrix} \end{equation*}
and
\begin{equation*} \tau\sigma = \begin{pmatrix}1& 2& 3\\ 1& 3& 2 \end{pmatrix}. \end{equation*}
But even this notation is unnecessarily cumbersome. Instead, we use cycle notation.
Definition: Cycle, Cycle Notation, and Transposition
A permutation \(\sigma\) in \(S_n\) is called a \(k\)-cycle or a cycle of length \(k\) (or, less specifically, a cycle) if there exist distinct elements \(a_1, a_2,\ldots, a_k\) in \(\{1,2,\ldots,n\}\) such that
-
\(\sigma(a_i)=a_{i+1}\) for each \(i=1,2,\ldots, k-1\text{;}\)
-
\(\sigma(a_k)=a_1\text{;}\)
-
\(\sigma(x)=x\) for every other element of \(\{1,2,\ldots, n\}\text{.}\)
We use the cycle notation \(\sigma = (a_1 a_2 \cdots a_k)\) to describe such a cycle. A \(2\)-cycle is often called a transposition.
Example \(\PageIndex{2}\)
The permutation \(\tau\) in \(S_3\) that sends \(1\) to \(3\text{,}\) \(2\) to \(1\text{,}\) and \(3\) to \(2\) is a cycle. It can be denoted by \(\tau =(132)\text{.}\) Similarly, the cycle \(\rho\) in \(S_3\) swapping \(1\) and \(3\) can be denoted by \(\rho=(13)\text{.}\) On the other hand, the permutation in \(S_4\) that swaps \(1\) with \(2\) and \(3\) with \(4\) is not a cycle.
Remark
Given a \(k\)-cycle \(\sigma=(a_1 a_2\cdots a_k)\text{,}\) there are \(k\) different expressions for \(\sigma\text{.}\) Indeed, we have
\begin{equation*} \sigma=(a_1 a_2\cdots a_k)=(a_2 a_3 \cdots a_k a_1)=(a_3 a_4 \cdots a_k a_1 a_2)=\cdots = (a_k a_1 \cdots a_{k-1}). \end{equation*}
Example \(\PageIndex{3}\)
The permutation \(\tau\) described in Example \(6.2.2\) can also be written as \((321)\) and as \((213)\text{.}\)
However, by convention, we usually “start” a cycle \(\sigma\) with the smallest of the numbers that \(\sigma\) doesn't fix: e.g., we'd write \(\sigma=(213)\) as \((132)\text{.}\)
Definition: Disjoint and Mutual Disjointness
Two cycles \(\sigma=(a_1 a_2 \cdots a_k)\) and \(\tau=(b_1 b_2 \cdots b_m)\) are said to be disjoint if \(a_i \neq b_j\) for all \(i\) and \(j\text{.}\) Cycles \(\sigma_1\text{,}\) \(\sigma_2\text{,}\) \(\ldots\text{,}\) \(\sigma_m\) are disjoint if \(\sigma_i\) and \(\sigma_j\) are disjoint for each \(i \neq j\text{.}\) (Notice: this version of disjointness is what we usually refer to as mutual disjointness.)
Remark
Note that if cycles \(\sigma\) and \(\tau\) are disjoint, then \(\sigma\) and \(\tau\) commute; that is, \(\sigma \tau=\tau \sigma\text{.}\)
Note
If cycles \(\sigma\) and \(\tau\) are not disjoint then they may not commute. For instance, see Example 6.2.3, where \(\sigma\tau \neq \tau \sigma\text{.}\)
Note that any permutation of \(S_n\) is a product of disjoint cycles (where by “product” we mean the permutation resulting from permutation multiplication).
Definition: (Disjoint) Cycle Notation
Writing a permutation in (disjoint) cycle notation means writing it as a product of disjoint cycles, where each cycle is written in cycle notation.
Remark
Note that if \(\sigma\) in \(S_n\) is written in cycle notation and the number \(a\in \{1,2,\ldots, n\}\) appears nowhere in \(\sigma\)'s representation, this means that \(\sigma\) fixes \(a\text{.}\) The only permutation that we cannot really write in cycle notation is the identity element of \(S_n\text{,}\) which we henceforth denote by \(e\text{.}\)
Example \(\PageIndex{4}\)
The permutation
\begin{equation*} \sigma =\begin{pmatrix}1& 2& 3& 4& 5& 6\\ 3& 1& 2&6& 5& 4 \end{pmatrix} \end{equation*}
is the product of disjoint cycles \((132)\) and \((46)\text{,}\) so in cycle notation we have
\begin{equation*} \sigma=(132)(46). \end{equation*}
Note that we could also write \(\sigma\) as \((321)(46)\text{,}\) \((213)(64)\text{,}\) \((64)(132)\text{,}\) etc.
While it is true that we also have \(\sigma=(13)(23)(46)\text{,}\) this is not a disjoint cycle representation of \(\sigma\) since both \((13)\) and \((23)\) “move” the element \(3\text{.}\)
Example \(\PageIndex{5}\)
In \(S_4\text{,}\) let \(\sigma=(243)\) and \(\tau=(13)(24)\text{.}\) Then \(\sigma \tau=(123)\) and \(\tau \sigma = (134).\)
Example \(\PageIndex{6}\)
In \(S_9\text{,}\) let \(\sigma=(134)\text{,}\) \(\tau=(26)(17)\text{,}\) and \(\rho=(358)(12)\text{.}\) Find the following, writing your answers using disjoint cycle notation.
- \(\sigma^{-1}\)
- \(\sigma^{-1}\tau\sigma\)
- \(\sigma^2\)
- \(\sigma^3\)
- \(\rho^2\)
- \(\rho^{-2}\)
- \(\sigma \tau\)
- \(\sigma \rho\)
Example \(\PageIndex{7}\)
Explicitly express all the elements of \(S_4\) in disjoint cycle notation.
Theorem \(\PageIndex{1}\)
Any \(k\)-cycle has order \(k\) in \(S_n\text{.}\) More generally, if permutation \(\sigma\) can be written in disjoint cycle notation as \(\sigma=\sigma_1 \sigma_2 \cdots \sigma_m\text{,}\) then
\begin{align*} o(\sigma)& =\text{lcm}(o(\sigma_1), o(\sigma_2),\ldots, o(\sigma_m))\\ & =\text{lcm}(\mathrm{length}(\sigma_1),\mathrm{length}(\sigma_2),\ldots,\mathrm{length}(\sigma_m)), \end{align*}
where \(\text{lcm}\) denotes the least common multiple.
Note
Permutation \(\sigma\) must be in disjoint cycle notation for the above formula to hold. For instance, let \(\sigma=(12)(23)\) in \(S_3\text{.}\) The transpositions \((12)\) and \((23)\) both have order \(2\text{,}\) but \(o(\sigma)\neq \text{lcm}(2,2)=2\text{.}\) Rather, \(o(\sigma)=3\text{,}\) since in disjoint cycle notation \(\sigma\) can be written as \(\sigma=(123)\text{.}\) You must write a permutation using disjoint cycle notation before attempting to use this method to compute its order!
Example \(\PageIndex{8}\)
-
Find the orders of each of the elements in Example \(6.2.6\), including \(\sigma\text{,}\) \(\tau\text{,}\) and \(\rho\) themselves.
-
Explicitly list the elements of \(\langle \sigma\rangle\text{,}\) \(\langle \tau\rangle\text{,}\) and \(\langle \rho\rangle\text{.}\)