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=gf(fg)(fg)=(fg)(gf)=f(gg)f=ff=1f g = g f \implies (f g) (f g) = (f g) (g f) = f (g g) f = f f = 1
(fg)(fg)=1fg=f((fg)(fg))g=(ff)(gf)(gg)=gf(f g) (f g) = 1 \implies f g = f ((f g) (f g)) g = (f f) (g f) (g g) = g f

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)

Last revised on January 26, 2021 at 07:40:30. See the history of this page for a list of all contributions to it.