25 Projective duality and the molecule modelling equivalence
Let \(G = (V, E)\) be a graph of minimum degree at least two. KT Corollary 5.7 is the rank formula
where \(r\) is the rank function of the generic bar-joint rigidity matroid in \({\mathbb {R}}^3\) (section 24), \(G^2\) is the square of \(G\), and \(\operatorname {def}(\tilde G)\) is the deficiency of definition 20.3 at \(D = 6\). Jackson and Jordán conjectured the formula and proved it equivalent to the molecular conjecture [ JJ08a , Conjecture 2.2 and Theorem 4.3 ] . Its proof relates three models, all in \({\mathbb {R}}^3\), of a molecule whose atoms and bonds form the graph \(G\):
A molecular framework is a body-hinge framework in which the hinges at each body pass through one point, the centre of the body. The second equivalence is projective duality. A polarity of projective three-space sends points to planes and lines to lines, so it turns a molecular framework into a panel-hinge framework, and infinitesimal rigidity is invariant under it [ CW82 , § 3.6 ] . The first equivalence is Whiteley’s: a graph of minimum degree at least two has an infinitesimally rigid molecular realization if and only if its square has an infinitesimally rigid bar-joint realization. Jackson and Jordán [ JJ08a , § 2.1 ] and Katoh and Tanigawa [ KT11 , pp. 650 and 671 ] cite it from Whiteley’s manuscript The equivalence of molecular rigidity models as geometric and generic graphs (2004).
Whiteley’s equivalence, in the form that Jackson and Jordán and Katoh and Tanigawa state, concerns rigid realizations. In this form it gives the rank formula only when \(\operatorname {def}(\tilde G) = 0\), where the formula says that \(G^2\) is rigid. Jackson and Jordán deduce the general formula from this case [ JJ08a , § § 3–4 ] . Their upper bound on \(r(G^2)\) is the value of an independent cover of \(G^2\) built from a partition of \(V\) of largest deficiency (their Theorem 4.1). It uses results on such covers, and on the maximal subgraphs of deficiency zero, from two further papers of theirs. Their lower bound is an induction on the deficiency, which attaches to \(G\) a path of length five between two of these maximal subgraphs (their Theorem 4.3).
We avoid this development. We prove both equivalences as equalities between the dimensions of the spaces of infinitesimal motions, at a single placement. KT Theorem 5.6 (theorem 23.50) realizes \(G\) as a panel-hinge framework of rank \(6(|V| - 1) - \operatorname {def}(\tilde G)\). The two equivalences turn this realization into a bar-joint framework on \(G^2\) of rank \(3|V| - 6 - \operatorname {def}(\tilde G)\), as Katoh and Tanigawa do for the second (KT p. 671). The reverse inequality comes from the first equivalence at a generic placement, together with the lower bound \(6 + \operatorname {def}(\tilde G)\) on the dimension of the motions of a molecular framework with nondegenerate hinges (lemma 20.16). Section 26 derives the formula in this way.
The chapter proceeds in five steps. Section 25.1 defines the square of a graph and molecular frameworks. Section 25.2 proves the projective invariance of the motion spaces, and shows that the polar of a molecular framework is a panel-hinge framework. Section 25.3 describes a screw by its field of velocities. Section 25.4 defines general position up to order four, and gives a molecular realization at the rank of KT Theorem 5.6 whose centres are in general position. Section 25.5 proves the first equivalence at such centres. Throughout, \(d = 3\) and \(D = 6\), the setting of Katoh and Tanigawa’s connection with molecules (KT §1.2). We use the extensors and the meet of section 18 and section 22, the body-hinge and panel-hinge frameworks of section 19 and section 23, and the bar-joint frameworks of section 6 and section 24.
25.1 The square graph and molecular frameworks
Katoh and Tanigawa describe two models of a molecule whose atoms are joined by covalent bonds [ KT11 , § 1.2 ] . Let \(G\) be the graph of the bonds. In the first model the molecule is a bar-joint framework on the square of \(G\), which joins two atoms when they are at distance one or two in \(G\) (definition 25.1). In the second it is a body-hinge framework on \(G\), with the atoms as bodies and the bonds as hinges, in which all the hinges at an atom pass through its centre (definition 25.3). In the square, an atom and its neighbours induce a complete subgraph (lemma 25.2), which acts as a rigid body [ JJ08a , § 2.1 ] .
The square of a graph \(G = (V,E)\) is the graph \(G^2 = (V, E^2)\) with
that is, \(G\) together with an edge joining every two vertices at distance two in \(G\).
Let \(G\) be a graph. For every vertex \(v\) of \(G\), the closed neighbourhood \(N[v] = \{ v\} \cup N(v)\) induces a complete subgraph of \(G^2\). Moreover, every edge of \(G^2\) has both ends in \(N[w]\) for some vertex \(w\) of \(G\).
Let \(x \neq y\) be vertices of \(N[v]\). If one of them is \(v\), then \(xy\) is an edge of \(G\). Otherwise \(v\) is a common neighbour of \(x\) and \(y\). In both cases \(xy \in E^2\). Now let \(uw\) be an edge of \(G^2\). If it is an edge of \(G\), then \(u\) and \(w\) lie in \(N[u]\). Otherwise \(u\) and \(w\) have a common neighbour \(v\), and they lie in \(N[v]\).
Katoh and Tanigawa call a body-hinge framework hinge-concurrent if all the hinges at each body pass through one point, the centre of the body [ KT11 , p. 650 ] . A molecule is modelled by such a framework, since the bonds at an atom pass through its centre. Following Whiteley [ Whi99 , Definition 4 ] , we give the framework by the centres of its bodies.
Let \(G = (V, E)\) be a multigraph, and let \(c \colon V \to {\mathbb {R}}^3\) assign a centre \(c(v)\) to each body \(v\). The molecular framework on \((G, c)\) is the body-hinge framework on \(G\) (definition 19.3) whose supporting extensor at an edge \(e\) with ends \(u\) and \(v\) is
(definition 18.8), where \(\bar c(v) = (c(v), 1)\).
Let \(e\) be an edge with ends \(u\) and \(v\). If \(c(u) \neq c(v)\), the extensor at \(e\) is a nonzero extensor of the line through \(c(u)\) and \(c(v)\) (the remarks after definition 18.8), and this line is the hinge at \(e\). So when adjacent bodies have distinct centres, every hinge at a body \(v\) passes through \(c(v)\), and the molecular framework is hinge-concurrent. Conversely, let a body-hinge framework on \(G\) be hinge-concurrent with centres \(c\), where \(c(u) \neq c(v)\) at every edge \(uv\). The hinge at \(uv\) passes through \(c(u)\) and \(c(v)\), so it is the line through them, and the framework is the molecular framework on \((G, c)\). Jackson and Jordán call these frameworks molecular frameworks [ JJ08a , § 2.1 ] , and Katoh and Tanigawa use their name [ KT11 , p. 671 ] .
If \(c(u) = c(v)\), the extensor at \(e\) is zero. The hinge at \(e\) is then degenerate, and it welds \(u\) and \(v\) together (the remarks after definition 23.5). Whiteley calls a molecular structure non-degenerate if distinct bodies have distinct centres [ Whi99 , Definition 4 ] . Where nondegenerate hinges are needed below, the centres are assumed distinct or in general position (definition 25.16).
The formal molecular framework records an ordered pair of bodies for every edge label, as a formal panel-hinge framework does (formalization note 23.6). Its extensor at a label is that of the centres of the pair.
25.2 Projective invariance and duality
A projective transformation of space acts linearly on homogeneous coordinates, and through them on the screw space. A collineation sends points to points, and a correlation sends points to planes. Crapo and Whiteley [ CW82 , § 3.6 ] showed that both take the infinitesimal motions of a body-hinge framework to those of the transformed framework. So infinitesimal rigidity is a projective invariant. We prove this for every linear automorphism of the screw space (theorem 25.7). We then apply it to a polarity, which turns a molecular framework into a panel-hinge framework (lemma 25.11).
In every dimension \(d\), an invertible linear map of \(K^{d+1}\) induces a linear automorphism of the screw space \(\bigwedge ^{d-1} K^{d+1}\). For \(d = 3\), Crapo and Whiteley let a collineation act on screws in this way [ CW82 , § 3.6 ] .
Let \(K\) be a field, let \(d \ge 1\), and let \(g\) be an invertible linear map of \(K^{d+1}\). The screw map of \(g\) is the linear automorphism \(\Lambda _g\) of the screw space \(\bigwedge ^{d-1} K^{d+1}\) (definition 19.1) with
The map \(\Lambda _g\) is the \((d-1)\)-th exterior power of \(g\), and its inverse is \(\Lambda _{g^{-1}}\). The extensors span \(\bigwedge ^{d-1} K^{d+1}\) (the remarks after definition 18.3), so the formula determines \(\Lambda _g\).
The first pin is \(\Lambda _g\), and the second is its formula.
Let \(K\) be a field, let \((G, p)\) be a body-hinge framework in \(K^3\) (definition 19.3), and let \(\Lambda \) be a linear automorphism of the screw space \(\bigwedge ^2 K^4\). Let \((G, \Lambda p)\) be the body-hinge framework on \(G\) whose supporting extensor at each edge \(e\) is \(\Lambda \, C(p(e))\).
The map \(S \mapsto \Lambda \circ S\) is an isomorphism from \(Z(G, p)\) onto \(Z(G, \Lambda p)\). In particular the two motion spaces have the same dimension, the two rigidity matrices have the same rank, and \((G, \Lambda p)\) is infinitesimally rigid if and only if \((G, p)\) is.
The hinge at an edge is nondegenerate in \((G, \Lambda p)\) if and only if it is nondegenerate in \((G, p)\).
The space \(Z(G, p)\) does not change when the supporting extensor at each edge is multiplied by a nonzero scalar.
(1) Let \(e\) be an edge with ends \(u\) and \(v\). As \(\Lambda \) is linear and injective, a screw \(w\) lies in \(\operatorname {span} C(p(e))\) if and only if \(\Lambda w\) lies in \(\operatorname {span} \Lambda C(p(e))\). Taking \(w = S(u) - S(v)\) shows that \(S\) satisfies the hinge constraint of \((G, p)\) at \(e\) if and only if \(\Lambda \circ S\) satisfies that of \((G, \Lambda p)\). The map \(S \mapsto \Lambda \circ S\) is a linear automorphism of the space of screw assignments, with inverse \(S \mapsto \Lambda ^{-1} \circ S\), so it maps \(Z(G, p)\) onto \(Z(G, \Lambda p)\). Moreover \(\Lambda \circ S\) is constant if and only if \(S\) is, so the map takes the trivial motions of one framework onto those of the other (definition 19.15), and infinitesimal rigidity transfers. The ranks agree because the rank of the rigidity matrix is \(D|V| - \dim Z\) (the remark after definition 19.7).
(2) A linear automorphism sends nonzero vectors to nonzero vectors. (3) A nonzero multiple of \(C(p(e))\) spans the same line as \(C(p(e))\), so no hinge constraint changes.
This is the argument of Crapo and Whiteley [ CW82 , § 3.6 ] . A collineation “is expressed by a non-singular linear transformation on the projective coordinates of the points”. The linear map that it induces on the space of screws “will transform an instantaneous motion into an instantaneous motion”, and it has an inverse.
The pinned results hold for body-hinge frameworks in \(K^d\) for every \(d\). The first pin is the framework \((G, \Lambda p)\). The next four prove (1): the isomorphism, the equality of the dimensions, that \((G, \Lambda p)\) satisfies the rank hypothesis (definition 23.21) at a target exactly when \((G, p)\) does, and rigidity. The last two prove (2) and (3).
For a general \(\Lambda \), the screw \(\Lambda \, C(p(e))\) need not be the extensor of a line. The hinge constraint at \(e\) is then \(S(u) - S(v) \in \operatorname {span} \Lambda \, C(p(e))\), as in the formal definition (the note after definition 19.3).
Over \({\mathbb {R}}\), every projective transformation of real projective space induces such a map \(\Lambda \), and theorem 25.7 is then Crapo and Whiteley’s projective invariance of infinitesimal rigidity [ CW82 , § 3.6 ] ; see also Whiteley [ Whi99 , Theorem 6 ] . A collineation is given by a nonsingular linear map \(g\) of \({\mathbb {R}}^4\) on homogeneous coordinates. It induces the screw map \(\Lambda _g\) (definition 25.5), with \(\Lambda _g(v_0 \vee v_1) = g v_0 \vee g v_1\), which sends the extensor of the line through two points to that of the line through their images. A correlation sends points to planes by a nonsingular linear map, and it also induces a linear automorphism of the screw space that sends lines to lines [ CW82 , § 3.6 ] . The polarity of the next lemma is a correlation. The proof uses only that \(\Lambda \) is linear and invertible, so we state the theorem over every field. The pencil chapters apply it over an arbitrary field (section 29.3). For the rows of the rigidity matrix, lemma 28.35 proves the invariance of the rank directly.
For \(d = 3\) and \(j = 2\), the complement isomorphism \(*\) (definition 22.5) is a linear automorphism of the screw space \(\bigwedge ^2 K^4\), over every field \(K\). It sends a nonzero extensor of a two-dimensional subspace \(U\) of \(K^4\) to a nonzero extensor of \(U^\perp \) (the remarks after definition 22.7). So it is the map that the polarity \(x \mapsto x^\perp \) of projective space induces on lines: the line through two points goes to the line in which their polar planes meet. We call \(*\) the polarity. The next lemma gives its value on joins.
Let \(K\) be a field, and let \(*\) be the polarity of \(\bigwedge ^2 K^4\). For all \(v_0, v_1 \in K^4\), \(*(v_0 \vee v_1) = C(v_0, v_1)\). In particular, for points \(a, b \in {\mathbb {R}}^3\), the polarity of \(\bigwedge ^2 {\mathbb {R}}^4\) sends the extensor \(C(a, b) = \bar a \vee \bar b\) to \(C(\bar a, \bar b)\).
The first statement holds by the definition of \(C(v_0, v_1)\) (definition 23.1). The second is the first at \(K = {\mathbb {R}}\), \(v_0 = \bar a\) and \(v_1 = \bar b\), as \(C(a, b) = \bar a \vee \bar b\) (definition 18.8).
The pins are the polarity and the two statements, in this order.
The polar plane of a point \(c \in {\mathbb {R}}^3\) is \(\{ x \in {\mathbb {R}}^3 : x \cdot c + 1 = 0\} \), since \((x, 1) \cdot (c, 1) = x \cdot c + 1\), and \(c\) is the pole of this plane. Its normal is \(\bar c = (c, 1)\), and it is the panel that Katoh and Tanigawa attach to the vector \(c\) [ KT11 , § 5.1 ] . They observe that the polar of a hinge-concurrent framework is a panel-hinge framework. Conversely, the polar of a nonparallel panel-hinge framework, in which any two panels meet in a line, is hinge-concurrent, with the poles of the panels as centres. By projective invariance, the two frameworks are infinitesimally rigid together [ KT11 , pp. 650 and 671 ] . Whiteley states this correspondence for molecular structures [ Whi99 , Corollary 12 ] . The next lemma proves it in the form that we use.
Let \(*\) be the polarity of \(\bigwedge ^2 {\mathbb {R}}^4\).
Let \(G\) be a multigraph on \(V\), and let \(c \colon V \to {\mathbb {R}}^3\). The panel-hinge framework on \(G\) with normals \(\bar c(v)\) (definition 23.5) is obtained from the molecular framework on \((G, c)\) (definition 25.3) by applying \(*\) to the supporting extensor at every edge. Hence the two frameworks have motion spaces of the same dimension and rigidity matrices of the same rank. One of them is infinitesimally rigid if and only if the other is, and the hinge at an edge is nondegenerate in one if and only if it is nondegenerate in the other.
The conclusions of (1) also hold for the panel-hinge framework on \(G\) with normals \(\lambda _v\, \bar c(v)\), for any nonzero scalars \(\lambda _v\). Its motion space is that of the panel-hinge framework with normals \(\bar c(v)\).
For (1), both frameworks have the multigraph \(G\). At an edge with ends \(u\) and \(v\), the molecular framework has the supporting extensor \(\bar c(u) \vee \bar c(v)\). Its image under \(*\) is \(C(\bar c(u), \bar c(v))\) (lemma 25.9), the supporting extensor of the panel-hinge framework at that edge. As \(*\) is a linear automorphism of \(\bigwedge ^2 {\mathbb {R}}^4\) (definition 22.5), theorem 25.7 gives the rest. For (2), the join is bilinear, so \(C(\lambda _u \bar c(u), \lambda _v \bar c(v)) = \lambda _u \lambda _v\, C(\bar c(u), \bar c(v))\). The two panel-hinge frameworks differ by nonzero multiples of their supporting extensors, so they have the same motion space by theorem 25.7(3).
The first pin is the identity of the two frameworks in (1), and the next four are its consequences: the dimensions of the motion spaces, the rank hypothesis (definition 23.21), rigidity, and the nondegeneracy of the hinges. The last two pins are the first two of lemma 30.38, which hold for any normals over any field, and give (2) at the normals \(\bar c(v)\). The first scales the hinge at an edge with ends \(u\) and \(v\) by \(\lambda _u \lambda _v \neq 0\), so it is nondegenerate exactly when the hinge at the normals \(\bar c(v)\) is. The second is the equality of the motion spaces, from which the other conclusions of (1) follow by the first five pins. The proof of theorem 25.20 rescales the normals it uses directly, by the argument above.
25.3 Screw velocity fields
The square-graph dictionary (theorem 25.22) compares the infinitesimal motions of the two models of a molecule. A motion of the molecular framework assigns a screw to each body, and a motion of the bar-joint framework assigns a velocity to each atom. A screw is an infinitesimal rigid motion of space. It moves a point \(x\) with velocity \(\omega \times x + t\), where \(\omega \) is its angular velocity and \(t\) is the velocity of the origin. This subsection defines this velocity field and proves the facts about it that the dictionary uses.
For \(v \in {\mathbb {R}}^4\), let \(v' \in {\mathbb {R}}^3\) be its first three coordinates and \(v_4\) its last. The rotation part \(\omega _S \in {\mathbb {R}}^3\) and the translation part \(t_S \in {\mathbb {R}}^3\) of a screw \(S \in \bigwedge ^2 {\mathbb {R}}^4\) are the linear functions of \(S\) with
The velocity field of \(S\) is
The two formulas are bilinear and alternating in \(v\) and \(w\), so they define linear maps \(S \mapsto \omega _S\) and \(S \mapsto t_S\) on \(\bigwedge ^2 {\mathbb {R}}^4\). Write \(S = \sum _{i {\lt} j} S_{ij}\, e_i \vee e_j\) in the standard basis. Then \(\omega _S = -(S_{14}, S_{24}, S_{34})\) and \(t_S = (S_{23}, -S_{13}, S_{12})\), so up to sign and order \(\omega _S\) and \(t_S\) are the six coordinates of \(S\). In particular \(S\) is determined by \(\omega _S\) and \(t_S\). For two points \(a, b \in {\mathbb {R}}^3\), the extensor \(\bar a \vee \bar b\) of the line through them has \(\omega = b - a\) and \(t = a \times b\), and
This is the velocity field of the rotation about the line through \(a\) and \(b\) with angular velocity \(b - a\). For every screw \(S\) and all \(x, y \in {\mathbb {R}}^3\),
Let \(a \neq b\) be points of \({\mathbb {R}}^3\), and let \(S\) be a screw. Then \(\mathrm{vel}_S(a) = \mathrm{vel}_S(b) = 0\) if and only if \(S\) is a multiple of \(\bar a \vee \bar b\). Moreover \(\langle x - y,\, \mathrm{vel}_S(x) - \mathrm{vel}_S(y) \rangle = 0\) for all \(x, y \in {\mathbb {R}}^3\), that is, every velocity field is an infinitesimal isometry.
The second statement holds because \(\mathrm{vel}_S(x) - \mathrm{vel}_S(y) = \omega _S \times (x - y)\) is orthogonal to \(x - y\). The velocity field of \(\bar a \vee \bar b\) is \((b - a) \times (x - a)\), which vanishes at \(a\) and at \(b\), and so do the velocity fields of its multiples. Conversely, suppose that \(\mathrm{vel}_S(a) = \mathrm{vel}_S(b) = 0\). Then \(\omega _S \times (b - a) = \mathrm{vel}_S(b) - \mathrm{vel}_S(a) = 0\), and since \(b - a \neq 0\), \(\omega _S = \lambda \, (b - a)\) for some \(\lambda \in {\mathbb {R}}\). From \(\mathrm{vel}_S(a) = 0\) we get \(t_S = -\omega _S \times a = \lambda \, a \times b\). So \(S\) and \(\lambda \, (\bar a \vee \bar b)\) have the same rotation and translation parts, and they are equal.
A screw whose velocity field vanishes at three non-collinear points of \({\mathbb {R}}^3\) is zero.
Let \((p_i)_{i \in I}\) be a family of points of \({\mathbb {R}}^3\), and let \(i_0, i_1, i_2 \in I\) be such that \(p_{i_0}, p_{i_1}, p_{i_2}\) are not collinear and, for every \(j \in I\) other than \(i_0\), \(i_1\) and \(i_2\), the points \(p_j, p_{i_0}, p_{i_1}, p_{i_2}\) are affinely independent. Let \((x_i)_{i \in I}\) be vectors of \({\mathbb {R}}^3\) with \(\langle p_i - p_j,\, x_i - x_j \rangle = 0\) for all \(i, j \in I\). Then there is a unique screw \(S\) with \(\mathrm{vel}_S(p_i) = x_i\) for every \(i \in I\).
(1) Let \(\mathrm{vel}_S\) vanish at non-collinear points \(q_0, q_1, q_2\). Then \(\omega _S \times (q_i - q_0) = \mathrm{vel}_S(q_i) - \mathrm{vel}_S(q_0) = 0\) for \(i = 1, 2\), so \(\omega _S\) is a multiple of both \(q_1 - q_0\) and \(q_2 - q_0\). These vectors are linearly independent, so \(\omega _S = 0\), and then \(t_S = \mathrm{vel}_S(q_0) = 0\). Hence \(S = 0\) (the remarks after definition 25.13).
(2) Uniqueness follows from (1): two such screws differ by a screw whose velocity field vanishes at the non-collinear points \(p_{i_0}, p_{i_1}, p_{i_2}\).
For existence, let \(q_k = p_{i_k}\), with prescribed velocity \(y_k = x_{i_k}\), for \(k = 0, 1, 2\), and let \(e_i = q_i - q_0\) and \(d_i = y_i - y_0\) for \(i = 1, 2\). The hypothesis on the pairs among \(q_0, q_1, q_2\) reads \(e_1 \cdot d_1 = e_2 \cdot d_2 = 0\) and \(e_1 \cdot d_2 + e_2 \cdot d_1 = 0\). We first find \(\omega \in {\mathbb {R}}^3\) with \(\omega \times e_1 = d_1\) and \(\omega \times e_2 = d_2\). By the vector triple product, \(\omega _0 = (e_1 \cdot e_1)^{-1}\, (e_1 \times d_1)\) satisfies \(\omega _0 \times e_1 = d_1\). The vector \(u = d_2 - \omega _0 \times e_2\) is orthogonal to \(e_2\), and the third of these equations makes it orthogonal to \(e_1\) as well. So \(u = \mu \, (e_1 \times e_2)\) for some \(\mu \in {\mathbb {R}}\), and \(\omega = \omega _0 + \mu \, e_1\) satisfies both equations. Let \(S\) be the screw with \(\omega _S = \omega \) and \(t_S = y_0 - \omega \times q_0\). Then \(\mathrm{vel}_S(q_0) = y_0\), and \(\mathrm{vel}_S(q_i) = y_0 + \omega \times e_i = y_i\) for \(i = 1, 2\).
Let \(j \in I\) be other than \(i_0\), \(i_1\) and \(i_2\), let \(w = p_j\), with prescribed velocity \(y_w = x_j\), and let \(r = \mathrm{vel}_S(w) - y_w\). For \(k = 0, 1, 2\), the vector \(w - q_k\) is orthogonal to \(\mathrm{vel}_S(w) - \mathrm{vel}_S(q_k)\) (lemma 25.14) and to \(y_w - y_k\) (by hypothesis). As \(\mathrm{vel}_S(q_k) = y_k\), it is orthogonal to \(r\). By hypothesis the points \(w, q_0, q_1, q_2\) are affinely independent, so the vectors \(w - q_0\), \(w - q_1\), \(w - q_2\) span \({\mathbb {R}}^3\), and \(r = 0\).
The hypothesis of affine independence cannot be dropped: four coplanar points, three of them not collinear, admit the out-of-plane flex of a flat complete quadrilateral, which is not the restriction of a screw. Indeed, every assignment of velocities perpendicular to the plane satisfies \(\langle p_i - p_j,\, x_i - x_j \rangle = 0\), and these assignments form a space of dimension four. But on the plane, the perpendicular component of a velocity field is an affine function, which is determined by its values at three non-collinear points.
25.4 Molecular realizations in general position
The square-graph dictionary (theorem 25.22) needs the centres of a molecular framework to be in general position up to order four. This subsection defines the condition and constructs placements that satisfy it: first together with genericity for row independence, then as the centres of a molecular realization at the rank of KT Theorem 5.6.
A placement \(p \colon V \to {\mathbb {R}}^3\) (definition 6.1) is in general position up to order four if, for every set \(S \subseteq V\) of at most four vertices, the points \(p(v)\) with \(v \in S\) are affinely independent.
Such a placement is injective, and no three of its points are collinear. For every finite \(V\) there is one. Let \(t \colon V \to {\mathbb {R}}\) be injective, and place each vertex \(v\) at the point \((t_v, t_v^2, t_v^3)\) of the moment curve. For four vertices with parameters \(t_1, \dots , t_4\), the matrix with rows \((t_i, t_i^2, t_i^3, 1)\) has the Vandermonde determinant \(\pm \prod _{i {\lt} j} (t_j - t_i) \neq 0\), so the four points are affinely independent (lemma 18.2). Fewer than four points of the curve lie among four of its points at distinct parameters, and a subfamily of an affinely independent family is affinely independent.
Let \(V\) be finite. Then there is a placement \(p \colon V \to {\mathbb {R}}^3\) that is generic for row independence (definition 24.1) and in general position up to order four.
Let \(p_0\) be a placement that is generic for row independence (lemma 24.2), let \(q\) be a placement in general position up to order four, and let \(p^t = p_0 + t\, (q - p_0)\) for \(t \in {\mathbb {R}}\).
Let \(I \subseteq E(K_V)\) be a set of edges that is row-independent at some placement. Then it is row-independent at \(p_0\). Its rigidity rows at \(p^t\) are affine in \(t\), so it is row-independent at \(p^t\) for all but finitely many \(t\), as in the proof of lemma 24.2. Let \(S \subseteq V\) have at most four vertices, and fix \(v_0 \in S\). The points \(p^t(v)\) with \(v \in S\) are affinely independent exactly when the vectors \(p^t(v) - p^t(v_0)\) with \(v \in S \setminus \{ v_0\} \) are linearly independent. These vectors are affine in \(t\) and linearly independent at \(t = 1\), so in the same way they are linearly independent for all but finitely many \(t\).
There are finitely many sets \(I\) and \(S\). Choose \(t\) outside the finitely many exceptional values of all of them. Then \(p^t\) is in general position up to order four, and it is generic for row independence, since every edge set that is row-independent at some placement is row-independent at \(p^t\).
KT Theorem 5.6 realizes a simple graph as a panel-hinge framework at the target rank (definition 23.21). The realization can be taken with nonparallel panels and nondegenerate hinges (theorem 23.48). We need more. A normal \(n \in {\mathbb {R}}^4\) with a nonzero last coordinate is a nonzero multiple of \(\bar c = (c, 1)\) for a unique point \(c \in {\mathbb {R}}^3\), the pole of its panel (section 25.2). We ask that the poles be in general position up to order four. Up to a rescaling of its normals, the realization is then the image under the polarity of a molecular framework whose centres are the poles (lemma 25.11).
Let \(G = (V, E)\) be a simple graph with \(V \neq \emptyset \). Then \(G\) has a panel-hinge realization \((G, p)\) in \({\mathbb {R}}^3\) whose normals are \(n_v = \lambda _v\, \bar c(v)\), for nonzero scalars \(\lambda _v\) and points \(c(v) \in {\mathbb {R}}^3\) in general position up to order four (definition 25.16), whose panels are nonparallel (definition 23.10), and which has
where \(D = 6\).
If \(|V| = 1\), then \(G\) has no edge, as it is simple, and \(\operatorname {def}(\tilde G) = 0\). Every realization of \(G\) then has \(\dim Z(G, p) = D\), the dimension of the screw space, and any normal \(\bar c(v)\) will do. Its panels are nonparallel, as it has no two distinct bodies.
Let \(|V| \ge 2\), and let \(N = D(|V| - 1) - \operatorname {def}(\tilde G)\). KT Theorem 5.6 at \(d = 3\) (theorem 23.52) holds with nondegenerate hinges (theorem 23.48). So \(G\) has a panel-hinge realization with normals \(q_0\) whose hinges are all nondegenerate and whose rigidity matrix has rank \(N\). We move the normals into general position without lowering the rank. The rank is lower semicontinuous on the normals at which every hinge is nondegenerate (lemma 23.112). We use this in the form of lemma 23.120, which keeps the minor of its proof: a polynomial \(Q_1\) in the coordinates of the normals, an \(N \times N\) minor of a matrix of rows of the rigidity matrix, such that \(Q_1(q_0) \neq 0\) and \(\operatorname {rank} R(G, q) \ge N\) at every \(q\) with \(Q_1(q) \neq 0\).
A second polynomial \(Q_2\) tests general position. Regard the normals as the rows of a \(|V| \times 4\) matrix of variables. Let \(Q_2\) be the product of the last coordinates of all the normals and of the minors on the first \(j\) columns of the submatrices formed by \(j\) distinct rows, for \(j = 2, 3, 4\). At normals with \(Q_2 \neq 0\), each normal has a nonzero last coordinate, so that \(n_v = \lambda _v\, \bar c(v)\) with \(\lambda _v \neq 0\). Any \(j\) of the normals, for \(2 \le j \le 4\), have a nonzero \(j \times j\) minor, so they are linearly independent, and so are the vectors \(\bar c(v)\), which differ from them by nonzero factors. Hence any four or fewer of the points \(c(v)\) are affinely independent (lemma 18.2). The polynomial \(Q_2\) is not zero. At the normals \((1, t_v, t_v^2, t_v^3)\) of the moment curve, with distinct nonzero \(t_v\), the last coordinates are \(t_v^3 \neq 0\), and each of the minors is a Vandermonde determinant, which is nonzero.
A third polynomial \(Q_3\) tests nonparallel panels: the product, over the ordered pairs \((u, v)\) of distinct bodies, of the \(2 \times 2\) minor on the first two columns of the rows \(n_u\) and \(n_v\). Where it is not zero, the first three coordinates of \(n_u\) and of \(n_v\) are linearly independent, so the panels are nonparallel (definition 23.10). At the same moment-curve normals each factor is \(t_v - t_u \neq 0\) (lemma 23.12), so \(Q_3\) is not zero.
As \({\mathbb {R}}\) is infinite, the nonzero polynomial \(Q_1 Q_2 Q_3\) has a non-root \(q\), and at \(q\) the poles are in general position up to order four and the panels are nonparallel. In particular any two of the normals are linearly independent, so every hinge of \((G, q)\) is nondegenerate (lemma 23.11). The deficiency bound for nondegenerate hinges (lemma 20.16) gives \(\operatorname {rank} R(G, q) \le N\), and \(Q_1(q) \neq 0\) gives \(\operatorname {rank} R(G, q) \ge N\). So \(\dim Z(G, q) = D|V| - N = D + \operatorname {def}(\tilde G)\).
Katoh and Tanigawa need only a nonparallel realization, one whose panels meet pairwise in lines, and they obtain it by a projective transformation (KT pp. 670–671). The square-graph dictionary needs the poles in general position up to order four. The argument above provides both.
The pinned theorem assumes that \(G\) spans the set \(W\) of bodies, and nothing of the edge labels (remark 23.40). It states the general position of the poles for the normals: each has a nonzero last coordinate, and any four or fewer of them are linearly independent. It also states that every hinge at an edge of \(G\) is nondegenerate. Its endpoint selector assigns each edge of \(G\) its two ends, as every panel-hinge framework’s does (formalization note 23.6).
Katoh and Tanigawa deduce from KT Theorem 5.6 that every simple graph has a molecular realization at the target rank (KT p. 671). Taking the poles of lemma 25.18 as centres, we obtain such a realization with centres in general position up to order four.
Let \(G = (V, E)\) be a simple graph with \(V \neq \emptyset \). Then there is a placement \(c \colon V \to {\mathbb {R}}^3\) in general position up to order four (definition 25.16) such that the space \(Z_{\mathrm{mol}}(G, c)\) of infinitesimal motions of the molecular framework on \((G, c)\) (definition 25.3) has dimension
where \(D = 6\). In particular, if \(\operatorname {def}(\tilde G) = 0\), then this molecular framework is infinitesimally rigid.
Let \((G, p)\) be the realization of lemma 25.18, with normals \(n_v = \lambda _v\, \bar c(v)\), where each \(\lambda _v \neq 0\) and the points \(c(v)\) are in general position up to order four. Up to the factors \(\lambda _v\), these are the normals \(\bar c(v)\) of the image of the molecular framework on \((G, c)\) under the polarity (lemma 25.11(1)). The factors multiply the supporting extensor at an edge with ends \(u\) and \(v\) by \(\lambda _u \lambda _v \neq 0\), which does not change the motion space (theorem 25.7(3)). So by lemma 25.11(2),
If \(\operatorname {def}(\tilde G) = 0\), then \(\dim Z_{\mathrm{mol}}(G, c) = D\). As \(V \neq \emptyset \), the trivial motions form a \(D\)-dimensional subspace of \(Z_{\mathrm{mol}}(G, c)\) (lemma 19.18), so every infinitesimal motion is trivial.
The pinned theorem assumes that \(G\) spans the set \(W\) of bodies, and nothing of the edge labels (remark 23.40). It also returns the endpoint selector of the molecular framework, and states that it assigns each edge of \(G\) its two ends (formalization note 23.6). This is the form in which theorem 25.22 takes the framework. The rescaling in the proof is proved directly, from the equality of the spans of the supporting extensors, by the inclusion of motion spaces of lemma 19.22 in both directions. The pinned theorem does not state the case \(\operatorname {def}(\tilde G) = 0\), which the last paragraph of the proof derives. Its formal step is the last pin of lemma 19.18: a framework on a nonempty set of bodies whose motion space has dimension \(D\) is infinitesimally rigid.
25.5 The square-graph dictionary
We prove Whiteley’s equivalence for the motion spaces at one placement \(c\) in general position up to order four. A screw assignment \(S\) of the molecular framework on \((G, c)\) gives each atom \(v\) the velocity of its own screw \(S(v)\) at its centre \(c(v)\). We show that this map is an isomorphism from the motions of the molecular framework onto those of the bar-joint framework on \(G^2\) at \(c\). Its inverse recovers the screw of a body \(v\) from the velocities at the centres of the closed neighbourhood \(N[v]\), which is a clique of \(G^2\) (lemma 25.2). Neither Jackson and Jordán nor Katoh and Tanigawa say which general position the equivalence needs. The proof needs any four centres of a closed neighbourhood to be affinely independent, because four coplanar points admit the out-of-plane flex of a flat complete quadrilateral, which is not the field of velocities of a screw (the end of the proof of lemma 25.15). It also needs every atom to have at least two bonds. Whiteley notes that, except in how atoms with only one bond or none are handled, the hinge model of a molecule is equivalent to the bond-bending networks used in modelling glasses [ Whi99 , p. 27 ] .
Let \(G = (V,E)\) be a graph of minimum degree at least two, and let \(c \colon V \to {\mathbb {R}}^3\) be a placement in general position up to order four. Then the space \(Z_{\mathrm{mol}}(G, c)\) of infinitesimal motions of the molecular framework on \((G, c)\) (definition 25.3) and the kernel of the rigidity map \(R(G^2, c)\) of the square of \(G\) (definition 25.1) are isomorphic. So
and \(\operatorname {rank} R(G^2, c) = 3|V| - \dim Z_{\mathrm{mol}}(G, c)\). Moreover, \(G\) has an infinitesimally rigid molecular realization with nondegenerate hinges, that is, with \(c(u) \neq c(v)\) at every edge \(uv\), if and only if \(G^2\) has an infinitesimally rigid bar-joint realization in \({\mathbb {R}}^3\).
The map. For a screw assignment \(S\), let \(\Phi (S)\) be the velocity assignment \(v \mapsto \mathrm{vel}_{S(v)}(c(v))\) (definition 25.13). It is linear in \(S\). Let \(S \in Z_{\mathrm{mol}}(G, c)\), and let \(u\) be a neighbour of a vertex \(v\). By the hinge constraint at \(uv\), the screw \(S(u) - S(v)\) is a multiple of \(\bar c(u) \vee \bar c(v)\), whose velocity field vanishes at \(c(u)\) (lemma 25.14). So \(\Phi (S)(u) = \mathrm{vel}_{S(v)}(c(u))\): on the closed neighbourhood \(N[v]\), the velocities \(\Phi (S)\) are those of the single screw \(S(v)\).
Motions go to motions. Every edge \(xy\) of \(G^2\) has both ends in \(N[w]\) for some vertex \(w\) (lemma 25.2). Hence \(\Phi (S)(x) - \Phi (S)(y) = \mathrm{vel}_{S(w)}(c(x)) - \mathrm{vel}_{S(w)}(c(y))\), which is orthogonal to \(c(x) - c(y)\) (lemma 25.14). So \(\Phi (S)\) lies in \(\ker R(G^2, c)\) (lemma 6.4).
Injectivity. Let \(\Phi (S) = 0\), and let \(v\) be a vertex. The velocity field of \(S(v)\) vanishes at the centres of \(N[v]\). There are at least three of them, as \(v\) has at least two neighbours, and they are not collinear, as \(c\) is in general position. So \(S(v) = 0\) (lemma 25.15(1)).
Surjectivity. Let \(x \in \ker R(G^2, c)\), and let \(v\) be a vertex. The closed neighbourhood \(N[v]\) is a clique of \(G^2\) (lemma 25.2), so \(\langle c(a) - c(b),\, x(a) - x(b) \rangle = 0\) for all \(a, b \in N[v]\). The centres of \(N[v]\) include three non-collinear points, and any four of them are affinely independent. By lemma 25.15(2) there is a unique screw \(S(v)\) with \(\mathrm{vel}_{S(v)}(c(a)) = x(a)\) for every \(a \in N[v]\). In particular \(\Phi (S)(v) = x(v)\). Let \(uv\) be an edge of \(G\). Both \(u\) and \(v\) lie in \(N[u]\) and in \(N[v]\), so the velocity fields of \(S(u)\) and \(S(v)\) agree at \(c(u)\) and at \(c(v)\). As \(c(u) \neq c(v)\), the screw \(S(u) - S(v)\) is a multiple of \(\bar c(u) \vee \bar c(v)\) (lemma 25.14), which is the hinge constraint at \(uv\). So \(S \in Z_{\mathrm{mol}}(G, c)\), and \(\Phi (S) = x\).
Hence \(\Phi \) restricts to an isomorphism from \(Z_{\mathrm{mol}}(G, c)\) onto \(\ker R(G^2, c)\). The map \(R(G^2, c)\) is defined on a space of dimension \(3|V|\) (lemma 6.2), so its rank is \(3|V| - \dim Z_{\mathrm{mol}}(G, c)\).
Realizations. Both sides of the equivalence hold when \(V = \emptyset \), so let \(V \neq \emptyset \). Suppose first that the molecular framework on \((G, c_0)\) is infinitesimally rigid for some \(c_0\) with \(c_0(u) \neq c_0(v)\) at every edge \(uv\). Its motions are the trivial ones, so \(\dim Z_{\mathrm{mol}}(G, c_0) = D\) (lemma 19.18). Its hinges are nondegenerate, so \(\dim Z_{\mathrm{mol}}(G, c_0) \ge D + \operatorname {def}(\tilde G)\) (lemma 20.15), and \(\operatorname {def}(\tilde G) = 0\). By theorem 25.20 there is a placement \(c'\) in general position up to order four with \(\dim Z_{\mathrm{mol}}(G, c') = D = 6\). By the first part, \(\dim \ker R(G^2, c') = 6\), so \(c'\) is infinitesimally rigid for \(G^2\) (definition 6.5).
Conversely, let \(p\) be infinitesimally rigid for \(G^2\), so that \(\operatorname {rank} R(G^2, p) \ge 3|V| - 6\). Let \(c'\) be a placement that is generic for row independence and in general position up to order four (lemma 25.17). The rank of \(R(G^2, p)\) is at most the generic rank of \(G^2\) (lemma 26.1), which is the rank of \(R(G^2, c')\) (lemma 24.9), so \(\operatorname {rank} R(G^2, c') \ge 3|V| - 6\). By the first part, \(\dim Z_{\mathrm{mol}}(G, c') \le 6 = D\). The trivial motions form a \(D\)-dimensional subspace of \(Z_{\mathrm{mol}}(G, c')\) (lemma 19.18), so the molecular framework on \((G, c')\) is infinitesimally rigid. Its hinges are nondegenerate, as \(c'\) is injective.
The first pinned theorem states the equality of the dimensions. It builds the molecular framework on a multigraph on \(V\) in which two distinct vertices are joined by an edge exactly when they are adjacent in \(G\), with an endpoint selector that assigns each edge its two ends (formalization note 23.6). Edges with the same ends impose the same hinge constraint, and a loop imposes none, so the motions are those of the molecular framework on \((G, c)\). The second pinned theorem states the equivalence of realizations in the last sentence of the theorem, for a simple graph \(G\), on the multigraph of lemma 26.3: a molecular realization takes an endpoint selector that assigns each edge its two ends, and centres \(c\) with \(c(u) \neq c(v)\) at every edge \(uv\) of \(G\). Its proof is the one above, the case \(V = \emptyset \) included.