Question

Explain why every permutation in S(n) can be represented by a product of n-1 or fewer cycles of length 2 (transpositions). Represent the permutationσ in problem (1) above as a product of 8 or fewer transpositions. Is σ an even or an odd permuation?

Answer 1

Theorem 2: Every permutation can be expressed as a composite of disjoint cycles Proof: Let the given permutation f be denoted by the usual two row symbol within a bracket. Let a be any element in the first row and b the element in the second row exactly beneath a, ie. f (a)b. Similarly, let f (b) c. Continuing this process, an element 1 may be found in the upper row such that its f image is a. Then a, b,c,...1 is one circular permutation. If there are additional elements a',b', etc., in the original permutation another cycle (a'' b',d, , Г). Even now, if some element or elements are left in the original permutation this procedure can be repeated to the extent that all the elements of f are exhausted. In this way the original permutation can be put as the product of disjoint cycles follow the above process to obtain Theorem 3: Every permutation can be expressed asa product of transpositions Proof: To prove the above result, we shall first show that every cycle can be expressed as a composite of transpositions. Let us consider a cycle (a1, a2,.. ., an then 1 an a1 an-1...(a1 a2 We have already proved that every permutation can be expressed as a composition of disjoint cycles. Therefore in the light of the two results stated above, every permutation can be expressed as a product of transpositions