Proof: every cycle expresses as a product of transpositions

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.

Leave a Reply

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

You are commenting using your 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