8

This question has been asked before, I know: Product of Permutations

However, his did not resolve my problem.

Here's an example I've been looking at, which is to find the product of two permutations in two-line notation:

$$ \left( \begin{array}{cc} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{array} \right) % \left( \begin{array}{cc} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{array} \right) $$

Now this is how the two functions compose:

$$1 \mapsto 3 \mapsto 4$$ $$2 \mapsto 5 \mapsto 2$$ $$3 \mapsto 1 \mapsto 3$$ $$4 \mapsto 2 \mapsto 5$$ $$5 \mapsto 4 \mapsto 1$$

That is:

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 \\ \end{pmatrix}

But since it has been a while that I last looked at permutations, I can't quite see how this works?

I can see, for a single permutation, i.e. \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \\ \end{pmatrix}

we have $$1 \mapsto 3 \mapsto 4 \mapsto 1$$ $$2 \mapsto 5 \mapsto 2 $$

which includes all the elements in the group, so at this point we stop.

This can then be written in cycle notation as: (134)(25). However, how do I work through two permutations this way. Would I look at the elements in the top row of the second permutation which I didn't start with before? What happens during the process of composition?

Some illumination would be great. (I know this is a very straight forward technique, but I've somehow got stuck!)

Community
  • 1
Seraphina
  • 641

1 Answers1

10

$$ \left( \begin{array}{cc} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{array} \right) % \left( \begin{array}{cc} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{array} \right) $$

The first mapping is the mapping dictated by the permutation on the right. If $a \mapsto b$ on the right, then we need to see what element $b$ maps to on the left: Let's say $b \mapsto c$ as determined by the permutation on the left. Then the mapping of $a$ given by the composition of the permutations is given by $$\overbrace{a\mapsto b}^{\text{right-hand}},\;\text{and}\;\;\underbrace{b\mapsto c}_{\text{left-hand}} \implies \overbrace{a \mapsto c}^{\text{composition}}$$ Then we return to the right permutation to see which element $(a+1) $ maps to in that permutation, say it's $d$. So we have $(a+1) \mapsto d\mapsto ?$, and to fill in the question mark, we move to the left-hand permutation to learn which element in the left permutation $d$ is mapped to.

And then, on to determining where $a+2$ maps to, starting always with the permutation on the right. $\cdots$.

Perhaps it will help you to see how to compose the two if we get the composition correct: (You have $5$ and $4$ swapped in the last column.)

$$1 \mapsto 3 \mapsto 5$$ $$2 \mapsto 5 \mapsto 2$$ $$3 \mapsto 1 \mapsto 3$$ $$4 \mapsto 2 \mapsto 4$$ $$5 \mapsto 4 \mapsto 1$$

$$\begin{pmatrix} 1 &2&3&4&5 \\ 5&2&3&4&1\end{pmatrix} = (1\;5)$$

amWhy
  • 209,954