Concerning the conjugation, I learned that two permutations $ \sigma,\pi\in S_n$ are conjugate if exists $\tau \in S_n $ such that: $\pi=\tau\sigma\tau^{-1}$. Also, these permutations are conjugate if and only if they have the same cycle type.

Although I know how to find the conjugate for a a permutation like in this post, I can't understand the definition of conjugation by a transposition!.

What is the difference between finding the conjugate of a permutation as in the previous link and the conjugation by a transposition? what is the role of the transposition here? how could we do this?

I would like to find a definition for the (conjugation by a transposition), In which consequence? for example, if I want to move from the permutation $ \sigma $ to $\pi$, how could I use the conjugation by a transposition.

Thanks in advance for any example or a reference

  • $\begingroup$ @Yanko the answers in the linked post construct $\tau$ $\endgroup$ – Rylee Lyman Jun 28 at 14:42

I'm not sure if "conjugate by a transposition" is a very common term, but here is what it should mean. $\pi$ and $\sigma$ in are conjugate, as you say, if there is $\tau$ such that $\pi = \tau\sigma\tau^{-1}$. If $\tau$ is a transposition (that is, $\tau = (ij)$ for some distinct $i$ and $j$ in $\{1,\dotsc,n\}$,) then $\pi$ and $\sigma$ are conjugate by a transposition.

Since if $(\sigma_1,\dotsc,\sigma_k)$ is a $k$-cycle and $\rho \in S_n$, we have $\rho(\sigma_1,\dotsc,\sigma_k)\rho^{-1} = (\sigma_{\rho(1)},\dotsc,\sigma_{\rho(k)})$, it should be simple to check whether $\sigma$ and $\pi$ are conjugate by a transposition: Write $\sigma$ and $\pi$ in cycle notation. If it is possible to arrange it so that $\sigma$ and $\pi$ differ in only two entries, then $\sigma$ and $\pi$ are conjugate by a transposition. If this is not possible, then they are not.

ETA – More generally, it should be possible to find a $\tau$ with minimal "complexity" (maybe in terms of cycle decomposition of $\tau$) with an adjustment of this method by writing $\sigma$ and $\tau$ in cycle notation with the fewest number of differing entries possible.

  • $\begingroup$ Great clarification. I am wondering why we use them? what makes them special (is there any property)? $\endgroup$ – Noah16 Jun 28 at 15:53
  • $\begingroup$ Also, (I think this is much harder) can we bound the maximum number of transpositions used for conjugation between two permutations? $\endgroup$ – Noah16 Jun 28 at 15:56
  • $\begingroup$ Any element of $S_n$ can be written as a product of transpositions! That's a fairly special property. $\endgroup$ – Rylee Lyman Jun 28 at 16:16
  • $\begingroup$ If we write $|\tau|$ for the minimal number of transpositions needed to write $\tau$ as a product of transpositions, since $S_n$ has $n!$ elements, there is a priori a maximum value of $|\tau|$ as $\tau$ varies. $\endgroup$ – Rylee Lyman Jun 28 at 16:18
  • $\begingroup$ More interesting would be, if $\sigma$ and $\pi$ are conjugate, to find a $\tau$ with $\pi = \tau\sigma\tau^{-1}$ and $|\tau|$ the minimum possible. $\endgroup$ – Rylee Lyman Jun 28 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.