1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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

    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?

  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

    0 & 0 & 1 & 0 \\
    0 & 0 & 0 & 1 \\
    0 & 1 & 0 & 0 \\
    1 & 0 & 0 & 0 \\

    (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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook