Skip to main content
Mathematics LibreTexts

3.1: Symmetric Groups

  • Page ID
    131846
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\dsum}{\displaystyle\sum\limits} \)

    \( \newcommand{\dint}{\displaystyle\int\limits} \)

    \( \newcommand{\dlim}{\displaystyle\lim\limits} \)

    \( \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{\longvect}{\overrightarrow}\)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\ket}[1]{\left| #1 \right>}\)
    \(\newcommand{\bra}[1]{\left< #1 \right|}\)
    \(\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}\)
    \(\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}\)
    \(\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}\)
    \(\newcommand{\op}[1]{\hat{\mathbf{#1}}}\)
    \(\newcommand{\expect}[1]{\langle #1 \rangle}\)
    \(\newcommand{\dfn}[1]{\emph{\textbf{#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

    Let \(n \geq 1\) be an integer and  let \(X=\{1,\ldots,n\}\). The symmetric group \(S_n\) is the group of all bijections from \(X\) to itself (permutations), under composition. Note that there are \(n!\) permutations. The operation \(\star : = \) composition of bijections.  Note that it is right-to-left. The composition of two bijections is a bijection; hence \(S_n\) is closed under composition.

    Screen Shot 2023-07-04 at 5.47.23 AM.png
    Figure \(\PageIndex{1}\): composition of bijections. (Copyright: Pamini Thangarajah)

    Thus, the symmetric group \(S_n\) is a finite group of order \(n!\) and a permutation group consisting of all possible permutations of \(n\) objects.

    The identity permutation is denoted as \(e\).

    We will denote a permutation by \(\sigma = \begin{bmatrix} 1 & 2& 3& \cdots & n\\
    \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n) \end{bmatrix} \in S_n.\) This is called two-row notation.

     

    Caution

    Permutation products are evaluated from right to left.
    Thus, in \( \sigma\tau, \) the permutation \(\tau\) is applied first and then \(\sigma\).

    Screenshot 2026-10-31 at 5.22.36 PM.png

     

    Example \(\PageIndex{1}\)

    Let \(\sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    2 & 4 & 3 & 5 & 1 \end{bmatrix} \in S_5\) and \( \gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    5 & 4 & 1 & 2 & 3 \end{bmatrix} \in S_5 \).

    We now calculate \(\gamma \circ \sigma\).

    Screen Shot 2023-07-04 at 5.45.01 AM.png

    Figure \(\PageIndex{2}\): \(\gamma \circ \sigma\). (Copyright; Pamini Thangarajah via Google draw)

    Figure \(\PageIndex{2}\) illustrates the process of moving from one function to another. 

    \((\gamma \circ \sigma)(1)=\gamma (\sigma(1))= \gamma(2)=4.\)

    Completing the process, we obtain the following: 

    Consider \(\gamma \circ \sigma = \gamma \sigma =\) \(\begin{bmatrix} 1 & 2& 3& 4 & 5\\
    5 & 4 & 1 & 2 & 3 \end{bmatrix}  \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    2 & 4 & 3 & 5 & 1 \end{bmatrix}= \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    4 & 2 & 1 & 3 & 5 \end{bmatrix} .\)

    Note that if we switch the order of the functions, we obtain: \(\sigma \gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    1 & 5 & 2 & 4 & 3 \end{bmatrix}\).

    Note that \(\sigma \gamma \ne \gamma \sigma\).  To prove it is not abelian, we need only show that for at least one element, \(k\), \(\sigma \gamma(k) \ne \gamma \sigma(k)\).

    Note

    The inverse of a permutation \(\sigma\) is the inverse of the function \(\sigma\), and it is denoted by  \(\sigma^{-1}\).

    Thus,  \(\sigma^{-1} \sigma=\sigma \sigma^{-1}=e.\)

    Example \(\PageIndex{2}\)

    Let \(\sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    2 & 4 & 3 & 5 & 1 \end{bmatrix} \in S_5\). Then   \(\sigma^{-1} = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    5 & 1 & 3 & 2 & 4 \end{bmatrix} \in S_5\).

    Cycle Notation

    Cycle notation is a simple, straightforward way to represent permutations in the symmetric group.

    Definition: Cycle
     

    Let \(a_1, a_2,\ldots, a_k\) be pairwise distinct elements of \(\{1,2,\ldots,n\}\), where \(k\ge 2\). The \(k\)-cycle
    \(
    \gamma=(a_1\,a_2\,\cdots\,a_k)
    \)
    is the permutation in \(S_n\) defined by \(
    \gamma(a_i)=a_{i+1}\quad(1\le i<k),
    \qquad \gamma(a_k)=a_1, \) and \(\gamma(x)=x\) for every element \(x\) not appearing in the cycle.


    A fixed point may be represented as a \(1\)-cycle \((a)\); such cycles are usually omitted when writing permutations in disjoint-cycle notation.

     clipboard_e90a3b1fc8bea88a5a08987246ea06870.png

    For example:

    Example \(\PageIndex{3}\)

    Let \(\gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    5 & 4 & 1 & 2 & 3 \end{bmatrix}=(1,5,3)(2,4)\).

    clipboard_ecf749fadb65f4c655fde26b4c0d8766f.png
    Figure \(\PageIndex{3}\): \(\gamma\). (Copyright: Pamini Thangarajah)
    \((1,5,3)\) can be read as 1 goes to 5, 5 goes to 3, and 3 goes back to 1, and is called a cycle of  \(\gamma\) of length \(3\). Then 2 goes to 4, and then 4 goes back to 2, and \((2,4)\) is called a cycle of  \(\gamma\) of length \(2\).
    Note
    •  \((1, 2, 4, 5)\) means that 1 goes to 2, 2 goes to 4, 4 goes to 5, and 5 goes to 1.  Note that 3 is not included, so 3 goes to 3. 
    • The identity may be written as \((1)(2)\cdots(n)\), but it is normally denoted by \(e\), and one-cycles are omitted.
    • The cycles are always listed in a logical and clear order. Although disjoint cycles may be written in any order, we generally list them in increasing order of their smallest elements.
    • If the permutation fixes an element (i.e., it remains unchanged), it is often omitted from the cycle notation.
    Definition: disjoint cycles

    Disjoint cycles mean that the elements involved in one cycle are distinct from those in another. 

    Two cycles in \(S_n\), \(\gamma=(a_1,\ldots,a_k)\) and \(\sigma=(b_1,\ldots,b_l)\) are disjoint if \(a_i \ne b_j, \; \forall i,j\).

    Note that the cycle lengths need not match. 

    Example:  \((1, 2)\) and \((3, 4)\) are disjoint, but \((1, 2, 3)\) and \((3, 4)\) are not disjoint.

    Note

    For consistency, we will usually list disjoint cycles in a fixed order. The order of disjoint cycles does not affect the permutation.

    Example \(\PageIndex{4}\)

    Let \( \sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5& 6 & 7 & 8 & 9 &10 &11&12\\
    12 & 2 & 3 & 1 & 11 & 9 & 5 &10 & 6 &4& 7 & 8 \end{bmatrix} .\)

    Then, a cycle decomposition of  \( \sigma = (1, 12, 8, 10, 4) (2)(3)(5,11,7)(6,9)= (1, 12, 8, 10, 4) (5,11,7)(6,9) \).

    These are disjoint cycles; therefore, they commute.

    Theorem \(\PageIndex{1}\)

    1. Disjoint cycles commute. Let \(\gamma\) and \(\sigma\) be disjoint cycles, then \(\gamma \sigma = \sigma \gamma\).

    2. Every permutation of a finite set can be written as a cycle or a product of disjoint cycles. The disjoint-cycle decomposition is unique up to the order of the disjoint cycles and cyclic rotation of the entries within each cycle, when fixed points are included.

    The inverse of a cycle:

    Theorem \(\PageIndex{2}\)

    \((a_1, a_2, \cdots, a_k)^{-1}= (a_k, a_{k-1}, \cdots, a_1)\).

    Example \(\PageIndex{5}\)

    \( (1,2,3)^{-1} = (3,2,1) \), and \((1,2)^{-1}=(2,1)=(1,2).\) 

    Let \( \sigma = \begin{bmatrix} 1 & 2& 3& 4 & 5& 6 & 7 & 8 & 9 &10 &11&12\\
    12 & 2 & 3 & 1 & 11 & 9 & 5 &10 & 6 &4& 7 & 8 \end{bmatrix} = (1, 12, 8, 10, 4) (5,11,7)(6,9). \)

    To find the inverse in a cycle decomposition, reverse the order of the cycles and find the inverse of each cycle. Hence, 

     \( \sigma^{-1} =(6,9)^{-1}(5, 11, 7)^{-1} (1, 12, 8, 10, 4)^{-1}=(9,6)(7, 11, 5) (4, 10, 8, 12, 1)  .\)

    Note that disjoint cycles are commutative!

    Inverse of a Product of Disjoint Cycles

    For any product of permutations, the inverse is obtained by taking the inverse of each factor and reversing the order of the factors. In particular,
    \(
    \boxed{(\sigma\tau)^{-1}=\tau^{-1}\sigma^{-1}.}
    \)

    However, disjoint cycles commute, so their order does not affect the resulting permutation. Therefore, when finding the inverse of a product of disjoint cycles,
    we may simply reverse the direction of each cycle without changing the order in which the cycles are written.

    Example \(\PageIndex{6}\)

    Find the inverse of
    \(
    \sigma=(1\,2\,3)(4\,5).
    \)

    Answer
    Applying the inverse-of-a-product rule, we obtain
    \(
    \begin{aligned}
    \sigma^{-1}
    &=\bigl((1\,2\,3)(4\,5)\bigr)^{-1}\\
    &=(4\,5)^{-1}(1\,2\,3)^{-1}\\
    &=(4\,5)(1\,3\,2)\\
    &=(1\,3\,2)(4\,5).
    \end{aligned}
    \)

    The last equality holds because the two cycles are disjoint and hence commute.

    Note

    Reversing the order of factors is required when taking the inverse of a general product. However, disjoint cycles may be rearranged freely because they commute.

    \(
    \boxed{
    \begin{gathered}
    \text{To invert a product of disjoint cycles,}\\
    \text{reverse the direction of each cycle.}
    \end{gathered}
    }
    \)

    Caution: Products of overlapping cycles

    \((2,3)(1,2) = (1,3,2) =(3,2,1)=(2,1,3).\) Note:  \(1\mapsto 2\) under \((1,2)\), then \(2 \mapsto 3\) under \((2,3)\), so the product sends \(1 \mapsto 3\).

    \((1,2)(2,3)= (1,2,3)=(2,3,1)=(3,1,2).\) Note: Since 1 is not in the inner function, it stays 1 and then goes to 2.

    \(((2,3)(1,2))^{-1}=(1,2)^{-1}(2,3)^{-1}=(1,2)(2,3)=(1,2,3) \ne (2,3)(1,2).\)

    Type of a permutation (cycle structure of a permutation)

    The type of a permutation (or cycle structure of a permutation) is the integer partition formed from the cycle lengths in decreasing order. We will denote it by

    \(\operatorname{type}(\sigma \)), where \(\sigma \) is a permutation in \(S_n\).

    Example \(\PageIndex{7}\)

    1. Let \(\gamma = \begin{bmatrix} 1 & 2& 3& 4 & 5\\
    5 & 4 & 1 & 2 & 3 \end{bmatrix}=(1,5,3)(2,4) \in S_5\).

    The type of \(\gamma\) is, \( \operatorname{type}(\gamma)=\)3 2.

     

    Example \(\PageIndex{8}\)

    Let \(\sigma = \begin{bmatrix} 1 & 2& 3& 4 \\
     4 & 1 & 2 & 3 \end{bmatrix}=(1,4,3,2) \in S_4\).

    The type \( \sigma\) is,  \( \operatorname{type}(\sigma)=\)4.

    Note

    A partition of a positive integer \(n\) is a sum of positive integers \(n=k_1+\cdots+k_s, k_i \in \mathbb{N} \), for \( i= 1, \cdots, s\), where the order of the summands does not matter. For example:  the partitions of \(6\) are \(6, 5+1, 4+2, 4+1+1 , 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1.\)

    Example \(\PageIndex{9}\)

    How many permutations in \(S_6\) have type 321?

    Type \((321)\) permutation is of the form \(( , , )( , )( ) \). There are \(6!\) ways of filling the blanks. Note that each cycle can be restarted anywhere.

    Hence, the number of permutations in \(S_6\) have type (321) is \(\dfrac{6!}{(3)(2)(1)}.\)

    Example \(\PageIndex{10}\)

    How many permutations in \(S_6\) have  \(3\) cycles of length \(2\)?

    The  permutation is of the form \( ( , )( , )( , ) \). There are \(6!\) ways of filling the blanks.  Since each cycle has two representations matching this format (by restarting at any two places), we divide by \(2^3\).

    The three disjoint 2-cycles can be written in \(3!\) different orders, all representing the same permutation.  Divide by \(3!\), the number of ways to reorder the cycles.

    Hence, the number of permutations in \(S_6\) have  \(3\) cycles of length \(2\) is \(\dfrac{6!}{(2^3)(3!)}.\)

    Theorem \(\PageIndex{3}\)

    Let \(\sigma \in S_n \) and let  \(m_i\) cycles of length \(i\), in its disjoint-cycle decomposition, counting fixed points as \(1\)-cycles,  for  \(i=1, \cdots, k\). Then
    \(
     \sum_{i=1}^{n} i\,m_i=m_1+2m_2+\cdots+(k-1)m_{(k-1)}+ km_k =n.
    \)

    The number of permutations with this cycle type is

    \(
     \boxed{\displaystyle \frac{n!}{\prod_{i=1}^{n} i^{m_i}m_i!}= \dfrac{n!}{1^{m_1}2^{m_2}\cdots k^{m_k} {m_1}! m_2! \cdots m_k!}.}
    \) 

    For  \(i=1, \cdots, k\), the division by \(i^{m_i}\) accounts for the \(i\) possible starting points of each \(i\)-cycle, while division by \(m_i!\) accounts for permutations among cycles of equal length.

    Example \(\PageIndex{11}\)

     \(|S_3|=3!=2\cdot 3=6\).

    Table \(\PageIndex{1}\): Cycle type for \(S_3\)
    Cycle type

    111

     21

    3

    Number of permutations

    \(\dfrac{3!}{1^3 3!}=1\)

    \(\dfrac{3!}{1^1 2^1 1!1!}=3\)

    \(\dfrac{3!}{ 3^1 1!1!}=2\)

    Notation: 

             \(e \equiv \begin{pmatrix}
    1 & 2 & 3\\
    1 & 2 & 3
    \end{pmatrix}\) the identity permutation.

       \((1,2) \equiv \begin{pmatrix}
    1 & 2 & 3\\
    2 & 1 & 3
    \end{pmatrix}\).  Note that 3 maps to itself.

    \((1,2,3) \equiv \begin{pmatrix}
    1 & 2 & 3\\
    2 & 3 & 1
    \end{pmatrix}\).

    \((1,3,2) \equiv \begin{pmatrix}
    1 & 2 & 3\\
    3 & 1 & 2
    \end{pmatrix}\).

    Hence, \(S_3= \{e,(1,2),(1,3), (2,3), (1,2,3),(1,3,2)\}\).    In the following Cayley table, the entry in row \(\sigma\) and column \(\tau\) is \(\sigma\tau\), with \(\tau\) applied first.

     

    Table \(\PageIndex{2}\): Cayley table for \(S_3\)

     

     

    e

    (1,2,3)

    (1,3)

    (1,2)

    (2,3)

    (1,3,2)

    e

    e

    (1,2,3)

    (1,3)

    (1,2)

    (2,3)

    (1,3,2)

    (1,2,3)

    (1,2,3)

    (1,3,2)

    (2,3)

    (1,3)

    (1,2)

    e

    (1,3)

    (1,3)

    (1,2)

    e

    (1,2,3)

    (1,3,2)

    (2,3)

    (1,2)

    (1,2)

    (2,3)

    (1,3,2)

    e

    (1,2,3)

    (1,3)

    (2,3)

    (2,3)

    (1,3)

    (1,2,3)

    (1,3,2)

    e

    (1,2)

    (1,3,2)

    (1,3,2)

    e

    (1,2)

    (2,3)

    (1,3)

    (1,2,3)

     

    Example \(\PageIndex{12}\)

    Let's explore \(S_4\). Note \(S_4\) has  \(4!=24\) elements.

     
    Table \(\PageIndex{3}\): Cycle type for \(S_4\)
     Cycle type

     1111

    211

    22

    31

    4

     

    Number of permutations

    \(\dfrac{4!}{1^4 4!}=1\)

    \(\dfrac{4!}{1^2 2^1 2!1!}=6\)

    \(\dfrac{4!}{ 2^2 2!}=3\)

    \(\dfrac{4!}{1^1 3^1 1!1!}=8\)

    \(\dfrac{4!}{4^1  1!}=6\)

     

    Hence, \(
    S_4 = \left\{ 
    \begin{array}{l}
    e, \\
    (12), (13), (14), (23), (24), (34), 
    (12)(34), (13)(24), (14)(23), \\
    (123), (132), (142), (124), (134), (143), (234), (243), \\
    (1234), (1243), (1324), (1342), (1423), (1432)
    \end{array} 
    \right\}.
    \)

    Note

    \(
     S_3\cong\{\sigma\in S_4:\sigma(4)=4\}\leq S_4.
    \)

     

    The following theorem shows that \(S_n\) is non-Abelian for \(n \ge 3\), meaning the order of composition matters. 

    Theorem \(\PageIndex{4}\)

    \(S_n\) is non-Abelian for all integers \(n \ge 3\).

    Proof

    Let \(n \ge 3\). We will show that there exists  \(a, b \in S_n, s.t.  ab \ne ba \), \(n \ge 3\).

    Choose \(a=(1,2)\) and \(b=(1,3)\) regarded as elements of \(S_n\) fixing \(4,\ldots,n\).

    Consider \(ab=(1,2)(1,3)=(1,3,2)\) and \(ba=(1,3)(1,2)=(1,2,3)\).

    Since \((1,3,2) \ne (1,2,3)\), \(ab\ne ba \). Thus \(S_n\) is non-abelian for \(n\ge 3\). \(\square\)

     

    Example \(\PageIndex{13}\)

    Given \(\alpha, \beta \in S_4\) with \(\alpha \beta =(1,4,3,2), \; \beta \alpha = (1,2,4,3)\), and \(\alpha(1)=4\),

    Screen Shot 2023-07-04 at 6.19.05 AM.pngdetermine \(\alpha\) and \(\beta\).

    Solution:

    Since \(\alpha(1)=4\) and \(\beta \alpha(1)=2\), implies \(\beta(4)=2\).

    Since \(\beta(4)=2\) and \(\alpha \beta(4)=3\), implies \(\alpha(2)=3\).

    Since \(\alpha(2)=3\) and \(\beta \alpha(2)=4\), implies \(\beta(3)=4\).

    Since \(\beta(3)=4\) and \(\alpha \beta(3)=2\), implies \(\alpha(4)=2\).

    Since \(\alpha(4)=2\) and \(\beta \alpha(4)=3\), implies \(\beta(2)=3\).

    Since \(\beta(2)=3\) and \(\alpha \beta(2)=1\), implies \(\alpha(3)=1\).

    Since \(\alpha(3)=1\) and \(\beta \alpha(3)=1\), implies \(\beta(1)=1\).

    \(\alpha=(1,4,2,3)\) and \(\beta=(2,3,4)\).

    Then \(\beta \alpha =(2,3,4)(1,4,2,3)=(2,4,3,1)=(1,2,4,3)\).

    And \(\alpha \beta =(1,4,2,3)(2,3,4)=(4,3,2,1)=(1,4,3,2)\).

    Figure \(\PageIndex{4}\): Thinking out Loud (Copyright: Pamini Thangarajah)

     

     

    Note that every permutation of a finite set can be written as a cycle or a product of disjoint cycles.

    2-Cycles (Transpositions)

     

    Definition: Transposition

    A transposition in \(S_n\) is a 2-cycle \((i,j)\) with \(1\leq i<j\leq n.\)

    It exchanges \(i\) and \(j\) and fixes all other elements. Also, \((i,j)^{-1}=(i,j)\).

     

    Example \(\PageIndex{14}\)

    \((1, 3, 2) = (1, 2) (1, 3).\)  (Why? Let's check!)

    Using the convention that the rightmost permutation acts first, consider \(\alpha=(1\,2)(1\,3)\). Then
    \(
    1\xmapsto{(1\,3)}3\xmapsto{(1\,2)}3,\qquad
    3\xmapsto{(1\,3)}1\xmapsto{(1\,2)}2,\qquad
    2\xmapsto{(1\,3)}2\xmapsto{(1\,2)}1.
    \)
    Therefore
    \(
    \boxed{(1\,2)(1\,3)=(1\,3\,2).}
    \)

    Hence,

    \((1, 2, 3) = (1, 3) (1, 2).\)

    \((2, 4, 1, 3, 5) = (2, 5) (2, 3) (2, 1) (2, 4).\)

    Note: Every cycle of length \(k \ge 2\) can be expressed as a product of \(k-1\) transpositions.

    Theorem \(\PageIndex{5}\)

    For \(k\geq 2\), a \(k-\)cycle  \((a_1, a_2,\ldots, a_k)\) can be decomposed into \(
     (a_1,a_2,\ldots,a_k)
     = (a_1, a_k)(a_1, a_{k-1})\cdots(a_1, a_2),
    \) which contains exactly \(k-1\) transpositions.

    For \(\sigma\in S_n\), define

    \(
    \operatorname{inv}(\sigma)=\#\{(i,j):1\le i<j\le n,\ \sigma(i)>\sigma(j)\}.
    \)

    Composing on the right with an adjacent transposition \(s_i=(i,i+1)\) interchanges two adjacent values in the two-row or one-line notation. Thus \(\operatorname{inv}(\sigma s_i)\) differs from \(\operatorname{inv}(\sigma)\) by exactly \(1\) or \(-1\). For \(i<j\) the transposition \((i,j)\) is a product of \(2(j-i)-1\) adjacent transpositions:
    \(
    (i,j)=s_i s_{i+1}\cdots s_{j-1}s_{j-2}\cdots s_i.
    \)


    Since this number is odd, composition with any transposition reverses inversion parity. If \(\sigma=\tau_1\cdots\tau_r\) is any product of transpositions, then, starting from \(\operatorname{inv}(e)=0\),
    \(
    \boxed{\operatorname{inv}(\sigma)\equiv r\pmod 2.}
    \)


    Therefore, every transposition factorization of \(\sigma\) has the same parity. This establishes that the definitions of even and odd permutations are unambiguous.

    Theorem \(\PageIndex{6}\)

    Every permutation in \(S_n\) can be expressed as a product of 2-cycles (Transpositions). The number of transpositions will always be either even or odd.

    That is, if a permutation \(\sigma\) can be expressed as a product of an even number of 2-cycles, then every decomposition of \(\sigma\) into 2-cycles has an even number of 2-cycles.  A similar statement holds for odd.

     

    Parity of Cycles

    For \(k\geq 2\), a  \(k\)-cycle can be written as \(k-1\) transpositions:
    \(
    (a_1,a_2,\cdots, a_k)
    =
    (a_1,a_k)(a_1,a_{k-1})\cdots(a_1,a_2).
    \)

    Therefore, a \(k\)-cycle is even if and only if \(k-1\) is even.
    Hence: 
    \begin{array}{c|c|c}
    \text{Length }k & k-1\text{ transpositions} & \text{Parity}\\ \hline
    k\text{ odd} & \text{even} & \text{even}\\
    k\text{ even} & \text{odd} & \text{odd}
    \end{array}

     

    Permutation Parity 

    Definition: Parity

    Let \(\sigma \in S_n\).  (i.e., a permutation)

    Then \(\sigma\) is an even permutation if \(\sigma\) can be expressed as a product of an even number of two-cycles (transpositions); otherwise, it is odd.

    The sign (or signature) of \(\sigma\) defined as: \(\text{sgn}(\sigma) = (-1)^k\), where \(k\) is the number of transpositions in any decomposition of \(\sigma = \tau_1 \tau_2 \cdots \tau_k\).

    Equivalently:

    \(\boxed{\text{sgn}(\sigma) = \begin{cases} +1 & \text{if } \sigma \text{ is an even permutation} \\ -1 & \text{if } \sigma \text{ is an odd permutation} \end{cases}}.\)

     

    Theorem \(\PageIndex{7}\)

    1. A cycle of even length is odd.

    2. A cycle of odd length is even.

     

    Example \(\PageIndex{15}\)

    1. let’s explore \(S_4\). Note \(S_4\) has  \(4!=24\) elements.

    \(
    S_4 = \left\{ 
    \begin{array}{l}
    e, \\
    (12), (13), (14), (23), (24), (34), \\
    (12)(34), (13)(24), (14)(23), \\
    (123), (132), (142), (124), (134), (143), (234), (243), \\
    (1234), (1243), (1324), (1342), (1423), (1432)
    \end{array} 
    \right\}.
    \)

    2. Find the center of \(S_4\).

    Since all symmetric groups, \(S_n\),  \(n \ge 3\), are non-abelian, the center of \(S_4\) is trivial, being the identity e, or (1)(2)(3)(4). (What do you think of this proof? Is this a valid argument?) No. Non-abelian means that some two elements fail to commute; it does not imply that the identity is the only element commuting with every group element. The conclusion \(Z(S_4)=\{e\}\) is true but requires a separate proof, as supplied by Theorem 8.

    Alternatively, proof by exhaustion:  Having tried all \(x \in S_4\), the only \( x \in S_4\) that satisfies \(xg=gx, \; \forall g \in S_4\) is the identity.

    Method II: direct proof
    Suppose \(z\in Z(S_4)\). For any distinct \(i,j\in\{1,2,3,4\}\),
    \(
    z(i\,j)z^{-1}=(z(i)\,z(j))=(i\,j).
    \)
    Hence \(\{z(i),z(j)\}=\{i,j\}\). Fix \(i\), and choose distinct \(j,k\) different from \(i\). The equalities for the pairs \(\{i,j\}\) and \(\{i,k\}\) imply
    \(
    z(i)\in\{i,j\}\cap\{i,k\}=\{i\}.
    \)
    Therefore \(z(i)=i\) for every \(i= 1,2,3,4\), so \(z=e\).

    3. Find a cyclic subgroup of \(S_4\) that has an order of 4.  

    Consider the \(4\)-cycle \(\sigma=(1\,2\,3\,4)\).
    Since \(\operatorname{ord}(\sigma)=4\), the subgroup generated by \(\sigma\) is
    \(
    \boxed{
    \langle\sigma\rangle
    =\{e,(1\,2\,3\,4),(1\,3)(2\,4),(1\,4\,3\,2)\}.
    }
    \)
    There are actually three distinct cyclic subgroups of \(S_4\) of order \(4\):
    \(
    \langle(1\,2\,3\,4)\rangle,\qquad
    \langle(1\,2\,4\,3)\rangle,\qquad
    \langle(1\,3\,2\,4)\rangle.
    \)
    Indeed, \(S_4\) has \(6\) distinct \(4\)-cycles, and each cyclic subgroup of order \(4\) has exactly \(2\) generators, namely a \(4\)-cycle and its inverse.
    Thus there are \(\dfrac{6}{2}=3\) such subgroups.

    4. Find a non-cyclic subgroup of \(S_4\) that has order 4.

    The identity together with the three products of two disjoint transpositions forms a non-cyclic subgroup of order \(4\):
    \(
    V_4=\{e,(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\}.
    \)  The product of any two distinct nonidentity elements is the third nonidentity element, and each nonidentity element has order \(2\).
    Consequently, \(V_4\) is a subgroup of order \(4\) but not cyclic: a cyclic group of order \(4\) must contain an element of order \(4 \).
    In fact, \(V_4\cong \mathbb{Z}_2\times \mathbb{Z}_2\).

    Theorem \(\PageIndex{8}\)

    For each integer \(n\geq 3\), the center of \(S_n, Z(S_n)=\{e\}.\)

    Proof

    Proof by contradiction

    Assume that \(\gamma (\ne e) \in Z(S_n).\)  We shall find an \(\alpha \in S_n\) such that \(\gamma \alpha \ne \alpha \gamma.\)

    Since \(\gamma (\ne e)\), there exist \(l,m \in \{1,2,3,\cdots, n\}\) such that  \(\gamma (l) =m \ne l.\)  Since \(n\geq3\),  we can choose an element \(k \in \{1,2,3,\cdots, n\}\) such that \(k\ne l\) and \(k\ne m\). Choose \(\alpha=(l,k).\) Then \(\gamma \alpha(l)=\gamma(k)\) and \( \alpha \gamma (l)= \alpha(m)=m\). Since \(\gamma\) is a bijection and  \(\gamma (l) =m \ne l\), \(\gamma(k) \ne m\).  This contradicts  the assumption \(\gamma (\ne e) \in Z(S_n).\)  Hence, \(Z(S_n) = \{e\}\). \(\square\)

    Order of a permutation

    Let \(\sigma=(1, 2, 3)\).

    Then \(\sigma^2=(1, 2, 3)(1, 2, 3)=(1, 3, 2)=\sigma^{-1}\).

    Further \(\sigma ^3=(1, 2, 3)(1, 3, 2)=(1)(2)(3)=e\).  Thus the order of \(\sigma\), \(|\sigma |=3\).

    Theorem \(\PageIndex{9}\)

    If \(\sigma=(a_1, \ldots, a_k)\) is a \(k-\) cycle, then  \(|\sigma |=k\). 

    Proof

     Let \(\sigma=(a_1, \ldots, a_k)\). Then the permutation \(\sigma\) moves each \(a_i\) to the next entry of the cycle, with subscripts taken modulo \(k\), and fixes every element not in the cycle. After \(k\) applications, every element returns to its original position; hence \(\sigma^k=e\).

    We shall show that \(k\) is the smallest positive integer such that \(\sigma^k=e.\) Suppose \( m\) is a positive integer such that \(0 < m<k.\) Then \(\sigma^m(a_1)=a_{1+m} \ne a_1 \).  Thus \(\sigma^r\ne e\) for all \(1\leq r<k\). Hence \(k\) the smallest positive integer such that \(\sigma^k=e.\)

    Example \(\PageIndex{16}\)

     Let \(\gamma = (1, 2, 4)\). Then

    \(\gamma^2=(1, 2, 4)(1,2, 4)=(1, 4, 2)\), and

    \(\gamma^3=(1, 2, 4)(1, 4, 2)=(1)(2)(4)=e\).

     
    Theorem \(\PageIndex{10}\): Order of Product of Disjoint Cycles

    Let \(\sigma=c_1c_2\cdots c_r\) be a product of pairwise disjoint cycles of lengths \(k_1,\ldots,k_r\). Then \(\operatorname{ord}(\sigma)=\operatorname{lcm}(k_1,\ldots,k_r)\).

    Proof

    Let \(\sigma= c_1c_2\cdots c_r\) be a product of pairwise disjoint cycles of lengths \(k_1,\ldots,k_r\).

    Since disjoint cycles commute, for any positive integer \(m\),
    \(
    \sigma^m=c_1^m c_2^m\cdots c_r^m.
    \)
    The cycles have disjoint supports. Therefore \(\sigma^m=e\) if and only if \(c_i^m=e\) for every \(i= 1, \cdots, r\). As a cycle of length \(k_i\) has order \(k_i\),
    \(
    c_i^m=e\quad\Longleftrightarrow\quad k_i\mid m.
    \)
    Thus \(\sigma^m=e\) precisely when \(m\) is a common multiple of all \(k_1,\ldots,k_r\). The least positive such integer is their least common
    multiple, proving the result. \(\square\)

     

     

    Screen Shot 2023-07-06 at 9.57.45 AM.png

    Example \(\PageIndex{17}\)

    Determine possible orders of elements of \(S_7 \).

    Solution

    The longest cycle in \(S_7\) includes all \(7\) elements. We will show cycle lengths as \(\underline{7}\).  Note the underlining.  The table below shows the possible cycles.  The leading term is the longest cycle in the permutation.

    Cycle type

    Order

    Cycle type

    Order

    Cycle type

    Order

    7

    7

    4 2 1

    4

    3 1 1 1 1

    3

    6 1

    6

    4 1 1 1

    4

    2 2 2 1

    2

    5 2

    10

    3 3 1

    3

    2 2 1 1 1

    2

    5 1 1

    5

    3 2 2

    6

    2 1 1 1 1 1

    2

    4 3

    12

    3 2 1 1

    6

    1 1 1 1 1 1 1

    1

     

    order 1 2 3 4 5 6 7 10 12
    number of elements 1 231 350 840 504 1470 720 504 420

     

    Conjugacy classes of \(S_n\)

    Recall:

    Two elements \(x,y \) in a group \(G\) are conjugate if \(y=gxg^{-1}\) for some \(g\in G\).

    Theorem \(\PageIndex{11}\): Cojugacy Classes

    For \(\alpha , \beta \in S_n\text{,}\) define \(\alpha \sim \beta\) if there exists a \(\sigma \in S_n\) such that \(\sigma \alpha \sigma^{-1} = \beta\text{.}\) Then \(\sim\) is an equivalence relation on \(S_n\text{.}\)

    Proof

    Reflexive: Let \(\alpha \in S_n\). Then \( e\in S_n\) and \(e \alpha e^{-1} = \alpha\text{.}\) Hence  \(\alpha \sim \alpha\). Thus \(\sim\) is reflexive on \(S_n\text{.}\)

    Symmetric: Let \(\alpha , \beta \in S_n\) such that \(\alpha \sim \beta\). Then there exists a \(\sigma \in S_n\) such that \(\sigma \alpha \sigma^{-1} = \beta\text{.}\)  Therefore,  \(\sigma^{-1} \beta \sigma= \alpha\text{,}\)  and \(\sigma^{-1} \in S_n\).  Hence, \(\beta \sim \alpha\). Thus \(\sim\) is symmetric on \(S_n\text{.}\)

    Transitive: Let \(\alpha , \beta , \gamma \in S_n\) such that \(\alpha \sim \beta\) and  \(\beta \sim \gamma\). Then there exist \(\sigma_1, \sigma_2 \in S_n\) such that \(\sigma_1 \alpha \sigma_1^{-1} = \beta\text{,}\) and  \(\sigma_2\beta \sigma_2^{-1}= \gamma\text{.}\) Consider, \begin{align*} \gamma &= \sigma_2\beta \sigma_2^{-1}\\ &= \sigma_2 \left( \sigma_1 \alpha \sigma_1^{-1}  \right) \sigma_2^{-1}\\ &=\left( \sigma_2 \sigma_1\right) \alpha \left( \sigma_1^{-1}   \sigma_2^{-1}\right)\\  &= \left( \sigma_2 \sigma_1\right) \alpha \left( \sigma_2  \sigma_1\right)^{-1} .\end{align*} Hence,  \(\alpha \sim \gamma\).  Thus \(\sim\) is transitive on \(S_n\text{.}\)

    Since \(\sim\) is reflexive, symmetric and transitive, \(\sim\) is an equivalence relation on \(S_n\text{.}\)

    The equivalence classes are called conjugacy classes of \(G\), subsets of \(G\) whose elements are conjugate to one another. For \(\pi\in S_n\),
    \(
     \pi(a_1,\ldots,a_k)\pi^{-1}
     =(\pi(a_1),\ldots,\pi(a_k)).
    \)
    Thus conjugation changes the labels, not cycle lengths. Conversely, when two permutations have the same cycle type, match the entries in their corresponding disjoint cycles and define a relabeling permutation \(\pi\); this gives \(\beta=\pi\alpha\pi^{-1}\).

    Theorem \(\PageIndex{12}\): Conjugate Permuataions

    Two permutations in \(S_n\) are conjugate if and only if their disjoint-cycle decompositions have the same cycle lengths, counted with
    multiplicity, including fixed points.

    Proof

    If \(\tau=\rho\sigma\rho^{-1}\), then conjugating each cycle \((a_1\,a_2\,\cdots\,a_k)\) of \(\sigma\) gives
    \(
    \rho(a_1\,a_2\,\cdots\,a_k)\rho^{-1}
    =(\rho(a_1)\,\rho(a_2)\,\cdots\,\rho(a_k)),
    \)
    which has the same length. Hence conjugation preserves cycle lengths.

    Conversely, suppose \(\sigma\) and \(\tau\) have the same cycle lengths. List all cycles, including fixed points, in corresponding pairs:
    \(
    \sigma=\prod_{r=1}^{t}(a_{r,1}\,\cdots\,a_{r,k_r}),
    \qquad
    \tau=\prod_{r=1}^{t}(b_{r,1}\,\cdots\,b_{r,k_r}).
    \)
    Define \(\rho(a_{r,j})=b_{r,j}\) for every \(r,j\). Because every element of \(\{1,\ldots,n\}\) occurs exactly once among the \(a_{r,j}\) and exactly
    once among the \(b_{r,j}\), this defines a permutation \(\rho\in S_n\). For each \(b_{r,j}\), the permutation \(\rho\sigma\rho^{-1}\) sends it to
    \(b_{r,j+1}\), with indices taken cyclically. Thus \(\rho\sigma\rho^{-1}=\tau\), and \(\sigma\) and \(\tau\) are conjugate.

    Example \(\PageIndex{18}\)

    Conjugacy classes of \(S_3.\)

    Solution

    There are three conjugacy classes. Those are \( \{(1,2),(2,3),(1,3)\},\{e\},\{(1,2,3),(1,3,2)\}.\)


    This page titled 3.1: Symmetric Groups was last modified on Sat, 14 Nov 2026 19:29:06 GMT and is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

    • Was this article helpful?