Tag Archives: Cycle

Proof: every cycle expresses as a product of transpositions

A book of abstract algebra, Abstract algebra, Books, Mathematics, , ,

The following self-contained post provides a proof of the fact that every cycle can be expressed as a product of one or more transpositions, as stated in chapter 8, p. 83, of the book “A book of abstract algebra” by Charles C. Pinter.

To show that a cycle (a_1~a_2~\dots~a_{r-1}~a_r) can be written as a product of one or more transpositions, it suffices to prove the validity of the identity (a_1~a_2~\dots~a_{r-1}~a_r)=(a_r~a_{r-1})\dots (a_r~a_2)(a_r~a_1), which will be done by using mathematical induction.

Assume that the identity holds for k. It will be shown that it also holds for k+1, as in (a_1~a_2~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_2)(a_{k+1}~a_1).

Start by noticing that (a_1~a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})(a_{k+1}~a_1).

Due to the induction assumption, which says that a k-length cycle can be decomposed into a product of transpositions, (a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1}) can be written as (a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_3)(a_{k+1}~a_2).

By combining the last two equations, the conclusion follows for k+1.

Proof: the product of disjoint cycles of a permutation is unique

A book of abstract algebra, Abstract algebra, Books, Mathematics, ,

Theorem 1, p. 82, in the book “A book of abstract algebra” by Charles C. Pinter states that “Every permutation is either the identity, a single cycle, or a product of disjoint cycles”. The theorem is proved in the book. After the proof, it is stated that it is easy to see that the product of cycles is unique, except for the order of factors. I have seen online proofs of this claim of uniqueness based on the concept of orbit. In what follows, an alternative proof is offered without relying on orbits.

Assume that there exists a permutation \pi which can be written as a product of disjoint cycles in two ways. So, there are two collections, each consisting of disjoint cycles, C=\left\{c_1,c_2,\dots,c_n\right\} and S=\left\{s_1,s_2,\dots,s_m\right\} such that C\ne S and \pi=\prod_{i=1}^{n}c_i=\prod_{i=1}^{m}s_i.

C\ne S\Rightarrow C\not\subseteq S~\mbox{or}~S\not\subseteq C. Without loss of generality, assume that C\not\subseteq S. Thus, (\exists~\mbox{cycle}~c_i \in C)(\forall~\mbox{cycles}~s_k\in S) c_i\ne s_k.

Let a_q be some element in cycle c_i. Since a_q\in c_i and the cycles in C are disjoint, a_q is permuted by \pi. Therefore, \exists~\mbox{cycle}~s_l\in S such that a_q\in s_l.

The cycles c_i and s_l are disjoint from the rest of cycles in C and S, respectively. Thus, c_i(a_q)=s_l(a_q)=\pi(a_q).

Since c_i\ne s_l, there exists an element a_p that breaks the equality arising from the successive implementation of permutation \pi in each of the two cycles c_i and s_l starting from a_q. Thereby, there exists an element a_p in c_i and in s_l with c_i(a_p)\ne s_l(a_p). This is a contradiction, since the permutation \pi is a function, so a_p should be mapped to a unique element \pi(a_p).