An involution is a permutation $P$ which is its own inverse: $P\cdot P = \text{id}$.

Every permutation can be written (in various ways) as a sequence of single-element swaps (transpositions). Sometimes these sequences are palindromes, in that the reversal of the sequence is the same sequence.

If $T$ is a sequence of transpositions for $P$, then the reversal of $T$ is a sequence of transpositions for $P^{-1}$. It follows that if the sequence $T$ is a palindrome, then $P$ is an involution.

I'm wondering whether the converse is true:

Conjecture: Any involution $P$ can be decomposed into a sequence of transpositions which is a palindrome.

— and if it's false, if there is any alternative way to characterize the involutions which can be decomposed in such a way.


Suppose we have a product of transpositions $\tau=\pi_1\pi_2\ldots\pi_n$ with $\pi_j=\pi_{n+1-j}$ for all $j$.

If $n=2m$ is even then $$\tau=\pi_1\cdots\pi_m\pi_m\cdots\pi_1$$ which cancels off from the middle to give the identity.

If $n=2m+1$ is odd then $$\tau=\pi_1\cdots\pi_m\pi_{m+1}\pi_m\cdots\pi_1 =\sigma\tau_{m+1}\sigma^{-1}$$ where $\sigma=\pi_1\cdots\pi_m$. Thus $\tau$ is a conjugate of the transposition $\pi_{m+1}$ and so a transposition itself.

Either way $\tau$ cannot be an involution with two or more cycles.

  • $\begingroup$ I see --- you're saying that the conjecture is false. In particular, every palindrome can be rewritten as the identity if it's even length, or as the single middle transposition if it's odd. Is that right? $\endgroup$ – user326210 Sep 7 '17 at 6:39
  • $\begingroup$ @user326210 As a conjugate of the middle transposition in the odd case - and hence a single transposition, because conjugation preserves cycle-type. $\endgroup$ – Mark Bennet Sep 7 '17 at 7:01
  • $\begingroup$ In this context, isn't the key property of involutions that they can be decomposed into disjoint 1- and 2-cycles, i.e. an involution either fixes a point, or swaps pairs independently of any other points? $\endgroup$ – Paul Aljabar Sep 7 '17 at 13:19

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.