An involution is an endomorphism whose square is the identity morphism. Such an endomorphism must be an automorphism; indeed, it is its own inverse.

Where this makes sense, an anti-involution is an antihomomorphism instead of a homomorphism (so an antiendomorphism and necessarily an antiautomorphism).


Commuting involutions

Two involutions f,g:XXf, g : X \to X commute if and only if their composition fgf g is also an involution, as displayed by the following algebra:

fg=f(fgfg)g=(ff)gf(gg)=gff g = f (f g f g ) g = (f f) g f (g g) = g f
(fg)(fg)=f(gf)g=f(fg)g=(ff)(gg)=1(f g)(f g) = f (g f) g = f (f g) g = (f f)(g g)= 1

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 nn may be specified by the choice of kk elements which are fixed together with a fixed point free involution on the remaining (nk)(n-k). The number of fixed point free involutions on a set of 2n2n labelled elements is counted by the double factorial (2n1)!!=(2n1)(2n3)31=(2n)!2 nn!(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 nn labelled elements are counted by OEIS sequence A000085, which also counts the number of Young tableaux with nn cells.

Monad of involutions

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

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

not:22 not : 2 \to 2

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

false:12xor:222false : 1 \to 2 \qquad xor : 2 \otimes 2 \to 2

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

X2XX+X X \mapsto 2 \otimes X \cong X + X

thus extends to a monad on CC, sending any object XX to the free object equipped with an involution over XX. Explicitly, the unit η X:X2X\eta_X : X \to 2\otimes X and the multiplication μ X:22X2X\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 XX, while the involution on 2X2 \otimes X is likewise defined by tensoring the involution on 2 with the identity on XX.

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

αinrαinr=α(2α)(2inr)inr=α(xorid)(2inr)inr\alpha \circ inr \circ \alpha \circ inr = \alpha \circ (2\otimes \alpha) \circ (2\otimes inr) \circ inr = \alpha \circ (xor\otimes id) \circ (2\otimes inr) \circ inr

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


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

Revised on October 14, 2016 13:24:20 by Urs Schreiber (