5
$\begingroup$

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.

Thanks for your help !

$\endgroup$
  • 1
    $\begingroup$ Here's an identical problem, differently phrased. Permutations are just bijections, and involutions are just elements of order 2: math.stackexchange.com/questions/1871783/… $\endgroup$ – Yacoub Kureh Oct 2 '16 at 23:19
  • 1
    $\begingroup$ 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". $\endgroup$ – Rob Arthan Oct 3 '16 at 0:29
  • 1
    $\begingroup$ @YacoubKureh: permutations are more than just bijections: they are bijections from a set onto itself. $\endgroup$ – Rob Arthan Oct 3 '16 at 0:31
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ This is a bit off topic, but is it actually logically impossible for there to exist an infinite length cycle? $\endgroup$ – DanielV Oct 3 '16 at 0:15
  • 1
    $\begingroup$ What do you mean by an "infinite length cycle"? $\endgroup$ – Robert Israel Oct 3 '16 at 0:57
  • 1
    $\begingroup$ 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 ? $\endgroup$ – TedMosby Oct 3 '16 at 19:50
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Robert Israel Oct 5 '16 at 4:55
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Oct 26 '16 at 22:39

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.