Invariant (mathematics)

Last updated March 24, 2024

In mathematics, an invariant is a property of a mathematical object (or a class of mathematical objects) which remains unchanged after operations or transformations of a certain type are applied to the objects.^[1]^[2] 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 of a triangle 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 is a property that is constant on each equivalence class.^[3]

Invariants are used in diverse areas of mathematics such as geometry, topology, algebra and discrete mathematics. Some important classes of transformations are defined by an invariant they leave unchanged. For example, conformal maps are defined as transformations of the plane that preserve angles. The discovery of invariants is an important step in the process of classifying mathematical objects.^[2]^[3]

Examples

A simple example of invariance is expressed in our ability to count. For a finite set of objects of any kind, there is a number to which we always arrive, regardless of the order in which we count the objects in the set. The quantity—a cardinal number—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.

Angles and ratios of distances are invariant under scalings, rotations, translations 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 circles are similar: they can be transformed into each other and the ratio of the circumference to the diameter is invariant (denoted by the Greek letter π (pi)).

Some more complicated examples:

The real part and the absolute value of a complex number are invariant under complex conjugation.
The degree of a polynomial is invariant under a linear change of variables.
The dimension and homology groups of a topological object are invariant under homeomorphism.^[4]
The number of fixed points of a dynamical system 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 Equiareal map § Linear transformations).
Some invariants of projective transformations include collinearity of three or more points, concurrency of three or more lines, conic sections, and the cross-ratio.^[5]
The determinant, trace, eigenvectors, and eigenvalues of a linear endomorphism are invariant under a change of basis. In other words, the spectrum of a matrix is invariant under a 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 are invariant under orthogonal transformations.
Lebesgue measure is invariant under translations.
The variance of a probability distribution is invariant under translations of the real line. Hence the variance of a random variable 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 ${\textstyle \int _{M}K\,d\mu }$ of the Gaussian curvature $K$ of a two-dimensional Riemannian manifold $(M,g)$ is invariant under changes of the Riemannian metric $g$ . This is the Gauss–Bonnet theorem.

MU puzzle

The MU puzzle ^[6] is a good example of a logical problem where determining an invariant is of use for an impossibility proof. 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 (xI → xIU)
The string after the M may be completely duplicated (Mx → Mxx)
Any three consecutive I's (III) may be replaced with a single U (xIIIy → xUy)
Any two consecutive U's may be removed (xUUy → xy)

An example derivation (with superscripts indicating the applied rules) is

MI →² MII →² MIIII →³ MUI →² MUIUI →¹ MUIUIU →² MUIUIUUIUIU →⁴ 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 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:

Rule	#I's	#U's	Effect on invariant
1	+0	+1	Number of I's is unchanged. If the invariant held, it still does.
2	×2	×2	If n is not a multiple of 3, then 2×n isn't either. The invariant still holds.
3	−3	+1	If n is not a multiple of 3, n−3 isn't either. The invariant still holds.
4	+0	−2	Number of I's is unchanged. If the invariant held, it still does.

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 S of the domain U of a mapping T: U → U is an invariant set under the mapping when $x\in S\implies T(x)\in S.$ Note that the elements 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,^[7] vs. pointwise invariant,^[8] 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 underT. For example, the normal subgroups that are so important in group theory are those subgroups that are stable under the inner automorphisms of the ambient group.^[9]^[10]^[11] In linear algebra, 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.

In probability theory and ergodic theory, invariant sets are usually defined via the stronger property $x\in S\Leftrightarrow T(x)\in S.$ ^[12]^[13]^[14] When the map $T$ is measurable, invariant sets form a sigma-algebra, the invariant sigma-algebra.

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: 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, an invariant is a logical assertion that is always held to be true during a certain phase of execution of a computer program. 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 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%4==0. Academic research prototypes also consider simple properties of pointer structures.^[15]

More sophisticated invariants generally have to be provided manually. In particular, when verifying an imperative program using the Hoare calculus,^[16] 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.

voidMUPuzzle(void){volatileintRandomRule;intICount=1,UCount=0;while(ICount%3!=0)// non-terminating loopswitch(RandomRule){case1:UCount+=1;break;case2:ICount*=2;UCount*=2;break;case3:ICount-=3;UCount+=1;break;case4:UCount-=2;break;}// computed invariant: ICount % 3 == 1 || ICount % 3 == 2}

Notes

↑ "Invariant Definition (Illustrated Mathematics Dictionary)". www.mathsisfun.com. Retrieved 2019-12-05.
1 2 Weisstein, Eric W. "Invariant". mathworld.wolfram.com. Retrieved 2019-12-05.
1 2 "Invariant – Encyclopedia of Mathematics". www.encyclopediaofmath.org. Retrieved 2019-12-05.
↑ Fraleigh (1976 , pp. 166–167)
↑ Kay (1969 , pp. 219)
↑ Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid , Basic Books, ISBN 0-465-02656-7 Here: Chapter I.
↑ Barry Simon. Representations of Finite and Compact Groups. American Mathematical Soc. p. 16. ISBN 978-0-8218-7196-6.
↑ Judith Cederberg (1989). A Course in Modern Geometries . Springer. p. 174. ISBN 978-1-4757-3831-5.
↑ Fraleigh (1976 , p. 103)
↑ Herstein (1964 , p. 42)
↑ McCoy (1968 , p. 183)
↑ Billingsley (1995) , pp. 313–314
↑ Douc et al. (2018) , p. 99
↑ Klenke (2020) , p. 494-495
↑ Bouajjani, A.; Drǎgoi, C.; Enea, C.; Rezine, A.; Sighireanu, M. (2010). "Invariant Synthesis for Programs Manipulating Lists with Unbounded Data" (PDF). Proc. CAV. doi: 10.1007/978-3-642-14295-6_8 .
↑ Hoare, C. A. R. (October 1969). "An axiomatic basis for computer programming" (PDF). Communications of the ACM . 12 (10): 576–580. doi:10.1145/363235.363259. S2CID 207726175. Archived from the original (PDF) on 2016-03-04.

Related Research Articles

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 of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.

In mathematics, many sets of transformations form a group under function composition; for example, the rotations around a point in the plane. It is often useful to consider the group as an abstract group, and to say that one has a group action of the abstract group that consists of performing the transformations of the group of transformations. The reason for distinguishing the group from the transformations is that, generally, a group of transformations of a structure acts also on various related structures; for example, the above rotation group acts also on triangles by transforming triangles into triangles.

<span class="mw-page-title-main">Algebraic topology</span> Branch of mathematics

Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify up to homotopy equivalence.

<span class="mw-page-title-main">Similarity (geometry)</span> Property of objects which are scaled or mirrored versions of each other

In Euclidean geometry, two objects are similar if they have the same shape, or if one has the same shape as the mirror image of the other. More precisely, one can be obtained from the other by uniformly scaling, possibly with additional translation, rotation and reflection. This means that either object can be rescaled, repositioned, and reflected, so as to coincide precisely with the other object. If two objects are similar, each is congruent to the result of a particular uniform scaling of the other.

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 as groups endowed with additional operations and axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right.

A shape is a graphical representation of an object's form or its external boundary, outline, or external surface; it is distinct from other object properties, such as color, texture, or material type. In geometry, shape excludes information about the object's location, scale, orientation and reflection. A figure is a representation including both shape and size.

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure". If the transformation is from a metric space to itself, it is a kind of geometric transformation known as a motion.

In mathematics, the conformal group of an inner product space is the group of transformations from the space to itself that preserve angles. More formally, it is the group of transformations that preserve the conformal geometry of the space.

Rotation in mathematics is a concept originating in geometry. Any rotation is a motion of a certain space that preserves at least one point. It can describe, for example, the motion of a rigid body around a fixed point. Rotation can have a sign (as in the sign of an angle): a clockwise rotation is a negative magnitude so a counterclockwise turn has a positive magnitude. A rotation is different from other types of motions: translations, which have no fixed points, and (hyperplane) reflections, each of them having an entire $(n - 1)$ -dimensional flat of fixed points in a $n$ -dimensional space.

In mathematics, equivariance is a form of symmetry for functions from one space with symmetry to another. A function is said to be an equivariant map when its domain and codomain are acted on by the same symmetry group, and when the function commutes with the action of the group. That is, applying a symmetry transformation and then computing the function produces the same result as computing the function and then applying the transformation.

In gauge theory and mathematical physics, a topological quantum field theory is a quantum field theory which computes topological invariants.

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an $-dimensional manifold, or -manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of -dimensional Euclidean space.$

In mathematics, more particularly in the fields of dynamical systems and geometric topology, an Anosov map on a manifold M is a certain type of mapping, from M to itself, with rather clearly marked local directions of "expansion" and "contraction". Anosov systems are a special case of Axiom A systems.

<span class="mw-page-title-main">Symmetry in mathematics</span>

Symmetry occurs not only in geometry, but also in other branches of mathematics. Symmetry is a type of invariance: the property that a mathematical object remains unchanged under a set of operations or transformations.

In physics, a symmetry of a physical system is a physical or mathematical feature of the system that is preserved or remains unchanged under some transformation.

The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them without changing their shape. However, the pieces themselves are not "solids" in the usual sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces.

In physics, a gauge theory is a type of field theory in which the Lagrangian, and hence the dynamics of the system itself, do not change under local transformations according to certain smooth families of operations. Formally, the Lagrangian is invariant.

Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods of analysis for the study of natural numbers.

In geometry, a motion is an isometry of a metric space. For instance, a plane equipped with the Euclidean distance metric is a metric space in which a mapping associating congruent figures is a motion. More generally, the term motion is a synonym for surjective isometry in metric geometry, including elliptic geometry and hyperbolic geometry. In the latter case, hyperbolic motions provide an approach to the subject for beginners.

<span class="mw-page-title-main">Symmetry (geometry)</span> Geometrical property

In geometry, an object has symmetry if there is an operation or transformation that maps the figure/object onto itself. Thus, a symmetry can be thought of as an immunity to change. For instance, a circle rotated about its center will have the same shape and size as the original circle, as all points before and after the transform would be indistinguishable. A circle is thus said to be symmetric under rotation or to have rotational symmetry. If the isometry is the reflection of a plane figure about a line, then the figure is said to have reflectional symmetry or line symmetry; it is also possible for a figure/object to have more than one line of symmetry.

References

Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016
Kay, David C. (1969), College Geometry, New York: Holt, Rinehart and Winston, LCCN 69-12075
McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68-15225
J.D. Fokker, H. Zantema, S.D. Swierstra (1991). "Iteratie en invariatie", Programmeren en Correctheid. Academic Service. ISBN 90-6233-681-7.
Weisstein, Eric W. "Invariant". MathWorld .
Popov, V.L. (2001) [1994], "Invariant", Encyclopedia of Mathematics , EMS Press
Billingsley, Patrick (1995). Probability and Measure. John Wiley & Sons. ISBN 0-471-00710-2.
Douc, Randal; Moulines, Eric; Priouret, Pierre; Soulier, Philippe (2018). Markov Chains. Springer. ISBN 978-3-319-97703-4.
Klenke, Achim (2020). Probability Theory: A comprehensive course. Springer. ISBN 978-3-030-56401-8.

External links

"Applet: Visual Invariants in Sorting Algorithms" by William Braynen in 1997

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Invariant Definition (Illustrated Mathematics Dictionary)". www.mathsisfun.com. Retrieved 2019-12-05.

[:1-2] 1 2 Weisstein, Eric W. "Invariant". mathworld.wolfram.com. Retrieved 2019-12-05.

[:2-3] 1 2 "Invariant – Encyclopedia of Mathematics". www.encyclopediaofmath.org. Retrieved 2019-12-05.

[4] Fraleigh (1976 , pp. 166–167)

[5] Kay (1969 , pp. 219)

[6] Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid , Basic Books, ISBN 0-465-02656-7 Here: Chapter I.

[Simon-7] Barry Simon. Representations of Finite and Compact Groups. American Mathematical Soc. p. 16. ISBN 978-0-8218-7196-6.

[8] Judith Cederberg (1989). A Course in Modern Geometries . Springer. p. 174. ISBN 978-1-4757-3831-5.

[9] Fraleigh (1976 , p. 103)

[10] Herstein (1964 , p. 42)

[11] McCoy (1968 , p. 183)

[billingsley-12] Billingsley (1995) , pp. 313–314

[douc-13] Douc et al. (2018) , p. 99

[klenke-14] Klenke (2020) , p. 494-495

[15] Bouajjani, A.; Drǎgoi, C.; Enea, C.; Rezine, A.; Sighireanu, M. (2010). "Invariant Synthesis for Programs Manipulating Lists with Unbounded Data" (PDF). Proc. CAV. doi: 10.1007/978-3-642-14295-6_8 .

[16] Hoare, C. A. R. (October 1969). "An axiomatic basis for computer programming" (PDF). Communications of the ACM . 12 (10): 576–580. doi:10.1145/363235.363259. S2CID 207726175. Archived from the original (PDF) on 2016-03-04.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]