55.6k views
2 votes
Prove the following about Sn : If n>3, every perμtation in Sn can be written as a product of at most n−1 transpositions.

a) True
b) False

User RHicke
by
8.2k points

1 Answer

3 votes

Final answer:

Yes, it is true that in Sn where n > 3, every permutation can be expressed as a product of at most n-1 transpositions. The proof relies on the decomposition of permutations into cycles and converting cycles into transpositions. Correct option is A) True

Step-by-step explanation:

The statement that every permutation in Sn can be written as a product of at most n-1 transpositions is true if n > 3. A permutation of n elements can be expressed as a product of cycles, and every cycle of length k can in turn be written as a product of k-1 transpositions. Thus, a cycle of length n can be expressed as n-1 transpositions.

An example of this would be the cycle (123) in S3, which can be written as the transpositions (12)(23), accounting for 2 transpositions which is less than 3-1=2. In the general case for n elements, writing the longest cycle as a product of transpositions will involve n-1 transpositions, and since any permutation can be decomposed into disjoint cycles, the total number of transpositions required to express any permutation will not exceed n-1. This argument relies on the ability to decompose permutations into cycles and understanding the relationship between cycles and transpositions.

User Niesha
by
8.1k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.