Here is my problem: Let $\tau \in S_{n}$ be the cycle $(1,2,...,k)$ of length $k$, where $k \leq n$. Prove that if $\sigma \in S_{n}$ then $\sigma \tau \sigma^{-1}=(\sigma(1)),\sigma(2),...,\sigma(k))$. Thus $\sigma \tau \sigma^{-1}$ has cycle length of $k$.

A proof is shown here:

Consider $\sigma \tau \sigma^{-1}(\sigma(1))=\sigma(\tau(1))=\sigma(2)$. Also, $\sigma \tau \sigma^{-1}(\sigma(2))=\sigma(\tau(2))=\sigma(3)$. And finally, $\sigma \tau \sigma^{-1}(\sigma(k))=\sigma(\tau(k))=\sigma(1)$ since $\tau(k)=1$. Therefore, $\sigma \tau \sigma^{-1}=(\sigma(1)),\sigma(2),...,\sigma(k))$ concluding that cycle length is $k$.

But I don't understand 2 things about this proof.

  1. Firstly, I understand the algebra, but why are they calculating $\sigma \tau \sigma^{-1}(\sigma(1))$ to begin with? Are they picking the elements from the thing we are trying to prove? Why or how can you do that? How did they know to do that? (I hope it makes sense I just don't understand the intent/purpose behind the method of proof...)

  2. I don't understand the mapping. The first output element that we obtain in the proof is $\sigma(2)$, so what happens to the output element of $\sigma({1})$? Do we not need it? And why does $\tau({k})=1$? Is it because $\tau({k})=\tau(1)$?

Edit: I think my question should not "quite" count as a duplicate of the other question. The questions are mostly the same in nature, but I wouldn't have been able to recognize it myself since the questions are spelled-out a bit differently. But, I am glad to see the reference to the other one since it helps solidify my understandings.


1 Answer 1


We can give a picture of the proof that might make it clearer what is going on here. There is another common notation to write such mappings that you will likely have seen:

\begin{align}\sigma &= \left(\begin{matrix} 1 & 2 & 3 & \dotsb & n\\ \sigma(1) & \sigma(2) & \sigma(3) & \dotsb &\sigma(n)\end{matrix}\right)\\[10pt] &= \left(\begin{matrix} 1 & 2 & 3 & \dotsb & n\\ {\scriptstyle\sigma}\downarrow & {\scriptstyle\sigma}\downarrow & {\scriptstyle\sigma}\downarrow & \dotsb & {\scriptstyle\sigma}\downarrow \\\sigma(1) & \sigma(2) & \sigma(3) & \dotsb & \sigma(n)\end{matrix}\right)\\[10pt] &= \left(\begin{matrix} 1 & 2 & 3 & \dotsb & n\\{\scriptstyle\sigma^{-1}}\uparrow & {\scriptstyle\sigma^{-1}}\uparrow & {\scriptstyle\sigma^{-1}}\uparrow & \dotsb & {\scriptstyle\sigma^{-1}}\uparrow \\ \sigma(1) & \sigma(2) & \sigma(3) & \dotsb & \sigma(n) \end{matrix}\right) \end{align} where we have added arrows representing the mappings.

With this notation we may represent the mappings of the first $k$ numbers, $1,\dotsc, k$ under $\sigma$. \begin{align} &\left(\begin{matrix} \;\;\;\;\;\downarrow-- &---&---&--\overset{\tau}{-}--&---&---&\dotsb&---&--|\;\;\;\;\;\\ 1 & \underset{\tau}{\rightarrow} & 2 & \underset{\tau}{\rightarrow} & 3 & \underset{\tau}{\rightarrow} & \dotsb & \underset{\tau}{\rightarrow}& k\\ {\scriptstyle\sigma}\downarrow\uparrow{\scriptstyle\sigma^{-1}} && {\scriptstyle\sigma}\downarrow\uparrow{\scriptstyle\sigma^{-1}} && {\scriptstyle\sigma}\downarrow\uparrow{\scriptstyle\sigma^{-1}} && \dotsb && {\scriptstyle\sigma}\downarrow\uparrow{\scriptstyle\sigma^{-1}}\\ \sigma(1) && \sigma(2) && \sigma(3) && \dotsb && \sigma(k) \end{matrix}\right)\\[20pt] &=\left(\begin{matrix} 1 && 2 && 3 && \dotsb && k\\ \sigma(1) &\overset{\sigma\tau\sigma^{-1}}{\rightarrow}& \sigma(2) &\overset{\sigma\tau\sigma^{-1}}{\rightarrow}& \sigma(3) &\overset{\sigma\tau\sigma^{-1}}{\rightarrow}& \dotsb &\overset{\sigma\tau\sigma^{-1}}{\rightarrow}& \sigma(k)\\ \;\;\;\;\;\uparrow-- &--&--&--&-\underset{\sigma\tau\sigma^{-1}}{--}&--&\dotsb&--&--|\;\;\;\;\;\\ \end{matrix}\right) \end{align}

As $\sigma \in S_n$ it is a bijective, so each $\sigma(j)$ is unique for $1\leq j \leq n$. Hence, $\sigma \tau \sigma^{-1} = (\sigma(1), \sigma(2), \dotsc, \sigma(k))$ is a cycle.

  • $\begingroup$ This was helpful. Thank you...So, can I write also that $\sigma \tau \sigma^{-1}(1)=\sigma(1)$ for the first mapping of the enumeration? I really want to specify how we get $\sigma(1)$ so that the enumeration can be clear that it starts at 1. $\endgroup$
    – PBJ
    Mar 5, 2017 at 14:45
  • $\begingroup$ Oh...but then I would have to write $\tau{(k)} = k-1$ is this correct? If not, I think I am still confused about why $\tau{(k)}=1$. $\endgroup$
    – PBJ
    Mar 5, 2017 at 14:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .