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

Permutation Matrices

  1. Nov 30, 2009 #1
    Hello!

    I was wondering if there is a way to generate a permutation matrix P such that each application of P to another matrix A will find the "next" permutation of A. I'm looking for a way to generate a permutation matrix P (size m x m) such that applying it m! times to A (m x m) returns A (after having rolled through all possible permutations of A).

    Am I looking for something I'm not going to be able to find?

    Thanks!
     
  2. jcsd
  3. Dec 1, 2009 #2
    If I understood you correctly you are trying to calculate [tex]P^{(m!)}[/tex], where P is a permutation matrix. One way I can think of is to use the http://www.ece.cmu.edu/~smart/examples/cycle/cycle.html" [Broken], e.g. (4,1,3,2) stands for the matrix

    [tex]
    \begin{bmatrix}
    0 & 0 & 1 & 0 \\
    0 & 0 & 0 & 1 \\
    0 & 1 & 0 & 0 \\
    1 & 0 & 0 & 0 \\
    \end{bmatrix}
    [/itex]

    (See also http://en.wikipedia.org/wiki/Permutation_matrix#Examples")

    Then you have to calculate (4,1,3,2)^(m!) = (4,1,3,2)^(4!). You can use the program http://www.gap-system.org/" [Broken] and type into the command line: (4,1,3,2)^24
    (see also http://people.math.jussieu.fr/~jmichel/htm/CHAP020.htm" [Broken])

    There is a probably a theorem to calculate (a1,a2,....,am)^(m!).
     
    Last edited by a moderator: May 4, 2017
  4. Dec 1, 2009 #3
    Let me ask it another way...

    Is there some permutation that can be done to a list of elements such that the recursive application of that permutation to that list will cycle through all possible permutations?

    Basically I'd like something like C++'s next_permutation (but without having each application of the function permute the input list in a different manner than the previous one).

    [After experimenting I think I'm looking for something that doesn't exist?]

    Thank you to everyone who has replied so far.
     
  5. Dec 1, 2009 #4
    Indeed, for size m > 2, this does not exist, because it would imply that Sm is a cyclic group (i.e. generated by one element), which it is not for m > 2.
     
  6. Dec 1, 2009 #5
    Oh phoey!

    Thank you Moo of Doom (and the greater whole that is PF).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Permutation Matrices
  1. Matrices ? (Replies: 6)

  2. Even Permutations (Replies: 4)

  3. On Matrices (Replies: 8)

Loading...