Permutations

Let $\mathbb{Z}_n = \{1,2, ..., n\}$ be the set of integers from 1 to a fixed positive integer $n$. A permutation of $\mathbb{Z}_n$ is a bijection from T to itself. For example, on the $3\times 3$ Rubik's cube there are $9\cdot 6=54$ facets. If you label them $1, 2, ..., 54$ (in any way you like) then any move of the Rubik's cube corresponds to a permutation of $\mathbb{Z}_{54}$. In this section we present some basic notation and properties of permutations. Notation: We may denote a permutation $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ by a $2\times n$ array:

$$f \leftrightarrow \left( \begin{array}{cccc} 1&2&...&n\\ f_1& f_2& ... & f_n \end{array} \right),$$

where $f_1,f_2,...,f_n$ is simply a rearrangement (in some order depending on $f$) of the integers $1,2,...,n$. This notation means that $f$ sends $1$ to $f_1$, $f$ sends $2$ to $f_2$, ..., $f$ sends $n$ to $f_n$. In other words, $f_1=f(1)$, $f_2=f(2)$, ..., $f_n=f(n)$.

Example 4.2.1 (a)   The identity permutation, denoted by I, is the permutation which doesn't do anything:

$$I= \left( \begin{array}{cccc} 1&2&...&n\\ 1& 2& ... & n \end{array} \right)$$

(b) The permutation $f:\mathbb{Z}_3\rightarrow \mathbb{Z}_3$ defined by

$$f= \left( \begin{array}{ccc} 1&2&3\\ 3& 2& 1 \end{array} \right)$$

simply swaps $1$ and $3$ and leaves $2$ alone. (a) The $n$-cycle is a permutation which cyclically permutes the values:

$$\left( \begin{array}{cccc} 1&2&...&n\\ 2& 3& ... & 1 \end{array} \right)$$

Imagine an analog clock with the numbers $1$, $2$, ..., $n$ arranged around the dial. An $n$-cycle simply moves each number forward (clockwise) by one unit. The permutation

$$\left( \begin{array}{cccc} 1&2&...&n\\ n& 1& ... & n-1 \end{array} \right)$$

is also called an $n$-cycle.

Definition 4.2.2   Let $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ be a permutation and let

$$e_f(i)=\char93 \{j>i\ \vert\ f(i)>f(j)\},\ \ \ \ \ 1\leq i\leq n-1.$$

Let

$$swap(f)=e_f(1)+...+e_f(n-1).$$

We call this the swapping number (or length) of the permutation $f$ since it counts the number of times $f$ swaps the inequality in $i<j$ to $f(i)>f(j)$. If we plot a bar-graph of the function $f$ then $swap(f)$ counts the number of times the bar at $i$ is higher than the bar at $j$. We call $f$ even if $swap(f)$ is even and we call $f$ odd otherwise. The number

$$sign(f) = (-1)^{swap(f)}$$

is called the sign (or signum function) of the permutation $f$.

The reader may verify that the sign function satisfies the following property.

Lemma 4.2.3   Let $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ be a permutation. Then

$$sign(f)=\prod_{i<j\leq n}{f(i)-f(j)\over i-j}.$$

Example 4.2.4   We define the permutation $f:\mathbb{Z}_3\rightarrow \mathbb{Z}_3$ for which $f(1)=2, f(2)=1, f(3)=3$ by a $2\times 3$ array

$$\left( \begin{array}{ccc} 1&2&3\\ 2&1&3 \end{array} \right)$$

This swaps $1$ and $2$ and leaves $3$ alone. There are 3 inequalities for $\mathbb{Z}_3$: $1<2$, $2<3$, and $1<3$. Applying $f$ to these, we get: $f(1)=2 > f(2)=1$, $f(2)=1<f(3)=3$, and $f(1)=2<f(3)=3$. Only the first inequality is changed, so the swapping number is $swap(f)=1$. Another way to picture $f$ is by a ``crossing diagram", where $f$ sends the left-hand column to the right-hand column:

The number of crosses in this diagram is the swapping number of $f$, from which we can see that $f$ is an odd permutation.

Definition 4.2.5   Let $f : \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ and $g : \mathbb{Z}_n \rightarrow \mathbb{Z}_n$ be two permutations. We can compose them to get another permutation, the composition, denoted $f\circ g:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$ (or sometimes simply $fg$):

$$\begin{array}{ccccc} k& \longmapsto& f(k)& \longmapsto& g(... ...ghtarrow &\mathbb{Z}_n&\rightarrow &\mathbb{Z}_n \end{array}$$

Notation We shall follow standard convention and write our compositions of permutations left-to-right. (This is of course in contrast to the right-to-left composition of functions you may have seen in calculus.) When a possible ambiguity may arise, we call this type of composition ``composition as permutations" and call ``right-to-left composition" the ``composition as functions". When $f=g$ then we write $ff$ as $f^2$. In general, we write the n-fold composition $f...f$ ($n$ times) as $f^n$. Every permutation $f$ has the property that there is some integer $N>0$, which depends on $f$, such that $f^N = I$. (In other words, if you repeatedly apply a permutation enough times you will eventually obtain the identity permutation.)

Lemma 4.2.6   Let $f$ and $g$ be permutations $\mathbb{Z}_n\rightarrow \mathbb{Z}_n$. $sign(fg)=sign(f)sign(g)$.

Definition 4.2.7   The smallest integer $N>0$ such that $f^N = I$ is called the order of $f$.

Example 4.2.8   Let

$$f= \left( \begin{array}{ccc} 1&2&3\\ 2& 1& 3 \end{ar... ... \begin{array}{ccc} 1&2&3\\ 3& 1& 2 \end{array} \right)$$

be permutations of $\mathbb{Z}_n$. We have

$$fg= \left( \begin{array}{ccc} 1&2&3\\ 1& 3& 2 \end{array} \right), \ \ \ \ \ f^2=I,\ \ \ \ \ \ g^3=I.$$

Exercise 4.2.9   Compute (a) $fg$ and (b) the order of $f$ and the order of $g$, where

$$(a)\ \ \ \ \ f= \left( \begin{array}{ccc} 1&2&3\\ 3&... ... \begin{array}{ccc} 1&2&3\\ 3& 1& 2 \end{array} \right)$$

$$(b)\ \ \ \ \ f= \left( \begin{array}{ccc} 1&2&3\\ 3&... ... \begin{array}{ccc} 1&2&3\\ 2& 1& 3 \end{array} \right)$$

Exercise 4.2.10   Compute (a) $fg$ and (b) the order of $f$ and the order of $g$, where

$$(a)\ \ \ \ \ f= \left( \begin{array}{cccc} 1&2&3&4\\ ... ...in{array}{cccc} 1&2&3&4\\ 3& 4& 2&1 \end{array} \right)$$

$$(b)\ \ \ \ \ f= \left( \begin{array}{cccc} 1&2&3&4\\ ... ...in{array}{cccc} 1&2&3&4\\ 4& 1& 3&2 \end{array} \right)$$

Exercise 4.2.11   For $f,g$ as in Lemma 4.2.6, we have

$$\prod_{i<j\leq n}{fg(i)-fg(j)\over i-j}= \prod_{i<j\leq n}{g(i)-g(j)\over i-j}\prod_{i<j\leq n}{fg(i)-fg(j)\over g(i)-g(j)}.$$

Why does this imply the lemma?

Exercise 4.2.12   Express $f:\mathbb{Z}_3\rightarrow \mathbb{Z}_3$ given by $f(1)=3, f(2)=1, f(3)=2$, as (a) a $2\times 3$ array, (b) a crossing diagram. Find its swapping number and sign.

Exercise 4.2.13   Express $f : \mathbb{Z}_4\rightarrow \mathbb{Z}_4$ given by $f(1)=3, f(2)=4, f(3)=2, f(4)=1$, as (a) a $2\times 4$ array, (b) a crossing diagram. Find its swapping number and sign.