# Permutation mapping

1. Jan 2, 2009

### FatTail

hi
if P and Q are 2 permutations of X, their product, P.Q, is the permutation of X (X=1,2,3,4,5), obtained by following the mapping Q with the mapping P. if Q=2 3 4 1 5, and P is 1 2 5 3 4, then how do i find P.Q and Q.P ?

i have tried a few mappings but can never get the same answer as in the book :)

answer for P.Q is 2 5 3 1 4
answer for Q.P is 2 3 5 4 1

please can anyone explain the steps.
thanks

2. Jan 2, 2009

### Marcaias

"Q=2 3 4 1 5" means that this mapping happens:

$$\begin{tabular}{ | c | c | c | c | c | } \hline 1 & 2 & 3 & 4 & 5 \\ \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\ 2 & 3 & 4 & 1 & 5 \\ \hline \end{tabular}$$

In other words:

1 gets mapped to 2,
2 gets mapped to 3,

And so on.

Similarly, "P=1 2 5 3 4" means this happens:

$$\begin{tabular}{ | c | c | c | c | c | } \hline 1 & 2 & 3 & 4 & 5 \\ \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\ 1 & 2 & 5 & 3 & 4 \\ \hline \end{tabular}$$

That is,

1 gets mapped to 1,
2 gets mapped to 2,
3 gets mapped to 5,

and so on.

So to find the product P.Q, you want to build a table like the ones above by "following the arrows". So first you need to find out what 1 gets mapped to under the product P.Q. Whenever you have a product of permutations, you work from right to the left. So you start with Q. You know that Q maps 1 to 2. And then P maps 2 to 2. So the first entry of the table is 2.

$$\begin{tabular}{ | c | c | c | c | c | } \hline 1 & 2 & 3 & 4 & 5 \\ \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\ 2 & ? & ? & ? & ? \\ \hline \end{tabular}$$

Next, you want to find out what 2 gets mapped to. Q maps 2 to 3, and P maps 3 to 5. So the second entry is a 5.

$$\begin{tabular}{ | c | c | c | c | c | } \hline 1 & 2 & 3 & 4 & 5 \\ \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\ 2 & 5 & ? & ? & ? \\ \hline \end{tabular}$$

And so on.

3. Jan 2, 2009

### HallsofIvy

Q= 2 3 4 1 5, if I understand your notation, would also be written
$$\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 1 & 5\end{array}\right)$$
and means that 1 is changed into 2, 2 is changed into 3, 3 is changed into 4, 4 is changed into 1, and 5 is changed into itself (remains the same). P= 1 2 5 3 4 is
$$\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 5 & 3 & 4\end{array}\right)$$
and means that 1 and 2 remain the same, 3 is changed into 5, 4 is changed into 3, and 5 is changed into 4. The standard convention is that Q.P means that P is applied first, then Q (but check with your teacher or text- that varies). So P leaves 1 along and then Q changes 1 to 2: together, 1 changes to 2. P leaves 2 alone and then Q changes 2 to 3: together, 2 changes to 3. P changes 3 to 5 and then Q leaves 5 alone: together, 3 changes to 5. P changes 4 to 3 and then Q changes 3 to 4: together 4 remains the same. P changes 5 to 4 and then Q changes 4 to 1: together 5 changes to 1. That is the permutation
$$\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 4 & 1\end{array}\right)$$
In your notation I think that would be 2 3 5 4 1.

Similarly, P.Q means that we apply Q first. Q changes 1 to 2 and then P leaves 2 alone: together 1 changes to 2. Q changes 2 to 3 and then P changes 3 to 5: together 2 changes to 5. Q changes 3 to 4 and then P changes 4 to 3: together 3 stays the same. Q changes 4 to 1 and then P leaves one alone: together 4 changes to 1. Q leaves 5 alone and then P changes 5 to 4: together 5 changes to 4. That is
$$\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\2 & 5 & 3 & 1 & 4\end{array}\right)$$
or, in your notation 2 5 3 1 4.

Again check your text's convention on order. If what your text has reverses those two answer, it is using the other convention.

4. Jan 2, 2009