# Composition of 2 involutions

How can we prove that any bijection on any set is a composition of 2 involutions ?

Since involutions are bijections mapping elements of a set to elements of the same set, I find it weird that this applies to any bijection.

• Here's an identical problem, differently phrased. Permutations are just bijections, and involutions are just elements of order 2: math.stackexchange.com/questions/1871783/… – Yacoub Kureh Oct 2 '16 at 23:19
• Your thinking is right: the question "how we can we prove that any bijection on any set is a composite of 2 involutions" is badly worded: the phrase "any bijection on any set" should read "any bijection from a set to itself". – Rob Arthan Oct 3 '16 at 0:29
• @YacoubKureh: permutations are more than just bijections: they are bijections from a set onto itself. – Rob Arthan Oct 3 '16 at 0:31

I assume that by "bijection" on a set $S$ you mean a bijection from $S$ to itself. The question would not make sense for a bijection from $S$ to some other set.

The bijection decomposes $S$ into orbits. It suffices to prove for a single orbit.

An orbit under the bijection is either a finite cycle $p_0 \to p_1 \to p_2\to \cdots \to p_n = p_0$ or a two-sided infinite sequence $\cdots \to p_{-2} \to p_{-1} \to p_0 \to p_{1} \to p_2 \to \cdots$.

In the infinite case, you can take the involutions $p_i \to p_{-i}$ and $p_i \to p_{1-i}$. In the finite case, $p_i \to p_{-i \pmod n}$ and $p_i \to p_{1-i \pmod n}$.

• This is a bit off topic, but is it actually logically impossible for there to exist an infinite length cycle? – DanielV Oct 3 '16 at 0:15
• What do you mean by an "infinite length cycle"? – Robert Israel Oct 3 '16 at 0:57
• I don't really understand what the pi's are, are they elements of S? How are the their composition equal to the bijection ? Could you please re-write this by specifying the bijection and the elements ? – TedMosby Oct 3 '16 at 19:50
• The $p_i$ are elements of $S$, forming an orbit of the bijection (which takes $p_i$ to $p_{i+1}$). The first involution takes each $p_i$ to the corresponding $p_{-i}$. The second involution takes each $p_i$ to $p_{1-i}$. Thus their composition takes $p_i$ to $p_{-i}$ to $p_{1-(-i)} = p_{i+1}$. – Robert Israel Oct 5 '16 at 4:55
• An orbit for bijection $f$ is a minimal nonempty set that is invariant under $f$ and $f^{-1}$. For any $p \in S$ the orbit containing $p$ consists of $f^{j}(p)$ for integers $j$. – Robert Israel Oct 26 '16 at 22:39