Permutation Matrices

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!

If I understood you correctly you are trying to calculate $$P^{(m!)}$$, 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]

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

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

Last edited by a moderator:
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.

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.

Oh phoey!

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