Generating a Permutation Matrix P for All Permutations of A

[xnull]

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!

 

[Edgardo]

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" , 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/" and type into the command line: (4,1,3,2)^24
(see also http://people.math.jussieu.fr/~jmichel/htm/CHAP020.htm" )

There is a probably a theorem to calculate (a1,a2,...,am)^(m!).

 

[xnull]

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.

 

[Moo Of Doom]

Indeed, for size m > 2, this does not exist, because it would imply that S_m is a cyclic group (i.e. generated by one element), which it is not for m > 2.

 

[xnull]

Oh phoey!

Thank you Moo of Doom (and the greater whole that is PF).