Outreach module (grades 9-12)
Part 4: Length and parity
Length and parity
The next goal is to measure how complicated a permutation is. The diagrams from the previous page suggest that crossings should be counted.
This page turns that idea into the definition of length, uses length to define even and odd permutations, and then explains why adjacent 3-cycles generate every even permutation.
One useful way to picture a permutation is to place \(1,2,3,4,5\) across the top and again across the bottom, then connect \(i\) on top to \(\sigma(i)\) on the bottom. The diagrams below show four examples in \(S_5\).
Fix \(i<j\). In the diagram for \(\sigma\), the string starting at \(i\) crosses the string starting at \(j\) exactly when \(\sigma(i)>\sigma(j)\).
Definition
The length of \(\sigma\in S_n\) is The length of sigma is the number of pairs i less than j for which sigma of i is greater than sigma of j. \[ \ell(\sigma)=\#\{(i,j):1\leq i<j\leq n \text{ and } \sigma(i)>\sigma(j)\}. \] In other words, \(\ell(\sigma)\) counts the out-of-order pairs.
For the four examples above, The four example permutations have lengths 0, 2, 2, and 10. \[ \ell(\sigma_1)=0, \qquad \ell(\sigma_2)=2, \qquad \ell(\sigma_3)=2, \qquad \ell(\sigma_4)=10. \]
Compute the length of the following permutations from Parts 3 and 4.
1. It has length \(2\): the inversions are \((3,1)\) and \((3,2)\).
2. It has length \(2\): the inversions are \((2,1)\) and \((3,1)\).
3. It has length \(4\): the inversions are \((4,1)\), \((4,3)\), \((4,2)\), and \((3,2)\).
4. It has length \(4\): the inversions are \((5,2)\), \((5,4)\), \((5,3)\), and \((4,3)\).
5. Every pair is out of order, and there are \(\binom{6}{2}=15\) pairs.
A permutation is even if \(\ell(\sigma)\) is even, and odd if \(\ell(\sigma)\) is odd.
Parity rule
Length gives a useful parity on permutations: even composed with even is even, odd composed with odd is even, and composing one even permutation with one odd permutation gives an odd permutation.
\([2\ 1\ 4\ 3\ 5]\) has length \(2\).
\([1\ 3\ 2\ 4\ 5]\) has length \(1\).
\([1\ 2\ 3\ 4\ 5]\) has length \(0\), so it is even.
1. It is odd, because it has one inversion.
2. It is even, because it has two inversions.
3. It is even.
For \(1\leq i\leq n-1\), let \(s_i=(i\ i+1)\). This swaps neighboring positions \(i\) and \(i+1\) and leaves everything else fixed.
If a list is not yet in order, some adjacent pair is out of order. Swapping that pair moves the list closer to the identity. Repeating this eventually sorts the list.
For example, One sorting chain sends 3, 1, 4, 2 to 1, 3, 4, 2, then to 1, 3, 2, 4, and finally to 1, 2, 3, 4. \[ [3\ 1\ 4\ 2]s_1=[1\ 3\ 4\ 2],\qquad [1\ 3\ 4\ 2]s_3=[1\ 3\ 2\ 4],\qquad [1\ 3\ 2\ 4]s_2=[1\ 2\ 3\ 4]. \]
Running this backward gives \([3\ 1\ 4\ 2]=s_2s_3s_1\).
The list \([3\ 1\ 4\ 2]\) has inversions \((3,1)\), \((3,2)\), and \((4,2)\), so its length is \(3\).
After multiplying by \(s_1\), we get \([1\ 3\ 4\ 2]\), which has length \(2\). In general, Multiplying by one adjacent transposition changes the length by exactly 1, so it flips parity. \[ \ell(\sigma s_i)=\ell(\sigma)\pm1. \]
Every adjacent transposition flips parity. So if \(\sigma=s_{i_1}s_{i_2}\cdots s_{i_N}\), then the parity of \(N\) must agree with the parity of \(\ell(\sigma)\).
1. One answer is \([2\ 4\ 1\ 3]=s_1s_3s_2\).
2. It is odd, because one adjacent transposition changes the length by \(1\).
3. Both factorizations start at the identity and flip parity once per adjacent swap, so both must end with the same parity as \(\ell(\sigma)\).
The set of even permutations is called the alternating group on \(n\) letters and is denoted \(A_n\).
Theorem
For \(1\leq i\leq n-2\), let \(t_i=(i\ i+1\ i+2)\). Every element of \(A_n\) can be written as a product of adjacent 3-cycles of the form \(t_i\) and \(t_i^{-1}\).
If \(\sigma\in A_n\), then a factorization into adjacent transpositions has an even number of terms: An even permutation sigma can be written as a product of an even number of adjacent transpositions. \[ \sigma=s_{i_1}s_{i_2}\cdots s_{i_{2m}}. \]
Regroup this as \((s_{i_1}s_{i_2})(s_{i_3}s_{i_4})\cdots(s_{i_{2m-1}}s_{i_{2m}})\).
When the two indices are adjacent, Two adjacent transpositions combine to give an adjacent 3-cycle or its inverse. \[ s_i s_{i+1}=(i\ i+1\ i+2)=t_i, \qquad s_{i+1}s_i=(i\ i+2\ i+1)=t_i^{-1}. \]
If \(i<j\), insert repeated factors to write If i is less than j, then the product s sub i s sub j can be rewritten as a product of adjacent 3-cycle pieces. \[ s_is_j=(s_is_{i+1})(s_{i+1}s_{i+2})\cdots(s_{j-1}s_j), \] and each parenthesized term is an adjacent 3-cycle. The case \(i>j\) gives inverse 3-cycles.
So every even permutation can be built from adjacent 3-cycles. This is the form we need for the puzzle.
1. Track what happens to \(i\), \(i+1\), and \(i+2\): \(i\mapsto i+1\), \(i+1\mapsto i+2\), and \(i+2\mapsto i\), while all other entries stay fixed.
2. \(s_2s_3=(2\ 3\ 4)\), which matches the rule with \(i=2\).
3. \([2\ 3\ 1\ 4\ 5]=(1\ 2\ 3)=t_1\).
4. It has one inversion, so it is odd.
To use parity on the puzzle, two things have to happen.
The next page does exactly this: first for the 7 puzzle, where the mechanism is easier to see, and then for the fifteen puzzle.