Permutation Matrices

  • Thread starter xnull
  • Start date
  • #1
16
0
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!
 

Answers and Replies

  • #2
703
13
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:
  • #3
16
0
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.
 
  • #4
367
1
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.
 
  • #5
16
0
Oh phoey!

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

Related Threads on Permutation Matrices

  • Last Post
Replies
4
Views
899
  • Last Post
Replies
1
Views
681
  • Last Post
Replies
2
Views
666
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
20
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
10
Views
5K
  • Last Post
Replies
2
Views
2K
Top