In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an involution, involutory function, or self-inverse function is a
function that is its own
inverse
Inverse or invert may refer to:
Science and mathematics
* Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence
* Additive inverse (negation), the inverse of a number that, when a ...
,
:
for all in the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
of . Equivalently, applying twice produces the original value.
General properties
Any involution is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
.
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 complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
(
),
reciprocation (
), and
complex conjugation (
) in
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
;
reflection, half-turn
rotation
Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...
, and
circle inversion in
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
;
complementation in
set theory
Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly concern ...
; 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 t ...
s such as the
ROT13 transformation and the
Beaufort Beaufort may refer to:
People and titles
* Beaufort (surname)
* House of Beaufort, English nobility
* Duke of Beaufort (England), a title in the peerage of England
* Duke of Beaufort (France), a title in the French nobility
Places Polar regions
* ...
polyalphabetic cipher
A polyalphabetic 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 is more complex but is st ...
.
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 v ...
of two involutions ''f'' and ''g'' is an involution if and only if they
commute
Commute, commutation or commutative may refer to:
* Commuting, the process of travelling between a place of residence and a place of work
Mathematics
* Commutative property, a property of a mathematical operation whose result is insensitive to th ...
: .
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:
:
and
for
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 (link will display the full calendar) 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'' ...
; these numbers are called the
telephone numbers
A telephone number is a sequence of digits assigned to a landline telephone subscriber station connected to a telephone line or to a wireless electronic telephony device, such as a radio telephone or a mobile telephone, or to other devices f ...
, 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 a ...
x with a given number of cells.
The number
can also be expressed by non-recursive formulas, such as the sum
The number of fixed points of an involution on a finite set and its
number of elements have the same
parity
Parity may refer to:
* Parity (computing)
** Parity bit in computing, sets the parity of data for the purpose of error detection
** Parity flag in computing, indicates if the number of set bits is odd or even in the binary representation of the ...
. 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 a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because
\begin
-2 \cdot 2 &= -4 \\
0 \cdot 2 &= 0 \\
41 ...
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
Pre-calculus
Some basic examples of involutions include the functions
the composition
and more generally the function
is an involution for constants
and
that satisfy
These are not the only pre-calculus involutions. Another one within the positive reals is
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 discre ...
of an involution (on the real numbers) is
symmetric 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.
Other elementary involutions are useful in
solving functional equations.
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, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
is
reflection Reflection or reflexion may refer to:
Science and technology
* Reflection (physics), a common wave phenomenon
** Specular reflection, reflection from a smooth surface
*** Mirror image, a reflection in a mirror or in water
** Signal reflection, in ...
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 R''n''. Such involutions are easy to characterize and they can be described geometrically.
Linear involutions
To give a ...
s.
Projective geometry
An involution is a
projectivity 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 is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
via Internet Archive
The Internet Archive is an American digital library with the stated mission of "universal access to all knowledge". It provides free public access to collections of digitized materials, including websites, software applications/games, music, ...
* Any projectivity that interchanges two points is an involution.
* The three pairs of opposite sides of a
complete quadrangle meet any line (not through a vertex) in three pairs of an involution. This theorem has been called
Desargues
Girard Desargues (; 21 February 1591 – September 1661) was a French mathematician and engineer, who is considered one of the founders of projective geometry. Desargues' theorem, the Desargues graph, and the crater Desargues on the Moo ...
'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 (; grc-gre, Πάππος ὁ Ἀλεξανδρεύς; AD) was one of the last great Greek mathematicians of antiquity known for his ''Synagoge'' (Συναγωγή) or ''Collection'' (), and for Pappus's hexagon theorem i ...
.
* 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 which 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 statistic ...
of period 2.
Linear algebra
In linear algebra, an involution is a linear operator ''T'' on a vector space, such that . Except for in characteristic 2, such operators are diagonalizable for a given basis with just 1s and −1s 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 ''V'' is chosen, and that ''e''1 and ''e''2 are basis elements. There exists a linear transformation ''f'' which sends ''e''1 to ''e''2, and sends ''e''2 to ''e''1, and which is the identity on all other basis vectors. It can be checked that for all ''x'' in ''V''. That is, ''f'' is an involution of ''V''.
For a specific basis, any linear operator can be represented by a matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** '' The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
''T''. Every matrix has a transpose
In linear algebra, the transpose of a 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 notations).
The tr ...
, obtained by swapping rows for columns. This transposition is an involution on the set of matrices.
The definition of involution extends readily to modules
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a s ...
. Given a module ''M'' over a ring ''R'', an ''R'' 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 gr ...
''f'' of ''M'' is called an involution if ''f'' 2 is the identity homomorphism on ''M''.
Involutions are related to idempotents; if 2 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 (e.g. inner product, norm, topology, etc.) and the linear functions defi ...
, 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 Banac ...
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 continuou ...
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 ...
s with involutions.
Quaternion algebra, groups, semigroups
In a quaternion algebra
In mathematics, a quaternion algebra over a 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 4 over ''F''. Every quaternion algebra becomes a ma ...
, an (anti-)involution is defined by the following axioms: if we consider a transformation then it is an involution if
* (it is its own inverse)
* and (it is linear)
*
An anti-involution does not obey the last axiom but instead
*
This former law is sometimes called antidistributive
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
. It also appears in groups
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 ide ...
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, consider ...
, of which there are natural examples that are not groups, for example square matrix multiplication (i.e. the full linear monoid) with transpose
In linear algebra, the transpose of a 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 notations).
The tr ...
as the involution.
Ring theory
In ring theory
In algebra, ring theory is the study of rings—algebraic structures in which addition and multiplication are defined and have similar properties to those operations defined for the integers. Ring theory studies the structure of rings, their r ...
, the word ''involution'' is customarily taken to mean an antihomomorphism
In mathematics, an antihomomorphism is a type of function defined on sets with multiplication that reverses the order of multiplication. An antiautomorphism is a bijective antihomomorphism, i.e. an antiisomorphism, from a set to itself. From ...
that is its own inverse function.
Examples of involutions in common rings:
* 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, then) the complex conjugate of a + bi is equal to a - ...
on the complex plane
In mathematics, the complex plane is the plane formed by the complex numbers, with a Cartesian coordinate system such that the -axis, called the real axis, is formed by the real numbers, and the -axis, called the imaginary axis, is formed by the ...
* multiplication by j in the split-complex number
In algebra, a split complex number (or hyperbolic number, also perplex number, double number) has two real number components and , and is written z=x+yj, where j^2=1. The ''conjugate'' of is z^*=x-yj. Since j^2=1, the product of a number wi ...
s
* taking the transpose in a matrix ring.
Group theory
In group theory
In abstract algebra, group theory studies the algebraic structures known as groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen ...
, 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 ide ...
is an involution if it has order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
2; i.e. an involution is an element such that and ''a''2 = ''e'', where ''e'' is the identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
.
Originally, this definition agreed with the first definition above, since members of groups were always bijections from a set into itself; i.e., ''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 is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
is an involution precisely 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 the finite simple groups is a result of group theory stating that every finite simple group is either cyclic, or alternating, or it belongs to a broad infinite class called the groups of Lie type, or else i ...
.
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 refle ...
s are groups generated by involutions with the relations determined only by relations given for pairs of the generating involutions. Coxeter groups can be used, among other things, to describe the possible regular polyhedra 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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s is an involution. Accordingly, negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
in classical logic satisfies the '' law of double negation:'' ¬¬''A'' is equivalent to ''A''.
Generally in non-classical logics, 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'').
Computing
In some pro ...
s. Examples of logics which 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 indetermina ...
s, Łukasiewicz many-valued logic, 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 completel ...
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.
The involutiveness of negation is an important characterization property for logics and the corresponding varieties of algebras. For instance, involutive negation characterizes 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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
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'' of '' ...
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 variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
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 Łukasiew ...
s and BL-algebras (and so correspondingly between Łukasiewicz logic and fuzzy logic BL), IMTL and MTL, and other pairs of important varieties of algebras (resp. corresponding logics).
In the study of binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
s, every relation has a converse relation
In mathematics, the converse relation, or transpose, 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&n ...
. 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 rel ...
. Binary relations are ordered through inclusion. While this ordering is reversed with the complementation involution, it is preserved under conversion.
Computer science
The XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
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 oper ...
with a given value for one parameter is an involution. XOR masks
A mask is an object normally worn on the face, typically for protection, disguise, performance, or entertainment and often they have been employed for rituals and rights. Masks have been used since antiquity for both ceremonial and pract ...
were once used to draw graphics on images in such a way that drawing them twice on the background reverts the background to its original state. The NOT bitwise operation is also an involution, and is a special case of the XOR operation where one parameter has all bits set to 1.
Another example is a bit mask and shift function operating on color values stored as integers, say in the form RGB, that swaps R and B, resulting in the form BGR.
f(f(RGB))=RGB, f(f(BGR))=BGR.
The RC4
In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...
cryptographic cipher is an involution, as encryption and decryption operations use the same function.
Practically all mechanical cipher machines implement a 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 t ...
, 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.[
Greg Goebel]
"The Mechanization of Ciphers"
2018.
See also
* Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphis ...
* Idempotence
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
* ROT13
References
Further reading
*
*
* {{springer, title=Involution, id=p/i052510
Algebraic properties of elements
Functions and mappings