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

• I
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?

• • 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?

Staff Emeritus
Gold Member
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.

Staff Emeritus
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.

• swampwiz, sysprog and member 587159
• 