More Math of Permutations

Mike

2021-06-03 (Last Modified: 2021-11-06)

Page content

Here we prove that permutations can be divided into even permutations and odd permutations. We’ll also go over what happens when you compose two permutations. Surprisingly, it behaves like adding numbers. E.g. composing an even permutation with an odd permutation results in an odd permutation. Two odd permutations result in an even permutation, etc…

This entry is a continuation of Some of the Math of Permutations.

Let’s get started! The first thing we’re going to do is prove a couple of nice lemmas.

Lemma a

Let $ \rho $ be a permutation on the set of integers $ \{ 1, 2, … , n \} $, and let $ f_{\rho} $ be a function from the set of ordered pairs $ \mathbb{D} = \{ (i, j) | 1 \leq j < i \leq n \} $ such that $ f_{\rho}( (i,j) ) := ( \rho(i), \rho(j) )$ then

$ f_{\rho}$ is 1 -1
If $ (u, v) \in Range(f_{\rho}) $, then $ (v, u) \not\in Range(f_{\rho}) $.

Proof

To prove 1, suppose $ f_{\rho}((i, j)) = f_{\rho}((k, l)) $, then by definition of $ f_{\rho}$, $ \rho(i) = \rho(k) $. Since $ \rho $ is a permutation, it is 1-1, so $ i = k $, similarly, $ j = l $, so $ (i,j) = (k, l) $.

To prove 2, suppose $ f_{\rho}( (i,j) ) = (u, v)$ and $ f_{\rho}( (k, l) ) = (v, u) $, then $ \rho(i) = u = \rho(l) $, so $ i = l $, and similarly we can show that $ j = k $, so we have shown that $ (k, l) = (j, i) $, but then $ k < l $, so it isn’t in $\mathbb{D} = Domain(f_{\rho}) $, a contradiction. QED.

Lemma b

Let $ \sigma $ and $ \rho $ be permutations on the set of integers $ \{ 1, 2, … , n \} $. Then

$$ \begin{align} \prod\limits_{i > j} { \frac{\sigma(i) - \sigma(j)}{i - j} } = \\ \prod\limits_{\rho(i) > \rho(j)}{ \frac{\sigma(i) - \sigma(j)}{i - j} } \tag{1}\label{1}\\ \end{align} $$

Proof

We split the products into two cases.

Case 1: $ i > j $ and $ \rho(i) > \rho(j) $

In this case $ \frac{\sigma(i) - \sigma(j)}{i - j} $ occurs on both sides of the equation. Before we handle case 2, notice that in both products, if $i \neq j $, then by lemma a above, either the tuple $ (i, j) $ or $ (j, i) $ occurs in the product, but not both.

Case 2: $ i > j $ but $ \rho(i) < \rho(j) $

In this case the product on the left will contain $ \frac{\sigma(i) - \sigma(j)}{i - j} $, but the product on the right will contain $ \frac{\sigma(j) - \sigma(i)}{j - i} $. Notice that $ \frac{\sigma(i) - \sigma(j)}{i - j} = \frac{-[\sigma(j) - \sigma(i)]}{i - j}$ and that $ \frac{-[\sigma(j) - \sigma(i)]}{i - j} = \frac{\sigma(j) - \sigma(i)}{j - i} $. So the terms occurring on both sides of the equation are equal. Thus the products are equal.

QED

In an earlier post, we noted that any permutation of a set $ X $ can be associated with a permutation of the indices of the elements of the set with respect to its ordering. What we mean by this is that if we let $ X = \{ x_1, x_2, … \} $, then $ \sigma(x_i) = x_j $, and we can identify $ \sigma $ with $ \dot{\sigma} $, where $ \sigma(x_i) = x_j \Leftrightarrow \dot{\sigma}(i) = j $. I.e. $ \sigma(x_i) = x_{\dot{\sigma}(i)} $.

Definition (Sign)

Now we can reintroduce the definition of $ Sign(\sigma) $, the sign of a finite permutation. Let $ \sigma $ be a permutation of a finite set. Then \[ Sign(\sigma) := \prod\limits_{i > j}{ \frac{ \dot{\sigma}(i) - \dot{\sigma}(j) }{i - j} } \] For the rest of this article, we will blur the distinction and assume that all permutations are permutations of $ \{ 1, 2, …, n \} $, for some finite $ n $.

Theorem (product)

Let $ \sigma $ and $ \tau $ be permutations, then

$$ \begin{align} &Sign(\sigma \circ \tau) =\\ &Sign(\sigma) \cdot Sign(\tau) \\ \end{align} $$

Proof

Note that $$ \begin{align} &Sign(\sigma \circ \tau) = \\ &\prod\limits_{i > j} { \frac{ \sigma \circ \tau(i) - \sigma \circ \tau(j) }{i - j} } \tag{2}\label{2}\\ \end{align} $$

The right side of (2) can be split as \[ \prod\limits_{i > j} { \frac{ \sigma \circ \tau (i) - \sigma \circ \tau (j) }{\tau(i) - \tau(j)} \cdot \frac{ \tau(i) - \tau(j) }{i - j} } \tag{3}\label{3}\]

That can be regrouped as \[ \prod\limits_{i > j} { \frac{ \sigma \circ \tau (i) - \sigma \circ \tau (j) }{\tau(i) - \tau(j)} } \prod\limits_{i > j} \frac{ \tau(i) - \tau(j) }{ i - j } \tag{4}\label{4} \]

The right product of (4) you’ll recognize as $ Sign(\tau) $, so now we turn our focus to the left side. By lemma (a) above, the left product is equal to

\[ \prod\limits_{ \tau(i) > \tau(j) } { \frac{ \sigma \circ \tau(i) - \sigma \circ \tau(j) }{ \tau(i) - \tau(j) } } \tag{5}\label{5} \]

If we define $ u := \tau(i) $ and $ v := \tau(j) $, then we can rewrite (5) as \[ \prod\limits_{u > v} { \frac{ \sigma(u) - \sigma(v) }{u - v} } \tag{6}\label{6} \] Clearly, (6) is equal to $ Sign(\sigma) $, and our proof is finished.

QED

Corollary (inverse)

Let $ \sigma $ be a permutation. Then \[ Sign(\sigma^{-1}) = \frac{1}{Sign(\sigma)} \tag{7}\label{7} \]

Proof

Let $ \iota $ be the identity permutation. I.e. $ \iota(i) = i $. If you calculate $ Sign(\iota) $, you get $ 1 $, notice that $ \sigma \circ (\sigma^{-1}) = \iota $.

QED

Theorem (units)

$Sign(\sigma) = \pm 1 $.

Proof

This proof only requires a slight extension of lemma (a). Recall from that proof that we defined $ \mathbb{D} := \{ (i, j ) | 1 \leq j < i \leq n \} $, and that we defined

\[ f_{\sigma}( (i,j) ) := (\sigma(i), \sigma(j)) \]

Now we introduce the function

\[ g(u, v) := \begin{cases} (u, v), u > v \\ (v, u), v > u \end{cases}\]

Notice that by definition, $ g \circ f_{\sigma} : \mathbb{D} \rightarrow \mathbb{D}$. Further, notice that by lemma a, $ g \circ f_{\sigma} : \mathbb{D} \xrightarrow{\text{1-1}} \mathbb{D} $. Since $ \mathbb{D} $ is finite, $ g \circ f_{\sigma} $ must also be onto. Thus every pair $ i - j $ in the denominator of the product $ \prod\limits_{i > j} { \frac{ \sigma(i) - \sigma(j) }{i - j} } $ occurs once in the numerator, or its negative occurs once in the numerator, but not both. Thus the product is $ \pm 1 $.

QED

Now that we’ve shown that $ Sign(\sigma) $ behaves nicely, you might be wondering whether it’s of any use at all. What if every permutation has $ Sign = 1$ ? That would be utterly useless. Fortunately, it’s not difficult to show that there are permutations whose $ Sign = -1 $.

Claim

Let $ n = 2 $, and $ \sigma(1) = 2$ and $ \sigma(2) = 1 $. Then $ Sign(\sigma) = -1 $. Doing the calculation results in $ Sign(\sigma) = \frac{1 - 2}{2 - 1 } $.

QED

Even more generally, for any $n \geq 2 $, if $ \sigma $ is a permutation that only swaps two numbers, say $ i $ and $ j $, where $ i \neq j $, then $ Sign(\sigma) = -1 $.

Proof

Without loss of generality, suppose $ j < i $, then we have

\[ \sigma(n) := \begin{cases} i, n = j \\ j, n = i \\ n, \text{otherwise} \end{cases} \]

Let’s define

$$ \begin{align} \tau(n) &:= \begin{cases} 1, n = j \\ 2, n = i \\ n, \text{otherwise} \end{cases} \\ \\ \rho(n) &:= \begin{cases} 1, n = 2 \\ 2, n = 1 \\ n, \text{otherwise} \end{cases} \\ \end{align} $$

We leave it to the reader to confirm that $ \rho = \tau \circ \sigma \circ \tau^{-1} $, even if $ i $ and $ j $ aren’t necessarily distinct from $ 1 $ and $ 2 $. Then, by the product theorem and the inverse corollary above, $ Sign(\sigma) = Sign(\rho) $. So now all we have to do is show that $ Sign(\rho) = -1 $.

Notice in the calculation of $ Sign(\rho) $ that the denominators are always positive. Notice as well that if $ i \geq 3 $, then no matter what $ j $ is, $ \rho(i) > \rho(j) $, so the numerator is positive in those cases. Finally, if $ i \leq 2 $, then it must be equal to $ 2 $, otherwise there is no $ j $ that can be strictly less than it. So in that case we are dealing with the pair $ i = 2 $ and $ j = 1 $. In that case, the numerator is negative. Since this is the only negative term in the entire product, we have shown that $Sign(\rho) = - 1$.

QED

Next we extend this result to cycles of length greater than 2. A permutation is a cycle if it is of the form

\[ \sigma(n) := \begin{cases} \sigma(i), & n = i \\ \sigma^{2}(i), & n = \sigma(i) \\ \sigma^3(i), & n = \sigma^2(i) \\ … \\ \sigma^{k-1}(i), & n = \sigma^{k-2}(i) \\ \sigma^{k}(i) = i, & n = \sigma^{k-1}(i) \\ n, & \text{otherwise} \end{cases} \]

In this case, $ k $ is the length or period of the cycle. You should convince yourself that all of the $ \sigma^n(i) $ ’s are unique for $ 1 \leq n \leq k $. Otherwise $ \sigma $ would not be 1-1.

We’ll introduce the standard notation for cycles. We can represent the $ \sigma $ defined above as

\[ (i, \sigma(i), \sigma^2(i), … , \sigma^{k-1}(i) ) \]

We leave it to the reader to confirm that

$$ \begin{align} &(i, \sigma(i), \sigma^2(i), … , \sigma^{k-1}(i) ) = \\ &( i, \sigma^{k-1}(i) ) \circ ( i, \sigma^{k-2}(i) ) \circ … \circ (i, \sigma^{1}(i)) \tag{8} \label{8} \\ \end{align} $$

Remember that when evaluating the composition of functions, you apply the right most function first. This means that in (8) above, the first permutation to be applied is the two-cycle $ (i, \sigma^{1}(i) ) $ and the last two-cycle to be applied is $ ( i, \sigma^{k-1}(i) ) $. Since all of the two cycles move $ i$, the order matters!

By breaking down a cycle of length $k$ (also called a k-cycle) into $k-1$ two-cycles, we can see that it has $ Sign = (-1)^{k-1} $. And we’ve proved the theorem

Theorem (sign of k-cycle)

Let $ \sigma $ be a k-cycle, then $ Sign(\sigma) = (-1)^{k-1} $.

Already Proved

Next we prove that cycles are disjoint. But first, notice that if $ \sigma^n(i) $ is an element of a k-cycle, then $ \sigma^k(i) = i $, which means that

$$ \begin{align} &\sigma^{n+k} (i) &&= \\ &\sigma^n \circ \sigma^k (i) &&= \\ &\sigma^n(\sigma^k(i)) &&= \\ &\sigma^n (i) \end{align} $$

Theorem (disjoint cycles)

Let

$$ \begin{align} C_1 &= \{ \sigma^1(i), \sigma^2(i), … , \sigma^{k_1}(i) \} \\ &\text{and} \\ C_2 &= \{ \sigma^1(j), \sigma^2(j), … , \sigma^{k_2}(j) \} \\ \end{align} $$

where $ \sigma^{k_1}(i) = i $ and $ \sigma^{k_2}(j) = j $, then either $ C_1 = C_2 $, or $ C_1 \cap C_2 = \emptyset $.

Proof

Suppose the two sets overlap, so for some $m$ and $ n$ we have$ \sigma^n(i) = \sigma^m(j) $. This means that for all $ k \geq 0 $, $ \sigma^{m+k}(i) = \sigma^{n+k}(j) $. From what we showed just before this theorem, that means that the two sets have to have the same size, so $ k_1 = k_2 $, and that means that the two sets have the exact same $ k_1 = k_2 $ members.

QED

That’s all for this entry. There will be more later!