Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutation mapping

  1. Jan 2, 2009 #1
    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. jcsd
  3. Jan 2, 2009 #2
    "Q=2 3 4 1 5" means that this mapping happens:

    [tex]
    \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}
    [/tex]

    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:

    [tex]
    \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}
    [/tex]

    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.

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    2 & ? & ? & ? & ? \\ \hline
    \end{tabular}
    [/tex]

    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.

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    2 & 5 & ? & ? & ? \\ \hline
    \end{tabular}
    [/tex]

    And so on.

    To find Q.P, perform the same process, but start with P.
     
  4. Jan 2, 2009 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Q= 2 3 4 1 5, if I understand your notation, would also be written
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 1 & 5\end{array}\right)[/tex]
    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
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 5 & 3 & 4\end{array}\right)[/tex]
    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
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 4 & 1\end{array}\right)[/tex]
    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
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\2 & 5 & 3 & 1 & 4\end{array}\right)[/tex]
    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.
     
  5. Jan 2, 2009 #4

    radou

    User Avatar
    Homework Helper

    To add, a permutation is a function, and the term "product" of permutations is actually a composition of functions, i.e. if P and Q are permutations of X, then the product PQ is defined as P(Q(x)), where x is an element of X.
     
  6. Jan 2, 2009 #5
    thanks guys. i get it now :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutation mapping
  1. Multiplying permutations (Replies: 10)

  2. Permutation Group (Replies: 29)

Loading...