The Central Idea
A structural invariant is a property or quantity that remains unchanged under a specified collection of allowed operations, transformations, or transitions.
The key phrase is
under the allowed operations.
A property may be invariant for one process and fail to be invariant for another.
Invariant Relative to a Transformation
Suppose a transformation
\[ T:S\to S \]acts on states in a set \(S\).
A function
\[ I:S\to K \]is invariant under \(T\) when
\[ \boxed{I(T(s))=I(s)} \]for every allowed state \(s\).
Invariant along a Sequence of Moves
If each allowed move preserves an invariant \(I\), then any finite sequence of allowed moves also preserves it.
If
\[ s_0\to s_1\to s_2\to\cdots\to s_n, \]then
\[ I(s_0)=I(s_1)=I(s_2)=\cdots=I(s_n). \]This is what makes invariants useful for reachability arguments.
Invariant versus Constant
A quantity that happens to remain unchanged in one example is not automatically an invariant.
To establish an invariant, we must show that every allowed move preserves the property.
Invariance is a rule-level statement, not merely an observed coincidence.
Example: Adding Two Preserves Parity
Consider the transformation
\[ T(n)=n+2. \]Adding \(2\) preserves parity.
An even integer remains even, and an odd integer remains odd.
Therefore parity is invariant under this transformation.
Parity as an Invariant
We may encode parity by
\[ I(n)=n\bmod2. \]Then
\[ I(n+2)=I(n). \]The exact integer changes, but its parity class does not.
Example: Adding One Does Not Preserve Parity
Now consider
\[ T(n)=n+1. \]An even integer becomes odd, and an odd integer becomes even.
Thus parity is not invariant under adding \(1\).
The same property can be invariant under one transformation and noninvariant under another.
Modular Invariants
More generally, a transformation may preserve a residue modulo \(m\).
If every move changes a quantity by a multiple of \(m\), then
\[ x\bmod m \]remains unchanged.
Such modular invariants are common in discrete impossibility proofs.
Example: Adding Multiples of Three
Suppose every allowed move changes \(n\) by
\[ 3k \]for some integer \(k\).
Then
\[ n\bmod3 \]is invariant.
A state beginning in residue class \([1]\) modulo \(3\) can never reach a state in class \([0]\) or \([2]\).
Invariants and Equivalence Classes
An invariant often partitions a state space into classes.
If
\[ I(s)=I(t), \]we may regard \(s\) and \(t\) as belonging to the same invariant class.
Allowed transformations cannot move between classes when \(I\) is truly invariant.
Invariant Classes Restrict Reachability
Suppose
\[ I(s_0)=a. \]Every state reachable from \(s_0\) must satisfy
\[ I(s)=a. \]Therefore any state with
\[ I(s)\ne a \]is unreachable.
Impossibility Proofs
Invariants are especially effective for proving impossibility.
A typical argument has this form:
- identify an invariant;
- compute its value at the initial state;
- compute its value at the target state;
- observe that the values differ;
- conclude that the target cannot be reached.
Example: An Impossible Target
Suppose a game starts at
\[ 4 \]and every move adds or subtracts \(2\).
Every reachable value is even.
Therefore the target
\[ 11 \]is impossible to reach because it is odd.
An Invariant Gives a Necessary Condition
If two states have different invariant values, they cannot be connected by allowed moves.
But having the same invariant value does not always guarantee reachability.
Therefore invariants usually provide necessary conditions, not automatically sufficient conditions.
Same Invariant Does Not Guarantee Reachability
Two states may share parity yet still lie in separate components of a state graph.
Thus
\[ I(s)=I(t) \]may remove one obstacle without proving that a path exists.
Conserved Quantities
Some invariants are numerical quantities that remain exactly constant.
Such quantities are often called conserved quantities.
For example, moving tokens between boxes may preserve the total number of tokens.
Example: Token Conservation
Suppose a state is
\[ (x,y) \]where \(x\) and \(y\) are token counts in two boxes.
An allowed move transfers one token:
\[ (x,y)\to(x-1,y+1). \]The total
\[ x+y \]is invariant because
\[ (x-1)+(y+1)=x+y. \]Conservation Partitions the State Space
If the total token count is \(10\), then every reachable state must satisfy
\[ x+y=10. \]States satisfying
\[ x+y=9 \]belong to a different invariant class.
Set Cardinality as an Invariant
Some transformations change the labels or positions of elements without changing how many elements exist.
Under a permutation of a finite set,
\[ |A| \]remains unchanged.
Cardinality is therefore invariant under relabeling or reordering.
Order Is Not an Invariant under Reordering
If a transformation permutes positions, then the sequence
\[ (a,b,c) \]may become
\[ (b,a,c). \]The multiset of entries remains the same, but their order changes.
An invariant depends on what the operation preserves.
Multiset of Values as an Invariant
Under pure reordering, the collection of values with multiplicities is unchanged.
For example,
\[ (1,2,2,5) \]and
\[ (2,5,1,2) \]have the same values with the same multiplicities.
Sum as an Invariant under Redistribution
Suppose one operation subtracts \(k\) from one component and adds \(k\) to another:
\[ (a,b)\to(a-k,b+k). \]Then
\[ a+b \]remains invariant.
Product as a Possible Invariant
Other transformations may preserve products rather than sums.
For example, if
\[ (a,b)\to(2a,b/2) \]whenever the operation is allowed, then
\[ ab \]remains unchanged.
Different operations suggest different candidate invariants.
Sign as an Invariant
Under multiplication by a positive number,
\[ x\to cx,\qquad c>0, \]the sign of every nonzero \(x\) is preserved.
But multiplication by a negative number reverses sign.
Again, invariance depends on the transformation family.
Graph Invariants
A graph invariant is a property unchanged by graph isomorphism.
Relabeling vertices may alter the drawing and labels without changing the abstract graph.
Useful graph invariants include:
- number of vertices;
- number of edges;
- degree multiset;
- number of connected components;
- presence or absence of cycles.
Vertex Count Is a Graph Invariant
If two graphs are isomorphic, then they must contain the same number of vertices.
Therefore
\[ |V| \]is an invariant under graph isomorphism.
Edge Count Is a Graph Invariant
Isomorphism preserves adjacency.
Therefore it preserves how many edges exist:
\[ |E|. \]Graphs with different edge counts cannot be isomorphic.
Degree Multiset Is a Graph Invariant
Relabeling vertices may move degree values to different labels, but it does not change the collection of degree values.
Thus the degree multiset is invariant under graph isomorphism.
Degree Sequence
A graph's degrees are often sorted into a degree sequence.
For example,
\[ 3,3,2,2,2 \]may describe the vertex degrees of a graph.
Isomorphic graphs must have the same degree sequence.
Matching Invariants Do Not Prove Isomorphism
Two graphs may have the same number of vertices, same number of edges, and same degree sequence while still being nonisomorphic.
Invariants are often useful for ruling possibilities out more easily than proving complete equivalence.
Connected Components as an Invariant
Graph isomorphism preserves connectivity.
Therefore the number of connected components is invariant.
A connected graph cannot be isomorphic to a disconnected graph.
Cycle Structure as an Invariant
Isomorphism preserves the existence of cycles.
A tree, which has no cycles, cannot be isomorphic to a graph containing a cycle.
More refined cycle information can also serve as an invariant.
Tree Invariants
For a finite tree,
\[ |E|=|V|-1. \]This relationship is structural.
Any graph claimed to be a tree must satisfy this condition, although the condition alone is not sufficient without additional assumptions.
Invariants under Relabeling
Relabeling changes names but not structure.
Quantities depending only on connectivity, cardinality, or incidence are natural candidates for invariants.
Quantities depending on the literal names of vertices are usually not.
State-Space Invariants
A state-space invariant is preserved under every allowed transition.
Examples include:
- parity;
- total resource count;
- modular residue;
- coloring class;
- permutation parity;
- certain connectivity properties.
Coloring Invariants
A common strategy assigns colors to states or positions.
If every allowed move preserves some coloring property, then color class can act as an invariant.
Checkerboard-coloring arguments are classic examples of this technique.
Example: Checkerboard Coloring
Color a board alternately black and white.
A move may always switch colors, always preserve colors, or preserve some count involving both colors.
Once that behavior is identified, coloring can become an invariant or a closely related tracking device.
Parity of a Permutation
Some discrete systems rearrange objects by swaps.
Permutations can be classified as even or odd according to the parity of the number of transpositions needed to produce them.
Under restricted move sets, permutation parity can become a powerful invariant.
This idea will appear again in combinatorics and algebraic structures.
Invariant Vectors
Sometimes one scalar invariant is not enough.
We may track several preserved quantities together:
\[ I(s)=\big(I_1(s),I_2(s),\ldots,I_k(s)\big). \]Two states with different invariant vectors cannot be connected by allowed moves.
Combining Invariants
Suppose both
\[ I_1(s) \]and
\[ I_2(s) \]are invariant.
Then the ordered pair
\[ (I_1(s),I_2(s)) \]is also invariant.
Combining weak invariants can produce a stronger classification.
Coarse and Fine Invariants
An invariant is coarse if many structurally different states share the same value.
An invariant is finer if it distinguishes more states.
Parity is coarse because it places all integers into only two classes.
Complete Invariants
A complete invariant distinguishes objects exactly up to the chosen equivalence relation.
If
\[ I(a)=I(b) \]exactly when
\[ a\sim b, \]then \(I\) completely classifies the equivalence classes.
Complete invariants are especially valuable but may be difficult to find.
Invariant versus Monovariant
An invariant remains unchanged.
A monovariant changes consistently in one direction, such as always increasing or always decreasing.
For example, if every move reduces a nonnegative integer by at least \(1\), that quantity is not invariant, but it is a decreasing monovariant.
Why Monovariants Matter
A decreasing nonnegative integer cannot decrease forever.
Therefore monovariants are often used to prove that a process terminates.
Invariants are especially useful for classification and impossibility, while monovariants are especially useful for progress and termination.
Example: Remaining Tasks
Suppose each step completes at least one unfinished task and never reopens a completed task.
The number of unfinished tasks decreases.
It is therefore a monovariant, not an invariant.
Finding an Invariant
Invariant discovery often begins by examining exactly what one legal move changes.
Ask:
- what increases?
- what decreases?
- what changes by an even amount?
- what changes by a multiple of \(m\)?
- what merely gets rearranged?
- what total is conserved?
Track the Net Effect
A move may change several components while preserving a combination of them.
For example,
\[ (x,y,z)\to(x+1,y-2,z+1) \]preserves
\[ x+y+z \]because the net change is
\[ 1-2+1=0. \]Weighted Invariants
Sometimes an ordinary sum is not preserved, but a weighted sum is.
Consider
\[ I(x,y)=2x+y. \]If every legal move changes \(x\) and \(y\) in a way that keeps \(2x+y\) fixed, then this weighted combination is an invariant.
Modularizing a Noninvariant Quantity
A quantity may change without its residue changing.
Suppose a move changes \(Q\) by
\[ 6. \]Then \(Q\) is not invariant, but
\[ Q\bmod6 \]is invariant.
Reducing modulo \(m\) is a common way to discover hidden invariants.
Signatures
A collection of invariant values can serve as a structural signature.
For a graph, a signature might include
\[ (|V|,|E|,\text{degree sequence},\text{component count}). \]Different signatures prove that structures are not equivalent under the chosen notion of equivalence.
Invariants in Algorithms
Algorithms often rely on properties that remain true throughout execution.
A loop invariant is a statement that holds before and after every iteration of a loop.
Loop invariants are used to reason about algorithm correctness.
Loop-Invariant Pattern
A standard loop-invariant proof has three parts:
- Initialization: the invariant holds before the loop begins.
- Maintenance: one iteration preserves it.
- Termination: when the loop ends, the invariant helps establish the desired result.
Invariant in a Running Sum
Suppose an algorithm processes values
\[ a_1,a_2,\ldots,a_n \]and maintains a variable \(S\).
After processing the first \(k\) values, an invariant may be
\[ \boxed{ S=\sum_{i=1}^{k}a_i. } \]Each iteration extends the statement to the next processed value.
Invariants in Data Structures
A data structure may maintain structural rules throughout all legal operations.
Examples include:
- ordering conditions in search trees;
- balance conditions;
- capacity constraints;
- parent-child consistency;
- uniqueness conditions.
Such persistent rules are structural invariants.
Invariants in Geometry and Topology
Although this lesson is discrete, the invariant idea extends widely.
Geometry studies quantities preserved by transformations such as distance, angle, or incidence.
Topology studies properties preserved under continuous deformation.
The general principle is the same: classify transformations by what they preserve.
Invariants in Symmetry
Symmetry transformations change presentation while preserving essential structure.
A rotationally symmetric object may change orientation while preserving shape.
In discrete settings, relabelings and permutations often play the same role.
Common Error: Calling Any Repeated Value an Invariant
Observing that a quantity stayed equal during three sample moves does not prove invariance.
You must show that every legal move preserves it.
Common Error: Forgetting the Move Set
Parity may be invariant under
\[ n\to n+2 \]but not under
\[ n\to n+1. \]An invariant must always be stated relative to specified transformations.
Common Error: Treating Equal Invariant Values as Proof of Reachability
If two states have different invariant values, reachability is impossible.
If they have the same invariant value, reachability may still fail for other reasons.
Invariants often rule out possibilities more readily than they confirm them.
Common Error: Confusing an Invariant with a Monovariant
If a quantity decreases every move, it is not invariant.
It is a monovariant because it changes consistently in one direction.
Common Error: Using a Property Not Preserved by Every Move
Suppose one legal move preserves a sum but another changes it.
Then the sum is not an invariant of the full system.
Every permitted transformation must be checked.
Common Error: Confusing Labels with Structure
A graph invariant should not depend on whether a vertex is called \(A\) or \(B\).
Relabeling changes notation, not abstract structure.
Structural invariants should survive such representational changes.
A Reliable Procedure for Finding and Using an Invariant
- Identify the state space or class of objects.
- List the allowed transformations or moves.
- Compute exactly what one general move changes.
- Look for totals, residues, parity, counts, or structural properties that remain fixed.
- Prove that every legal move preserves the candidate.
- Evaluate the invariant at the initial object or state.
- Evaluate it at the proposed target or comparison object.
- If the invariant values differ, conclude that the transformation is impossible.
- If the values match, remember that further analysis may still be required.
- Combine several invariants when one is too coarse.
Example: Full Invariant Argument
Suppose a system begins at
\[ 7 \]and every legal move adds or subtracts a multiple of \(4\).
Therefore
\[ n\bmod4 \]is invariant.
Initially,
\[ 7\equiv3\pmod4. \]The target
\[ 20 \]satisfies
\[ 20\equiv0\pmod4. \]The invariant values differ.
Therefore,
\[ \boxed{\text{the target }20\text{ is unreachable from }7.} \]Practice 1: Parity Invariant
A process changes an integer only by adding or subtracting \(2\).
What simple invariant is preserved?
Practice 2: Reachability by Parity
Starting from \(6\), every move adds or subtracts \(2\).
Can the process reach \(15\)?
Practice 3: Modular Invariant
Every move changes an integer by a multiple of \(5\).
Which residue information is invariant?
Practice 4: Conserved Sum
A state changes by
\[ (x,y)\to(x-3,y+3). \]Name a numerical invariant.
Practice 5: Graph Invariant
Two graphs have different numbers of vertices.
Can they be isomorphic?
Practice 6: Degree Sequence
Graph \(G\) has degree sequence
\[ 3,2,2,1. \]Graph \(H\) has degree sequence
\[ 2,2,2,2. \]Can \(G\) and \(H\) be isomorphic?
Practice 7: Invariant or Monovariant?
A process decreases a nonnegative integer by \(1\) or \(2\) every step.
Is that integer an invariant or a monovariant?
Practice 8: Same Invariant Value
Two states have the same parity, and parity is known to be invariant.
Does that alone prove one state is reachable from the other?
Practice 9: Weighted Invariant
Suppose a move changes
\[ (x,y)\to(x+1,y-2). \]Show that
\[ 2x+y \]is invariant.
Practice 10: Invariant Vector
Suppose both parity and total token count are invariant in a system.
How can they be combined into one invariant description?
Practice Answers
Practice 1
Parity is preserved:
\[ \boxed{n\bmod2}. \]Practice 2
No. Starting from \(6\), every reachable value remains even, while \(15\) is odd.
\[ \boxed{15\text{ is unreachable}.} \]Practice 3
The residue modulo \(5\) is invariant:
\[ \boxed{n\bmod5}. \]Practice 4
The sum is preserved:
\[ (x-3)+(y+3)=x+y. \]Therefore
\[ \boxed{x+y} \]is invariant.
Practice 5
No. Isomorphic graphs must have the same number of vertices.
Practice 6
No. Their degree sequences differ, and degree sequence is invariant under graph isomorphism.
Practice 7
It is a monovariant because it decreases rather than remaining unchanged.
Practice 8
No. Matching invariant values remove one obstruction but do not guarantee that an allowed path exists.
Practice 9
After the move,
\[ 2(x+1)+(y-2) = 2x+2+y-2 = 2x+y. \]Therefore
\[ \boxed{2x+y} \]is invariant.
Practice 10
Combine them into an ordered pair, for example
\[ \boxed{ I(s)= (\text{parity of }s,\text{ total token count}) }. \]This invariant vector distinguishes states more finely than either invariant alone.
What to Remember
- An invariant is a property preserved by every allowed transformation.
- Invariance must always be stated relative to a move set or transformation family.
- Parity and modular residues are common discrete invariants.
- Conserved sums, products, counts, and weighted combinations can be invariants.
- Invariant values partition a state space into classes that legal moves cannot cross.
- Different invariant values prove nonreachability.
- Matching invariant values do not automatically prove reachability.
- Graph invariants include vertex count, edge count, degree sequence, and component count.
- A monovariant changes consistently in one direction rather than remaining fixed.
- Combining several invariants can produce a stronger structural signature.
The central habit is: study what one legal move changes, then search for a quantity or property whose net change is always zero—or whose structural class never changes.
Where We Go Next
Structural invariants complete our introduction to discrete objects and structures. We now have the language to describe finite objects, ordered structures, relations, graphs, state spaces, equivalence classes, and properties preserved under transformation.
The next section, Discrete Reasoning and Proof, uses these structures to develop systematic proof methods including direct proof, contradiction, induction, case analysis, pigeonhole reasoning, and invariant-based arguments.