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

• I
• swampwiz
In summary, there is a theorem known as "The symmetric group is generated by transpositions" that states that a set of binary swaps can result in any permutation. This fact is also used in the proof of the correctness of the quicksort algorithm. The idea is to use adjacent binary swaps to rearrange the numbers in the desired order. This can be achieved by using transpositions to put each number in its correct spot.
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?

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?

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
.

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

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.

swampwiz said:
Is there a theorem that states that a set of binary swaps can result in any permutation?
Math_QED said:
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
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
Infrared said:
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.

## 1. What is a binary swap?

A binary swap is an operation that swaps the positions of two elements in a sequence or permutation, where the elements can only take on two possible values (typically 0 and 1).

## 2. Can a set of binary swaps affect any permutation?

Yes, a set of binary swaps can affect any permutation. This means that by performing a series of binary swaps, you can rearrange the elements of a permutation into any desired order.

## 3. Is there a specific theorem that proves this?

Yes, there is a theorem known as the "even-odd theorem" or the "parity theorem" that proves that any permutation can be achieved through a series of binary swaps.

## 4. How does the even-odd theorem work?

The even-odd theorem works by considering the parity (even or odd) of the number of inversions in a permutation. An inversion occurs when a larger element appears before a smaller element in a sequence. By performing binary swaps, the number of inversions can be reduced until it matches the parity of the desired permutation, thus achieving the desired order.

## 5. Are there any limitations to using binary swaps to affect permutations?

Yes, there are limitations to using binary swaps to affect permutations. For example, the number of binary swaps needed to achieve a specific permutation may vary depending on the initial order of the elements. Additionally, the size of the set being permuted may also affect the efficiency of using binary swaps.

• General Math
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
15
Views
4K
• Linear and Abstract Algebra
Replies
10
Views
2K
• Linear and Abstract Algebra
Replies
2
Views
1K
• Linear and Abstract Algebra
Replies
5
Views
2K
• Quantum Interpretations and Foundations
Replies
54
Views
4K
• Linear and Abstract Algebra
Replies
7
Views
2K
• Quantum Interpretations and Foundations
Replies
45
Views
4K
• Quantum Physics
Replies
5
Views
1K
• Linear and Abstract Algebra
Replies
4
Views
3K