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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s