Which diagonal rigidifies a grid

The second essay in this field established that a network is a graph before it is a mechanism, and that the one quantity readable straight off a drawing is how many independent loops it has. Here is a case where the graph answers a question the count cannot even ask.

A grid of squares, pin-jointed, is a mechanism: every square shears. Bracing a cell with a diagonal triangulates it and removes a freedom. The counting question — how many diagonals — has a one-line answer. The design question is which cells, and the answer has nothing to do with counting.

What an unbraced grid’s freedoms are #

Start with no diagonals. A grid of $m$ columns and $n$ rows has $(m+1)(n+1)$ joints and $m(n+1) + n(m+1)$ bars, so Maxwell’s count gives $2(m+1)(n+1) - 3 - m(n+1) - n(m+1) = mn$ — one freedom per cell, which is the obvious answer and is right.

What the count does not say is what those freedoms look like, and that is the whole of the rest.

An unbraced grid’s every flex shears whole columns and whole rows together. A vertical bar in one column cannot tilt without every vertical bar in that column tilting with it, because the horizontal bars joining them are rigid; likewise for rows. So a configuration of the grid is one angle per column and one angle per row — $m + n$ numbers, less the three that are rigid motions of the whole thing, which is $m + n - 3$… except that the shears are not independent of the rigid rotation, and the careful count comes out at $mn$ again by a different route.

The useful part is the picture, not the count: the grid’s motions are parameterised by column angles and row angles.

What a brace does #

Put a diagonal in cell $(i, j)$ and the cell is triangulated: it cannot shear. Column $i$’s angle and row $j$’s angle must then be equal.

That is the whole effect of a brace. Not “removes one freedom” — identifies two of the angles. And a set of identifications on a set of labels is a graph.

The grid is rigid exactly when all the angles are forced equal, which is exactly when the bipartite graph on the columns and rows is connected. That is Bolker and Crapo’s theorem, and it turns a rank computation into a question a reader can answer by eye.

Two computations that share only a list of cells #

The theorem is a claim, so it gets a test it could fail. Every subset of up to five cells of a three-by-three grid is enumerated — 381 bracings — and for each one two completely independent quantities are computed.

The first is the nullity of the rigidity matrix: the grid built as a framework, one row per bar, the rank taken numerically, the freedoms counted as coordinates less rank. Nothing in that knows about columns, rows or graphs.

The second is the component count of the bipartite graph, computed by union-find on the braces alone. Nothing in that knows about geometry, bars or rank.

They agree at every one of the 381 bracings — not merely about whether the grid is rigid, but about how many freedoms it has: the nullity is the component count less one, exactly, every time.

What the two routes actually compute #

The word “independent” is doing real work above, so it is worth saying what each route touches.

The rank route builds the grid as a framework: sixteen points with coordinates, twenty-nine bars each contributing a row of the rigidity matrix, one point pinned and one coordinate of its neighbour frozen to remove the three rigid motions. The nullity comes from a singular value decomposition with a stated tolerance. Its inputs are floating-point coordinates and its output is an integer read off a spectrum with a gap in it.

The graph route never looks at a coordinate. It has six labels and a list of pairs, and it runs union-find. Its output is an integer by construction.

The only thing they share is the list of braced cells. So the agreement is not two calculations of one formula; it is a geometric computation and a combinatorial one landing on the same integer 381 times.

One detail of the framework construction is worth recording because it was wrong first. Pinning two points removes four coordinates where three rigid motions need removing, so the nullity came out one short at every bracing — a consistent off-by-one that looked like a disagreement with the theorem rather than like an over-constrained model. Pinning one point and one coordinate of another removes exactly three, and the two routes then agree everywhere. A model that removes the wrong number of freedoms produces perfectly plausible integers.

Enough is not enough #

The sweep’s most useful row is the one at five braces. Five is $m + n - 1$, the size of a spanning tree on six nodes, so five is the minimum — and forty-five of the hundred and twenty-six ways of placing five braces leave the grid moving.

That is the sentence the counting argument cannot reach. A designer who braces the bottom two rows of a grid has used the right number of diagonals, has triangulated more than half the cells, and has built something that shears.

And it is not a rare accident. Thirty-six per cent of the minimal bracings fail, so a bracing chosen carelessly fails more often than one in three.

Eighty-one is a number about graphs #

The sharpest form of the result is the count itself.

A minimal rigid bracing is a set of edges that connects six nodes with five edges, which is a spanning tree of the complete bipartite graph $K_{3,3}$. The number of spanning trees of $K_{m,n}$ is $m^{n-1}n^{m-1}$, which for $m = n = 3$ is $3^2 \cdot 3^2 = 81$.

The enumeration counts 81 by building a hundred and twenty-six frameworks and taking a hundred and twenty-six ranks. The formula gets 81 from two exponentiations and knows nothing about rigidity. The two agree, and they agree on other shapes too: a three-by-two grid has $3^1 \cdot 2^2 = 12$ minimal bracings and twelve are counted; a four-by-three grid has $4^2 \cdot 3^3 = 432$ and four hundred and thirty-two are counted, out of nine hundred and twenty-four sets of that size.

Two routes to a number is the strongest shape of evidence available here, and this is an unusually clean instance: one route is a rank computation in floating point and the other is an integer identity.

Where the freedom is, when there is one #

A rank gives the number of freedoms a network has and not where they are, and this field has an instrument for the second question: read the null vector back onto the bars.

Done on a badly braced grid, the answer is unambiguous and it is what the graph predicted. The flex displaces every joint of the unbraced row and leaves every joint of the braced part alone — so the motion is localised on one component of the graph, and the components are not an abstraction but a partition of the structure into pieces that move relative to one another.

That gives the theorem a second reading which is more useful than the first. It does not only say whether a grid is rigid. It says, when the grid is not rigid, exactly which columns and rows move together, because each component of the bipartite graph is one shear angle and the grid’s configuration space is a product of them.

A designer looking at a grid that moves therefore does not need to inspect a null vector. The components of the graph name the parts, and joining any two of them with one more brace removes one freedom — whichever cell that brace goes in, as long as its column is in one component and its row in the other.

Why the count is blind here #

It is worth being precise about what Maxwell’s count gets wrong, because it does not get the arithmetic wrong.

A three-by-three grid with five braces has 16 joints, 24 grid bars and 5 diagonals — 29 bars against 32 coordinates, less 3 rigid motions, so the count gives zero: no freedoms and no redundancies. That is the right answer for the 81 good bracings and the wrong answer for the 45 bad ones, which have one freedom and one redundancy each.

The count is right about the difference and can be wrong about either term, which this field established four essays ago on a deployable ring. The grid is the same statement with a difference: the ring’s count is wrong because of a geometric coincidence in where its bars are, and the grid’s is wrong because of a combinatorial one in which cells are braced.

That distinction matters because the two have different repairs. A geometric degeneracy is fixed by moving something slightly, and usually the designer does not want to. A combinatorial one is fixed by moving a brace from one cell to another, which costs nothing at all — the same five diagonals, rearranged.

The grid against the field’s other networks #

It is worth placing this result beside the two the field already has, because all three are about a count being wrong and they are wrong for three different reasons.

A Miura sheet keeps one freedom at every size while the count runs to minus ninety-nine — the count is wrong by a hundred, and the reason is that a hundred of its constraints repeat things already said. That is redundancy from repetition.

A deployable ring opens while the count says it cannot, and the reason is an angle held at exactly 135° by the shape of its bars. That is redundancy from a geometric coincidence.

A badly braced grid moves while the count says it cannot, and the reason is that two of its braces constrain the same pair of angles. That is redundancy from a combinatorial coincidence — and it is the only one of the three that a reader can find without computing anything.

The three together say what this field’s central claim amounts to. A count sees the number of constraints; a rank sees how many of them are independent; and independence has at least three sources, of which counting can see none.

The rule a designer can carry #

The theorem gives a procedure with no arithmetic in it.

Write the columns on one row of a page and the rows on another. For each brace, draw a line from its column to its row. If the drawing is connected, the grid is rigid; if it is a tree, the bracing is minimal; and if it has a cycle, at least one brace is doing nothing.

The last clause is the one worth having and it follows immediately: a connected graph with more edges than a tree has a cycle, and an edge on a cycle can be removed without disconnecting anything. So a grid braced with more than $m + n - 1$ diagonals has redundant diagonals, and the graph says which ones — any edge on a cycle.

That is a stronger statement than the rank gives. The rank says how many dependencies there are; the graph says which specific braces are removable, which is what a designer taking weight out of a structure actually needs.

What it does not cover #

Three restrictions, all of them real.

Square cells. The argument uses the fact that a brace forces two shear angles to be equal, which needs the cell’s four bars to be a parallelogram. A grid of general quadrilaterals has the same combinatorics only when its cells are parallelograms throughout, which a rectangular grid of unit squares certainly is.

Diagonals, not cross-braces. One diagonal triangulates a cell; the other diagonal of the same cell triangulates it too and adds nothing, so a doubly-braced cell contributes one edge and one redundancy. The essay on the cell that repeats counted exactly that on an infinite grid and found the second diagonal adding a dependency and no rigidity.

First order. The nullity computed here is the dimension of the first-order flex space, and this field knows that a flex need not be a motion. For a braced grid the two coincide — the shears are genuine finite motions, since a parallelogram grid shears through a whole range — but that coincidence is a fact about this family rather than a general licence.

Why this is the network a reader will have met #

Every other network in this field is a specialist object — a deployable ring, a Miura sheet, a lazy tong, a kagome lattice — and the braced grid is not. It is a garden gate, a bookshelf back panel, a scaffolding tower, a warehouse rack, a bicycle-shed wall. Anything built as a rectangular frame of members with some cells diagonally braced is this network, and the question of which cells is asked by whoever is holding the diagonals.

That makes the result unusually easy to act on and unusually easy to get wrong in practice, and the two are the same fact. The failing arrangement is the natural one. A person bracing a grid works along it — finish one row, start the next — and bracing the bottom two rows of a three-row grid is exactly the 45-out-of-126 failure above. The arrangement that works is the one that looks careless: a diagonal in a different column each time, scattered.

The graph says why. Working along a row puts every edge from that row’s node, so the graph is a star on one node and reaches no other row at all; scattering puts edges between different pairs, and a tree is what scattering looks like. So the rule a builder needs is the opposite of tidy: never put two braces in the same row unless their columns are already connected to each other.

There is a second practical reading that the count makes invisible. A grid braced along its diagonal — cell (0,0), (1,1), (2,2) and so on — uses one brace per row and one per column, which is a perfect matching rather than a tree, and a matching on six nodes with three edges leaves three components. So the diagonal bracing, which is the arrangement that looks most deliberate of all, is two braces short on a three-by-three grid and fails. Adding the two that make it a tree is the fix, and which two is again a graph question.

Still open: the same question for the other networks #

The grid is the one network in this field whose rigidity has a combinatorial answer, and the obvious question is which others do.

Laman’s condition answers it for generic planar frameworks: a graph is generically rigid when it has $2v - 3$ edges and no subgraph has more than $2v' - 3$. That is a graph condition and it is decidable, and it says nothing about the networks this field is actually about — because every one of them is built on a coincidence, and a coincidence is exactly what “generic” excludes. A deployable ring is generically rigid and moves; a Miura sheet is generically rigid and folds.

So the field has two combinatorial results and they point in opposite directions. The grid’s is exact because its geometry is a parallelogram grid throughout and the combinatorics captures it; Laman’s is exact for geometry nobody in this field builds. What is missing is a combinatorial condition for a stated non-generic family, which is what rigid origami’s flat-foldable vertices would need and which nobody here has.

The nearer question, and a measurable one, is what happens to the grid’s graph when the cells stop being squares by a stated amount. The identification a brace forces is then approximate rather than exact, the rank stays full, and the freedom becomes a nearly-flex with a small singular value — which is a number this field already knows how to read.

The other direction is three dimensions, and the answer there is known to be harder in a way worth stating. A cubical grid of pin-jointed boxes has a shear per plane rather than per line, so the bracing structure is a graph on three families rather than two — and the condition for rigidity is no longer connectivity of a bipartite graph but a matroid condition not built here and not currently within reach. What it does have is the framework code that would decide any particular case by rank, which is enough to test a conjecture and not enough to state one.