Willow Pratt

2022-07-02

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

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.

Kaylie Mcdonald

Expert

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 $\left(1\phantom{\rule{thickmathspace}{0ex}}2\phantom{\rule{thickmathspace}{0ex}}3\right)$, 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 $\left(1\phantom{\rule{thickmathspace}{0ex}}2\phantom{\rule{thickmathspace}{0ex}}3\right)\left(2\phantom{\rule{thickmathspace}{0ex}}4\right)$ 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 $\left(1\phantom{\rule{thickmathspace}{0ex}}2\right)\left(2\phantom{\rule{thickmathspace}{0ex}}3\right)\dots \left(47\phantom{\rule{thickmathspace}{0ex}}48\right)\left(48\phantom{\rule{thickmathspace}{0ex}}1\right)$ (for example) is the cyclic permutation $\left(1\phantom{\rule{thickmathspace}{0ex}}2\phantom{\rule{thickmathspace}{0ex}}\dots \phantom{\rule{thickmathspace}{0ex}}48\right)$. And, in general that if the ${a}_{i}$ are all distinct that $\left({a}_{1}\phantom{\rule{thickmathspace}{0ex}}{a}_{2}\right)\left({a}_{2}\phantom{\rule{thickmathspace}{0ex}}{a}_{3}\right)\dots \left({a}_{n-1}\phantom{\rule{thickmathspace}{0ex}}{a}_{n}\right)\left({a}_{n}\phantom{\rule{thickmathspace}{0ex}}{a}_{1}\right)$ is the cyclic permutation $\left({a}_{1}\phantom{\rule{thickmathspace}{0ex}}{a}_{2}\phantom{\rule{thickmathspace}{0ex}}\dots \phantom{\rule{thickmathspace}{0ex}}{a}_{n}\right)$.

Rapsinincke

Expert

Step 1
$\left({a}_{1},{a}_{2},\cdots ,{a}_{n}\right)=\left({a}_{1},{a}_{n}\right)\left({a}_{1},{a}_{n-1}\right)\cdots \left({a}_{2},{a}_{1}\right)$
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 $\left({a}_{1},{a}_{k}\right).$. 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.
$\left({a}_{n},{a}_{n-1}\right)\cdots \left({a}_{n},{a}_{1}\right)$ is the same idea, except ${a}_{k}$ is acting as the interchange.
$\left({a}_{1},{a}_{2}\right)\left({a}_{2},{a}_{3}\right)\cdots \left({a}_{n-1},{a}_{n}\right)$ 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 $\left({a}_{k+1},{a}_{k}\right)$ gets shifted and then again the rest of the transpositions do nothing.

Do you have a similar question?