Theorems of Cyclic Permutations

Theorem 1: The product of disjoint cycles is commutative.

Proof: Let f and g be any two disjoint cycles, i.e. there is no element common in two when they are expressed in one row notation. Therefore, the elements permuted by f are invariant under g and the elements permuted by g are invariant under f.
Hence f \circ g = g  \circ f the product of disjoint cycles is commutative.

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 with in a bracket. Let a be any element in the first row and b the element in the second row exactly beneath a, i.e. f\left( a \right) = b. Similarly, let f\left( b \right) = 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 f, follow the above process to obtain another cycle \left( {a',b',c',...,1'}  \right). Even now if, some element or elements are left in 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.

Theorem 3: Every permutation can be expressed as a 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 \left( {{a_1},{a_2},...,{a_n}} \right) then

\left( {{a_1},{a_2},...,{a_n}} \right) = \left( {{a_1}\,{a_n}} \right)\left( {{a_1}\,{a_{n - 1}}} \right)...\left( {{a_1}\,{a_2}} \right)

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.

Comments

comments