Machine Kinematics
solved, then drawn
The chain before the lengths

Right until the size nobody checked

The characteristic polynomial of a chain's adjacency matrix is a fingerprint that costs nothing and separates every six-link chain and every eight-link one. At ten links it fails on two pairs — and on one of them, counting the ternary links tells the two chains apart while the polynomial does not.

Assumes Same links, same pins, different machines and The mechanism is the graph.

14 min read 8 figures Two routes to the same numberExact and approximateThe constant that is not constant

Deciding whether two chains are the same chain is a search over relabellings, and a search over relabellings of a ten-link chain has 3,628,800 candidates. Nobody wants to run it, and for most of the twentieth century nobody did: the standard shortcut was to compute a number — or a short list of numbers — from each chain, compare, and declare them different when the numbers differed.

The best of those shortcuts is the characteristic polynomial of the adjacency matrix, and it is a genuinely good idea. Write the chain’s adjacency matrix, take det⁡(λI−A)\det(\lambda I - A), and compare the coefficients.

A fingerprint that costs nothing and is almost always right. The characteristic polynomial of each chain's adjacency matrix, coefficient by coefficient. Isomorphic chains have identical polynomials — relabelling the links is a permutation similarity and a similarity does not move an eigenvalue — so a difference anywhere in this column is proof that two chains are different, obtained without searching over a single relabelling. Watt's and Stephenson's first differ at λ^2, which is where a triangle-free graph's polynomial first notices how many four-cycles it has. The coefficients are computed on the integers by the Faddeev–LeVerrier recursion and checked against the eigenvalues of the same matrix from an unrelated Jacobi routine, which agree to 3 × 10⁻¹³.
Fig. 1 The polynomials of the two six-link chains, coefficient by coefficient. They agree until λ², and one difference anywhere is proof that two chains are different.

The reason it works is a one-line argument. Relabelling the links of a chain permutes the rows and columns of AA by the same permutation, which is a similarity transformation, and a similarity does not move an eigenvalue. So isomorphic chains have identical polynomials, and a difference anywhere in the coefficients is a proof — obtained without searching over a single relabelling.

What it does on the censuses that can be checked

At six links there are two chains and they have different polynomials. At eight links there are sixteen and they have sixteen different polynomials. In both cases the test is not merely useful; it is complete. Comparing coefficients decides isomorphism exactly, on every chain in either census, and it costs a determinant instead of a search.

Right on every chain small enough to check by hand. How well the spectrum works as a fingerprint, at each size the census reaches. At six links and at eight it is perfect: every chain has its own polynomial, so comparing coefficients is a complete isomorphism test on those censuses and a great deal cheaper than searching relabellings. At ten links it is not. Two pairs of genuinely different chains share a polynomial, so a catalogue built on this test would hold 228 entries where there are 230 chains — and would report the missing two as duplicates of ones already in it. That is the shape of the failure worth carrying: a test that is exact on every case anybody checked it against, and wrong at the size where checking by hand stopped being possible.
Fig. 2 How the fingerprint performs at each size. Perfect at six links and at eight, and losing two chains at ten.

That is the condition under which a test enters a literature. It was checked, on every case anybody could check, and it passed every time. It is fast. It is easy to implement. And the argument for its correctness in one direction is airtight — isomorphic chains really do have equal polynomials, always, and that half of the claim never fails.

What was never established is the converse, and the converse is what a test needs.

Where it fails

Among the 230 ten-link chains there are exactly two pairs whose polynomials agree in every one of their eleven coefficients, and whose members are not isomorphic.

Different numbers of ternary links, and the same spectrum. Two of the 230 ten-link chains whose adjacency matrices have identical characteristic polynomials — identical in every one of the eleven coefficients — and which are not the same chain. They do not even share their assortment — 6×2 + 2×3 + 2×4 on the left and 4×2 + 6×3 on the right. Counting the ternary links tells them apart and the spectrum does not. That is worth pausing on: the spectrum is the more sophisticated invariant, it is the one that got written into the literature as a test, and here it is beaten by the first thing anybody would try. The polynomial both of them have is λ^10 − 13λ^8 + 52λ^6 − 4λ^5 − 76λ^4 + 8λ^3 + 32λ^2.
Fig. 3 The first pair. The two chains have different link assortments — and identical characteristic polynomials.

The first pair is the more startling of the two, and it is worth stating slowly. One chain has six binary links, two ternary and two quaternary. The other has four binary and six ternary. They do not have the same number of ternary links. Counting them separates the two chains instantly, with no matrix and no determinant, and it is the first thing anybody would try.

The polynomial, which is the more sophisticated instrument and the one that got written down as a test, does not separate them. Both are

λ10−13λ8+52λ6−4λ5−76λ4+8λ3+32λ2.\lambda^{10} - 13\lambda^{8} + 52\lambda^{6} - 4\lambda^{5} - 76\lambda^{4} + 8\lambda^{3} + 32\lambda^{2}.

The second pair does share an assortment — five binary, four ternary and one quaternary link each — so on that pair the assortment test fails too, and something that actually reads the adjacency is needed. What separates them is that one has a nontrivial symmetry and the other has none: their automorphism groups have two members and one, and they give nine mechanisms and ten.

Two different chains with one spectrum. Two of the 230 ten-link chains whose adjacency matrices have identical characteristic polynomials — identical in every one of the eleven coefficients — and which are not the same chain. They share their assortment as well, 5×2 + 4×3 + 1×4, so the two cheapest tests both pass them as equal. What separates them is the refinement colouring: the left chain's links fall into 10 classes and the right's into 9, and their automorphism groups have 1 and 2 members. The polynomial both of them have is λ^10 − 13λ^8 + 53λ^6 − 8λ^5 − 82λ^4 + 26λ^3 + 39λ^2 − 16λ.
Fig. 4 The second pair. Same assortment, same polynomial, different chains — separated by symmetry rather than by any count.

What an eigenvalue cannot see

It is tempting to treat cospectrality as bad luck. It is not; it is a consequence of what an eigenvalue is.

The coefficients of a characteristic polynomial are sums over closed walks. The λn−2\lambda^{n-2} coefficient is minus the number of edges; the λn−3\lambda^{n-3} coefficient counts triangles; the ones below count progressively more elaborate collections of cycles and matchings. Every one of them is a total over the whole graph.

So the polynomial is a family of global averages, and a global average cannot distinguish two graphs that have the same totals distributed differently. That is exactly the situation the two cospectral pairs are in.

The contrast with refinement is the useful one, and it is the reason the next rung is built on refinement rather than on the spectrum. Refinement is entirely local: a link’s colour is a statement about its own neighbourhood, then about its neighbourhood’s neighbourhood, and the process stops when nothing more can be learned locally. It is not complete either — two links genuinely alike to every local measurement stay the same colour — but its failures are of a different kind, and the two instruments fail on different pairs.

On the first cospectral pair, refinement separates the chains in one step, because a link with four pins is not a link with three. On the second, refinement gets further than the spectrum and still needs the backtracking search behind it to finish the job.

What the coefficients actually count

It is worth reading the small case in detail, because it shows both why the test works and where its information goes.

Watt’s chain has polynomial λ6−7λ4+7λ2−1\lambda^6 - 7\lambda^4 + 7\lambda^2 - 1 and Stephenson’s has λ6−7λ4+9λ2−4λ\lambda^6 - 7\lambda^4 + 9\lambda^2 - 4\lambda. Four things are visible in that pair.

The λ5\lambda^5 coefficient is nought in both, and it is nought in every graph: it is minus the trace of the adjacency matrix, and a simple graph has no self-loops.

The λ4\lambda^4 coefficient is −7-7 in both, and it has to be. For any graph it is minus the number of edges, so it carries exactly one of the two numbers Grübler’s rule reads and nothing else. Two chains of the same census can never differ here.

The λ3\lambda^3 coefficient is nought in both, and for a graph it is minus twice the number of triangles. Both are triangle-free — they are chains, and a triangle would have disqualified them — so this coefficient is nought on every chain in every census here, which is a whole coefficient the test cannot use.

3 of these 6 links never move relative to one another. A graph that passes every arithmetic test and is not a mechanism of 6 links. The shaded links are a subchain that is already a structure: 3 links held by 3 pins, whose own count is 3 × 2 − 2 × 3 = 0. Grübler cannot see it, because the formula reads two totals for the whole graph and this is a statement about a subset. Neither can the rank. A rigid triangle removes exactly the freedoms the count says it does, so the constraint Jacobian is not deficient, the measured mobility is 1, and the two routes this site checks everything with agree — with each other and with the wrong answer. The assembly moves, and it moves as a mechanism with 4 links, one of which happens to be welded out of 3 pieces.
Fig. 5 The only six-link graphs whose λ³ coefficient is not nought are the ones a triangle disqualified. On the census itself the coefficient carries nothing.

The λ2\lambda^2 coefficient is where they differ, at 7 against 9 — which is where the difference between the two six-link chains first reaches something computed rather than looked at, and for a triangle-free graph it counts pairs of disjoint edges minus twice the four-cycles. That is the first coefficient that reads which links the pins run between rather than how many of each there are, and it is where all of the test’s actual power lives.

And one more, which is the prettiest of them. Watt’s odd-degree coefficients are all nought and Stephenson’s are not. A polynomial with only even terms means the eigenvalues come in ±\pm pairs, which means the graph is bipartite, which means it has no odd cycle. Watt’s chain has none: its loops are two four-cycles. Stephenson’s has a five-cycle, and the −4λ-4\lambda is that cycle showing.

So on a census of chains the polynomial has n+1n+1 coefficients of which three are fixed by construction, one is the edge count, and the rest do the work. That is less information than it appears to carry, and it is a fair summary of why it eventually runs out.

Every other fingerprint fails the same way

The natural repair, once a test collides, is to add another number to it. It is worth being clear about why that does not fix anything in general.

Every invariant of this kind is a summary: a function of the graph that is constant on isomorphism classes. Any such function maps 230 chains into some set of values, and it decides isomorphism only if that map is injective. The degree sequence maps them into seven values. The number of loops maps all of them to four. The polynomial maps them into 228. Adding invariants together makes the map finer and never makes it injective on principle — it makes it injective on this census, which is precisely the thing the ten-link case shows is not the same claim.

The same links and pins, and between 12 and 15 link lengths in the stack-up. Every closed loop in a mechanism is one equation a tolerance analysis has to satisfy, and the equation involves every link the loop passes through. All 16 chains here have the same number of independent loops — 3, which is pins minus links plus one and is fixed by the two totals — but not the same shortest set of them. The bars are the total length of a minimum cycle basis, and they run from 12 to 15. So the smallest number of link dimensions that any stack-up on this mechanism can involve is decided by the graph, before a single dimension has been chosen, and two topologies a count cannot tell apart differ by 3 of them.
Fig. 6 An invariant that fails immediately: every chain in a census has the same number of loops, so it separates nothing. The shortest loop basis is finer and still far from injective.

There is a clean stopping point available: the pair (canonical form) is not a summary at all. It is a labelling, chosen by a rule that reads the graph, and two chains are the same exactly when the strings match. That is a decision procedure rather than a filter, it has no counterexamples by construction, and it is what a census must be built on.

The practical arrangement is to use both, in the order that costs least: filter by the cheap summaries, decide by the canonical form on whatever survives. At ten links that is 26,335 questions reduced to two, and two canonical-form comparisons is nothing.

The shape of the failure, which is the part to carry

The instance is a curiosity. The shape is not, and it recurs across this site.

A test was exact on every case anybody checked, and the cases anybody could check were the small ones. Six links: two chains, checkable on a page. Eight links: sixteen chains, 120 pairs, checkable by somebody patient. Ten links: 230 chains, 26,335 pairs, and the first counterexample.

Every column grows by about a factor of fifteen a step. The three counts on a logarithmic axis, which is the only way they fit on one picture: one chain at four links and 230 at ten. What the log axis shows and a table cannot is that the upper two lines diverge. The ratio between graphs that pass the count and graphs that are chains is 1.00, 2.50, 4.44 and 8.17 — roughly doubling at every step — so the fourth condition is not a small correction that matters at four links and washes out. It does more of the work at every size, and a designer working from a list that had passed only the count would be working from a list eight times too long at ten links and worse above it. The slope of the lines themselves is what makes twelve links a different kind of problem: at about a factor of fifteen a step, the next row is five figures.
Fig. 7 Why the checking stopped where it did. Each row of the census is about fifteen times the one before, so hand-verification runs out one row before the first failure.

That is not a coincidence about this test. It is the general reason a shortcut survives: verification effort and counterexample density grow together, and the place where the first fails is close to the place where the second succeeds.

The site has met the same shape twice before. The conjugate-action test in the gears field was circular — it parameterised both flanks by the same roll angle and announced the ratio was constant — and it passed on every flank it was shown because the flanks were all correct. The closure program in the holding field is necessary and not sufficient, and the case that shows it is the one part in the field that cannot be held at all.

In all three the pattern is the same. The half of the claim that is easy to prove is proved, the half that a test actually needs is assumed, and the assumption is confirmed by every case in reach.

What to use instead, and what it costs

The honest replacement is a canonical form: a labelling chosen by a rule that depends on the graph and not on how it arrived, so that two chains are the same exactly when their canonical adjacency strings match.

Same links, same pins, different chains. Watt chain on the left and Stephenson chain on the right. They have the same number of links, the same number of pins and the same assortment — 4×2 + 2×3 — so no count of anything can tell them apart. What differs is where the pins go: on the left the two ternary links share a pin, on the right they do not, and that single fact makes two mechanisms with different coupler curves, different numbers of inversions and different position problems. It is the smallest case in the subject of the thing this field exists to say: the arithmetic is a filter and the graph is the answer.
Fig. 8 Two chains whose canonical forms differ. The canonical form is not an invariant computed from the graph — it is a labelling of it, and equality of the strings is equality of the chains.

That is what this field’s census is built on, it has no counterexamples by construction, and it is the subject of the next rung. It costs more than a determinant: refinement first, then a backtracking search over the classes refinement could not split. On ten-vertex chains the search is a handful of branches and the whole census of 1,878 graphs is canonicalised in under half a second, so the cost argument that justified the shortcut has expired.

The spectrum is still worth having, and this is not an argument for discarding it, any more than a bound that happened to be tight is an argument against bounds. It is a superb filter: bucket the census by polynomial, and only chains landing in the same bucket need the expensive comparison. At ten links that reduces 26,335 pairwise questions to two. Used that way it is exactly right, because a filter is allowed to have collisions and a test is not.

And how it was found here

Worth recording, because it says something about what a census is for.

Nobody looked for a counterexample. The census was computed for its own sake, every chain’s polynomial was computed to build the bucketing filter, and the number of distinct polynomials came out two short of the number of chains. The two pairs fell out of a routine that was not testing anything.

That is the ordinary way an enumeration earns its cost. A complete list makes questions checkable that were previously matters of opinion — and it does so for questions nobody thought to ask, because the check is a comparison of two column totals rather than a search for a case.

The polynomials themselves are computed on the integers, by the Faddeev–LeVerrier recursion, which divides by kk at each step and whose quotients are integers for an integer matrix. That is asserted rather than assumed: a non-integer coefficient would mean the recursion had lost a digit, and two chains would be compared on noise. And because the whole finding is a claim that two polynomials are identical, a systematically wrong polynomial would be identically wrong on both — so the coefficients are checked against the eigenvalues of the same matrix from an unrelated Jacobi routine, which agree to 3×10−133 \times 10^{-13}.

A bad test can be an excellent filter

The polynomial is refuted as a test and kept as a filter, and the two verdicts sit oddly together until the numbers are put to them — at which point the arrangement stops looking like a compromise and starts looking like the obvious thing to do.

The census asks whether two chains are the same 26,335 times, and among all those comparisons the polynomial produces exactly two false matches. Everything else it separates correctly and instantly. So its rate of getting the answer wrong is under one in ten thousand, and the expensive canonical form is invoked on essentially nothing.

That is the whole economics of it. A filter’s value is set by how often it is right, and a test’s value is set by whether it can ever be wrong — and those are completely different requirements. A summary that fails once in thirteen thousand is worthless as a proof and near-perfect as a pre-filter, because the cases it fails on are handed to something that cannot fail.

So the correct reading of this rung is not that the polynomial is a bad instrument. It is that validity and usefulness are independent properties, and the mistake in the literature was never using the polynomial — it was using it alone, where the two properties get conflated because nothing downstream ever disagrees with it.

The arrangement generalises and is worth naming, because this site has several instruments of the same shape. A cheap invariant that is fast, sound in one direction and unproven in the other, followed by an expensive procedure that is sound in both: the cheap one does all the work, the expensive one supplies the guarantee, and the combined cost is the cheap one’s cost plus almost nothing. The degree sequence is the same arrangement one level down — weaker, cheaper, and used first for exactly that reason.

The condition on the arrangement is the part that has to be respected. The expensive procedure must be sound, not merely better; a chain of increasingly good summaries is still a chain of summaries and has no last link. That is what makes the canonical form the right terminus and any further invariant the wrong one, however many collisions it would have resolved.

And it explains what the two colliding pairs are actually worth. They are not a reason to distrust the census, since the census never relied on the polynomial alone. They are the evidence that the terminus was needed — a discovery that cost nothing to make, because it was made by an enumeration that would have run anyway.

The size at which a claim stops being checked

There is a practical rule buried in all of this, and it is not about polynomials.

A census has a size at which hand-verification stops, and this site has met that boundary before: a solver refusing a quarter of a sweep went unnoticed because every case anybody looked at was one it got right. For kinematic chains that size is eight links: sixteen objects, a hundred and twenty pairs, and a patient afternoon. Everything anybody claimed about chains before machine enumeration was claimed on evidence that ended there — and every one of those claims is true of the eight-link census, because that is where it was checked.

The ten-link census is not qualitatively different mathematics. It is the same objects, one row further down, and it is the first row where several convenient things stop being true at once: the spectral test collides, the first assortments appear that contain no mechanism at all, and the fraction of chains with no closed-form driving choice rises from a quarter to nearly two fifths.

None of that is a criticism of anybody. It is a description of what a census is worth: not new mathematics, but the first evidence about the region where the evidence ran out.

Where this goes next

Colour by degree, recolour by neighbours' colours, stop when nothing changes. The cheap half of every isomorphism routine there is, and the half that does most of the work. Start by colouring each link with how many pins it carries. Then repeatedly recolour it with its own colour plus the multiset of its neighbours', until a pass changes nothing. On this chain the process ends with 3 classes of sizes 2, 2, 2, and two links of different colours are certainly different links — no relabelling can carry one to the other. What refinement cannot do is separate links that are alike to every local measurement, and that residue is what the backtracking search is for. It is also, exactly, why a spectral test fails: an eigenvalue is a global average over walks and has no more to say about two locally identical links than the refinement does. Deciding that two chains are one Two chains are the same chain when a relabelling of the links carries one to the other. Ten links admit 3,628,800 relabellings, and the census asks the question 26,335 times — so the answer is not a search but a rule that picks one labelling out of the graph itself, and asking whether the two strings match. Same links, same pins, different chains. Watt chain on the left and Stephenson chain on the right. They have the same number of links, the same number of pins and the same assortment — 4×2 + 2×3 — so no count of anything can tell them apart. What differs is where the pins go: on the left the two ternary links share a pin, on the right they do not, and that single fact makes two mechanisms with different coupler curves, different numbers of inversions and different position problems. It is the smallest case in the subject of the thing this field exists to say: the arithmetic is a filter and the graph is the answer. Same links, same pins, different machines Watt's six-bar and Stephenson's have six links, seven pins, four binary links and two ternary ones. Every count anybody can make on them agrees. They are different chains, they give two mechanisms and three, and the difference is whether the two ternary links share a pin. What each of them can reach. Nine hundred control histories of four legs each, from the same starting configuration, with the resulting position plotted. The wheel's cloud is two-dimensional and fills the region; the trolley's is one-dimensional and lies exactly on its rail — the same number of coordinates, the same number of constraints, the same count of freedoms, and a reachable set of a different dimension. Nothing here is a matter of degree. Not unreachable, only expensive The sentence is false of every wheeled mechanism in this field and true of exactly one — the trolley bolted to a rail. A rolling constraint forbids a direction and reaches everywhere; the mistake is reading a statement about instants as a statement about intervals, and it is made in both directions.

What this makes readable

Essays that name this one as a prerequisite.

About the same objects

Not linked from either essay — found by the objects both name.

What links here

Essays that link to this one from their own argument.

The objects this essay names

Each one links to every other essay that touches it.

AutomorphismCanonical formCharacteristic polynomialCospectralEigenvalueGraph isomorphismInversionKinematic chainLink assortmentType synthesis