Generating a Permutation Matrix P for All Permutations of A

• xnull
In summary, the conversation discusses the possibility of finding a permutation matrix P that can be applied to another matrix A to generate the "next" permutation of A. It is suggested to use the cycle notation and calculate P^(m!), but it is concluded that such a permutation does not exist for m > 2 as it would imply that Sm is a cyclic group.
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!

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" , 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/" 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).

1. What is a permutation matrix?

A permutation matrix is a square matrix that represents a permutation of a set of objects. It is an arrangement of the elements in a specific order.

2. How do you generate a permutation matrix for a given set of elements?

To generate a permutation matrix for a given set of elements, you can use the concept of factorials. The number of permutations for a set of n elements is n!. So, for example, if you have a set of 3 elements, the permutation matrix will have a size of 3x3 and will have 6 different permutations.

3. How do you represent the permutations in a permutation matrix?

In a permutation matrix, each row and column represents an element from the original set. The value at each position in the matrix represents whether the element in that row is present in that position in the permutation or not. For example, if the first row in the matrix has a value of 1 in the second column, it means that the second element of the original set is present in the first position in the permutation.

4. Can you generate a permutation matrix for a large set of elements?

Yes, it is possible to generate a permutation matrix for a large set of elements. However, the size of the matrix will increase exponentially with the number of elements. So, it may not be practical to generate a permutation matrix for a very large set of elements.

5. Why is generating a permutation matrix useful?

A permutation matrix can be useful in various mathematical and scientific applications, such as in linear algebra, graph theory, and coding theory. It can also be used to generate all possible combinations of a set of elements, which can be helpful in solving certain types of problems.

Replies
1
Views
1K
Replies
3
Views
1K
Replies
4
Views
5K
Replies
32
Views
1K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
11
Views
1K
Replies
4
Views
2K
Replies
4
Views
2K
Replies
4
Views
3K