Is every involution a palindrome of transpositions?

Question

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.

Answer 1

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.

Answer 2

It's not possible in general to express an involution as a palindrome of transpositions. In fact, because of cancellation properties, the only involutions that can be expressed as palindromes are (1) a single transposition, and (2) the identity.

Indeed, any even-length palindrome of transpositions cancels itself out: $$\pi_1\pi_2\ldots \pi_m \pi_m\ldots \pi_2\pi_1$$ Each consecutive pair of transpositions in the middle will cancel out successively until they're all gone.

On the other hand, an odd length palindrome has the form $$\pi_1\pi_2\ldots \pi_m \pi_{m+1}\pi_m\ldots \pi_2\pi_1$$. Grouping the other transpositions together, we see that it has the form $Q\cdot \pi_{m+1}\cdot Q^{-1}$ for some permutation $Q$. Hence the palindrome is conjugate to the transposition $\pi_{m+1}$ by similarity; it is therefore itself a single transposition.