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:

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

where $ f_1,f_2,...,f_n$ is simply a linear rearrangement 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)$. In this way, we see that there is a 1-1 correspondence between the linear rearrangements of the integers $ 1,2,...,n$ and permutations. (In fact, many books define a permutation to be a linear rearrangement and then prove that it gives rise to a function as above.)

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

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

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

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

simply swaps $ 1$ and $ 3$ and leaves $ 2$ alone.

(a) The $ n$-cycle is a permutation which cyclically permutes the values:

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

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

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

is also called an $ n$-cycle.

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

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

Let

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

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

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:


\begin{picture}(200.00,150.00)(-120.00,0.00)\thicklines \put(0.00,0.00){\circ... ...60.00){\line(2,1){118.00}} \put(0.00,120.00){\line(2,-1){118.00}} \end{picture}

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{displaymath} \begin{array}{ccccc} k& \longmapsto& f(k)& \longmapsto& g(f(... ...\rightarrow &\mathbb{Z}_n&\rightarrow &\mathbb{Z}_n \end{array}\end{displaymath}

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

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

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

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

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

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

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

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

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

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

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

$\displaystyle \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.


David Joyner 2007-09-03