The Arithmetic of Permutations

One may have noticed that in a braid, the strands that start out at given positions don't always end up in those same positions. If we color the strands, this has the effect of changing the order of the colors seen on one end of the braid from what they were on the other.

As an example, in the braid below, from the left side to the right, the order of colors changes in the following way: $$\{\textrm{red, green, blue, orange, black}\} \longrightarrow \{\textrm{red, black, green, blue, orange} \}$$

Interestingly, focusing only on how the order of the colors has changed yields another strange arithmetic...

Let us call the act of changing the order of some sequence of $n$ elements a permutation of $n$ elements.

Note: one can also talk about permutations in the context of an infinite number of elements -- but to keep things simple for the moment, let us assume all the permutations discussed below involve only a finite number of elements $n$

The generic term "elements" used in the definition above is purposeful -- these might be colored strands in a braid, or people in a line, or paintings on a wall. We don't really care what the "elements" are -- only how their order is changing.

One natural notation we might adopt to identify a permutation is to create a matrix whose top row consists of the consecutive numbers from $1$ to $n$ in that order, representing the initial positions of the elements, and whose bottom row consists of the positions of the elements after the permutation has occurred.

As an example, we might represent the permutation of colors induced by the braid above with the following -- where each vertical pair corresponds to the positions where a single color started and ended. $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 3 & 4 & 5 & 2 \end{bmatrix}$$

Note also that one can easily find a braid on $n$ strands that induces any given permutation on $n$ elements. (Indeed, there are many different braids for any single given permutation.)

As an example, consider the permutation given by $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 4 & 6 & 5 & 2 \end{bmatrix}$$ Simply write to columns of numbers $1,2,3,4,5,6$ and connect with straight lines of different colors the vertical pairs seen in the matrix above (see the image on the left, below). Remember, we don't care anymore about which strand crosses over which other strand -- so these can be chosen at random. The only thing one needs to worry about is more than two lines crossing at the same exact point. In such instances, one can always "jiggle" the strands involved left or right a bit to avoid that from happening. Then we can "clean up" the braid (see the image on the right, below) to more easily identify its braid word, if that is desired.

   

Given that we can always find a braid in this way that will induce any given permutation we encounter, permutations on $n$ elements will share many of the same properties enjoyed by braids on $n$ strands.

Recall that we could combine braids (with an equal number of strands) through concatenation to create a new braid. We did this by placing one braid after the other, and then fusing them together.

In a very connected way, we can combine any two permutations (on $n$ elements) to produce a third permutation (also on $n$ elements) by applying one permutation after the other. The resulting permutation is called the composition of the other two.

As it seems timely to mention it -- notice this means this operation of "composing permutations" is closed.

We must be careful though -- depending on which permutation we apply first, we run the risk of getting different permutations. So to be concrete: if $P_1$ and $P_2$ represent two permutations of $n$ elements, let us define their composition (product?), denoted by $P_1 * P_2$, to be the permutation produced by applying $P_1$ first and then $P_2$ to the result.

Note: we choose this order so that we can draw upon what we know about braids -- but be aware in some textbooks and other resources the reader might find online, such compositions are evaluated from right to left instead.

As an example, $$\begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 3 & 5 & 1 \end{bmatrix} * \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 2 & 1 & 3 & 5 \end{bmatrix}$$

Here's the same product represented in a more braid-like form:

Notice, the permutations that such "products" represent can be quickly found by simply tracing where each position/color goes under the first permutation, and then where that position goes under the second permutation.

For example, notice that above [the element at position] $1$ moves to [position] $2$ in the first permutation. Also notice that $2$ similarly moves to $4$ in the second permutation. Thus, when both of these happen in the product/composition of the two permutations, we have $1$ moving to $4$. This gives us the first column of the product matrix.

Likewise (and reading each arrow shown as "moves to"), we see $2 \rightarrow 4$ in the first permutation, and $4 \rightarrow 2$ in the second. So $2 \rightarrow 2$ in their product, as indicated by the second column in the product matrix.

Continuing in this fashion: $3 \rightarrow 3$ in the first, $3 \rightarrow 1$ in the second, so $3 \rightarrow 1$ in their product; $4 \rightarrow 5$ in the first, $5 \rightarrow 3$ in the second, so $4 \rightarrow 3$ in their product; and finally $5 \rightarrow 1$ in the first, $1 \rightarrow 5$ in the second, so $5 \rightarrow 5$ in their product. These pairs give us the 3rd, 4th, and 5th columns of the product matrix, respectively.

Readers will want to ensure they see how to trace "what goes to what" to produce the product matrix directly from the two matrices being multiplied (without having to draw the braid-like picture).

As a matter of convenience (and as we have done before for both braids and the multiplication of variables representing real values), we often drop the "$*$" symbol (i.e., we write $P_1 P_2$ instead of $P_1 * P_2$).

Like their braided cousins, permutations are not generally commutative. As an example,

$$\begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{bmatrix} \quad \textrm{ but } \quad \begin{bmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{bmatrix}$$

However, permutations on $n$ elements are associative. That is to say, for any such permutations $P_1, P_2, P_3$, we have $(P_1 P_2) P_3 = P_1 (P_2 P_3)$, as the following suggests: $$ \begin{array}{rcl} \left( \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{bmatrix} \right) \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{bmatrix} & = & \begin{bmatrix} 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{bmatrix}\\\\ & = & \begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 3 & 2 \end{bmatrix} \end{array} $$

 

$$ \begin{array}{rcl} \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{bmatrix} \left( \begin{bmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{bmatrix} \right) & = & \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{bmatrix}\\\\ & = & \begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 3 & 2 \end{bmatrix} \end{array}$$

We can define a special identity permutation on $n$ elements that leaves the order of the corresponding $n$ elements unchanged, denote this permutation by $I$:

$$\begin{bmatrix} 1 & 2 & 3 & \cdots & n\\ 1 & 2 & 3 & \cdots & n \end{bmatrix}$$

Not surprisingly given its name, this permutation functions in the anticipated way: For any permutation $P$, we have $P * I = I * P = P$. The reader should check this on a permutation $P$ of their choosing.

Inverses exist too, and are simply constructed by flipping the vertical pairs seen upside-down and re-ordering the columns to again see $1$ to $n$ in the top row: $$ \begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 3 & 2 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 3 & 1 \end{bmatrix} $$

The reader might want to verify the product of the permutation and its inverse shown above is indeed the identity permutation. This should be checked in both directions, as $x$ and $x^{-1}$ are inverses if and only if $x \cdot x^{-1} = x^{-1} \cdot x = I$.


Cycle Notation

Another notation for describing permutations exists -- one that can be a bit easier to both write and type than the matrix form used previously, and which highlights the "cycles" present in a permutation.

To what "cycles" do we refer? Consider the permutation

$$P = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 1 & 4 & 7 & 5 & 3 & 6 \end{bmatrix}$$ In this permutation $P$, note that each number in $1,2,\ldots,n$ "goes to" some single other value in $1,2,\ldots,n$.

As examples: $3 \rightarrow 4$ and $4 \rightarrow 7$

Given that one of these two facts tells us what leads to $4$ and the other tells us where $4$ leads, one might be tempted to collapse these two facts into a more compact form, and write $3 \rightarrow 4 \rightarrow 7$ instead.

However, this begs the question: "Where does $7$ then go?" -- which in turn makes us wonder where that number will go. In this case, these next two value are $6$ and $3$, respectively.

We can keep asking where each new value "goes" under this permutation $P$, but a pattern quickly emerges: $$3 \rightarrow 4 \rightarrow 7 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 7 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 7 \rightarrow 6 \rightarrow \cdots$$

Do you see how the above just "cycles" through the values $3,4,7,6$ over and over? Of course, had we started with either $4$, $7$, or $6$ instead, we would have seen the same cycle.

So this is one of the cycles present in our given permutation $P$. However, we haven't captured everything this permutation does yet, as there are other values associated with $P$ that "go places" that this cycle doesn't address.

Looking at one of these, say $1$, gives us another cycle: $$1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow \cdots$$

The only remaining value not yet considered is $5$, but this too leads to a (trivial) cycle: $$5 \rightarrow 5 \rightarrow 5 \rightarrow \cdots$$

Indeed, regardless of the permutation in question -- if we consider what happens to any number under repeated applications of that permutation, we will ALWAYS see the resulting sequence eventually start to repeat in some cycle as we must eventually run out of values we haven't yet seen, but every number goes somewhere.

As a matter of verbiage, the number of unique values that appear before it repeats is known as the length of the cycle.

The three cycles found above (with lengths $4$, $2$, and $1$), when taken together, completely describe where all the value $1,2,3,\ldots,n$ all go under our permutation $P$. Wrapping the repeating part of each in parentheses so we can distinguish the cycles from one another, we can thus describe $P$ with $$(3476)(12)(5)$$

The above is an example of a permutation written in cycle notation.

Multiplying/composing permutations written in cycle notation can notably be easily done -- and without having to first translate them back to their matrix forms. Consider the product of permutations $P = (153)(24)$ and $Q = (12)(3)(45)$:

$$PQ = (153)(24) * (12)(3)(45) = (14)(253)$$

Let's dissect how we calculated the expression on the right side of the equal sign:

Note that -- as long as the number of elements being permuted is clear from the context -- writing cycles of length $1$ is not really needed and we often omit these. Just remember if a number isn't present in a permutation's cycle notation, it "goes to" itself. This adds a little more for us to remember, but saves our pencil lead! 😜

As an example, we could express the evaluation of the product just seen more compactly by writing the following (note the absence of the previously seen "$(3)$" in the second factor): $$(153)(24) * (12)(45) = (14)(253)$$

Adopting this convention also allows us to view each individual cycle as a permutation in its own right (called a cyclic permutation), with these all multiplied together to produce the overall permutation.

So for example, the following two expressions are equivalent: $$(153) * (24) = (153)(24)$$ as is quickly verified by looking at the same product in matrix form: $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 2 & 1 & 4 & 3 \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 4 & 3 & 2 & 5 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3 \end{bmatrix} $$

There is one time however, when this convention of not writing any cycles of length $1$ creates a problem. Remember, the identity permutation is the permutation where everybody "goes to" themselves -- and thus, every cycle is a cycle of length $1$. We can't very well write nothing at all for this special permutation! As a work-around, we often denote the identity permutation of $n$ elements either with its own special symbol like the "$I$" used earlier, or something equally unambiguous like "$(1)$".


Transpositions

Again drawing upon our previous work with braids, let us re-examine the braid that appeared at the beginning of this section -- only this time with the crossings "jiggled" far enough left or right so that no two happen simultaneously as we scan the braid from left to right:

Notice how each individual crossing can be interpreted as a cycle of length $2$, otherwise known as a transposition.

With this perspective, it is easy to write re-write the overall permutation of $5$ elements given as a product of $11$ transpositions:

$$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 3 & 4 & 5 & 2 \end{bmatrix} = (2345) = (12)(34)(12)(45)(23)(45)(23)(45)(34)(23)(45)$$

As it is always possible to find a braid that induces a given permutation, and every braid can be "jiggled" so no simultaneous crossings occur -- it must also be the case that we can always express any given permutation as some sequence of transpositions. In fact, there will always be multiple ways to do this -- with some of these "chains" of transpositions longer than others.

Just in case you are thinking that all we are doing is writing the braids with some new bizarre notation, remember that all of the information about which strand crossed "over" or "under" another in the braid has been lost in the way we write permutations. While elementary braids $x_i$ and $x_i^{-1}$ are different braids, the transpositions $(i,i+1)$ and $(i+1,i)$ are the same transposition. Related to this, again remember that for any single permutation like the one above -- there can be many different, non-equal braids that induce it.

That cautionary comment aside, braids can still help "guide the way" when dealing with permutations.

As an example, we've already noted that permutations, like braids, are not generally commutative. That is to say, if $P$ and $Q$ are both permutations, $PQ$ and $QP$ are not always the same permutation.

However, "distant elementary braids" did commute. We said two elementary braids $x_i$ and $x_j$ were "distant" when $|i-j| \ge 2$, but this was really just a very compact way of saying the two crossings in question didn't involve any strands at the same position.

Of course there is a direct analog to this in the language of transpositions: When transpositions are disjoint (meaning they do not move any common elements), they commute.

Realizing that any cycle can be written as a product of transpositions of pairs of elements that appear in that cycle, the above result can be quickly generalized to the even more powerful rule:

Cycles that share no common elements (i.e., disjoint cycles) commute.

As an example, notice that the calculations below show that the first two cycles commute with each other (they have no common elements), but not the third cycle (which shares a $2$ with the first cycle and a $3$ and $4$ with the second).

$$\begin{array}{rcl} (12)(345)(243) & = &(1452)\\ (345)(12)(243) & = &(1452)\\ (12)(243)(345) & = &(1532)\\ (243)(12)(345) & = &(1253)\\ \end{array}$$

The reader may find useful practice in independently finding these four cycle products.


Expanding Permutation and Cycle Notation

We might occassionally want to permute a set of elements multiple times in the same way, towards some desired end.

For example: when solving the Rubik's Cube puzzle, one often must make the same sequence of moves multiple times -- each of which permutes the stickers on the face of the cube in the exact same way.

Letting $p$ represent a given permutation, we then abbreviate the permutation that results from applying $p$ exactly $a$ times by $p^a$.

Recalling that for any permutation $p$ we can find an inverse permutation $p^{-1}$ that undoes it (i.e., their composition is the identity permutation $I$), we likewise abbreviate with $p^{-a}$ this inverse permutation applied $a$ times. Note that $p^a$ and $p^{-a}$ are then necessarily inverse permutations of one another.

Following suit with what we did with braids and what many will remember to be true about powers of real values -- and for consistency with the rules to come -- we make two additional definitions for any permutation $p$:

With the above abbreviations and definitions, the following must hold for ANY permutation $p$ and integers $a$ and $b$:

As an immediate application of how inverses combine (similar to what we saw with braids), we also know

Again remembering that the division of one real number by another is equivalent to multiplying the first by the reciprical (i.e., the multiplicative inverse) of the second, we define and denote the "division of one permutation by another" (and the equivalent "fraction of permutation") in the following way: $$p \div q = \frac{p}{q} = p q^{-1}$$

As with braids, doing this leads to more (familiar) results:

For permutations which are disjoint cycles, say $c_1$ and $c_2$ (which being disjoint, automatically commute), we can say even more!

Be careful! One should note that these last two can't be applied in general to just any two permutations -- so always check to make sure you have the commutativity needed before using these last two rules.

As one final and very useful property when it comes to simplifying things, note that a cycle $c$ of $k$ elements when raised to the $k^{th}$ power simply returns each element to its original position. As such, for any positive integer $n$, we have $$c^{nk} = I$$