Combining Permutations

Of course it's nice to have a method to write down a permutation, but things begin to get interesting when we combine them. If you twist one face of Rubik's Cube and then twist another one, each twist jumbles the faces, and the combination of two twists usually causes a jumbling that is more complicated than either of the two individual twists.

Rather than begin with Rubik's Cube, let's begin by looking at permutations of just 3 objects. We listed them in Table 1, but there we used a very clumsy notation. Here are the six possible permutations of three items listed in the same order as in Table 1:

$$(1), (12), (13), (23), (123), (132).$$

What happens if we begin with ball 1 in box 1, ball 2 in box 2, and ball 3 in box 3, and then we apply $(1 2)$ followed by $(1 3)$?

A good way to think about this is to follow the contents of the boxes one at a time. For example, ball 1 begins in box 1, but after $(1 2)$ it has moved to box 2. The second permutation, $(1 3)$, does not move the contents of box 2, so after both permutations have been applied, ball 1 will have moved to box 2. So the final result will look like this:

$$(1 2 \ldots$$

where we're not sure what comes next. We don't know if 2 will go back to one and the cycle will close, or whether it will continue to another box. So since the fate of 2 is in question, let's see where it goes.

The first permutation, $(1 2)$ moves box 2 to box 1, and then $(1 3)$ will move box 1 to box 3, so now we know the combination of permutations looks like this:

$$(1 2 3 \ldots$$

Since there are only three objects, we know that 3 will go back to 1 and close the cycle, but (especially when you're beginning), it's good to trace each ball, including ball 3 in this case.

The first permutation, $(1 2)$, does not move the contents of box 3, but the second, $(1 3)$ moves it to box 1, so the combination of $(1 2)$ followed by $(1 3)$ is equivalent to the single permutation $(1 2 3)$.

Combining permutations as above is written just like a multiplication in algebra, and we can write our result as follows¹:

$$(1 2)(1 3) = (1 2 3).$$

Beware, however. This is not the same as multiplication that you're used to for real numbers. By doing the same analysis as above, convince yourself that:

$$(1 3)(1 2) = (1 3 2) \ne (1 2 3) = (1 2)(1 3).$$

In other words, the order of multiplication makes a difference. If $P_1$ and $P_2$ are two different permutations, it may not be true that $P_1P_2 = P_2P_1$. Multiplication of permutations is not commutative.

Test your understanding of multiplication of permutations by verifying all of the entries in the ``multiplication table'' for the permutations of three objects in Table 2.

Table 2: Multiplication table of permutations

	$(1)$	$(1 2)$	$(1 3)$	$(2 3)$	$(1 2 3)$	$(1 3 2)$
$(1)$	$(1)$	$(1 2)$	$(1 3)$	$(2 3)$	$(1 2 3)$	$(1 3 2)$
$(1 2)$	$(1 2)$	$(1)$	$(1 3 2)$	$(1 2 3)$	$(2 3)$	$(1 3)$
$(1 3)$	$(1 3)$	$(1 2 3)$	$(1)$	$(1 3 2)$	$(1 2)$	$(2 3)$
$(2 3)$	$(2 3)$	$(1 3 2)$	$(1 2 3)$	$(1)$	$(1 3)$	$(1 2)$
$(1 2 3)$	$(1 2 3)$	$(1 3)$	$(2 3)$	$(1 2)$	$(1 3 2)$	$(1)$
$(1 3 2)$	$(1 3 2)$	$(2 3)$	$(1 2)$	$(1 3)$	$(1)$	$(1 2 3)$

Remember that the order of multiplication is important. In Table 2, if you are trying to look up the product of $(1 2)(1 3)$, find the column labelled $(1 2)$ and the row labelled $(1 3)$. If you use the row labelled $(1 2)$ and the column labelled $(1 3)$ you will be looking up the product $(1 3)(1 2)$ which may be different.

As a final check on your understanding of multiplication of permutations, verify the following multiplications of permutations:

$$\begin{eqnarray*} (1 3 4 2)(3 6 4 5)(1 6 2 3) &=& (1 2 6 4 3 5) \\ (1 2)(2 3)(3... ... &=& (1 5 4 3 2) \\ (1 3 5)(3 2)(5 4 3 2 1)(4 1 3)(1 3) &=& (1) \end{eqnarray*}$$

Here are some general properties of multiplication of permutations. They hold for the sets of permutations of any number of elements, but you should check to see that they do hold in the particular case of the three-element permutations in Table 2.

• Identity: The permutation $(1)$ that leaves everything fixed is an identity under multiplication. If $P$ is any permutation, then $P(1) = (1)P = P$. In other words, the permutation $(1)$ behaves for permutation multiplication just like the number 1 behaves for multiplication of real numbers. Sometimes the identity is written as $e$. It is not hard to prove that the identity is unique.

• Inverses: Every permutation has an inverse that ``undoes'' the operation. In other words, if you apply a permutation to a set and then apply its inverse, the result is that the final order is unchanged from the original. If $P$ is a permutation and $P^{-1}$ is its inverse, we can write $PP^{-1} = P^{-1}P = (1) = e$.

  If you have a permutation written in cycle notation and you want to find its inverse, simply reverse all the cycles. For example, $[(134)(256)]^{-1} = (652)(431)$. To see why this works, multiply: $(134)(256)(652)(431)$. The result will be $(1)$.

• Associativity: If $P$, $Q$, and $R$ are any three permutations, then $P[QR] = [PQ]R$. In other words, if you have to multiply 3 or more permutations together, it doesn't matter how you group them to do the multiplications. We use braces ``[`` and ``]'' to indicate the grouping since we've used parentheses to indicate the cycles of the permutations.

  For example, let's work out $(1 3 4 5)(2 4 3)(1 6 3)$ two different ways. First we'll multiply $(1 3 4 5)$ by $(2 4 3)$ and then take that result and multiply it by $(1 6 3)$. Then we'll do the multiplication beginning with the last two permutations (check these yourself):

  $$\begin{eqnarray*}[(1 3 4 5)(2 4 3)](1 6 3) &=& (1 2 4 5)(1 6 3) = (1 2 4 5 6 3) ... ... 3 4 5)[(2 4 3)(1 6 3)] &=& (1 3 4 5)(1 6 3 2 4) = (1 2 4 5 6 3) \end{eqnarray*}$$
  
  
  
  
  

• Not (necessarily) Commutativity: This is really just a reminder that the commutative law does not hold in general. If you swap the order of a product, the result may change, so $PQ$ and $QP$ are not necessarily the same.

  There are some cases, however, where things do commute. For example, if your permutations are two cycles that share no elements in common, the order in which they occur does not matter. So $(1 2 3)(4 5) = (4 5)(1 2 3)$. This is obviously true since each cycle rearranges a different subset of elements, so their operations are completely independent and can be reversed in order with no effect on the final outcome.