Intuition for expressing a cycle as a product of transpositions. I have recently learned the proof

Willow Pratt

Willow Pratt

Answered question

2022-07-02

Intuition for expressing a cycle as a product of transpositions.
I have recently learned the proof of:
( a 1   a 2     a n ) = ( a 1   a k ) ( a 1   a k 1 ) ( a 1   a 2 ) = ( a k   a k 1 ) ( a k   a k 2 ) ( a k   a 1 ) = ( a 1   a 2 ) ( a 2   a 3 ) ( a k 1   a k )
Now I can prove the above 3 equalities through induction but unfortunately induction, unlike a direct proof, doesn't quite tell me what is really going on. I'm struggling to understand this intuitively. I don't want to just memorize it.

Answer & Explanation

Kaylie Mcdonald

Kaylie Mcdonald

Beginner2022-07-03Added 19 answers

Step 1
The intuition you seem to need is how to read off from a permutation given as a product of cycles the mapping the permutation represents. If you consider a single cycle such as ( 1 2 3 ), then it is the permutation that maps 1 to 2, 2 to 3 and 3 to 1. When you look at a product of two or more cycles that may overlap, then you have to decide whether to work from left to right or from right to left. If I work from left to right ( 1 2 3 ) ( 2 4 ) maps 1 to 4 (via 2), 2 to 3, 3 to 1 and 4 to 2.
Step 2
So now it should be intuitively clear that ( 1 2 ) ( 2 3 ) ( 47 48 ) ( 48 1 ) (for example) is the cyclic permutation ( 1 2 48 ). And, in general that if the a i are all distinct that ( a 1 a 2 ) ( a 2 a 3 ) ( a n 1 a n ) ( a n a 1 ) is the cyclic permutation ( a 1 a 2 a n ).
Rapsinincke

Rapsinincke

Beginner2022-07-04Added 3 answers

Step 1
( a 1 , a 2 , , a n ) = ( a 1 , a n ) ( a 1 , a n 1 ) ( a 2 , a 1 )
Read the composition of cycles from right to left. How do they act on the element a 1 ? The right most transposition "sees" a 1 and takes it to a 2 .. None of the rest of the transpositions act on a 2 ..
Consider the element a k ,, the first several transpositions do not act on a k .. The first transposition that does is ( a 1 , a k ) .. That takes a k to a 1 .. The next transpositions takes that element to a k + 1 ..
Step 2
In this chain of transpositions, a 1 is acting as the interchange for all of the other elements. Every element gets sent to a 1 and then sent from a 1 to its destination.
( a n , a n 1 ) ( a n , a 1 ) is the same idea, except a k is acting as the interchange.
( a 1 , a 2 ) ( a 2 , a 3 ) ( a n 1 , a n ) even though it is ultimately the same cycle, the activity that is going on is a little bit different. Consider the element a k ,, it glides along unaffected by the first several transpositions, until it hits ( a k + 1 , a k ) gets shifted and then again the rest of the transpositions do nothing.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?