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 within 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 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.

 

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.