In
mathematics, an invariant is a property of a
mathematical object
A mathematical object is an abstract concept arising in mathematics.
In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical ...
(or a
class of mathematical objects) which remains unchanged after
operations
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
or
transformations of a certain type are applied to the objects.
The particular class of objects and type of transformations are usually indicated by the context in which the term is used. For example, the
area
Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while ''surface area'' refers to the area of an open su ...
of a
triangle
A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, any three points, when non- colli ...
is an invariant with respect to
isometries of the
Euclidean plane. The phrases "invariant under" and "invariant to" a transformation are both used. More generally, an invariant with respect to an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relatio ...
is a property that is constant on each
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
.
Invariants are used in diverse areas of mathematics such as
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 ...
,
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
,
algebra
Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...
and
discrete mathematics. Some important classes of transformations are defined by an invariant they leave unchanged. For example,
conformal map
In mathematics, a conformal map is a function that locally preserves angles, but not necessarily lengths.
More formally, let U and V be open subsets of \mathbb^n. A function f:U\to V is called conformal (or angle-preserving) at a point u_0\in ...
s are defined as transformations of the plane that preserve
angle
In Euclidean geometry, an angle is the figure formed by two rays, called the '' sides'' of the angle, sharing a common endpoint, called the '' vertex'' of the angle.
Angles formed by two rays lie in the plane that contains the rays. Angles ...
s. The discovery of invariants is an important step in the process of classifying mathematical objects.
Examples
A simple example of invariance is expressed in our ability to
count
Count (feminine: countess) is a historical title of nobility in certain European countries, varying in relative status, generally of middling rank in the hierarchy of nobility. Pine, L. G. ''Titles: How the King Became His Majesty''. New Yor ...
. For a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
of objects of any kind, there is a number to which we always arrive, regardless of the
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 d ...
in which we count the objects in the
set. The quantity—a
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
—is associated with the set, and is invariant under the process of counting.
An
identity is an equation that remains true for all values of its variables. There are also
inequalities that remain true when the values of their variables change.
The
distance between two points on a
number line is not changed by
adding the same quantity to both numbers. On the other hand,
multiplication does not have this same property, as distance is not invariant under multiplication.
Angle
In Euclidean geometry, an angle is the figure formed by two rays, called the '' sides'' of the angle, sharing a common endpoint, called the '' vertex'' of the angle.
Angles formed by two rays lie in the plane that contains the rays. Angles ...
s and
ratios of distances are invariant under
scalings,
rotations,
translation
Translation is the communication of the Meaning (linguistic), meaning of a #Source and target languages, source-language text by means of an Dynamic and formal equivalence, equivalent #Source and target languages, target-language text. The ...
s and
reflections. These transformations produce
similar shapes, which is the basis of
trigonometry. In contrast, angles and ratios are not invariant under non-uniform scaling (such as stretching). The sum of a triangle's interior angles (180°) is invariant under all the above operations. As another example, all
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
s are similar: they can be transformed into each other and the ratio of the
circumference
In geometry, the circumference (from Latin ''circumferens'', meaning "carrying around") is the perimeter of a circle or ellipse. That is, the circumference would be the arc length of the circle, as if it were opened up and straightened out t ...
to the
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
is invariant (denoted by the Greek letter π (
pi)).
Some more complicated examples:
* The
real part and the
absolute value of a
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
are invariant under
complex conjugation.
* The
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
of a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
is invariant under a linear change of variables.
* The
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
and
homology groups of a topological object are invariant under
homeomorphism.
* The number of
fixed points of a
dynamical system
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water i ...
is invariant under many mathematical operations.
* Euclidean distance is invariant under
orthogonal transformations.
* Euclidean area is invariant under
linear maps which have
determinant ±1 (see ).
* Some invariants of
projective transformations include
collinearity of three or more points,
concurrency
Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to:
Law
* Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea''
* Concurring opinion (also called a "concurrence"), a ...
of three or more lines,
conic section
In mathematics, a conic section, quadratic curve or conic is a curve obtained as the intersection of the surface of a cone with a plane. The three types of conic section are the hyperbola, the parabola, and the ellipse; the circle is a ...
s, the
cross-ratio.
* The
determinant,
trace, and
eigenvectors and
eigenvalues of a
square matrix are invariant under
changes of basis. In other words, the
spectrum of a matrix is invariant to the change of basis.
* The principal invariants of
tensors do not change with rotation of the coordinate system (see
Invariants of tensors).
* The
singular values of 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 ...
are invariant under orthogonal transformations.
*
Lebesgue measure is invariant under translations.
* The
variance
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of number ...
of a
probability distribution is invariant under translations of the
real line
In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...
; hence the variance of a
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the p ...
is unchanged after the addition of a constant.
* The
fixed points of a transformation are the elements in the
domain that are invariant under the transformation. They may, depending on the application, be called
symmetric with respect to that transformation. For example, objects with
translational symmetry are invariant under certain translations.
*The integral
of the Gaussian curvature
of a 2-dimensional
Riemannian manifold is invariant under changes of the
Riemannian metric ''
''. This is the
Gauss–Bonnet theorem.
*
Differential invariants for
differential equations
In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, a ...
MU puzzle
The
MU puzzle is a good example of a logical problem where determining an invariant is of use for an
impossibility proof
In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. Such a case is also known as a negative ...
. The puzzle asks one to start with the word MI and transform it into the word MU, using in each step one of the following transformation rules:
# If a string ends with an I, a U may be appended (''x''I → ''x''IU)
# The string after the M may be completely duplicated (M''x'' → M''xx'')
# Any three consecutive I's (III) may be replaced with a single U (''x''III''y'' → ''x''U''y'')
# Any two consecutive U's may be removed (''x''UU''y'' → ''xy'')
An example derivation (with superscripts indicating the applied rules) is
:MI →
2 MII →
2 MIIII →
3 MUI →
2 MUIUI →
1 MUIUIU →
2 MUIUIUUIUIU →
4 MUIUIIUIU → ...
In light of this, one might wonder whether it is possible to convert MI into MU, using only these four transformation rules. One could spend many hours applying these transformation rules to strings. However, it might be quicker to find a
property
Property is a system of rights that gives people legal control of valuable things, and also refers to the valuable things themselves. Depending on the nature of the property, an owner of property may have the right to consume, alter, share, r ...
that is invariant to all rules (i.e. that isn't changed by any of them), and demonstrates that getting to MU is impossible. By looking at the puzzle from a logical standpoint, one might realize that the only way to get rid of any I's is to have three consecutive I's in the string. This makes the following invariant interesting to consider:
:''The number of I's in the string is not a multiple of 3''.
This is an invariant to the problem, if for each of the transformation rules the following holds: if the invariant held before applying the rule, it will also hold after applying it. Looking at the net effect of applying the rules on the number of I's and U's, one can see this actually is the case for all rules:
:
The table above shows clearly that the invariant holds for each of the possible transformation rules, which means that whichever rule one picks, at whatever state, if the number of I's was not a multiple of three before applying the rule, then it won't be afterwards either.
Given that there is a single I in the starting string MI, and one that is not a multiple of three, one can then conclude that it is impossible to go from MI to MU (as the number of I's will never be a multiple of three).
Invariant set
A
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
''S'' of the domain ''U'' of a mapping ''T'': ''U'' → ''U'' is an invariant set under the mapping when
Note that the
elements
Element or elements may refer to:
Science
* Chemical element, a pure substance of one type of atom
* Heating element, a device that generates heat by electrical resistance
* Orbital elements, parameters required to identify a specific orbit of ...
of ''S'' are not
fixed, even though the set ''S'' is fixed in the
power set of ''U''. (Some authors use the terminology ''setwise invariant,''
vs. ''pointwise invariant,'' to distinguish between these cases.)
For example, a circle is an invariant subset of the plane under a
rotation about the circle's center. Further, a
conical surface is invariant as a set under a
homothety of space.
An invariant set of an operation ''T'' is also said to be stable under ''T''. For example, the
normal subgroups that are so important in
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 ...
are those
subgroups that are stable under the
inner automorphism
In abstract algebra an inner automorphism is an automorphism of a group, ring, or algebra given by the conjugation action of a fixed element, called the ''conjugating element''. They can be realized via simple operations from within the group i ...
s of the ambient
group.
In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matric ...
, if a
linear transformation ''T'' has an
eigenvector v, then the line through 0 and v is an invariant set under ''T'', in which case the eigenvectors span an
invariant subspace which is stable under ''T''.
When ''T'' is a
screw displacement, the
screw axis is an invariant line, though if the
pitch is non-zero, ''T'' has no fixed points.
Formal statement
The notion of invariance is formalized in three different ways in mathematics: via
group actions, presentations, and deformation.
Unchanged under group action
Firstly, if one has a
group ''G''
acting on a mathematical object (or set of objects) ''X,'' then one may ask which points ''x'' are unchanged, "invariant" under the group action, or under an element ''g'' of the group.
Frequently one will have a group acting on a set ''X'', which leaves one to determine which objects in an ''associated'' set ''F''(''X'') are invariant. For example, rotation in the plane about a point leaves the point about which it rotates invariant, while translation in the plane does not leave any points invariant, but does leave all lines parallel to the direction of translation invariant as lines. Formally, define the set of lines in the plane ''P'' as ''L''(''P''); then a
rigid motion of the plane takes lines to lines – the group of rigid motions acts on the set of lines – and one may ask which lines are unchanged by an action.
More importantly, one may define a ''function'' on a set, such as "radius of a circle in the plane", and then ask if this function is invariant under a group action, such as rigid motions.
Dual to the notion of invariants are ''
coinvariants,'' also known as ''orbits,'' which formalizes the notion of
congruence
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
: objects which can be taken to each other by a group action. For example, under the group of rigid motions of the plane, the
perimeter of a triangle is an invariant, while the set of triangles congruent to a given triangle is a coinvariant.
These are connected as follows: invariants are constant on coinvariants (for example, congruent triangles have the same perimeter), while two objects which agree in the value of one invariant may or may not be congruent (for example, two triangles with the same perimeter need not be congruent). In
classification problems, one might seek to find a
complete set of invariants, such that if two objects have the same values for this set of invariants, then they are congruent.
For example, triangles such that all three sides are equal are congruent under rigid motions, via
SSS congruence, and thus the lengths of all three sides form a complete set of invariants for triangles. The three angle measures of a triangle are also invariant under rigid motions, but do not form a complete set as incongruent triangles can share the same angle measures. However, if one allows scaling in addition to rigid motions, then the
AAA similarity criterion shows that this is a complete set of invariants.
Independent of presentation
Secondly, a function may be defined in terms of some presentation or decomposition of a mathematical object; for instance, the
Euler characteristic of a
cell complex is defined as the alternating sum of the number of cells in each dimension. One may forget the cell complex structure and look only at the underlying
topological space (the
manifold) – as different cell complexes give the same underlying manifold, one may ask if the function is ''independent'' of choice of ''presentation,'' in which case it is an ''intrinsically'' defined invariant. This is the case for the Euler characteristic, and a general method for defining and computing invariants is to define them for a given presentation, and then show that they are independent of the choice of presentation. Note that there is no notion of a group action in this sense.
The most common examples are:
* The
presentation of a manifold in terms of coordinate charts – invariants must be unchanged under
change of coordinates.
* Various
manifold decompositions, as discussed for Euler characteristic.
* Invariants of a
presentation of a group.
Unchanged under perturbation
Thirdly, if one is studying an object which varies in a family, as is common in
algebraic geometry and
differential geometry, one may ask if the property is unchanged under perturbation (for example, if an object is constant on families or invariant under change of metric).
Invariants in computer science
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, an invariant is a
logical assertion that is always held to be true during a certain phase of execution of a
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer progra ...
. For example, a
loop invariant is a condition that is true at the beginning and the end of every iteration of a loop.
Invariants are especially useful when reasoning about the
correctness of a computer program. The theory of
optimizing compilers, the methodology of
design by contract, and
formal methods
In computer science, formal methods are mathematically rigorous techniques for the specification, development, and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the exp ...
for determining
program correctness, all rely heavily on invariants.
Programmers often use
assertions in their code to make invariants explicit. Some
object oriented programming languages have a special syntax for specifying
class invariants.
Automatic invariant detection in imperative programs
Abstract interpretation tools can compute simple invariants of given imperative computer programs. The kind of properties that can be found depend on the
abstract domains used. Typical example properties are single integer variable ranges like
0<=x<1024
, relations between several variables like
0<=i-j<2*n-1
, and modulus information like
y%40
. Academic research prototypes also consider simple properties of pointer structures.
More sophisticated invariants generally have to be provided manually.
In particular, when verifying an imperative program using
the Hoare calculus,
a loop invariant has to be provided manually for each loop in the program, which is one of the reasons that this approach is generally impractical for most programs.
In the context of the above
MU puzzle example, there is currently no general automated tool that can detect that a derivation from MI to MU is impossible using only the rules 1–4. However, once the abstraction from the string to the number of its "I"s has been made by hand, leading, for example, to the following C program, an abstract interpretation tool will be able to detect that
ICount%3
can't be 0, and hence the "while"-loop will never terminate.
void MUPuzzle(void)
See also
*
Erlangen program
*
Invariant (physics)
*
Invariant estimator in statistics
*
Invariant theory
*
Invariants of tensors
*
Symmetry in mathematics
*
Graph invariant
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 disc ...
*
Knot invariant
*
Topological invariant
*
Invariant differential operator In mathematics and theoretical physics, an invariant differential operator is a kind of mathematical map from some objects to an object of similar type. These objects are typically functions on \mathbb^n, functions on a manifold, vector valued fu ...
*
Invariant measure
*
Mathematical constant
*
Mathematical constants and functions
A mathematical constant is a key number whose value is fixed by an unambiguous definition, often referred to by a symbol (e.g., an alphabet letter), or by mathematicians' names to facilitate using it across multiple mathematical problems. For ex ...
Notes
References
*
*
*
*
* J.D. Fokker,
H. Zantema, S.D. Swierstra (1991). "Iteratie en invariatie", Programmeren en Correctheid. Academic Service. .
*
*
External links
"Applet: Visual Invariants in Sorting Algorithms"by William Braynen in 1997
{{DEFAULTSORT:Invariant (Mathematics)
Mathematical terminology