Let A be an m by n matrix (you can assume that all elements of A are distinct). By a "legitimate transposition" on A, I mean an operation on A that swaps the (i,j)th and (k,l)th elements of A for some i<=k and j<=l. My question is : How many different permutations of A can be formed by imposing all possible finite compositions of these legitimate transposition operations on A? Of course, (mn)! is a trivial upper bound. A lower bounds is: (((m+n-1)!)((m+n-3)!) ((m+n-5)!) .... -1). An exact answer will be greatly appreciated. In case this is very difficult, a good upper and lower bound will be useful.
Asked
Active
Viewed 609 times
3
-
The subgroup generated by these transpositions is isomorphic to some smaller symmetric group, so the exact answer is the factorial of some number. To figure out exactly which number that is, I'd have to think harder. – Matt Samuel Jun 17 '15 at 01:28
-
Where does this come from? I'm thinking the answer is actually $(mn)!$, I.e. everything. You can trace a path from any node to any other node and create the rest of the transpositions (the "illegitimate" ones) using only the ones you're allowed. – Matt Samuel Jun 17 '15 at 01:38