Exercises - The Arithmetic of Permutations

  1. Find the following products of permutations:

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 3 & 5 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 4 & 5 & 2 & 3 \end{bmatrix} }$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 5 & 2 & 3 & 4 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 3 & 2 \end{bmatrix} }$

    3. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 4 & 5 & 3 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 1 & 4 \end{bmatrix} }$

    4. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 3 & 2 & 1 \end{bmatrix} }$

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 5 & 3 & 4 & 1 \end{bmatrix}}$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 2 & 4 & 1 & 3 \end{bmatrix}}$

    3. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 1 & 4 & 5 \end{bmatrix}}$

    4. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & 3 & 4 & 5 \end{bmatrix}}$

  2. Show $(P_1 P_2) P_3 = P_1 (P_2 P_3)$ when $$P_1 = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 3 & 1 & 2 & 4 \end{bmatrix}, \quad P_2 = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 1 & 4 \end{bmatrix}, \quad \textrm{and} \quad P_3 = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 1 & 2 & 3 & 5 \end{bmatrix}$$

    As both of the following calculations result in the same resulting permutation, it must be the case that $(P_1 P_2) P_3 = P_1 (P_2 P_3)$: $$\begin{array}{rcl} (P_1 P_2) P_3 &=& \left( \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 3 & 1 & 2 & 4 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 1 & 4 \end{bmatrix}\right) \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 1 & 2 & 3 & 5 \end{bmatrix}\\ &=& \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 5 & 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 1 & 2 & 3 & 5 \end{bmatrix}\\ &=& \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 2 & 1 & 4 \end{bmatrix} \end{array}$$ $$\begin{array}{rcl} P_1 (P_2 P_3) &=& \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 3 & 1 & 2 & 4 \end{bmatrix} \left( \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 5 & 1 & 4 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 1 & 2 & 3 & 5 \end{bmatrix}\right)\\ &=& \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 3 & 1 & 2 & 4 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 5 & 4 & 3 \end{bmatrix}\\ &=& \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 2 & 1 & 4 \end{bmatrix} \end{array}$$

  3. Find the inverse of each permutation below:

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 2 & 1 & 4 \end{bmatrix}}$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 4 & 2 & 3 \end{bmatrix}}$

    3. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 3 & 2 & 1 \end{bmatrix}}$

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 3 & 1 & 5 & 2 \end{bmatrix}}$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 5 & 3 & 1 \end{bmatrix}}$

    3. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 3 & 2 & 1 \end{bmatrix}}$

  4. Convert the each permutation given into cycle notation.

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 5 & 3 & 1 \end{bmatrix}}$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 4 & 6 & 5 & 1 & 7 & 3 \end{bmatrix}}$

    3. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 2 & 1 & 8 & 3 & 7 & 6 & 5 & 4 \end{bmatrix}}$

    1. $(1,2,4,3,5)$

    2. $(1,2,4,5)(3,6,7)$

    3. $(1,2)(3,8,4)(5,7)$

  5. Use the trick mentioned in the notes to find a braid (one of many possible) that induces each permutation given. Then use each braid found to write the corresponding permutation as a product/composition of transpositions (in cycle notation):

    1. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{bmatrix}}$

    2. $\displaystyle{ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 4 & 1 & 6 & 2 & 5 & 3 \end{bmatrix}}$

    Note, there are multiple ways to write the given permutations as products/compositions of transpositions. However, for the specific braids given in this problem -- no "jiggling" is necessary to avoid simultaneous crossings in any braid induced by drawing straight lines from the starting position to the ending one. Using these crossings in the order in which they occur produces the following products/compositions of transpositions:

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

    2. (3,4)(1,2)(5,6)(4,5)(2,3)(5,6)(3,4)

  6. Decide if the cycles present in each product/composition (of $8$ elements) below commute with one another.

    1. $(1,3)(2,4,5)(7,8)$

    2. $(1,2)(2,3)(5,6,8)$

    3. $(1,8,2,7)(3,4,5)$

    4. $(1,2)(1,2)$

    1. No two cycles in $(1,3)$, $(2,4,5)$, and $(7,8)$ share any common elements. Hence these three cycles all commute with each another.

    2. Note $(1,2)(2,3) = (1,3,2)$ but $(2,3)(1,2) = (2,3,1)$, so these two elements do not commute.

    3. The two cycles $(1,8,2,7)$ and $(3,4,5)$ share no elements in common. As such, these two cycles commute.

    4. This one is sneaky. Here, we have two cycles -- both $(1,2)$ -- that obviously share common elements. However, note that the statement found in the notes that "Cycles that share no common elements (i.e., disjoint cycles) commute" does not prohibit cycles that do share common elements from commuting. In general, sometimes they will and sometimes they won't. In this case, note that two elements/permutations that are inverses with one another will always automatically commute. After all, recall that we define $x$ and $x^{-1}$ to be inverses if and only if $x \cdot x^{-1} = x^{-1} \cdot x = I$). As $(1,2)$ is its own inverse, it will commute with itself.

  7. Express each as either a single cycle or a product of disjoint cycles

    1. $(1,6,7,4,5)^2$

    2. $(3,8,9,5,7,2,1,6)^2$

    3. $(1,5,4,2,3,6,7)^3$

    4. $(1,5,4,2,3,6)^3$

    5. $(1,5,4,2,3,6)^2$

    6. $(1,6,5,7,2,3,4)^{-1}$

    7. $(8,3,5,4)^{-1}$

    8. $(1,7,4,3,5)^{-2}$

    9. $(1,7,4,3,5)^{-3}$

    10. $(9,6,2,7)^{-2}$

    11. $(1,5,4,3)(1,4,2)(5,4,1)$

    12. $(1,6,2,3,5)(5,2,6)(2,3,6)$

    1. $(1,7,5,6,4)$
    2. $(3,9,7,1)(8,5,2,6)$ (note you can write this in different ways $(3,9,7,1)(2,6,8,5)$ works too, for instance)
    3. $(1,2,7,4,6,5,3)$
    4. $(1,2)(5,3)(4,6)$
    5. $(1,4,3)(5,2,6)$
    6. $(1,4,3,2,7,5,6)$ (here again, you can write this in different ways $(4,3,2,7,5,6,1)$ might be preferred by some here)
    7. $(8,4,5,3)$
    8. $(1,3,7,5,4)$
    9. $(1,4,5,7,3)$
    10. $(9,2)(6,7)$
    11. $(1,4,3)(5,2)$
    12. $(1,5)(2,6)$

  8. Given the permutations (on $10$ elements): $p_1 = (1,8,7,10,9)$, $p_2 = (1,3,5,4)$, and $p_3 = (2,6)(3,4,5)$ find the permutations corresponding to each of the following (expressing each as products of disjoint cycles):

    1. $p_1^3$

    2. $p_2^9 p_2^3$     Hint: Given the cycle length of $p_2$, what is $p_2^4$? Now, what can you say about $(p_2^4)^3$

    3. $\left(\cfrac{p_2^3}{p_2^{2}}\right)^3$

    4. $\left(\cfrac{p_1^2 p_3^3 p_1^{-1}}{p_2^3}\right)^2$     Hint: be careful regarding what commutes!

    5. $\cfrac{(p_1^2 p_3^3)^2}{(p_2 p_1^{-1} p_3^0)^2}$     Hint: be careful regarding what commutes!

    1. $(1,10,8,9,7)$

    2. This answer will be equivalent to $p_2^{12}$, but as $p_2^4 = I$, this simplifies to $I^4 = I$.

    3. $p_2^3 = (1,4,5,3)$

    4. Note $p_1$ and $p_3$ share no common elements, so they commute. For a similar reason $p_1^{-1}$ and $p_3$ commute (recall $p^{-1}$ involves the same elements as $p_1$). Of course $p_1$ and $p_1^{-1}$ commute by virtue of being inverses. This allows us to reduce the numerator to $p_1 p_3^3$. Taking into account the denominator, we can write the whole expression as $(p_1 p_3^3 p_2^{-3})^2$

      Note that because $(2,6)$ and $(3,4,5)$ are disjoint, they commute. Hence, $p_3^3 = ((2,6)(3,4,5))^3 = (2,6)^3 (3,4,5)^3 = (2,6)$

      Also, note that $p_2^{-3} = (p_2^{-1})^3 = (1,4,5,3)^3 = (1,3,5,4)$

      So $p_1 p_3^3 p_2^{-3} = (1,8,7,10,9)(2,6)(1,3,5,4) = (1,8,7,10,9,3,5,4)$

      Squaring this, we have $(p_1 p_3^3 p_2^{-3})^2 = (1,7,9,5)(8,10,3,4)$

    5. In the numerator, note again that $p_1$ and $p_3$ commute. Thus, we have $$(p_1^2 p_3^3)^2 = p_1^4 p_3^6 = p_1^4 = p_1^{-1} = (1,8,7,10,9)^{-1} = (1,9,10,7,8)$$ (The switch from $p_1^4$ to $p_1^{-1}$ is sneaky, do you see it? Hint: $p_1^5 = I$)

      Now in the denominator, note we may ignore the $p_3^0 = I$. This leaves $$\begin{array}{rcl} (p_2 p_1^{-1})^2 &=& p_2 p_1^{-1} p_2 p_1^{-1}\\ &=& (1,3,5,4)(1,8,7,10,9)^{-1}(1,3,5,4)(1,8,7,10,9)^{-1}\\ &=& (1,3,5,4)(1,9,10,7,8)(1,3,5,4)(1,9,10,7,8)\\ &=& (1,5,9,7)(3,4,10,8) \end{array}$$

      Finally, dealing with the numerator over the denominator we have $$\begin{array}{rcl}\cfrac{(1,9,10,7,8)}{(1,5,9,7)(3,4,10,8)} &=& (1,9,10,7,8)[(1,5,9,7)(3,4,10,8)]^{-1}\\ &=& (1,9,10,7,8)(1,5,9,7)^{-1}(3,4,10,8)^{-1}\\ &=& (1,9,10,7,8)(1,7,9,5)(3,8,10,4)\\ &=& (1,5)(3,8,7,10,9,4) \end{array}$$