Cycle notation

Rubik's cubers will often, without knowing it perhaps, use the following lemma to solve their cube.

Lemma 4.4.1   Let $r\in S_n$ denote any permutation and let $i,j$ denote distinct integers belonging to $\{1,2,...,n\}$. Let $s$ denote a permutation sending $i$ to $j$:

$$s(i)=j.$$

Then $s^r=r^{-1}sr$ is a permutation sending $r(i)$ to $r(j)$:

$$s^r(r(i))=r(j).$$

More specifically (and this is the case which this lemma is most often applied in this book): let $i_1,i_2,...,i_k$ denote distinct integers belonging to $\{1,2,...,n\}$. Let $s$ denote the permutation sending $i_j$ to $i_{j+1}$:

$$s(i_j)=i_{j+1},\ \ \ \ \ \ 1\leq j<k, \ \ \ \ \ \ \ s(i_k)=i_1,\ \ \ \ \ \ \ s(m)=m,\ \ \forall m\notin \{i_1,...,i_k\}.$$

Then $s^r=r^{-1}sr$ is the permutation sending $(i_j)r$ to $(i_{j+1})r$:

$$s^r(r(i_j))=r(i_{j+1}),\ \ \ \ \ \ 1\leq j<k, \ \ \ \ \ \ \ s^r(r(i_k))=r(i_1),$$

$$s^r(m)=m,\ \ \forall m\notin \{r(i_1),...,r(i_k)\}.$$

Example 4.4.2   Let us label the $12$ edges of the Rubik's cube using the Singmaster notation:

• $uf$ denotes the ``up, front edge'',
• $ul$ denotes the ``up, left edge'',
• $ur$ denotes the ``up, right edge'',
• $ub$ denotes the ``up, back edge'',
• $df$ denotes the ``down, front edge'',
• $dl$ denotes the ``down, left edge'',
• $dr$ denotes the ``down, right edge'',
• $db$ denotes the ``down, back edge'',
• $fl$ denotes the ``front, left edge'',
• $br$ denotes the ``front, right edge'',
• $fl$ denotes the ``back, left edge'',
• $br$ denotes the ``back, right edge''.

Suppose you have a Rubik's cube move $s$ which is a 3-cycle on 3 particular edges, say

$$uf\longmapsto ul\longmapsto ur\longmapsto uf.$$

Suppose you have another move $r$ which sends these edges somewhere else, say $r=F^2$ so that $r:uf\longmapsto df$ and $r:fl\longmapsto fr$, but leaves the other edges alone. Then $r^{-1}sr$ is the permutation

$$df\longmapsto ul\longmapsto ur\longmapsto df.$$

Try it!

The most common notation for a permutation is the ``cycle notation". This notation is more compact that the array notation we've been using and from this point on we will switch over to the cycle notation. If $a_1,a_2,...,a_r\in \mathbb{Z}_n$ then the symbol

$$(a_1\ a_2\ ...\ a_r) \ \ \ \ \ \ \ {\rm (some\ r\ less\ than\ or\ equal\ to\ n)}$$

denotes the permutation $f$ of $\mathbb{Z}_n$ which sends $a_1$ to $a_2$, sends $a_2$ to $a_3$, ..., sends $a_{r-1}$ to $a_r$, sends $a_r$ to $a_1$, and leaves all the other numbers in $\mathbb{Z}_n$ alone. In other words,

$$f(a_1)=a_2,\ f(a_2)=a_3,\ ... , f(a_r)=a_1,$$

and $f(i)=i$, if $i$ is not equal to one of the $a_1, ..., a_r$. Such a permutation is called cyclic. The number $r$ is called the length of the cycle. We call two such cycles $(a_1\ a_2\ ...\ a_r)$ and $(b_1\ b_2\ ...\ b_t)$ disjoint if the sets $\{a_1, a_2, ..., a_r\}$ and $\{b_1, b_2, ..., b_t\}$ are disjoint.

Lemma 4.4.3   If $f$ and $g$ are disjoint cyclic permutations of $\mathbb{Z}_n$ then $fg=gf$.

proof: This is true because the permutations $f$ and $g$ of $\mathbb{Z}_n$ affect disjoint collections of integers, so the permutations may be performed in either order. $\Box$

Lemma 4.4.4   The cyclic permutation $(a_1,\ a_2,\ ..., a_r)$ has order $r$.

proof: Note $f(a_1)=a_2$, $f^2(a_1)=a_3$, ..., $f^{r-1}(a_1)=a_r$, $f^r(a_1)=a_1$, by definition of $f$. Likewise, for any $i=1,...,r$, we have $f^r(a_i)=a_i$. $\Box$

Definition 4.4.5   A transposition is a cycle $(i,j)$ of length $2$ which interchanges $i$ and $j$.

Theorem 4.4.6   Every permutation $f : \{1,2,...,n\} \rightarrow \{1,2,...,n\}$ is the product of disjoint cyclic permutations. More precisely, if $f$ is a permutation of $\{1,2,...,n\}$ (with $n>1$) then there are non-empty disjoint subsets of distinct integers

$$\begin{array}{c} S_1=\{a_{11},...,a_{1,r_1}\}\subset \{1,2... ...,n\},\\ ...,\\ S_k=\{a_{k1},...,a_{k,r_k}\}, \end{array}$$

such that

$$\{1,2,...,n\}=S_1\cup ...\cup S_k,\ \ \ \ n=r_1+r_2+...+r_k,$$

and

$$f=(a_{11},...,a_{1,r_1})...(a_{k1},...,a_{k,r_k}).$$

This product is called a cycle decomposition of f . If we rearrange the cardinalities $r_i$ of these sets $S_i$ in decreasing order, say we write this as

$$r_1'\geq r_2'\geq ... \geq r_k',$$

then the $k$-tuple $(r_1',...,r_k')$ is called the cycle structure of $f$ and $f$ is called a $(r_1',...,r_k')$-cycle. For example, $(1,2)(3,4,5)$ is a $(3,2)$-cycle. proof: The proof is constructive. Let $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ be a permutation. List all the distinct elements in $\mathbb{Z}_n$ you get by repeatedly applying $f$ to $1$. Call them (for lack of a better notation!), $a_{10}, a_{11}, a_{12}, ..., a_{1,r_1}$, where,

$$O_1=\{a_{10}=1, a_{11}=f(1), a_{12}=f^2(1), ..., a_{1,r_1}=f^{r_1}(1)\}.$$

(Incidently, this is called the orbit of $1$ under $f$. We shall discuss orbits more later in this book.) Now list the elements in the orbit of $2$:

$$O_2=\{a_{20}=2, a_{21}=f(2), a_{22}=f^2(2), ..., a_{2,r_2}=f^{r_2}(2)\},$$

and so on until we get to the ``orbit of $n$":

$$O_n=\{a_{n0}=n, a_{n1}=f(n), a_{n2}=f^2(n), ..., a_{n,r_n}=f^{r_n}(n)\}.$$

An example: let $f:\mathbb{Z}_3\rightarrow \mathbb{Z}_3$ be the $3$-cycle permutation, $f(1)=2, f(2)=3, f(3)=1$. In this case, $O_1=\{1,2,3\}$, $O_2=\{2,f(2)=3,f(f(2))=f(3)=1\}$, and $O_3=\{3,f(3)=1,f(f((3))=f(1)=2\}$, so all three orbits are equal to each other in this example. In general, if you pick any two of these $n$ orbits $O_1$, ..., $O_n$, they will either be the same or disjoint. Denote all the distinct orbits by $O'_1$, ..., $O'_k$. (The $O'_1$, ..., $O'_k$ are a subsequence of the $O_1$, ..., $O_n$. It doesn't matter what order you write the $O'_i$'s in or in what order you write the elements in each individual orbit.) Suppose that

$$\begin{array}{c} O'_1 = \{b_{11}, ..., b_{1,s_1}\} \ \ \ ... ..._{k,s_k}\}\ \ \ \ {\rm so}\ \vert O'_k\vert=s_k. \end{array}$$

(The $a_{ij}$'s have been relabeled as $b_{ij}$'s to try to simplify the notation.) In this case,

$$\mathbb{Z}_n= \cup_{i=1}^k O'_i=O'_1\cup ...\cup O'_k,$$

and $s_1 + s_2 + ... + s_k = n$. The restriction of $f$ to $O'_1$, denoted $f_{O'_1}:O'_1\rightarrow O'_1$, is equal to the $s_1$-cycle $(b_{11}, b_{12}, ... ,b_{1,s_1})$. In general, the restriction of $f$ to $O'_j$, denoted $f_{O'_j}:O'_1\rightarrow O'_j$, is equal to the $s_j$-cycle $(b_{j1}, b_{j2}, ... ,b_{j,s_j})$. Since the $O'_j$'s partition $\mathbb{Z}_n$, the definition of $f$ and our construction implies that

$$f=(b_{11}, b_{12}, ... ,b_{1,s_1})...(b_{k1}, b_{k2}, ... ,b_{k,s_k}).$$

$\Box$

Example 4.4.7  

• The cycle notation for
  $$\left( \begin{array}{ccc} 1&2&3\\ 2&1&3 \end{array} \right)$$
  is $(1,2)(3)$ or simply $(1,2)$. In general, if any of the orbits $O_j$ in the above construction is a singleton, it is often omitted from the notation, with the implicit understanding that $f$ doesn't permute the omitted numbers.
• The cycle notation for
  $$\left( \begin{array}{ccc} 1&2&3\\ 2&3&1 \end{array} \right)$$
  is $(1,\ 2,\ 3)$.
• The cycle notation for
  $$\left( \begin{array}{cccc} 1&2&3&4\\ 3&4&1&2 \end{array} \right)$$
  is $(1,\ 3)(2,\ 4)=(2,\ 4)(1,\ 3)$.
• The cycle notation for
  $$\left( \begin{array}{ccccc} 1&2&3&4&5\\ 3&4&1&5&2 \end{array} \right)$$
  is $(1,\ 3)(2,\ 4,\ 5)=(4,\ 5,\ 2)(1,\ 3)$.
• The disjoint cycle decomposition of $(2,3,7)(3,7,10)$ is $(2,3)(7,10)$.

Lemma 4.4.8   A cyclic permutation is even if and only if the length of its cycle is odd. A general permutation $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ is odd if and only if the number of cycles of even length in its cycle decomposition is odd.

This follows from the definition of even/odd (see Definition 4.2.2) and the fact that $sign(p_1p_2...p_k)=sign(p_1)sign(p_2)...sign(p_n)$, for permutations $p_i$ (because of Lemma 4.2.6). The proof is left as an exercise.

Lemma 4.4.9   The order of a permutation is the least common multiple (lcm) of the lengths $r_1, r_2 , ..., r_k$ of the disjoint cycles in its cycle decomposition.

Example 4.4.10   The order of $(1,\ 3)(2,\ 4)$ is $2$. It is even. The order of $(1,\ 3)(2,\ 4,\ 5)$ is $6$. It is odd.

Exercise 4.4.11   Let $s=(1,2,3)$ and $r=(1,3)(2,4)$ be permutations of $\{1,2,3,4\}$. Compute $r^{1}sr$ using Lemma 4.4.1.

Exercise 4.4.12   Let $s=(1,5)(2,4,3)$ and $r=(1,2,3,4,5)$ be permutations of $\{1,2,3,4,5\}$. Compute $r^{1}sr$ using Lemma 4.4.1.

Exercise 4.4.13 (a)   Show that the inverse of $(a_1, a_2, a_3, a_4)$ is $(a_1, a_4, a_3,a_2)=(a_4, a_3, a_2, a_1)$. (b) Find the inverse of $(a_1, a_2, a_3, ..., a_n)$.

Exercise 4.4.14   Consider the equation given in $2\times n$ array form as

$$\left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 ... ...& 2 & 3 & 4 & 5 \\ 4 & 1 & 2 & 5 & 3 \end{array} \right).$$

Solve for $x$ in two ways:

(i)

by directly considering what $2\times n$ array would 'fit' for $x$ (so that the composition on the left hand side would indeed by the right side)

(ii)

solving for $x$ algebraically (hint: if $a x b^{-1} = c$, then $x = a^{-1} c b$).

It is recommended that you rewrite the equation first in disjoint cycle notation, then solve.

Exercise 4.4.15 (a)   Show that $(a_1, a_2, a_3, a_4)=(a_1, a_2) (a_1, a_3) (a_1, a_4)$. (b) Express $(a_1, a_2, ... a_n)$ as a product of transpositions.

Exercise 4.4.16   When first opened, a new package containing a standard deck of 52 cards is typically found to be in a naturally ordered state (and the customer can quickly verify that all cards are present). How does (b) of Exercise 4.4.15 show that any deck of cards, no matter how thoroughly shuffled, can be brought back to its original state simply by the following single operation: repeatedly swapping various cards with the current top card?

Exercise 4.4.17   Divide a square into 4 subsquares (``facets") and label them $1, 2, 3, 4$. For example,

               -----------------
              |        |        |
              |    1   |   2    |
              |        |        |
               -----------------
              |        |        |
              |    3   |    4   |
              |        |        |
               -----------------

Let $r$ denote counterclockwise rotation by 90 degrees. Then, as a permutation on the facets, $r=(1,\ 3,\ 4,\ 2)$. Let $f_x$ denote reflection about the horizonal line dividing the square in two, let $f_y$ denote reflection about the vertical line dividing the square in two. Use the cycle notation to determine the permutations of the facets (a) $r^2$ (b) $r^3$, (c) $f_x$, (d) $f_y$, (e) $f_xrf_x$, (f) $f_xf_y$, (c) $f_x^{-1}$, (d) $f_y^{-1}$.

Exercise 4.4.18   Label the 24 facets of the $2\times 2$ Rubik's cube as follows:

                         +--------------+
                         |  1         2 |

                         |       u      |

                         |  3         4 |
          +--------------+--------------+--------------+--------------+
          |  5         6 |  9        10 | 13        14 | 17        18 |

          |       l      |       f      |       r      |       b      |

          |  7         8 | 11        12 | 15        16 | 19        20 |
          +--------------+--------------+--------------+--------------+
                         | 21        22 |

                         |       d      |

                         | 23        24 |
                         +--------------+

(You may want to xerox this page then cut this cube out and tape it together for this.) Let $X$ denote rotation clockwise by 90 degrees of the face labeled $x$, where $x\in\{ r, l, f, b, u, d\}$ (so, for example, if $x=f$ then $X=F$). Use the cycle notation to determine the permutations of the facets given by (a) $R$, (b) $L$, (c) $F$, (d) $B$, (e) $U$, (f) $D$.