Undergrad Is there a theorem that a set of binary swaps can affect any permutation?

[swampwiz]

Is there a theorem that states that a set of binary swaps can result in any permutation?

For example, the original set (1,2,3,4,5) can have the swap (24) and result in (1,4,3,2,5). is there a set of specific swaps for each net result permutation?

 

[member 587159]

Yes, there is such a theorem. This is worded as: "The symmetric group is generated by transpositions". See e.g. here: https://planetmath.org/symmetricgroupisgeneratedbyadjacenttranspositions

 

[swampwiz]

I was just thinking. Since the quicksort algorithm only does binary swaps, and can sort any initial permutation order - and thus could be run in reverse to get to any permutation from the sorted set - doesn't this also prove this theorem?

 

[Office_Shredder]

I guess the question is how do you prove quicksort actually sorts the list at the end? I think you need this theorem to prove it, or at least to substantially prove this theorem as part of your proof of the algorithms correctness
.

 

[swampwiz]

I wonder if anyone has done a YouTube video that does this proof without requiring a lot of abstract algebra terminology.

 

[swampwiz]

OK, I think I've got this. Given a vector of indices, a binary swap can be accomplished by concatenating it with an elementary swap matrix. Since the Gauss-Jordan reduction algorithm can decompose any matrix into a set of elementary matrices, and a permutation matrix is composed only of such elementary swap matrices, and as well because the determinant of an elementary swap matrix is -1, its inverse exists. Thus, the identity matrix can have a set of concatenations of swap matrices to get to any possible permutation.

 

[Vanadium 50]

Is there a theorem that states that a set of binary swaps can result in any permutation?

Yes, there is such a theorem. This is worded as: "The symmetric group is generated by transpositions"

Note that this overdoes it - it proves that a set of adjacent binary swaps can result in any permutation.

 

[Infrared]

This fact is much easier than it seems like you think it is. If I have the numbers 1,...,n in some order and I want to rearrange them into the standard order, then I first make a transposition to put $1$ in the first spot and leave it alone thereafter. Then I make a transposition to put $2$ into the second spot, etc.

 

[swampwiz]

This fact is much easier than it seems like you think it is. If I have the numbers 1,...,n in some order and I want to rearrange them into the standard order, then I first make a transposition to put $1$ in the first spot and leave it alone thereafter. Then I make a transposition to put $2$ into the second spot, etc.

Yes, that is the idea I was getting at in a subsequent post.