Contents

Definition

Such an endomorphism is necessarily an automorphism, being its own inverse.

In dependent type theory

In dependent type theory, there are two different notions of involution.

Properties

Commuting involutions

Two involutions $f, g \colon X \to X$ commute if and only if their composition $f g$ is also an involution, as shown by the following manipulations:

Fixed point free involutions

In combinatorics, an important class of involutions are the fixed point free ones: an arbitrary involution on a finite set of cardinality $n$ may be specified by the choice of $k$ elements which are fixed together with a fixed point free involution on the remaining $(n-k)$. The number of fixed point free involutions on a set of $2n$ labelled elements is counted by the double factorial $(2n-1)!! = (2n-1)\cdot (2n-3)\cdot\dots\cdot 3\cdot 1 = \frac{(2n)!}{2^n n!}$, while arbitrary involutions on a set of $n$ labelled elements are counted by OEIS sequence A000085, which also counts the number of Young tableaux with $n$ cells.

Monad of involutions

An involution on a set $X$ is the same thing as an action of $\mathbb{Z}/2\mathbb{Z}$ on $X$.

More generally, let $(C,\otimes,1)$ be a monoidal category with distributive finite coproducts. The object $2 = 1 + 1$ is equipped with an involution

defined as the copairing $not = [inr,inl]$ of the right and left injections. Moreover, 2 can be given the structure of a monoid in $C$, with unit and multiplication

defined by $false = inl$ and $xor = [id,not]$ (here we make use of the isomorphism $2 \otimes 2 \cong 2 + 2$ to define $xor$ by copairing). The mapping

thus extends to a monad on $C$, sending any object $X$ to the free object equipped with an involution over $X$. Explicitly, the unit $\eta_X : X \to 2\otimes X$ and the multiplication $\mu_X : 2\otimes 2\otimes X \to 2\otimes X$ of the monad are defined by tensoring the unit and the multiplication of the monoid with the identity on $X$, while the involution on $2 \otimes X$ is likewise defined by tensoring the involution on 2 with the identity on $X$.

We then have that involutions in $C$ are precisely the algebras of the monad $(2\otimes-,false\otimes-,xor\otimes-)$. In the forward direction, given an involution $f : X \to X$, we define a monad algebra structure $\alpha : 2\otimes X \to X$ on $X$ by $\alpha = [id,f]$ (again using the isomorphism $2\otimes X \cong X+X$). Conversely, given a monad algebra $\alpha : 2\otimes X \to X$, we can define an endomorphism $f : X \to X$ by $f = \alpha \circ inr$. The monad algebra laws imply that

and since $xor$ is defined such that $(xor\otimes id) \circ (2\otimes inr) \circ inr = id$, we derive that $\alpha \circ inr$ is an involution.

Related concepts

• star-algebra

• dagger category

• complex conjugation

• anti-linear map, anti-dual linear space

• duality

• involutive Hopf algebra

• idempotent

References

Discussion in combinatorics:

• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, CUP, 2009. (author pdf)

Discussion in differential topology:

• Santiago López de Medrano, Involutions on Manifolds, Ergebnisse der Mathematik und ihrer Grenzgebiete 59, Springer 1971 (doi:10.1007/978-3-642-65012-3)