Editing Invariant (mathematics)

{{Short description|Property that is not changed by mathematical transformations}}
{{Other uses|Invariant (disambiguation)}}
{{confusing|reason=all this article confuses "invariance" (a property) and "an invariant" (a mathematical object that is left invariant under a [[group action]])|date=January 2024}}{{more inline|date=April 2015}}

[[File:Wallpaper group-p2-3.jpg|thumb|A [[Wallpaper group|wallpaper]] is invariant under some transformations. This one is invariant under horizontal and vertical translation, as well as rotation by 180° (but not under reflection).]]
In [[mathematics]], an '''invariant''' is a property of a [[mathematical object]] (or a [[Class (set theory)|class]] of mathematical objects) which remains unchanged after [[Operation (mathematics)|operations]] or [[Transformation (function)|transformations]] of a certain type are applied to the objects.<ref>{{Cite web|url=https://www.mathsisfun.com/definitions/invariant.html|title=Invariant Definition (Illustrated Mathematics Dictionary)|website=www.mathsisfun.com|access-date=2019-12-05}}</ref><ref name=":1">{{Cite web|url=http://mathworld.wolfram.com/Invariant.html|title=Invariant|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-05}}</ref> 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 [[isometry|isometries]] of the [[Plane (geometry)|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]].<ref name=":2">{{Cite web|url=https://www.encyclopediaofmath.org/index.php/Invariant|title=Invariant – Encyclopedia of Mathematics|website=www.encyclopediaofmath.org|access-date=2019-12-05}}</ref>

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 map]]s are defined as transformations of the plane that preserve [[angle]]s. The discovery of invariants is an important step in the process of classifying mathematical objects.<ref name=":1" /><ref name=":2" />

== Examples ==
A simple example of invariance is expressed in our ability to [[counting|count]]. For a [[finite set]] of objects of any kind, there is a number to which we always arrive, regardless of the [[total order|order]] in which we count the objects in the [[set (mathematics)|set]]. The quantity—a [[cardinal number]]—is associated with the set, and is invariant under the process of counting.

An [[List of mathematical identities|identity]] is an equation that remains true for all values of its variables. There are also [[List of inequalities|inequalities]] that remain true when the values of their variables change.

The [[distance]] between two points on a [[number line]] is not changed by [[addition|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]]s and [[ratio]]s of distances are invariant under [[Scaling (geometry)|scalings]], [[Rotation (mathematics)|rotation]]s, [[Translation (geometry)|translation]]s and [[Reflection (mathematics)|reflection]]s. These transformations produce [[Similarity (geometry)|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]]s 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 [[tricolorability]] of [[Knot (mathematics)|knots]].<ref>{{Cite web |last=Qiao |first=Xiaoyu |date=January 20, 2015 |title=Tricolorability.pdf |url=https://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Tricolorability.pdf |url-status=dead |archive-url=https://web.archive.org/web/20240525145629/https://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Tricolorability.pdf |archive-date=May 25, 2024 |access-date=May 25, 2024 |website=Knot Theory Week 2: Tricolorability }}</ref>
* The [[degree of a polynomial]] is invariant under a linear change of variables.
* The [[topological dimension|dimension]] and [[homology group]]s of a topological object are invariant under [[homeomorphism]].<ref>{{harvtxt|Fraleigh|1976|pp=166–167}}</ref>
* The number of [[fixed point (mathematics)|fixed points]] of a [[dynamical system]] is invariant under many mathematical operations.
* Euclidean distance is invariant under [[orthogonal transformation]]s.
* [[Area]] is invariant under [[linear map]]s which have [[determinant]] ±1 (see {{slink|Equiareal map|Linear transformations}}).
* Some invariants of [[projective transformation]]s include [[collinearity]] of three or more points, [[concurrent lines|concurrency]] of three or more lines, [[conic section]]s, and the [[cross-ratio]].<ref>{{harvtxt|Kay|1969|pp=219}}</ref>
* The [[determinant]], [[Trace (linear algebra)|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-value decomposition|singular values]] of a [[matrix (mathematics)|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 point (mathematics)|fixed points]] of a transformation are the elements in the [[domain of a function|domain]] that are invariant under the transformation. They may, depending on the application, be called [[symmetry|symmetric]] with respect to that transformation. For example, objects with [[translational symmetry]] are invariant under certain translations.
*The integral <math display="inline">\int_M K\,d\mu</math> of the Gaussian curvature <math>K</math> of a two-dimensional [[Riemannian manifold]] <math>(M,g)</math> is invariant under changes of the [[Riemannian metric]] ''<math>g</math>''.  This is the [[Gauss–Bonnet theorem]].

===MU puzzle===
The [[MU puzzle]]<ref>{{Citation | last1 = Hofstadter | first1 = Douglas R. | title = Gödel, Escher, Bach: An Eternal Golden Braid | publisher = Basic Books | year = 1999 | orig-year = 1979 | isbn = 0-465-02656-7 | url-access = registration | url = https://archive.org/details/gdelescherbachet00hofs }}
Here: Chapter I.</ref> 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 (''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 →<sup>2</sup> MII →<sup>2</sup> MIIII →<sup>3</sup> MUI →<sup>2</sup> MUIUI →<sup>1</sup> MUIUIU →<sup>2</sup> MUIUIUUIUIU →<sup>4</sup> 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 [[Predicate (mathematical logic)|property]] that is invariant to all rules (that is, not changed by any of them), and that 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:

:{| class=wikitable
|-
! Rule !! #I's !! #U's !! Effect on invariant
|-
| style="text-align: center;" | 1 || style="text-align: right;" | +0 || style="text-align: right;" | +1 || Number of I's is unchanged. If the invariant held, it still does.
|-
| style="text-align: center;" |  2 || style="text-align: right;" | ×2 || style="text-align: right;" | ×2 || If ''n'' is not a multiple of 3, then 2×''n'' is not either. The invariant still holds.
|-
| style="text-align: center;" |  3 || style="text-align: right;" | −3 || style="text-align: right;" | +1 || If ''n'' is not a multiple of 3, ''n''−3 is not either. The invariant still holds.
|-
| style="text-align: center;" |  4 || style="text-align: right;" | +0 || style="text-align: right;" | −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  will not be afterwards either.

Given that there is a single I in the starting string MI, and one 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 <math>x \in S \iff T(x) \in S.</math> The [[element (mathematics)|elements]] of ''S'' are not necessarily [[Fixed point (mathematics)|fixed]], even though the set ''S'' is fixed in the [[power set]] of ''U''. (Some authors use the terminology ''setwise invariant,''<ref name="Simon">{{cite book|author=Barry Simon|title=Representations of Finite and Compact Groups|publisher=American Mathematical Soc.|isbn=978-0-8218-7196-6|page=16|url=https://books.google.com/books?id=SFlDLVqVZJgC}}</ref> vs. ''pointwise invariant,''<ref>{{cite book|author=Judith Cederberg|title=A Course in Modern Geometries|url=https://archive.org/details/courseinmodernge0000cede|url-access=registration|year=1989|publisher=Springer |isbn=978-1-4757-3831-5|page=[https://archive.org/details/courseinmodernge0000cede/page/174 174]}}</ref> 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 [[Homothetic transformation|homothety]] of space.

An invariant set of an operation ''T'' is also said to be '''stable under''' ''T''. For example, the [[normal subgroup]]s that are so important in [[group theory]] are those [[subgroup]]s that are stable under the [[inner automorphism]]s of the ambient [[group (mathematics)|group]].<ref>{{harvtxt|Fraleigh|1976|p=103}}</ref><ref>{{harvtxt|Herstein|1964|p=42}}</ref><ref>{{harvtxt|McCoy|1968|p=183}}</ref>
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 (screw)|pitch]] is non-zero, ''T'' has no fixed points.

In [[probability theory]] and [[ergodic theory]], invariant sets are usually defined via the stronger property <math>x \in S \Leftrightarrow T(x) \in S.</math><ref name=billingsley>{{harvp|Billingsley|1995|pages=313-314}}</ref><ref name="douc">{{harvp|Douc|Moulines|Priouret|Soulier|2018|page=99}}</ref><ref name="klenke">{{harvp|Klenke|2020|page=494-495}}</ref> When the map <math>T</math> is measurable, invariant sets form a [[sigma-algebra]], the [[invariant sigma-algebra]].

== Formal statement ==
{{unreferenced section|date=February 2010}}
The notion of invariance is formalized in three different ways in mathematics: via [[group action]]s, presentations, and deformation.

=== Unchanged under group action ===
Firstly, if one has a [[group (mathematics)|group]] ''G'' [[group action|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 ''[[coinvariant]]s,'' also known as ''orbits,'' which formalizes the notion of [[congruence relation|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 problem (mathematics)|classification problem]]s, 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 [[Congruence (geometry)#Congruence of triangles|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 [[Similarity (geometry)#Similar triangles|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 [[Differentiable manifold#Definition|presentation of a manifold]] in terms of coordinate charts – invariants must be unchanged under [[change of coordinates]].
* Various [[manifold decomposition]]s, 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==
{{For|other uses of the word "invariant" in computer science|invariant (disambiguation)}}
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 (computer science)|correctness of a computer program]]. The theory of [[optimizing compiler]]s, the methodology of [[design by contract]], and [[formal methods]] for determining [[program correctness]], all rely heavily on invariants.

Programmers often use [[Assertion (computing)|assertions]] in their code to make invariants explicit. Some [[object oriented]] [[programming language]]s have a special syntax for specifying [[class invariant]]s.

===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 interpretation#Examples of abstract domains|abstract domains]] used. Typical example properties are single integer variable ranges like <code>0<=x<1024</code>, relations between several variables like <code>0<=i-j<2*n-1</code>, and modulus information like <code>y%4==0</code>. Academic research prototypes also consider simple properties of pointer structures.<ref>{{cite conference|first1=A.|last1=Bouajjani|first2=C.|last2=Drǎgoi|first3=C.|last3=Enea|first4=A.|last4=Rezine|first5=M.|last5=Sighireanu|author5-link= Mihaela Sighireanu |title=Invariant Synthesis for Programs Manipulating Lists with Unbounded Data|book-title=Proc. CAV|year=2010|doi=10.1007/978-3-642-14295-6_8|url=https://link.springer.com/content/pdf/10.1007/978-3-642-14295-6_8.pdf|doi-access=free}}</ref>

More sophisticated invariants generally have to be provided manually.
In particular, when verifying an imperative program using [[Hoare logic|the Hoare calculus]],<ref>{{Cite journal
 |last1=Hoare 
 |first1=C. A. R. 
 |author-link1=C.A.R. Hoare 
 |title=An axiomatic basis for computer programming 
 |doi=10.1145/363235.363259 
 |journal=[[Communications of the ACM]] 
 |volume=12 
 |issue=10 
 |pages=576&ndash;580 
 |date=October 1969 
 |s2cid=207726175 
 |url=http://www.spatial.maine.edu/~worboys/processes/hoare%20axiomatic.pdf 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20160304013345/http://www.spatial.maine.edu/~worboys/processes/hoare%20axiomatic.pdf 
 |archive-date=2016-03-04 
}}</ref> 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 <code>ICount%3</code> cannot be 0, and hence the "while"-loop will never terminate.

<syntaxhighlight lang="C">
void MUPuzzle(void) {
    volatile int RandomRule;
    int ICount = 1, UCount = 0;
    while (ICount % 3 != 0)                         // non-terminating loop
        switch(RandomRule) {
        case 1:                  UCount += 1;   break;
        case 2:   ICount *= 2;   UCount *= 2;   break;
        case 3:   ICount -= 3;   UCount += 1;   break;
        case 4:                  UCount -= 2;   break;
        }                                          // computed invariant: ICount % 3 == 1 || ICount % 3 == 2
}
</syntaxhighlight>

==See also==
{{Div col|colwidth=20em}}
* [[Erlangen program]]
* [[Graph invariant]]
* [[Invariant differential operator]]
* [[Invariant estimator]] in statistics
* [[Invariant measure]]
* [[Invariant (physics)]]
* [[Invariants of tensors]]
* [[Invariant theory]]
* [[Knot invariant]]
* [[Mathematical constant]]
* [[Mathematical constants and functions]]
* [[Scale invariance]]
* [[Symmetry in mathematics]]
* [[Topological invariant]]
* [[Young–Deruyts development]]
{{Div col end}}

== Notes ==

{{Reflist}}

== References ==
{{Refbegin}}
* {{ citation | first1 = John B. | last1 = Fraleigh | year = 1976 | isbn = 0-201-01984-1 | title = A First Course In Abstract Algebra | edition = 2nd | publisher = [[Addison-Wesley]] | location = Reading }}
* {{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = [[Blaisdell Publishing Company]] | location = Waltham }}
* {{ citation | first1 = David C. | last1 = Kay | year = 1969 | lccn = 69-12075 | title = College Geometry | publisher = [[Holt, Rinehart and Winston]] | location = New York }}
* {{ citation | first1 = Neal H. | last1 = McCoy | year = 1968 | title = Introduction To Modern Algebra, Revised Edition | publisher = [[Allyn and Bacon]] | location = Boston | lccn = 68-15225 }}
* J.D. Fokker, [[Hans Zantema|H. Zantema]], S.D. Swierstra (1991). "Iteratie en invariatie", Programmeren en Correctheid. Academic Service. {{ISBN|90-6233-681-7}}.
*{{MathWorld|title=Invariant|urlname=Invariant}}
*{{springer|title=Invariant|id=I/i052200|last=Popov|first=V.L.|authorlink=Vladimir L. Popov}}
*{{Cite book 
|last=Billingsley |first=Patrick 
|title=Probability and Measure
|publisher=John Wiley & Sons
|year=1995 
|isbn=0-471-00710-2
|url=https://www.wiley.com/en-gb/Probability+and+Measure%2C+Anniversary+Edition-p-9781118122372
}}
*{{Cite book 
|last1=Douc |first1=Randal 
|last2=Moulines |first2=Eric 
|last3=Priouret |first3=Pierre 
|last4=Soulier |first4=Philippe 
|title=Markov Chains 
|publisher=Springer 
|year=2018 
|doi=10.1007/978-3-319-97704-1 
|isbn=978-3-319-97703-4
|url=https://link.springer.com/book/10.1007/978-3-319-97704-1 
}}
*{{Cite book 
|last=Klenke |first=Achim 
|title=Probability Theory: A comprehensive course
|series=Universitext 
|publisher=Springer 
|year=2020 
|doi=10.1007/978-1-4471-5361-0 
|isbn=978-3-030-56401-8
|url=https://link.springer.com/book/10.1007/978-1-4471-5361-0
}}
{{Refend}}

==External links==
* [http://www.u.arizona.edu/~wbraynen/software/VisualInvariants/index.html "Applet: Visual Invariants in Sorting Algorithms"] {{Webarchive|url=https://web.archive.org/web/20220224135515/http://www.u.arizona.edu/~wbraynen/software/VisualInvariants/index.html |date=2022-02-24 }} by William Braynen in 1997

{{Authority control}}

{{DEFAULTSORT:Invariant (Mathematics)}}
[[Category:Mathematical terminology]]