Invariant (mathematics)

Inmathematics,aninvariantis a property of amathematical object(or aclassof mathematical objects) which remains unchanged afteroperationsortransformationsof 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, theareaof atriangleis an invariant with respect toisometriesof theEuclidean plane.The phrases "invariant under" and "invariant to" a transformation are both used. More generally, an invariant with respect to anequivalence relationis a property that is constant on eachequivalence class.^[3]

Invariants are used in diverse areas of mathematics such asgeometry,topology,algebraanddiscrete mathematics.Some important classes of transformations are defined by an invariant they leave unchanged. For example,conformal mapsare defined as transformations of the plane that preserveangles.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 tocount.For afinite setof objects of any kind, there is a number to which we always arrive, regardless of theorderin which we count the objects in theset.The quantity—acardinal number—is associated with the set, and is invariant under the process of counting.

Anidentityis an equation that remains true for all values of its variables. There are alsoinequalitiesthat remain true when the values of their variables change.

Thedistancebetween two points on anumber lineis not changed byaddingthe same quantity to both numbers. On the other hand,multiplicationdoes not have this same property, as distance is not invariant under multiplication.

Anglesandratiosof distances are invariant underscalings,rotations,translationsandreflections.These transformations producesimilarshapes, which is the basis oftrigonometry.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, allcirclesare similar: they can be transformed into each other and the ratio of thecircumferenceto thediameteris invariant (denoted by the Greek letter π (pi)).

Some more complicated examples:

Thereal partand theabsolute valueof acomplex numberare invariant undercomplex conjugation.
Thetricolorabilityofknots.^[4]
Thedegree of a polynomialis invariant under a linear change of variables.
Thedimensionandhomology groupsof a topological object are invariant underhomeomorphism.^[5]
The number offixed pointsof adynamical systemis invariant under many mathematical operations.
Euclidean distance is invariant underorthogonal transformations.
Euclidean area is invariant underlinear mapswhich havedeterminant±1 (seeEquiareal map § Linear transformations).
Some invariants ofprojective transformationsincludecollinearityof three or more points,concurrencyof three or more lines,conic sections,and thecross-ratio.^[6]
Thedeterminant,trace,eigenvectors,andeigenvaluesof alinear endomorphismare invariant under achange of basis.In other words, thespectrum of a matrixis invariant under a change of basis.
The principal invariants oftensorsdo not change with rotation of the coordinate system (seeInvariants of tensors).
Thesingular valuesof amatrixare invariant under orthogonal transformations.
Lebesgue measureis invariant under translations.
Thevarianceof aprobability distributionis invariant under translations of thereal line.Hence the variance of arandom variableis unchanged after the addition of a constant.
Thefixed pointsof a transformation are the elements in thedomainthat are invariant under the transformation. They may, depending on the application, be calledsymmetricwith respect to that transformation. For example, objects withtranslational symmetryare invariant under certain translations.
The integral ${\textstyle \int _{M}K\,d\mu }$ of the Gaussian curvature $K$ of a two-dimensionalRiemannian manifold $(M,g)$ is invariant under changes of theRiemannian metric $g$ .This is theGauss–Bonnet theorem.

MU puzzle

TheMU puzzle^[7]is a good example of a logical problem where determining an invariant is of use for animpossibility 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 apropertythat 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:

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	Ifnis not a multiple of 3, then 2×nis not either. The invariant still holds.
3	−3	+1	Ifnis not a multiple of 3,n−3 is not 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 will not 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

AsubsetSof the domainUof a mappingT:U→Uis aninvariant setunder the mapping when $x\in S\implies T(x)\in S.$ Note that theelementsofSare notfixed,even though the setSis fixed in thepower setofU.(Some authors use the terminologysetwise invariant,^[8]vs.pointwise invariant,^[9]to distinguish between these cases.) For example, a circle is an invariant subset of the plane under arotationabout the circle's center. Further, aconical surfaceis invariant as a set under ahomothetyof space.

An invariant set of an operationTis also said to bestable underT.For example, thenormal subgroupsthat are so important ingroup theoryare thosesubgroupsthat are stable under theinner automorphismsof the ambientgroup.^[10]^[11]^[12] Inlinear algebra,if alinear transformationThas aneigenvectorv,then the line through0andvis an invariant set underT,in which case the eigenvectors span aninvariant subspacewhich is stable underT.

WhenTis ascrew displacement,thescrew axisis an invariant line, though if thepitchis non-zero,Thas no fixed points.

Inprobability theoryandergodic theory,invariant sets are usually defined via the stronger property $x\in S\Leftrightarrow T(x)\in S.$ ^[13]^[14]^[15]When the map $T$ is measurable, invariant sets form asigma-algebra,theinvariant sigma-algebra.

Formal statement

The notion of invariance is formalized in three different ways in mathematics: viagroup actions,presentations, and deformation.

Unchanged under group action

Firstly, if one has agroupGactingon a mathematical object (or set of objects)X,then one may ask which pointsxare unchanged, "invariant" under the group action, or under an elementgof the group.

Frequently one will have a group acting on a setX,which leaves one to determine which objects in anassociatedsetF(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 planePasL(P); then arigid motionof 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 afunctionon 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 arecoinvariants,also known asorbits,which formalizes the notion ofcongruence:objects which can be taken to each other by a group action. For example, under the group of rigid motions of the plane, theperimeterof 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). Inclassification problems,one might seek to find acomplete 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, viaSSS 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 theAAA similarity criterionshows 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, theEuler characteristicof acell complexis 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 underlyingtopological space(themanifold) – as different cell complexes give the same underlying manifold, one may ask if the function isindependentof choice ofpresentation,in which case it is anintrinsicallydefined 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:

Thepresentation of a manifoldin terms of coordinate charts – invariants must be unchanged underchange of coordinates.
Variousmanifold decompositions,as discussed for Euler characteristic.
Invariants of apresentation of a group.

Unchanged under perturbation

Thirdly, if one is studying an object which varies in a family, as is common inalgebraic geometryanddifferential 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

Incomputer science,an invariant is alogical assertionthat is always held to be true during a certain phase of execution of acomputer program.For example, aloop invariantis a condition that is true at the beginning and the end of every iteration of a loop.

Invariants are especially useful when reasoning about thecorrectness of a computer program.The theory ofoptimizing compilers,the methodology ofdesign by contract,andformal methodsfor determiningprogram correctness,all rely heavily on invariants.

Programmers often useassertionsin their code to make invariants explicit. Someobject oriented programming languageshave a special syntax for specifyingclass invariants.

Automatic invariant detection in imperative programs

Abstract interpretationtools can compute simple invariants of given imperative computer programs. The kind of properties that can be found depend on theabstract domainsused. Typical example properties are single integer variable ranges like0<=x<1024,relations between several variables like0<=i-j<2*n-1,and modulus information likey%4==0.Academic research prototypes also consider simple properties of pointer structures.^[16]

More sophisticated invariants generally have to be provided manually. In particular, when verifying an imperative program usingthe Hoare calculus,^[17]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 aboveMU puzzleexample, 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 thatICount%3cannot be 0, and hence the "while" -loop will never terminate.

voidMUPuzzle(void){
volatileintRandomRule;
intICount=1,UCount=0;
while(ICount%3!=0)// non-terminating loop
switch(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.Retrieved2019-12-05.
^^a ^bWeisstein, Eric W."Invariant".mathworld.wolfram.com.Retrieved2019-12-05.
^^a ^b"Invariant – Encyclopedia of Mathematics".www.encyclopediaofmath.org.Retrieved2019-12-05.
^Qiao, Xiaoyu (January 20, 2015)."Tricolorability.pdf"(PDF).Knot Theory Week 2: Tricolorability.Archived fromthe original(PDF)on May 25, 2024.RetrievedMay 25,2024.
^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 fromthe original(PDF)on 2016-03-04.

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.doi:10.1007/978-3-319-97704-1.ISBN 978-3-319-97703-4.
Klenke, Achim (2020).Probability Theory: A comprehensive course.Universitext. Springer.doi:10.1007/978-1-4471-5361-0.ISBN 978-3-030-56401-8.

External links

"Applet: Visual Invariants in Sorting Algorithms"Archived2022-02-24 at theWayback Machineby William Braynen in 1997

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

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

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

[4] Qiao, Xiaoyu (January 20, 2015)."Tricolorability.pdf"(PDF).Knot Theory Week 2: Tricolorability.Archived fromthe original(PDF)on May 25, 2024.RetrievedMay 25,2024.

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

[6] Kay (1969,pp. 219)

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

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

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

[10] Fraleigh (1976,p. 103)

[11] Herstein (1964,p. 42)

[12] McCoy (1968,p. 183)

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

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

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

[16] 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.

[17] 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 fromthe original(PDF)on 2016-03-04.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]