mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, an involution, involutory function, or self-inverse function is a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...

that is its own inverse, : for all in the

domain A domain is a geographic area controlled by a single person or organization. Domain may also refer to: Law and human geography * Demesne, in English common law and other Medieval European contexts, lands directly managed by their holder rather ...

of . Equivalently, applying twice produces the original value.

General properties

Any involution is a

bijection In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

. The

identity map Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...

is a trivial example of an involution. Examples of nontrivial involutions include

negation In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...

(), reciprocation (), and

complex conjugation In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, if a and b are real numbers, then the complex conjugate of a + bi is a - ...

() in

arithmetic Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and taking logarithms. ...

; reflection, half-turn

rotation Rotation or rotational/rotary motion is the circular movement of an object around a central line, known as an ''axis of rotation''. A plane figure can rotate in either a clockwise or counterclockwise sense around a perpendicular axis intersect ...

, and

circle inversion In geometry, inversive geometry is the study of ''inversion'', a transformation of the Euclidean plane that maps circles or lines to other circles or lines and that preserves the angles between crossing curves. Many difficult problems in geometry ...

geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

; complementation in

set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...

; and

reciprocal cipher Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between ...

s such as the

ROT13 ROT13 is a simple letter substitution cipher that replaces a letter with the 13th letter after it in the Latin alphabet. ROT13 is a special case of the Caesar cipher which was developed in ancient Rome, used by Julius Caesar in the 1st centur ...

transformation and the Beaufort

polyalphabetic cipher A polyalphabetic cipher is a substitution cipher, substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine i ...

. The

composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography * Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...

of two involutions and is an involution if and only if they commute: .

Involutions on finite sets

The number of involutions, including the identity involution, on a set with elements is given by a

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

found by

Heinrich August Rothe Heinrich August Rothe (1773–1842) was a German mathematician, a professor of mathematics at Erlangen. He was a student of Carl Hindenburg and a member of Hindenburg's school of combinatorics. Biography Rothe was born in 1773 in Dresden, and in ...

in 1800: :

a_0 = a_1 = 1

and

a_n = a_ + (n - 1)a_

for

n > 1.

The first few terms of this sequence are 1, 1, 2, 4, 10, 26, 76,

232 Year 232 ( CCXXXII) was a leap year starting on Sunday of the Julian calendar. At the time, it was known as the Year of the Consulship of Lupus and Maximus (or, less frequently, year 985 ''Ab urbe condita''). The denomination 232 for this year ...

; these numbers are called the

telephone numbers A telephone number is the address of a telecommunication endpoint, such as a telephone, in a telephone network, such as the public switched telephone network (PSTN). A telephone number typically consists of a sequence of digits, but histori ...

, and they also count the number of

Young tableau In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups an ...

x with a given number of cells. The number can also be expressed by non-recursive formulas, such as the sum

a_n = \sum_^ \frac .

The number of fixed points of an involution on a finite set and its

number of elements In mathematics, the cardinality of a finite set is the number of its elements, and is therefore a measure of size of the set. Since the discovery by Georg Cantor, in the late 19th century, of different sizes of infinite sets, the term ''cardinal ...

have the same parity. Thus the number of fixed points of all the involutions on a given finite set have the same parity. In particular, every involution on an

odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...

of elements has at least one fixed point. This can be used to prove Fermat's two squares theorem.

Involution throughout the fields of mathematics

Real-valued functions

The

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

of an involution (on the real numbers) is

symmetric Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...

across the line . This is due to the fact that the inverse of any ''general'' function will be its reflection over the line . This can be seen by "swapping" with . If, in particular, the function is an ''involution'', then its graph is its own reflection. Some basic examples of involutions include the functions

\begin
f(x) &= a-x \; , \\
f(x) &= \frac+a
\end

Besides, we can construct an involution by wrapping an involution in a bijection and its inverse (

h^ \circ  g \circ h

). For instance :

& \bigl(g(x) = 1-x \quad\textrm\quad h(x) = x^2\bigr), \\ f(x) &= \ln\left(\frac \right) & \bigl(g(x) = \frac=\frac+1 \quad\textrm\quad h(x) = e^x\bigr) \\ \end

Euclidean geometry

A simple example of an involution of the three-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

is reflection through a plane. Performing a reflection twice brings a point back to its original coordinates. Another involution is reflection through the origin; not a reflection in the above sense, and so, a distinct example. These transformations are examples of

affine involution In Euclidean geometry, of special interest are involutions which are linear or affine transformations over the Euclidean space Such involutions are easy to characterize and they can be described geometrically. Linear involutions To give a linea ...

Projective geometry

An involution is a

projectivity In projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps line (geometry), lines to lines, and thus a collineati ...

of period 2, that is, a projectivity that interchanges pairs of points.A.G. Pickford (1909
Elementary Projective Geometry

Cambridge University Press Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...

via

Internet Archive The Internet Archive is an American 501(c)(3) organization, non-profit organization founded in 1996 by Brewster Kahle that runs a digital library website, archive.org. It provides free access to collections of digitized media including web ...

* Any projectivity that interchanges two points is an involution. * The three pairs of opposite sides of a

complete quadrangle In mathematics, specifically in incidence geometry and especially in projective geometry, a complete quadrangle is a system of geometric objects consisting of any four points in a plane, no three of which are on a common line, and of the six ...

meet any line (not through a vertex) in three pairs of an involution. This theorem has been called Desargues's Involution Theorem. Its origins can be seen in Lemma IV of the lemmas to the ''Porisms'' of Euclid in Volume VII of the ''Collection'' of

Pappus of Alexandria Pappus of Alexandria (; ; AD) was a Greek mathematics, Greek mathematician of late antiquity known for his ''Synagoge'' (Συναγωγή) or ''Collection'' (), and for Pappus's hexagon theorem in projective geometry. Almost nothing is known a ...

. * If an involution has one fixed point, it has another, and consists of the correspondence between harmonic conjugates with respect to these two points. In this instance the involution is termed "hyperbolic", while if there are no fixed points it is "elliptic". In the context of projectivities, fixed points are called double points. Another type of involution occurring in projective geometry is a polarity that is a

correlation In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...

of period 2.

Linear algebra

In linear algebra, an involution is a linear operator on a vector space, such that . Except for in characteristic 2, such operators are diagonalizable for a given basis with just s and s on the diagonal of the corresponding matrix. If the operator is orthogonal (an orthogonal involution), it is orthonormally diagonalizable. For example, suppose that a basis for a vector space is chosen, and that and are basis elements. There exists a linear transformation that sends to , and sends to , and that is the identity on all other basis vectors. It can be checked that for all in . That is, is an involution of . For a specific basis, any linear operator can be represented by a

matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

. Every matrix has a

transpose In linear algebra, the transpose of a Matrix (mathematics), matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other ...

, obtained by swapping rows for columns. This transposition is an involution on the set of matrices. Since elementwise

is an independent involution, the

conjugate transpose In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \mathbf is an n \times m matrix obtained by transposing \mathbf and applying complex conjugation to each entry (the complex conjugate ...

Hermitian adjoint In mathematics, specifically in operator theory, each linear operator A on an inner product space defines a Hermitian adjoint (or adjoint) operator A^* on that space according to the rule :\langle Ax,y \rangle = \langle x,A^*y \rangle, where \l ...

is also an involution. The definition of involution extends readily to modules. Given a module over a

ring (The) Ring(s) may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...

, an

endomorphism In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a g ...

of is called an involution if is the identity homomorphism on . Involutions are related to idempotents; if is invertible then they correspond in a one-to-one manner. In

functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...

Banach *-algebra In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra A over the real or complex numbers (or over a non-Archimedean complete normed field) that at the same time is also a Banach sp ...

s and

C*-algebra In mathematics, specifically in functional analysis, a C∗-algebra (pronounced "C-star") is a Banach algebra together with an involution satisfying the properties of the adjoint. A particular case is that of a complex algebra ''A'' of contin ...

s are special types of

Banach algebra In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra A over the real or complex numbers (or over a non-Archimedean complete normed field) that at the same time is also a Banach sp ...

s with involutions.

Quaternion algebra, groups, semigroups

In a

quaternion algebra In mathematics, a quaternion algebra over a field (mathematics), field ''F'' is a central simple algebra ''A'' over ''F''See Milies & Sehgal, An introduction to group rings, exercise 17, chapter 2. that has dimension (vector space), dimension 4 ove ...

, an (anti-)involution is defined by the following axioms: if we consider a transformation

x \mapsto f(x)

then it is an involution if *

f(f(x))=x

(it is its own inverse) *

f(x_1+x_2)=f(x_1)+f(x_2)

and

f(\lambda x)=\lambda f(x)

(it is linear) *

f(x_1 x_2)=f(x_1) f(x_2)

An anti-involution does not obey the last axiom but instead *

f(x_1 x_2)=f(x_2) f(x_1)

This former law is sometimes called antidistributive. It also appears in groups as . Taken as an axiom, it leads to the notion of

semigroup with involution In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, conside ...

, of which there are natural examples that are not groups, for example square matrix multiplication (i.e. the full linear monoid) with

as the involution.

Ring theory

In ring theory, the word ''involution'' is customarily taken to mean an antihomomorphism that is its own inverse function. Examples of involutions in common rings: *

on the

complex plane In mathematics, the complex plane is the plane (geometry), plane formed by the complex numbers, with a Cartesian coordinate system such that the horizontal -axis, called the real axis, is formed by the real numbers, and the vertical -axis, call ...

, and its equivalent in the

split-complex number In algebra, a split-complex number (or hyperbolic number, also perplex number, double number) is based on a hyperbolic unit satisfying j^2=1, where j \neq \pm 1. A split-complex number has two real number components and , and is written z=x+y ...

s * taking the transpose in a matrix ring.

Group theory

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...

, an element of a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

is an involution if it has

order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...

2; that is, an involution is an element such that and , where is the

identity element In mathematics, an identity element or neutral element of a binary operation is an element that leaves unchanged every element when the operation is applied. For example, 0 is an identity element of the addition of real numbers. This concept is use ...

. Originally, this definition agreed with the first definition above, since members of groups were always bijections from a set into itself; that is, ''group'' was taken to mean ''

permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...

''. By the end of the 19th century, ''group'' was defined more broadly, and accordingly so was ''involution''. A

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

is an involution if and only if it can be written as a finite product of disjoint transpositions. The involutions of a group have a large impact on the group's structure. The study of involutions was instrumental in the

classification of finite simple groups In mathematics, the classification of finite simple groups (popularly called the enormous theorem) is a result of group theory stating that every List of finite simple groups, finite simple group is either cyclic group, cyclic, or alternating gro ...

. An element of a group is called strongly real if there is an involution with (where ).

Coxeter group In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean ref ...

s are groups generated by a set of involutions subject only to relations involving powers of pairs of elements of . Coxeter groups can be used, among other things, to describe the possible

regular polyhedra A regular polyhedron is a polyhedron whose symmetry group acts transitively on its flags. A regular polyhedron is highly symmetrical, being all of edge-transitive, vertex-transitive and face-transitive. In classical contexts, many different eq ...

and their generalizations to higher dimensions.

Mathematical logic

The operation of complement in

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

s is an involution. Accordingly,

classical logic Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy. Characteristics Each logical system in this c ...

satisfies the '' law of double negation'': is equivalent to . Generally in

non-classical logic Non-classical logics (and sometimes alternative logics or non-Aristotelian logics) are formal systems that differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this ...

s, negation that satisfies the law of double negation is called ''involutive''. In algebraic semantics, such a negation is realized as an involution on the algebra of

truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Truth values are used in ...

s. Examples of logics that have involutive negation are Kleene and Bochvar

three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'', and some third value ...

s, Łukasiewicz many-valued logic, the

fuzzy logic Fuzzy logic is a form of many-valued logic in which the truth value of variables may be any real number between 0 and 1. It is employed to handle the concept of partial truth, where the truth value may range between completely true and completely ...

' involutive monoidal t-norm logic' (IMTL), etc. Involutive negation is sometimes added as an additional connective to logics with non-involutive negation; this is usual, for example, in

t-norm fuzzy logics T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real number, real unit interval , 1for the system of truth values and functions called t-norms for permissible interpretatio ...

. The involutiveness of negation is an important characterization property for logics and the corresponding varieties of algebras. For instance, involutive negation characterizes

s among

Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' call ...

s. Correspondingly, classical

Boolean logic In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

arises by adding the law of double negation to

intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...

. The same relationship holds also between

MV-algebra In abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation \oplus, a unary operation \neg, and the constant 0, satisfying certain axioms. MV-algebras are the algebraic semantics of Łukasiewic ...

s and BL-algebras (and so correspondingly between

Łukasiewicz logic In mathematics and philosophy, Łukasiewicz logic ( , ) is a non-classical, many-valued logic. It was originally defined in the early 20th century by Jan Łukasiewicz as a three-valued modal logic;Łukasiewicz J., 1920, O logice trójwartościow ...

and fuzzy logic BL), IMTL and MTL, and other pairs of important varieties of algebras (respectively, corresponding logics). In the study of

binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...

s, every relation has a

converse relation In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms ...

. Since the converse of the converse is the original relation, the conversion operation is an involution on the

category of relations In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms. A morphism (or arrow) ''R'' : ''A'' → ''B'' in this category is a relation between the sets ''A'' and ''B'', so . The composition of two re ...

. Binary relations are ordered through

inclusion Inclusion or Include may refer to: Sociology * Social inclusion, action taken to support people of different backgrounds sharing life together. ** Inclusion (disability rights), promotion of people with disabilities sharing various aspects of lif ...

. While this ordering is reversed with the complementation involution, it is preserved under conversion.

Computer science

The

XOR Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one ...

bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operatio ...

with a given value for one parameter is an involution on the other parameter. XOR

masks A mask is an object normally worn on the face, typically for protection, disguise, performance, or entertainment, and often employed for rituals and rites. Masks have been used since antiquity for both ceremonial and practical purposes, ...

in some instances were used to draw graphics on images in such a way that drawing them twice on the background reverts the background to its original state. Two special cases of this, which are also involutions, are the

bitwise NOT In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operatio ...

operation which is XOR with an all-ones value, and

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystrea ...

encryption In Cryptography law, cryptography, encryption (more specifically, Code, encoding) is the process of transforming information in a way that, ideally, only authorized parties can decode. This process converts the original representation of the inf ...

, which is an XOR with a secret

keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext). The "characters" in the keystream can be bit The bit is the most basic ...

. This predates binary computers; practically all mechanical cipher machines implement a

, an involution on each typed-in letter. Instead of designing two kinds of machines, one for encrypting and one for decrypting, all the machines can be identical and can be set up (keyed) the same way. Another involution used in computers is an order-2 bitwise permutation. For example. a color value stored as integers in the form , could exchange and , resulting in the form : .

Physics

Legendre transformation In mathematics, the Legendre transformation (or Legendre transform), first introduced by Adrien-Marie Legendre in 1787 when studying the minimal surface problem, is an involutive transformation on real-valued functions that are convex on a rea ...

, which converts between the Lagrangian and

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

, is an involutive operation. Integrability, a central notion of physics and in particular the subfield of

integrable systems In mathematics, integrability is a property of certain dynamical systems. While there are several distinct formal definitions, informally speaking, an integrable system is a dynamical system with sufficiently many conserved quantities, or first ...

, is closely related to involution, for example in context of

Kramers–Wannier duality The Kramers–Wannier duality is a symmetry in statistical physics. It relates the free energy of a two-dimensional square-lattice Ising model at a low temperature to that of another Ising model at a high temperature. It was discovered by Hendr ...

References

External links

* {{Commonscatinline, Involution Algebraic properties of elements Functions and mappings