Permutations – Is Any Permutation the Product of Two Involutions?

combinatoricspermutations

The abstract of this paper says:

"It is well-known that any permutation can be written as a product of two involutions."

I was looking for any web resource that can provide an affirmation and (hopefully easy) proof of this statement — can anyone please help?

And if any permutation can indeed be written as a product of two involutions, are the following guesses correct?

  1. If $P$ is a permutation and $X$ & $Y$ are involutions, and $P = XY$, then $P^{-1} = YX$
  2. If $X$ & $Y$ are distinct involutions such that neither is the identity permutation $I$, then the permutation $XY$ is not an involution.
  3. The only ways to express any involution $X$ as a product of two involutions is $X = XI$ & $X = IX$ (given that $I$ itself is an involution)

Thanks …

Best Answer

For your three numbered statements, $(1)$ is true (easy proof), but $(2)$ and $(3)$ are false. A counter example for $(2)$ is obtained by taking $X = (1,2)$ and $Y = (3,4)$. Then $XY = (1,2)(3,4)$ is an involution as well. A counterexample for $(3)$ is obtained from this example as well; the involution $X = (1,2)(3,4)$ can be factored as $YZ$ where $Y = (1,2)$ and $Z = (3,4)$.

As for the statement in question, here's a quick proof sketch:

(1) By using the disjoint cycle decomposition, you can reduce to proving that the cycle $(1,2,3,\dots,n)$ can be written as a product of two involutions in $S_n$.

(2) To handle that case, draw $n$ vertices in the plane (labelled $1,2,\dots,n$) and connect the $n$ vertices by drawing $n-1$ edges. This will make a unique (up to choice of direction to travel) path in your graph. Label the edges $1,2,\dots,n-1$ in the order of the path. For each edge, put the two vertices connected by that edge into a two-cycle. Then form $\pi_1$, the product of the two-cycles formed in this way from odd-numbered edges, and $\pi_2$, the product of the two-cycles formed in this way from even-numbered edges. Then the product $\pi_2 \pi_1$ is an $n$-cycle $\tau$. This needs to be checked; in fact, if you number the vertices in the order of the path, then $\tau = (1,3,5,\dots, 6,4,2)$. Conjugate the relation $\tau = \pi_2 \pi_1$ to get that $(1,2,\dots,n)$ is a product of two involutions.

Related Question