\(\newcommand{\customstrut}{}\)

[Formats: html | pdf]

This is a collection of notes about permutations — all the different ways of ordering a set of distinct elements. In group theory, the group of permutations of size \(n\) is denoted \(S_n\). For example:

You can think of a single permutation as either a particular ordering of the integers 1 through \(n\), or, equivalently, as a 1-1 and onto mapping \(f:\{1,\ldots, n\}\to\{1,\ldots,n\}\). There’s a natural way to write such a mapping \(f\), which is to list out \(f(1), f(2), \ldots, f(n)\) as a string; you can consider the lists of elements of \(S_2, S_3, S_4\) above to be in this string notation. By default, this article will view permutations as mappings.

This article covers the following independent observations about permutations:

• I’ll introduce the idea of a cut-merge operation, and show how this corresponds to a transposition; a transposition is a permutation that exchanges two elements of a set, and changes no others. Given the set {1, 2, 3, 4, 5}, the swap of 2 and 5 would be a transposition; I might write this permutation as \(\tt 1\underline{5}34\underline{2}\).
• Permutations can be split into two kinds: odd permutations and even permutations. Just as odd + even = odd when it comes to integer addition, the analogous rules hold for permutations under composition. For example, if I apply an odd permutation, and then apply an even permutation after that, the result of the combined permutations is itself an odd permutation (and this analogy holds for all combinations of odd/even). I’ll present a simple proof of this breakdown using cut-merge operations.
• I’ll discuss a generalization of the parity (even-ness or odd-ness) of a permutation \(\pi\) that I call the magnitude \(m(\pi)\) of the permutation.
• I’ll define the cycle structure \(\mathsf{cs}(\pi)\), which captures the sizes of cycles in the permutation \(\pi\); and I’ll show that \(\mathsf{cs}(a \cdot b) = \mathsf{cs}(b \cdot a)\) for any two permutations \(a, b\).
• I’ll show that the magnitude \(m(\cdot)\) acts like a norm on the group \(S_n\), and that it can define a coherent distance function \(\mathsf{dist}(\cdot, \cdot)\) on \(S_n\).

When I say these are independent observations, I mean that these ideas are new to me. I have not tried much to check if they are new to the world altogether — in all likelihood, many of these ideas have been discovered by others before me. Still, I think they’re fun ideas worth sharing.

1 Cycle Notation

Any permutation is a specific ordering of a set of distinct elements. This article focuses on finite permutations, and I’ll generally use the variable \(n\) to denote the size of the set being permuted. It’s simple and traditional to think of a permutation as a bijection (a 1-1 and onto mapping) of the first \(n\) integers — for example, here’s a permutation of the set \(\{1, 2, \ldots, 8\}\) in string notation:

\[\pi = 15273648.\qquad(1)\]

Despite the possible confusion with the constant \(\pi=3.141\ldots\), it’s also traditional to use the variable \(\pi\) for a permutation, as (clearly) \(\pi\) stands for “\(\pi\)ermutation.”

There are many fun ways to denote or think about a particular permutation. For example, given \(\pi\) as in (1), we could think of it as the sequence \(\pi_1=1\), \(\pi_2=5\), \(\ldots\), \(\pi_8=8\). We could also think of it as a function \(\pi:[n]\to[n]\), using \([n]\) to denote the integers \(\{1, 2,\ldots, n\}\).

This article uses a particular notation for permutations called cycle notation: the idea for cycle notation is to write out a string of integers in \([n]\) with the interpretation that any consecutive pair \(ij\) indicates that \(i\) is mapped to \(j\), and any \(i\) at the end of a parenthesized group maps to \(j\) at the start of the same group. Our permutation from (1) looks like this in cycle notation:

\[ \pi = (2\;5\;3)(4\;7) \]

because \(\pi(2) = 5\), \(\pi(5) = 3\), and \(\pi(4) = 7\). Each sequence in parentheses wraps around, so \(\pi(3)=2\) and \(\pi(7)=4\). Thus each parenthesized sequence is a cycle. It is understood that any omitted elements are mapped to themselves; since \(\pi(1)=1\), we don’t need to include \(1\) in the cycle notation for \(\pi\).

Examples:

You could write the same permutation many ways in cycle notation; for example:

Among those choices, I consider the last one to be standard because it’s lexicographically first.

2 The Cut-Merge Operation

Now I’ll introduce an operation that acts naturally on the cycle notation of a permutation. Intuitively, a merge is an operation that combines two cycles by concatenating their cycle notation. When two elements — say 3 and 5 — are in different cycles, then I’ll write \(\pi * (3\;5)\) to mean “merge, in \(\pi\), the cycles starting with 3 and 5.”

An example:

What if 3 and 5 were already in the same cycle? Then \(\pi * (3\;5)\) takes on the meaning “cut apart the subcycles starting with 3 and 5:”

or

this last example might be easier to see when you keep in mind that

\[(1\;2\;3\;4\;5) = (\underline{3}\;4\;\underline{5}\;1\;2).\]

Now I’m ready to more carefully define the cut-merge operation \(*(x\;y)\). In the definition below, I’ll write \((x{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot})\) to denote the cycle starting with \(x\); and, analogously, I’ll write \((x{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot}\;y{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot})\) to indicate a cycle containing both \(x\) and \(y\), possibly with other elements indicated by the dots.

The operation cuts a cycle if \(x\) and \(y\) are in the same cycle; otherwise it merges the cycles of \(x\) and \(y\). A shorthand for the definition is:

\[ (x{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot}\;y{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot}) \; \underset{*(x\;y)}{\longleftrightarrow} \; (x{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot})(y{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot}). \]

Note that a merge can still operate on elements not explicitly written in cycle notation. If I write \(e\) to denote the identity permutation, with \(\pi_i=i\;\forall i\), then

\[e * (x\;y) = (x\;y). \]

Similarly,

\[(1\;2) * (2\;3) = (2\;1\;3)\]

because, setting \(x=2\) and \(y=3\), we think of the left side as \((x{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot})(y{\cdot}\kern -0.1pt{\cdot}\kern -0.1pt{\cdot})=(2 1)(3)\).

To state this observation again, I’ll introduce the notation \(\rho_{ab}()\) for the function that swaps input elements \(a\) and \(b\), but otherwise acts as the identity function. Thus \(\rho_{ab}()\) is the function version of the transposition that we would write in cycle notation as \((a\;b)\). With \(\rho_{ab}()\) defined, I can express observation 1 like so:

\[ \left(\pi * (x\;y)\right)(i) = \rho_{xy}(\pi(i)), \qquad(2)\]

where I’m thinking of permutations as functions, so the \((i)\) sub-expression is evaluating the function on input \(i \in \{1, 2, \ldots, n\}\).

I could stop to carefully prove observation 1, but I think you’ll have more fun if you convince yourself it’s true on your own.

Why did I bother to define the cut-merge operation when I could have just started with (2) instead? Because the perspective of the definition I’m using will let us make some interesting further observations, as we’ll see below.

3 The Magnitude and Parity of a Permutation

For example, the permutation \(\pi = (2\;5\;3)(4\;7)\) has 5 cycle elements and 2 cycles, so \(m(\pi) = 3\).

Notice that \(m(\pi)\) remains the same if we include singleton cycles in our cycle notation. It would be nonstandard to include singletons, but it would still be a consistent notation. Continuing our example, \(\pi = (1)(2\;5\;3)(4\;7)(6)\) \(\Rightarrow\) \(m(\pi) = 7 - 4 = 3\), as before. This leads to:

Let’s see why the definition of \(m(\pi)\) is interesting.

Parts (i) and (ii) are easy to check.

Part (iii) is clear from the cut-merge perspective in that (a) we cannot build \(\pi\) in fewer operations, based on (i); and (b) we can indeed build \(\pi\) in \(m(\pi)\) merges by appending together the appropriate singletons one at a time. For example:

Starting now, I’ll write simply \(\sigma \tau\) or \(\sigma\cdot\tau\) to denote the composition of permutations \(\sigma\) and \(\tau\). Using observation 1, we can see that the construction pattern used in (3) must work for any cycle that we want to write as a composition of transpositions:

In other words, every permutation is the product of \(m(\pi)\) transpositions, and cannot be the product of fewer. It could be the product of more, though:

\[ (1\;2\;3) = (1\;2)(1\;3)(8\;9)(8\;9). \]

Now we’re ready to define an interesting way to classify all permutations into two different types:

As soon as we call something even or odd, we expect some kind of behavior like this to happen:

\[ \begin{alignedat}{2} \text{even} &+ \text{even} &&= \text{even} \\ \text{odd} &+ \text{even} &&= \text{odd} \\ \text{odd} &+ \text{odd} &&= \text{even}. \\ \end{alignedat} \qquad(4)\]

It turns out that these rules do indeed hold true in the sense that, for example, if we compose an odd permutation with another odd permutation, the result is an even permutation. Next I’ll explain why the intuitive identities of (4) are true for permutations.

The key to the proof is to see that, for any sequence of transpositions \(t_1, t_2, \ldots, t_k\):

This fact follows from observation 3. In more detail: Certainly \(m(e)=0\) (recall that \(e\) is the identity permutation); this corresponds to \(k=0\) in (5), an empty product. Now for larger values of \(k\): If \(\pi=t_1t_2\cdots t_{k-1}\) and we compose \(\pi\) with \(t_k\) (move from \(\pi\) to \(\pi\cdot t_k\)), then the parity (even/odd-ness) of the permutation switches because \(m(\pi\cdot t_k) = m(\pi) \pm 1\) by observation 3. So \(\pi\cdot t_k\) is even iff \(\pi\) is odd. This is enough to complete a proof of (5) by induction on \(k\).

It will be useful to define the sign function of a permutation \(\pi\) like so: \[\textsf{sign}(\pi) := \begin{cases} \phantom{-}1 & \text{if $\pi$ is even, and} \\ -1 & \text{if $\pi$ is odd.} \end{cases}\] Notice that \(\textsf{sign}(\pi) = (-1)^{m(\pi)}\).

When we use this sign function, we’re essentially moving from an additive view of even/odd-ness and into a multiplicative view — but the two views are equivalent. For example, the equation \[\text{even} + \text{odd} = \text{odd}\] becomes \[(-1)^\text{even}(-1)^\text{odd} = (-1)^\text{odd}.\] The general equation \((-1)^a(-1)^b = (-1)^{a+b}\) provides the equivalence.

We can now state the idea of (4) both more formally and more succinctly.

Let’s see why (6) is true. Let \(k = m(\sigma)\) and \(k' = m(\tau)\). Then, using observation 3(iii), we can find transpositions \((t_i)_1^k\) and \((t'_i)_1^{k'}\) so that \[\begin{align*} \sigma &= t_1 \cdots t_k \\ \tau &= t'_1 \cdots t'_{k'}. \end{align*}\] Then

This completes the proof of (6). And (6) expresses the same idea as (4), so that we have now justified all of those formulae.

Moving back to group theory: Notice that if \(\sigma\) and \(\tau\) are both even permutations, then so is \(\sigma\tau\). In other words, the subset of even permutations is closed under composition, so that they form a subgroup of \(S_n\). This subgroup is called the alternating group. Since odd permutations are not closed under composition, they don’t form a subgroup.

4 Previous Approaches to Permutation Parity

I like the cut-merge proof of (6) because it provides an intuition for why parity makes sense for permutations. In a nutshell, every permutation is a sequence of transpositions (cut-merges), and every transposition is a flip of the parity because the magnitude must either increase or decrease by 1.

Here’s a sketch of the intuitive paths we’ve crossed:

I’ll contrast the proof above of (6) with two other approaches.

4.1 Herstein’s Proof

In his book Topics in Algebra, I.N. Herstein uses the Vandermonde polynomial:

\[ p(x_1,\ldots, x_n) := \prod_{i<j}(x_i-x_j). \]

Given a permutation \(\pi\), we can now define

\[ \pi(p(x_1,\ldots, x_n)) := p(x_{\pi_1},\ldots, x_{\pi_n}). \]

The polynomial \(\pi(p)\) is still a product of \((x_i - x_j)\) for all \(i\ne j\), but the sign of the polynomial may change. For example, when \(n=3\), and \(\pi=(1\;2)\):

Since \(\pi(p) = \pm p\) for any \(\pi\), we can (re)define

(Temporarily forget our original definition of \(\textsf{sign}(\pi)\). We’ll re-prove (6), and because our new and old \(\textsf{sign}()\) functions are the same on \(e\) and on transpositions, it will follow that they are in fact the same function.)

Notice that

\[\pi(-p) = -\pi(p)\qquad(8)\]

based on the definition of \(\pi(p)\).

This means that, for any two permutations \(\sigma\) and \(\tau\),

In summary, \(\textsf{sign}(\sigma\cdot\tau) = \textsf{sign}(\sigma)\cdot\sigma(\tau)\), which confirms (6) for this new definition of \(\textsf{sign}()\). This proof provides less insight than the cut-merge approach as to why (6) is true — into what is going on behind the scenes to make things click.

4.2 Artin’s Proof

The other approach I’ll consider is from the book Algebra by Michael Artin. This second alternative proof works by translating permutations into the language of linear algebra, and relies upon properties of the determinant of a matrix. On the off chance that you’re not fluent in properties of determinants, you can skim or skip this section and safely resume reading afterwards (the remainder of this note does not rely on linear algebra). I’m not a huge fan of this proof because it’s so easy to get lost in the details of tracking the relationship between vector coordinates and how permutations act on them. I’ll break the proof down into small steps to walk you through the dance of indices.

I’ll use the variable \(e_i\) to denote the column vector of length \(n\):

\[e_i = \begin{array}{l} 0 \\ 0 \\ \vdots \\ 1 \longleftarrow i^\text{th}\text{ place}. \\ \vdots \\ 0 \\ 0 \\ \end{array}\]

For example, if \(n=3\), then

\[ e_1 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \quad e_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \quad e_3 = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}. \]

Now I can define, for permutation \(\pi\), the \(n\times n\) matrix \(M_\pi\) as having \(e_{\pi_i}\) for its \(i^\text{th}\) column; this is how Artin represents a permutation as a matrix. For example, if \(\sigma = (3\;2\;1)\), then \(M_\sigma = \left(\begin{smallmatrix}&1\\ &&1\\ 1 \end{smallmatrix}\right)\).

Let’s see why this matrix definition makes sense. Using the column-expansion perspective of matrix multiplication, with \(x=\begin{pmatrix}x_1 \\ \vdots \\ x_n\end{pmatrix}\),

In other words, when we multiply \(M_\pi\) on the left of a column vector, we take whatever value was in the \(i^\text{th}\) row and move it to the \(\pi_i^\text{th}\) row. For example, \(M_\sigma\left(\begin{smallmatrix}1 \\ 2 \\ 3 \end{smallmatrix}\right) = \left(\begin{smallmatrix}&1\\ &&1\\ 1 \end{smallmatrix}\right) \left(\begin{smallmatrix}1 \\ 2 \\ 3 \\ \end{smallmatrix}\right) = \left(\begin{smallmatrix}2 \\ 3 \\ 1 \\ \end{smallmatrix}\right)\). Continuing with this intuition, left-multiplying by \(M_\tau M_\sigma\) is like performing \(\sigma\) followed by \(\tau\) in the sense that the \(i^\text{th}\) row is moved to the \(\tau(\sigma(i))^\text{th}\). I personally prefer to have statements like this algebraically checked, so in the next couple of paragraphs, I’ll spell out more carefully why this is true.

It’s useful to slightly rewrite (9) as in the right-hand expression below, using the notation \([v]_i\) to indicate the \(i^\text{th}\) coordinate of column vector \(v\):

So left-multiplying by both \(M_\tau\) and \(M_\sigma\) works like so, using (10):

Writing \(M_{\sigma\tau}\) for the matrix of permutation \(\sigma\tau\), we have

Together, (11) and (12) confirm that: \[ M_{\sigma\tau} = M_\tau M_\sigma \] in the sense that they act the same in matrix multiplications, from which we can conclude that they are in fact identical matrices.

At long last, I’m ready to (re)define the \(\textsf{sign}()\) function, following Artin: \[\textsf{sign}(\pi) := \det(M_\pi),\] where \(\det()\) is the determinant function of a square matrix.

It turns out that this definition is also consistent with our earlier definitions because:

• \(\det(M_t) = -1\) for any transposition \(t\) because exchanging any two columns of a matrix negates its determinant; and
• when \(\pi=\prod_{i=1}^k t_i\) for transpositions \((t_i)_1^k\), \(\textsf{sign}(\pi) = \det(M_\pi)\) \(= \det(\prod_{i=1}^kM_{t_i})\) \(= (-1)^k =\) our cut-merge definition of \(\textsf{sign}()\), based on (5).

In using this approach, Artin is able to show that (6) holds simply by delegating the work to the properties of matrix determinants. In particular, using the fact that \(\det(AB) = \det(A)\det(B)\):

Artin’s proof is certainly valid, though I think it offers less insight into why equation (6) holds when compared to the cut-merge proof.

5 Cycle Structures

Let \(\sigma = (1\;3)(2\;4\;5)\) and \(\tau = (1\;4)(2\;3)\). Then \[\begin{align*} \sigma \tau &= (1\;2)(3\;4\;5), \text{ and} \\ \tau \sigma &= (1\;5\;2)(3\;4). \end{align*}\]

Notice that these two permutations each have one cycle of length 2 and another of length 3. Is this a coincidence? It turns out that this similarity of structure will always hold between \(\sigma \tau\) and \(\tau \sigma\). I’ll have to define a new concept before I can precisely formulate this relationship.

As a shorthand, I’ll write \((f(1), f(2), f(3), \ldots)\) to express a cycle structure. For example, when \(n=5\), the permutation \((1\;2)(3\;4\;5)\) has cycle structure \((0, 1, 1)\); so does the permutation \((1\;5\;2)(3\;4)\). Now I can state:

I’ll provide two proofs because they each shed their own light on why this is true.

Proof 1 \(\quad\) Given permutation \(\pi\), I’ll write \(\textsf{order}_\pi(i)=k\) to mean that \(\pi^k(i)=i\), and there is no \(\ell < k : \pi^\ell(i)=i\). To prove the observation, it’s sufficient to show that there is a 1-1 and onto mapping \(f:[n]\to[n]\) such that \(\textsf{order}_{\sigma\tau}(i)=k \Leftrightarrow \textsf{order}_{\tau\sigma}(f(i))=k\).

Suppose \(\textsf{order}_{\sigma\tau}(i)=k\). Let \(j=\tau^{-1}(i)\). In the following equations, I’ll use a left-to-write, input-to-output notation, where \(i\pi\) means \(\pi(i)\) and \(i\sigma\tau\) means \(\tau(\sigma(i))\). We have: \[ i = i(\sigma\tau)^k = j\tau(\sigma\tau)^k = j(\tau\sigma)^k\tau. \] Now apply \(\tau^{-1}\) to the left-most and right-most expressions above to arrive at:

On the other hand, if \(\ell=\textsf{order}_{\tau\sigma}(j)\), then

Combining (13) and (14), \[ \textsf{order}_{\sigma\tau}(i) = \textsf{order}_{\tau\sigma}(j=\tau^{-1}(i)), \] and it turns out that \(\tau^{-1}\) is the mapping \(f:[n]\to [n]\) we needed to complete the proof. \(\square\)

Proof 2 \(\quad\) Given any permutation product \(\sigma\tau\), we can decompose \(\tau\) into transpositions as in \(\tau = t_1\cdots t_k\). Now we can think in terms of a series of smaller steps that carry us from \(\sigma\tau\) over to \(\tau\sigma\): \[\begin{align*} \pi_0 &= \sigma\tau = \sigma\cdot t_1 \cdots t_k \\ \pi_1 &= t_k \cdot \sigma \cdot \tau \cdot t_k^{-1} = t_k\sigma t_1\cdots t_{k-1} \\ \vdots \\ \pi_k &= t_1\cdots t_k \sigma \tau t_k^{-1}\cdots t_1^{-1} = \tau\sigma. \end{align*}\] Each small step here can be characterized as \(\pi_{i+1} = t_{k-i}\pi_i t_{k-i}\), using the fact that \(t_j^{-1}=t_j\), which is true for any transposition. So the problem is reduced to showing that, for any permutation \(\pi\) and transposition \(t\), \[ \mathsf{cs}(\pi) = \mathsf{cs}(t \pi t). \qquad(15)\] It turns out that applying \(t=(x\;y)\) in this manner simply swaps the places of \(x\) and \(y\) in the cycle notation of \(\pi\). For example: \[ (1\;3)(\underline{1}\;2\;5\;\underline{3}\;7)(1\;3) = (\underline{3}\;2\;5\;\underline{1}\;7). \] This confirms (15), which completes the proof. \(\square\)

Notice that observation 4 can be generalized for any rotation of any finite product of permutations. For example,

The equation \(\mathsf{cs}(\sigma\tau) = \mathsf{cs}(\tau\sigma)\) makes it tempting to suspect that cycle structure is preserved no matter what order we multiply a given list of permutations. For example, we could ask if the following identities would hold for any three permutations \(a,b,c\):

for all the orderings of \(a,b,c\); and similarly for any finite list of permutations.

But this is not true in general. For example, if \(a = (1\;2\;3)\), \(b = (1\;2)\), \(c=(1\;3)\), then \[ \begin{alignedat}{2} a\;b\;c &= (1\;2\;3)(1\;2)(1\;3) &&= (1\;3\;2) \\ c\;b\;a &= (1\;3)(1\;2)(1\;2\;3) &&= e. \end{alignedat} \] There is a natural follow-up question to observation 4 which I can state clearly once I’ve provided a couple new definitions.

Given any permutation \(\pi\), let \[\textsf{flips}(\pi) := \{b\cdot a: \pi = a\cdot b\}. \] And let

This is similar to asking: Given \(\pi\) and the freedom to decompose it as \(\pi=a\cdot b\), what are all the possible values of \(b\cdot a\)?

The answer arises from a simple permutation decomposition. Let’s start with:

The observation is true because \[ (i\tau)(\tau^{-1}\sigma\tau) = i\sigma\tau; \] that is, if \(\sigma' := \tau^{-1}\sigma\tau\) and \(\sigma : i \mapsto j\), then \(\sigma' : i\tau \mapsto j\tau\).

For example, if \(\tau = (2\;5\;3)\) and \(\sigma = (1\;2)(3\;4\;5)\), then

Note that this replacement operation is specific to cycle notation. If we were to instead write out \(\pi\) as the string \(\pi_1 \pi_2 \ldots \pi_n\), then the corresponding string for \(\tau^{-1}\sigma\tau\) is no longer replacement with \(\tau\). I’ll illustrate this distinction with an example:

To help build intuition for the set \(\textsf{same$\\\_$cycles}(\pi)\), we can choose a canonical “first” element of \(\textsf{same$\\\_$cycles}(\pi)\). A simple way to do this it to treat all singleton-free cycle notations in \(\textsf{same$\\\_$cycles}(\pi)\) as strings, treating the “)” character as the last in the alphabet (we’ll ignore the “(” character for the sake of ordering). Then we can define \(\textsf{canon}(\pi)\) to be the lexicographically first element of \(\textsf{same$\\\_$cycles}(\pi)\). For example, \(\textsf{canon}(3\;4\;2)(1\;5) = (1\;2\;3)(4\;5)\). If we had not specified the ordering of “)”, then it would be unclear if \((1\;2)(3\;4\;5)\) or \((1\;2\;3)(4\;5)\) were first.

Now we’re ready for:

Proof \(\quad\) We can use observation 5 to find \(\tau\) so that \[ \pi = \tau^{-1}\sigma\tau. \qquad(16)\] Let \(a = \tau^{-1}\) and \(b=\tau\pi\). Then \[ \begin{alignedat}{2} ab &= \pi \\ ba &= \tau\pi\tau^{-1} = \sigma\quad\text{by (16).} \end{alignedat} \] \(\square\)

The main idea of this proof is to use observation 5 to see that \(\mathsf{cs}(\tau^{-1}\sigma\tau) = \mathsf{cs}(\sigma)\) for any \(\tau\). As the proof shows, by choosing the right \(\tau\), we can make \(\tau^{-1}\sigma\tau\) equal to anything in \(\textsf{flips}(\sigma)\). And anything of the form \(\tau^{-1}\sigma\tau\) is in \(\textsf{flips}(\sigma)\) by considering \(a=\tau\) and \(b=\tau^{-1}\sigma\).

Note that the \(\tau\) used in the proof may not be unique because there are different cycle notation strings for the same permutation. Consider \(\pi=(1\;2)\) and \(\sigma=(3\;4)\). We can convert \(\pi\) into \(\sigma\) in different ways:

The above diagram is an informal way of writing that \[ \tau^{-1}\pi\tau = (3\;4) = (4\;3) = \tau'^{-1}\pi\tau'. \]

6 The Magnitude is Like a Norm

In this section I’ll point out some interesting properties of the magnitude function.

Proof \(\quad\) Start by noticing that \(m(\pi)\) is the least number of transpositions by which we can get from \(e\) to \(\pi\); ie, \(m(\pi)\) is the least integer for which we can write \(\pi=\prod_{i=1}^{m(\pi)}t_i\) for some transpositions \((t_i)_1^{m(\pi)}\).

Considering each of \(\pi\) and \(\sigma\) as a composition of this minimal number of transpositions, parts (i) and (ii) are straightforward.

Part (iii) follows since the cycle notation for \(\pi^{-1}\) is simply the reverse of the cycle notation for \(\pi\).

Part (iv) follows from observation 4. \(\square\)

In many ways, the magnitude of a permutation acts like a vector norm — the key difference is that we don’t have a meaningful interpretation of \(k\pi\) for any \(k\in\mathbb{R}\), so we don’t have the additional rule \(m(k\pi) = |k|\cdot m(\pi)\).

This makes it interesting to define a notion of distance between permutations:

I’ll justify why this definition makes sense. Let \(x=\pi^{-1}\sigma\). Then \(\pi x=\sigma\), so \(\mathsf{dist}(\pi, \sigma)\) is measuring the fewest “hops” — transpositions — needed to get from \(\pi\) to \(\sigma\).

We’d like a good distance function to be symmetric, and luckily for us, this one is:

the middle equality following since \(m(\pi) = m(\pi^{-1})\) by observation 6. This symmetry addresses the apparent inelegance of the definition; indeed, the definition may appear to treat \(\pi\) and \(\sigma\) differently, but the end result does not depend on the order of these inputs to \(\mathsf{dist}()\).

To conclude this note, I’ll ask a fun and intriguing question whose answer I don’t yet know:

References