28 The generic form of the realization theorems
Several theorems of the preceding chapters assert that a graph has some realization with a given property, or give the rank of a matroid. Tay’s theorem (theorem 16.27) and the theorem of Tay and Whiteley (theorem 17.5) characterize the multigraphs that have an independent, or an independent and infinitesimally rigid, body-bar or body-hinge framework. In the formalization the body-hinge frameworks of the second theorem are bundles of bars, which need not come from hinges (the note after definition 17.2). KT Theorem 5.6 (theorem 23.50) gives a panel-hinge realization of a simple graph, with nonparallel panels, at the target rank of definition 23.21. The molecule rank formula (corollary 26.8) gives the rank of a square \(G^2\) in the generic rigidity matroid \(\mathcal{R}_3(V)\). This chapter proves generic forms of these results: they hold at every generic realization, and almost all realizations are generic. We follow the coordinate argument of Jackson and Jordán [ JJ10 ] , not Whiteley’s argument on irreducible varieties [ Whi88 , § 3.1 ] , which the body-bar chapter recalls (section 16).
In each class of frameworks a realization is given by parameters: the coordinates of the points of a placement, of the normals of the panels, of the endpoints of the bars, or of points that span the hinges. A fixed family of linear forms, with coefficients that are polynomials in the parameters, spans the rows of the rigidity matrix. For placements and bars the forms are the rows. For a hinge they span its rows when it is nondegenerate. A realization is generic for row independence if every subfamily that is linearly independent at some realization is linearly independent at it (definition 24.1 is the bar-joint instance). So a rank that the rigidity matrix of a graph attains at one realization, with nondegenerate hinges where there are hinges, is attained or exceeded at every generic realization. A bound that holds at every realization then gives the rank there. The realizations that are not generic lie in the zero set of a nonzero polynomial in the parameters (lemma 28.1 for placements). So over an infinite field generic realizations exist, and over \({\mathbb {R}}\) they form a dense open set, which is the precise content of “almost all realizations are generic”. Jackson and Jordán instead note that realizations whose coordinates are algebraically independent over \({\mathbb {Q}}\) are generic [ JJ10 , § 5 ] .
Jackson and Jordán call a realization generic if its rigidity matrix and all its edge-induced submatrices have the largest rank over all realizations of the graph [ JJ10 , § § 5–7 ] . Where each edge has one row, as for placements (section 24.1) and for bars, the two notions agree; for bars this needs the dimension \(d\) to be positive and the multigraph to have no loops. A hinge has \(D - 1\) rows, where \(D = \binom {d+1}{2}\), and a degenerate hinge welds its two bodies together. For \(d \ge 2\) and a graph without loops, a generic assignment of normals or of hinge points has nondegenerate hinges. It attains the largest ranks over the assignments whose hinges are nondegenerate, as Jackson and Jordán’s are. For hinge points these assignments are their realizations, so a generic hinge-point assignment is generic in their sense (lemma 28.34, where loops are allowed). The panel, body-bar and body-hinge sections each compare the two notions.
Section 28.1 shows that the placements that are not generic lie in the zero set of a nonzero polynomial. Section 28.2 proves the molecule rank formula at every generic placement. It deduces that every generic placement is infinitesimally rigid for \(G^2\) when \(5 \cdot G\) contains six edge-disjoint spanning trees, as Jackson and Jordán noted the molecular conjecture would imply. Section 28.3 proves the rank formula of KT Proposition 2.3, Jackson and Jordán’s Theorem 6.1, at every generic assignment of normals to a simple graph. Its rigidity corollary contains their theorem on generic panel-and-hinge realizations (their Theorem 7.2). Section 28.4 proves Tay’s theorem at every generic choice of the endpoints of the bars. Section 28.5 proves the rank formula at every generic choice of points spanning the hinges of a multigraph, with parallel edges and loops allowed, and with it the theorem of Tay and Whiteley for frameworks with hinges.
28.1 Abundance of generic placements
Generic placements exist in every dimension, by an argument that moves along one line at a time (lemma 24.2). Taken as polynomials in all the coordinates of a placement, the minors of that argument show more: the placements that are not generic lie in the zero set of one nonzero polynomial.
Let \(V\) be finite and \(d \in {\mathbb {N}}\). Then there is a nonzero real polynomial \(P\) in the \(d\, |V|\) coordinates of a placement of \(V\) in \({\mathbb {R}}^{d}\) such that every placement \(p\) with \(P(p) \neq 0\) is generic for row independence. In particular, the placements that are not generic lie in the zero set of a nonzero polynomial.
Let \(\mathcal{F}\) be the family of sets \(I \subseteq E(K_V)\) that are row-independent at some placement. It is finite, since \(E(K_V)\) is. Let \(I \in \mathcal{F}\), and let \(q\) be a placement at which \(I\) is row-independent. The rigidity row of an edge \(uv\) at a placement \(p\) is \(x \mapsto \langle p_u - p_v,\, x_u - x_v \rangle \) (lemma 6.4), which depends linearly on \(p\). Fix a basis of \((({\mathbb {R}}^{d})^{V})^{*}\). The coordinate vectors of the rows at \(p\) of the edges in \(I\) are the rows of a matrix \(A(p)\) whose entries are linear forms in the coordinates of \(p\). These rows are linearly independent at \(q\) (lemma 9.6), so some \(|I| \times |I|\) minor of \(A(q)\) is nonzero. The same minor of \(A(p)\) is a polynomial \(P_I\) in the coordinates of \(p\). It is nonzero, as \(P_I(q) \neq 0\), and \(I\) is row-independent at every placement \(p\) with \(P_I(p) \neq 0\).
Let \(P\) be the product of the polynomials \(P_I\) for \(I \in \mathcal{F}\). It is nonzero, as a finite product of nonzero polynomials. If \(P(p) \neq 0\), then \(P_I(p) \neq 0\) for every \(I \in \mathcal{F}\). So every member of \(\mathcal{F}\) is row-independent at \(p\), and \(p\) is generic (definition 24.1).
28.2 Every generic realization of a square
The molecule rank formula (corollary 26.8) gives the rank of the square \(G^2\) in the generic rigidity matroid \(\mathcal{R}_3(V)\). We show that it gives the rank of the rigidity map of \(G^2\) at every placement that is generic for row independence, and we deduce when every such placement is infinitesimally rigid for \(G^2\).
Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\), and let \(p\) be a placement of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence. Then
where \(\operatorname {def}(\tilde G)\) is the deficiency of definition 20.3 at \(D = 6\), with \(\tilde G = 5 \cdot G\).
As \(p\) is generic, \(\operatorname {rank} R(G^2, p) = r(G^2)\), the rank of \(G^2\) in \(\mathcal{R}_3(V)\) (lemma 24.9). By the molecule rank formula (corollary 26.8), \(r(G^2) = 3|V| - 6 - \operatorname {def}(\tilde G)\).
Let \(G\) be a simple graph of minimum degree at least two on a finite, nonempty vertex set \(V\), and suppose that \(\operatorname {def}(\tilde G) = 0\), where \(\tilde G = 5 \cdot G\). Then every placement \(p\) of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence is infinitesimally rigid for \(G^2\).
By theorem 28.2, \(\operatorname {rank} R(G^2, p) = 3|V| - 6\). The space of placements has dimension \(3|V|\) (lemma 6.2), so by rank–nullity \(\dim \ker R(G^2, p) = 6\). This is the bound of definition 6.5 at \(d = 3\).
Jackson and Jordán noted that the molecular conjecture (their Conjecture 1.1), together with Tay and Whiteley’s theorem on body-and-hinge frameworks (their Corollary 6.3; section 17.2), would imply that every generic bar-joint realization of \(G^2\) in \({\mathbb {R}}^3\) is infinitesimally rigid whenever \(5 \cdot G\) contains six edge-disjoint spanning trees [ JJ10 , p. 586 ] . Katoh and Tanigawa proved the molecular conjecture [ KT11 ] , and theorem 23.56 is its form for simple graphs. We derive the consequence from corollary 28.3, and so from the molecule rank formula.
Let \(G\) be a simple graph on a finite, nonempty vertex set \(V\), and suppose that \(5 \cdot G\) contains six edge-disjoint spanning trees. Then every placement of \(V\) in \({\mathbb {R}}^3\) that is generic for row independence is infinitesimally rigid for \(G^2\).
If \(|V| = 1\), then \(G^2\) has no edge, and every placement \(p\) is infinitesimally rigid for \(G^2\), as \(\dim \ker R(G^2, p) \le 3 \le 6\) (lemma 6.2). Let \(|V| \ge 2\), and let \(\tilde G = 5 \cdot G\).
We first show that \(\operatorname {def}(\tilde G) = 0\). The argument is that of the proof of KT Proposition 2.2 (lemma 20.14). Each of the six spanning trees has \(|V| - 1\) edges and is a forest of \(\tilde G\). They are edge-disjoint, so their union \(F\) has \(6(|V| - 1)\) edges, and \(F\) is independent in the union of six copies of the cycle matroid of \(\tilde G\) (lemma 15.8). This union is \(M(\tilde G)\) (definition 20.1). As \(\operatorname {def}(\tilde G) \ge 0\), KT eq. (2.4) gives \(\operatorname {rank} M(\tilde G) \le 6(|V| - 1)\) (theorem 20.12). So \(F\) is a base of \(M(\tilde G)\), and KT eq. (2.4) gives \(\operatorname {def}(\tilde G) = 0\).
Next we show that \(G\) has minimum degree at least two. Regard \(G\) as the multigraph of lemma 26.3. As its deficiency is \(\operatorname {def}(\tilde G) = 0\), it is a \(0\)-dof-graph (definition 20.8), with at least two vertices. So each of its vertices has degree at least two (lemma 20.23). It is simple, and its edges join exactly the adjacent pairs of \(G\), so each vertex has the same degree in \(G\). Now corollary 28.3 applies.
28.3 Every generic panel-and-hinge realization
As in section 23.1, \(d\) is the dimension, \(D = \binom {d+1}{2}\), and \(K\) is a field. A panel-and-hinge realization of a multigraph \(G = (V, E)\) is a panel-hinge framework (definition 23.5). It gives each body \(v\) a normal \(q_v \in K^{d+1}\), and the hinge of an edge with ends \(u\) and \(v\) has the supporting extensor \(C(q_u, q_v)\). So the realization parameters are the \((d+1)|V|\) coordinates of the normals. Jackson and Jordán describe the panel of \(v\) as the hyperplane \(\{ x \in {\mathbb {R}}^d : x \cdot p_v = 1\} \) for a vector \(p_v \in {\mathbb {R}}^d\) [ JJ10 , § 7 ] . Its normal is \((p_v, -1)\) (the remarks after definition 23.1).
Our main result is Jackson and Jordán’s rank formula, which Katoh and Tanigawa state for body-hinge frameworks as their Proposition 2.3 (proposition 28.42), at every generic assignment of normals to a simple graph (theorem 28.12). Here \(\tilde G = (D-1) \cdot G\), and \(\operatorname {def}(\tilde G)\) is its deficiency (definition 20.3). For a multigraph the formula can fail. At a generic assignment the two-vertex double edge has rank \(D - 1\), while the formula gives \(D\) (formalization note 23.57).
Genericity is the transfer condition of definition 24.1, applied to the forms of lemma 23.91. These forms span the rows of the rigidity matrix at each edge. Jackson and Jordán derive their Theorem 7.2 from the realization of their Theorem 6.5, whose hinges all lie in one hyperplane. They perturb it so that each hinge is the intersection of two hyperplanes, one for each end of its edge (their Lemma 7.1). These hyperplanes are the panels of a panel-and-hinge realization. We start instead from KT Theorem 5.6 (theorem 23.50). It gives a panel-hinge realization at the target rank \(D(|V|-1) - \operatorname {def}(\tilde G)\) (definition 23.21) whose panels are nonparallel, so that its hinges are nondegenerate.
Let \(G = (V, E)\) be a multigraph. A normal assignment \(q\) of \(G\) gives each body \(v\) a vector \(q_v \in K^{d+1}\), and \((G, q)\) is the panel-hinge framework with these normals. The annihilator-row family of \(q\) is the family of linear forms
on screw assignments \(S\), indexed by an edge \(e\) of \(G\), with ends \(u\) and \(v\), and a pair \((t, t')\) of indices of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Here \(y_t\) is the coordinate of \(y\) at the \(t\)-th basis vector. The assignment \(q\) is generic for row independence, and \((G, q)\) has generic normals, if every subfamily of the annihilator-row family that is linearly independent at some normal assignment is linearly independent at \(q\).
These are the forms of lemma 23.91 at the edges of \(G\). A form does not depend on the order of \(u\) and \(v\), since exchanging them changes the signs of both \(x\) and \(C\) (definition 23.1). When the hinge of \(e\) is nondegenerate, the forms at \(e\) span the same space as the rows of \(R(G, q)\) at \(e\) (lemma 23.91).
The formalization indexes the family by all the edge labels, and reads the ends of each label from an endpoint selector (formalization note 23.6), not from \(G\). Genericity is a property of a panel-hinge framework: it asks about the subfamilies indexed by edges of \(G\), with the framework’s own selector, which gives each edge of \(G\) its two ends. As a form does not depend on the order of the ends, two frameworks with the same graph and the same normals have generic normals together, whatever their selectors. The pinned lemma on abundance fixes one selector that gives each edge of \(G\) its two ends, and the one on existence assumes a body, for the endpoint choice of \(G\) (formalization note 21.11). The first pin is the family, the second genericity, and the third that genericity reads only the graph and the normals.
Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then there is a nonzero polynomial \(P\) in the \((d+1)|V|\) coordinates of a normal assignment such that every normal assignment \(q\) with \(P(q) \neq 0\) is generic for row independence. In particular, the normal assignments that are not generic lie in the zero set of a nonzero polynomial.
Fix the standard basis of the space of screw assignments. In its dual basis, each coordinate of a member of the annihilator-row family at an edge with ends \(u\) and \(v\) is \(0\) or \(\pm \) a coordinate of \(C(q_u, q_v) = *(q_u \vee q_v)\), where \(q_u \vee q_v\) is the join (definition 18.4). Its coordinates are the \(2 \times 2\) minors \(q_u(i)\, q_v(j) - q_u(j)\, q_v(i)\) (lemma 18.6). The complement isomorphism \(*\) sends each standard basis vector to \(\pm \) a standard basis vector (definition 22.5). So each coordinate of each member of the family is a polynomial of degree at most two in the coordinates of \(q\), as in the proof of lemma 23.91.
The argument of lemma 28.1 now applies. The family has finitely many indices, as \(E\) is finite. Let \(s\) be a set of indices whose members are linearly independent at some normal assignment \(q^s\). Some \(|s| \times |s|\) minor of the coordinate matrix of these members is nonzero at \(q^s\). As a polynomial \(P_s\) in the coordinates of \(q\), it is nonzero, and the members indexed by \(s\) are linearly independent at every \(q\) with \(P_s(q) \neq 0\). The product \(P\) of the polynomials \(P_s\) is nonzero, and every \(q\) with \(P(q) \neq 0\) is generic.
Let \(K\) be infinite, and let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then some normal assignment of \(G\) is generic for row independence.
The polynomial \(P\) of lemma 28.7 is nonzero. Over an infinite field a nonzero polynomial has a non-root, and every non-root of \(P\) is generic.
Let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph without loops. Let \(q\) be a normal assignment of \(G\) that is generic for row independence. Then every hinge of \((G, q)\) is nondegenerate.
Let \(e\) be an edge of \(G\), with ends \(u \neq v\). Let \(q^0\) be the normal assignment that gives \(u\) the point \((1, 0, \dots , 0)\) of the moment curve and every other body the point \((1, 1, \dots , 1)\) (lemma 23.12). These two vectors are linearly independent, so \(C^0 = C(q^0_u, q^0_v)\) is not zero (the remark after definition 23.1). Let \(t\) be an index with \(C^0_t \neq 0\). As \(d \ge 2\), the screw space has dimension \(D \ge 3\), so there is an index \(t' \neq t\). As \(u \neq v\), there is a screw assignment \(S\) for which \(S(u) - S(v)\) is the \(t'\)-th basis vector. At \(S\) the member of the annihilator-row family of \(q^0\) at \((e, t, t')\) takes the value \(C^0_t \neq 0\).
So this member alone is a linearly independent family at \(q^0\). As \(q\) is generic, the member of the family of \(q\) at \((e, t, t')\) is not zero. If \(C(q_u, q_v)\) were zero, every member of the family of \(q\) at \(e\) would be zero. So the hinge of \(e\) in \((G, q)\) is nondegenerate.
Jackson and Jordán call a panel-and-hinge realization generic if its rigidity matrix, and the submatrix of the rows of every set of edges, have the largest rank over all realizations of the graph. Their realizations have nondegenerate hinges [ JJ10 , § 7 ] . Let \(d \ge 2\), let \(G\) have no loops, and let \(q\) be generic, so that the hinges of \((G, q)\) are nondegenerate. Then for every set \(F\) of edges, the rows of \(R(G, q)\) at the edges of \(F\) have the largest rank over all normal assignments at which the hinges of these edges are nondegenerate. Indeed, at such an assignment \(q'\) the members of the annihilator-row family at \(F\) span the rows at \(F\) (lemma 23.91). So as many of these members as the rank are linearly independent at \(q'\), and hence at \(q\), where they lie in the span of the rows at \(F\). The condition on the hinges is needed. A degenerate hinge welds its two bodies together (the remarks after definition 23.5), so its edge imposes \(D\) independent linear conditions, where a nondegenerate hinge imposes \(D - 1\).
Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite, and let \((G, q)\) be a panel-hinge framework whose hinges are all nondegenerate. Then for every \(N \le \operatorname {rank} R(G, q)\), some \(N\) members of the annihilator-row family of \(q\) are linearly independent.
As the hinges are nondegenerate, the members of the family at each edge span the same space as the rows of \(R(G, q)\) at that edge (lemma 23.91). So the family spans the row space of \(R(G, q)\), which has dimension \(\operatorname {rank} R(G, q) \ge N\). Hence some \(N\) of its members are linearly independent (lemma 23.110).
The pinned lemma takes the family with any selector that gives each edge of \(G\) its two ends (formalization note 28.6), and extracts the rows at that selector by the pinned theorem of lemma 23.110, all at edges of \(G\). Their hinges are the realization’s, read with its own selector, which also gives each edge its two ends, in either order (formalization note 23.6). Where the two orders differ, the hinge of the realization is \(-C(q_u, q_v)\) (definition 23.1), and the rows it extracts differ from the members of the family by a sign. Signs do not affect linear independence. The pinned lemma asks nondegenerate hinges at the edges of \(G\) only.
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a simple graph with \(V\) finite and nonempty. Let \(q\) be a normal assignment of \(G\) that is generic for row independence. Then
As \(G\) has no loops, the hinges of \((G, q)\) are nondegenerate (lemma 28.9). So \(\operatorname {rank} R(G,q) \le D(|V|-1) - \operatorname {def}(\tilde G)\) (lemma 20.16).
For the reverse inequality, KT Theorem 5.6 (theorem 23.50) gives a panel-hinge realization \((G, q^0)\) at the target rank \(D(|V|-1) - \operatorname {def}(\tilde G)\), whose hinges are nondegenerate, as its panels are nonparallel. By lemma 28.10, some \(D(|V|-1) - \operatorname {def}(\tilde G)\) members of the annihilator-row family of \(q^0\) are linearly independent. As \(q\) is generic, the members of the family of \(q\) with the same indices are linearly independent. Each of them lies in the row space of \(R(G, q)\). Indeed, a member at an edge with ends \(u\) and \(v\) is a linear form in \(S(u) - S(v)\) that vanishes at \(C(q_u, q_v)\), and so a linear combination of the rows of \(R(G, q)\) at that edge (the remark after definition 19.5). Hence \(\operatorname {rank} R(G,q) \ge D(|V|-1) - \operatorname {def}(\tilde G)\).
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a simple graph with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every normal assignment \(q\) of \(G\) that is generic for row independence if and only if \(\operatorname {def}(\tilde G) = 0\).
Suppose first that \(\operatorname {def}(\tilde G) = 0\), and let \(q\) be generic. By theorem 28.12, \(\operatorname {rank} R(G,q) = D(|V|-1)\), so \(\dim Z(G,q) = D|V| - D(|V|-1) = D\). Hence every infinitesimal motion of \((G, q)\) is trivial (lemma 23.117, with \(W = V\)).
Conversely, suppose that \((G, q)\) is infinitesimally rigid at every generic \(q\). As \(K\) is infinite, some normal assignment \(q\) is generic (lemma 28.8). Then \((G, q)\) is infinitesimally rigid, so its motions are constant on \(V\), and \(\dim Z(G,q) = D\) (lemma 23.124, with \(W = V\)). As the screw assignments form a space of dimension \(D|V|\), \(\operatorname {rank} R(G,q) = D(|V|-1)\), and theorem 28.12 gives \(\operatorname {def}(\tilde G) = 0\).
The formalization writes \(d = k + 1\) here, as in the note after definition 23.1; the pinned theorems of theorem 28.12 and corollary 28.13 take \(d\) and the frameworks with \(k = d - 1\). They range over the panel-hinge frameworks on \(G\) with generic normals, whatever their selectors (formalization note 28.6). They assume that every body is a vertex of \(G\), and nothing of the edge labels (remark 23.40): they apply to every simple graph on the bodies, a single edge or a tree among them.
Jackson and Jordán’s Theorem 7.2 states that if \((d-1) \cdot G\) contains \(d\) edge-disjoint spanning trees, then every generic panel-and-hinge realization of the graph \(G\) is infinitesimally rigid [ JJ10 , § 7 ] . Their condition implies \(\operatorname {def}(\tilde G) = 0\). Indeed, \(\tilde G = (D-1) \cdot G\) has \(D - d = \binom {d}{2}\) further copies of each edge, and these hold \(\binom {d}{2}\) edge-disjoint copies of a spanning tree of \(G\). So \(\tilde G\) contains \(D\) edge-disjoint spanning trees, as in the proof of their Theorem 6.5, and \(\operatorname {def}(\tilde G) = 0\) by KT Proposition 2.2 (lemma 20.14). Hence corollary 28.13 contains their theorem for simple graphs, under the weaker hypothesis \(\operatorname {def}(\tilde G) = 0\), which it shows to be necessary.
28.4 Every generic body-and-bar realization
As in section 16, \(d\) is the dimension, \(D = \binom {d+1}{2}\), and the vertices and edges of a multigraph are its bodies and bars. Jackson and Jordán realize each bar \(e\) as a line segment of \({\mathbb {R}}^d\), with distinct endpoints \(p_e\) and \(p'_e\) [ JJ10 , § § 2.1 and 3 ] . A bar \(e\) that joins the bodies \(u\) and \(v\) imposes one linear condition on their screws \(S(u), S(v) \in {\mathbb {R}}^D\): the difference \(S(u) - S(v)\) is orthogonal to the vector of \(2 \times 2\) minors of the matrix with rows \((p_e, 1)\) and \((p'_e, 1)\). So their realization is a body-bar framework (definition 16.20) with this vector on each bar, while Tay’s frameworks allow any vector of \({\mathbb {R}}^D\). In this section the realization parameters are the \(2d\) coordinates of the endpoints of each bar. So “almost all realizations” refers to the choice of the endpoints, as in Jackson and Jordán’s paper.
The coordinates of this vector are polynomials in the coordinates of the endpoints. So, as for placements (section 28.1), generic choices of endpoints exist, and the choices that are not generic lie in the zero set of a nonzero polynomial. The generic form of Tay’s theorem then needs a witness. For a finite multigraph \(G\) and a set \(E'\) of bars such that \(G \restriction E'\) is \((D, D)\)-sparse, we need endpoints at which the rows of the bars in \(E'\) are linearly independent. This is Jackson and Jordán’s Lemma 5.1. We derive it from the framework of proposition 16.25 by a change of coordinates of \({\mathbb {R}}^D\), following Whiteley. Genericity then gives Tay’s theorem at every generic choice of endpoints (corollary 28.26).
We put the coordinate \(1\) of the rows first, and call the vector of minors the two-extensor of the segment.
For \(p \in {\mathbb {R}}^d\) let \(h(p) = (1, p) \in {\mathbb {R}}^{d+1}\), with coordinates indexed by \(0, 1, \dots , d\). Index the \(D\) coordinates of \({\mathbb {R}}^D\) by the pairs \((i, j)\) with \(0 \le i {\lt} j \le d\), through a fixed bijection. The two-extensor of an ordered pair of points \(p, p' \in {\mathbb {R}}^d\) is the vector \(T(p, p') \in {\mathbb {R}}^D\) with
We call the coordinates \((0, j)\) of \(T(p, p')\) its direction coordinates and the others its moment coordinates. As \(h(p)_0 = 1\), they are
polynomials of degree one and two in the \(2d\) coordinates of \(p\) and \(p'\). The vector \(T(p, p')\) is the coordinate vector of the join \(h(p) \vee h(p')\) (definition 18.4), whence its name. Its coordinates are taken in the basis of \(\bigwedge ^2 {\mathbb {R}}^{d+1}\) formed by the products of two standard basis vectors in increasing order, as in lemma 18.6. Jackson and Jordán’s vector of minors puts the coordinate \(1\) last, as definition 18.1 does. It has the same coordinates as \(T(p, p')\) up to their order, with the direction coordinates negated. Such a change of the coordinates of \({\mathbb {R}}^D\) does not change which sets of rows are linearly independent (lemma 28.23 below).
Not every vector of \({\mathbb {R}}^D\) is the two-extensor of a segment. If the direction coordinates of \(T(p, p')\) vanish, then \(p = p'\), and the moment coordinates vanish too. So the standard basis vector of \({\mathbb {R}}^D\) at a moment coordinate \((i, j)\) is the two-extensor of no pair of points. It is the coordinate vector of the product of the \(i\)-th and \(j\)-th standard basis vectors of \({\mathbb {R}}^{d+1}\), the line at infinity through the points at infinity of the \(i\)-th and \(j\)-th coordinate axes. Hence the framework of proposition 16.25, which puts standard basis vectors on the bars, does not in general come from a choice of endpoints.
The formalization calls the dimension \(n\), as in the note after definition 16.20. For the bijection of the pairs \((i, j)\) with the coordinates of \({\mathbb {R}}^D\), it takes the one that the equality of their numbers provides (pairIdxEquiv).
Let \(G\) be a multigraph, and fix an orientation of its bars (definition 16.22). An endpoint assignment \(q\) of \(G\) gives each bar \(e\) an ordered pair \((p_e, p'_e)\) of points of \({\mathbb {R}}^d\). Its endpoint realization is the body-bar framework \((G, b)\) in \({\mathbb {R}}^d\) with \(b_e = T(p_e, p'_e)\) for every bar \(e\). The assignment \(q\) is generic for row independence if every set of bars whose rows are linearly independent at the endpoint realization of some endpoint assignment has linearly independent rows at the endpoint realization of \(q\).
Reversing a bar changes only the sign of its row (section 16.4), so genericity does not depend on the orientation.
The formalization gives a pair of endpoints to every edge label, not only to the bars of \(G\): an endpoint assignment is a real function of a label, one of its two ends and a coordinate. The pairs at labels that are not bars of \(G\) do not enter the rows. The bodies and the labels are drawn from two fixed sets, which the pinned lemmas below assume finite. So the polynomial of lemma 28.20 has \(2d\) variables for each label, not only for each bar. The first pin is the endpoint realization, and the second is genericity.
Let \(G\) be a multigraph, let \(e\) be a bar of \(G\), and let \(0 \le i {\lt} j \le d\). Then there is a polynomial \(P\) in the coordinates of the endpoints of the bars of \(G\) such that \(P(q) = T(p_e, p'_e)_{(i,j)}\) for every endpoint assignment \(q\) of \(G\), where \((p_e, p'_e)\) is the pair of points that \(q\) gives \(e\).
By definition 28.15, \(T(p_e, p'_e)_{(i,j)} = h(p_e)_i\, h(p'_e)_j - h(p_e)_j\, h(p'_e)_i\). Each coordinate of \(h(p_e) = (1, p_e)\) and of \(h(p'_e)\) is \(1\) or a coordinate of \(q\). So this is a polynomial of degree at most two in the coordinates of \(q\).
Let \(G\) be a finite multigraph. Then there is a nonzero polynomial \(P\) in the \(2d\, |E(G)|\) endpoint coordinates such that every endpoint assignment \(q\) of \(G\) with \(P(q) \neq 0\) is generic for row independence. In particular, the endpoint assignments that are not generic lie in the zero set of a nonzero polynomial.
The row of a bar \(e\) has the coefficient \(-(b_e)_c\, (a_e)_v\) at a body \(v\) and a coordinate \(c\) of \({\mathbb {R}}^D\), where \(a_e\) is the signed incidence vector of \(e\) (the remarks after definition 16.22). So each coefficient is \(0\) or \(\pm (b_e)_c\). At the endpoint realization of \(q\), it is \(0\) or \(\pm \) a coordinate of \(T(p_e, p'_e)\), a polynomial in the coordinates of \(q\) (lemma 28.19).
The argument of lemma 28.1 now applies. There are finitely many sets of bars, as \(E(G)\) is finite. Let \(F\) be a set of bars whose rows are linearly independent at some endpoint assignment \(q^F\). Some \(|F| \times |F|\) minor of the coefficient matrix of these rows is nonzero at \(q^F\). As a polynomial \(P_F\) in the coordinates of \(q\), it is nonzero, and the rows of \(F\) are linearly independent at every \(q\) with \(P_F(q) \neq 0\). The product \(P\) of the polynomials \(P_F\) is nonzero, and every \(q\) with \(P(q) \neq 0\) is generic.
Let \(G\) be a finite multigraph. Then some endpoint assignment of \(G\) is generic for row independence.
The polynomial \(P\) of lemma 28.20 is nonzero. As \({\mathbb {R}}\) is infinite, \(P\) has a non-root, and every non-root of \(P\) is generic.
Each bar has one row. So if \(q\) is generic for row independence, then for every set \(F\) of bars the rows of \(F\) have at \(q\) the largest rank over all endpoint assignments. Indeed, a subset of \(F\) whose rows are linearly independent at some assignment has linearly independent rows at \(q\). Conversely, an assignment with this property is generic. Jackson and Jordán call a body-and-bar realization generic if its rigidity matrix and the submatrices formed by its rows at sets of bars have the largest rank over all realizations of the multigraph [ JJ10 , § 5 ] . Their bars have distinct endpoints. Let \(d \ge 1\), and let \(G\) be finite and without loops. Then the row of each bar is nonzero at some endpoint assignment, so a generic assignment gives every bar distinct endpoints. As a generic assignment exists (lemma 28.21), the largest ranks over their realizations are those over all endpoint assignments. So the two notions of genericity agree.
Let \(c_0 = 0\), and let \(c_1, \dots , c_d\) be the standard basis vectors of \({\mathbb {R}}^d\), the vertices of a simplex. Jackson and Jordán put the bars of each of \(D\) disjoint forests \(F_{ij}\), \(0 \le i {\lt} j \le d\), on the edge from \(c_i\) to \(c_j\). They prove that the rows of these bars are linearly independent by an elimination on the coordinates of the two-extensors of the edges. Whiteley pointed out that their lemma follows from the framework in his proof of Theorem 8 [ Whi88 ] , which is that of proposition 16.25 [ JJ10 , Remark after Lemma 5.1 ] . This framework places the bars on the edges of a projective simplex with one vertex at the origin and the others at infinity on the coordinate axes. A projective transformation, which preserves independence, takes this simplex to the one with vertices \(c_0, \dots , c_d\). We use a linear form of the argument. The two-extensors of the edges of the simplex form a basis of \({\mathbb {R}}^D\) (lemma 28.22). An invertible linear map of \({\mathbb {R}}^D\), applied to the vectors on all the bars, preserves linear independence of rows (lemma 28.23).
Let \(c_0 = 0 \in {\mathbb {R}}^d\), and for \(1 \le i \le d\) let \(c_i\) be the \(i\)-th standard basis vector of \({\mathbb {R}}^d\). Then the \(D\) two-extensors \(T(c_i, c_j)\), \(0 \le i {\lt} j \le d\), are linearly independent, and so form a basis of \({\mathbb {R}}^D\).
Let \(u_{ij}\) be the standard basis vector of \({\mathbb {R}}^D\) at \((i, j)\). By definition 28.15, \(T(c_0, c_k) = u_{0k}\) for \(1 \le k \le d\), and
Jackson and Jordán list these entries in the proof of their Lemma 5.1, with the signs of the direction coordinates reversed. So every \(u_{0k}\) is one of the two-extensors, and \(u_{hk} = T(c_h, c_k) - u_{0k} + u_{0h}\) is a linear combination of them. Hence the \(D\) two-extensors span \({\mathbb {R}}^D\), and \(D\) vectors that span \({\mathbb {R}}^D\) form a basis.
Let \((G, b)\) be a body-bar framework in \({\mathbb {R}}^d\), and let \(M\) be an invertible linear map of \({\mathbb {R}}^D\). Let \((G, Mb)\) be the framework with the vector \(M b_e\) on each bar \(e\). If the rows of a set of bars are linearly independent in \((G, b)\), then they are linearly independent in \((G, Mb)\).
Let \(M^{\top }\) be the transpose of \(M\). In \((G, Mb)\) the row of a bar \(e\) takes a motion \(m\) to
So it is the row of \(e\) in \((G, b)\), composed with the map \(\Phi \) of motions that applies \(M^{\top }\) to the vector of every body. As \(M^{\top }\) is invertible, so is \(\Phi \). Hence composition with \(\Phi \) is an injective linear map of the space of linear functionals on motions, and it preserves linear independence.
Let \(G\) be a finite multigraph, and let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((D, D)\)-sparse. Then there is an endpoint assignment of \(G\) at whose endpoint realization the rows of the bars in \(E'\) are linearly independent.
If \(E'\) is empty there is nothing to prove, so let \(E'\) be non-empty. By lemma 16.11, \(E'\) is the union of \(D\) pairwise disjoint forests. Index them by the pairs, as \(F_{ij}\) for \(0 \le i {\lt} j \le d\). Give each bar \(e\) a pair \(\iota (e)\): the pair \((i, j)\) with \(e \in F_{ij}\) if \(e \in E'\), and any pair otherwise.
Let \(b_e\) be the standard basis vector of \({\mathbb {R}}^D\) at \(\iota (e)\), as in proposition 16.25. In \((G, b)\) the rows of the bars in \(E'\) are linearly independent. Indeed, up to sign the row of \(e\) is \(a_e^{(\iota (e))}\) (section 16.4). The vectors \(a_e^{(ij)}\) with \(e \in F_{ij}\) are linearly independent over \({\mathbb {R}}\), as the sets \(F_{ij}\) are forests, by the argument of lemma 16.9.
Let \(M\) be the linear map of \({\mathbb {R}}^D\) that sends the standard basis vector at \((i, j)\) to \(T(c_i, c_j)\). It is invertible, by lemma 28.22. Let \(q\) give each bar \(e\) with \(\iota (e) = (i, j)\) the endpoints \(c_i\) and \(c_j\). Then \(M b_e = T(c_i, c_j)\) for every bar \(e\), so \((G, Mb)\) is the endpoint realization of \(q\). Its rows at the bars of \(E'\) are linearly independent, by lemma 28.23.
Let \(G\) be a finite multigraph, and let \(q\) be an endpoint assignment of \(G\) that is generic for row independence. Let \(E' \subseteq E(G)\). Then the rows of the bars in \(E'\) at the endpoint realization of \(q\) are linearly independent if and only if \(G \restriction E'\) is \((D, D)\)-sparse.
If \(G \restriction E'\) is \((D, D)\)-sparse, then the rows of \(E'\) are linearly independent at some endpoint assignment (lemma 28.24), and so at \(q\), as \(q\) is generic.
By the argument of lemma 16.26, the converse holds at every endpoint assignment. Suppose that the rows of \(E'\) are linearly independent, and let \(E''\) be a non-empty subset of \(E'\). Let \(A_{E''}\) be the span of the vectors \(a_e\) with \(e \in E''\). Up to sign, the row of a bar \(e \in E''\) is \(\sum _c (b_e)_c\, a_e^{(c)}\), which lies in \(A_{E''}^D\). This space has dimension \(D\, r(E'')\) (lemma 16.6 and lemma 16.7), and it contains the \(|E''|\) linearly independent rows of \(E''\). As \(r(E'') \le |V(E'')| - 1\), we get \(|E''| \le D|V(E'')| - D\). So \(G \restriction E'\) is \((D, D)\)-sparse.
Let \(G\) be a finite multigraph, and let \(q\) be an endpoint assignment of \(G\) that is generic for row independence. Then the endpoint realization of \(q\) is independent if and only if \(G\) is \((D, D)\)-sparse. It is isostatic, that is, independent and infinitesimally rigid, if and only if \(G\) is \((D, D)\)-tight.
Take \(E' = E(G)\) in theorem 28.25. As \(G \restriction E(G) = G\), the rows of all the bars are linearly independent, that is, the realization is independent (definition 16.24), if and only if \(G\) is \((D, D)\)-sparse. If the realization is independent, the rank of its rigidity map is \(|E(G)|\). Then it is infinitesimally rigid if and only if \(|E(G)| = D|V(G)| - D\) (definition 16.23). So it is isostatic if and only if \(G\) is \((D, D)\)-sparse with \(|E(G)| = D|V(G)| - D\), that is, \((D, D)\)-tight (definition 16.1).
So Tay’s theorem (theorem 16.27) holds at every generic endpoint assignment. So does rigidity from spanning trees. Let \(G\) be a finite multigraph that has at least one body and contains \(D\) edge-disjoint spanning trees, and let \(F\) be their union. Then \(F\) has \(D(|V(G)| - 1)\) bars. As \(F\) is a union of \(D\) forests, \(G \restriction F\) is \((D, D)\)-sparse (lemma 15.8 and theorem 16.2). By theorem 28.25, the rows of \(F\) are linearly independent at every generic endpoint assignment. So the rank of the rigidity map there is at least \(D|V(G)| - D\). It is at most \(D|V(G)| - D\) (the remarks after definition 16.22), so every generic endpoint realization of \(G\) is infinitesimally rigid.
By theorem 28.25 and theorem 16.2, a set of bars has linearly independent rows at a generic endpoint assignment if and only if it is independent in the union of \(D\) copies of the cycle matroid of \(G\). Tay proved this for his generic frameworks, in which the vectors on the bars are independent indeterminates [ Tay84 , Corollary 5.4 ] . So the rank of the rigidity map at a generic endpoint assignment is the rank of this union. For bars that are segments, Jackson and Jordán’s Theorem 5.2, which they credit to Tay, gives this rank as
where \(P\) ranges over the partitions of \(V(G)\), and \(e_G(P)\) is the number of bars that join different parts of \(P\) [ JJ10 , § 5 ] . That the rank of the union has this value is their Theorem 4.1(a), which they credit to Tutte and Nash-Williams.
28.5 Every generic body-and-hinge realization
As in section 19, \(d\) is the dimension, \(D = \binom {d+1}{2}\), and \(K\) is a field. Jackson and Jordán realize a multigraph \(G = (V, E)\) as a body-and-hinge framework by giving each edge a hinge, a \((d-2)\)-dimensional affine subspace of \({\mathbb {R}}^d\) [ JJ10 , § 3.3 ] . This is a body-hinge framework in the sense of definition 19.3. We give each hinge by \(d - 1\) points of \(K^d\) that span it (definition 28.27). So the realization parameters are the \(d(d-1)\, |E|\) coordinates of these points, and “almost all realizations” refers to the choice of the points. The coordinates of the supporting extensor of a hinge are polynomials in the coordinates of its points (lemma 28.29). So, as for normals and endpoints, the choices of hinge points that are not generic lie in the zero set of a nonzero polynomial (lemma 28.31), and over an infinite field generic choices exist.
Our main result is Jackson and Jordán’s rank formula, KT Proposition 2.3 (proposition 28.42), for every multigraph, with parallel edges and loops allowed. We prove it first at every hinge-point assignment that is generic for row independence (theorem 28.40), and then at every realization that is generic in the sense of Jackson and Jordán and of Katoh and Tanigawa, with the largest ranks over all realizations (definition 19.16, corollary 28.41). An assignment that is generic for row independence is generic in their sense (lemma 28.34). Jackson and Jordán prove the formula for every multigraph (their Theorem 6.1). Our proof starts from the realization that KT Theorem 5.6 gives for every multigraph (theorem 23.66). At deficiency zero the formula gives the theorem of Tay and Whiteley at every generic hinge-point assignment, in either sense (corollary 28.44).
For one hinge-point assignment at the target rank \(D(|V| - 1) - \operatorname {def}(\tilde G)\) we start, as for normals, from KT Theorem 5.6 for multigraphs (theorem 23.66). It gives a hinge-coplanar panel realization at the target rank, whose hinges are nonzero. The hinge of an edge with ends \(u\) and \(v\) lies in the panels of \(u\) and \(v\), so it is an extensor of \(d - 1\) vectors of the hyperplane \(n_u^\perp \) of \(K^{d+1}\), where \(n_u\) is the normal of \(u\) (lemma 28.38). If these vectors lie in the hyperplane of the vectors with last coordinate \(0\), the hinge lies at infinity. Then no points of \(K^d\) span it, as their homogeneous coordinate vectors have last coordinate \(1\) (definition 18.1). Such a hinge is the body-and-hinge counterpart of the line at infinity of section 28.4. The construction of the realization does not keep its hinges off the hyperplane at infinity, so we change coordinates. One invertible linear map of \(K^{d+1}\) moves every hinge off the hyperplane at infinity (lemma 28.37). Jackson and Jordán make a similar choice of coordinates in the proof of their Lemma 7.1, where they choose the origin off finitely many hyperplanes. The map induces an invertible linear map of the screw space, which does not change the rank of the rigidity matrix (lemma 28.35). Each moved hinge is spanned by points of \(K^d\) (lemma 28.36), and these points form a hinge-point assignment at the target rank (lemma 28.39). Jackson and Jordán construct a realization at the largest rank directly, with each hinge spanned by \(d - 1\) of the vertices \(0, e_1, \dots , e_d\) of a simplex (their Theorem 6.4). We use KT Theorem 5.6 instead, which the earlier chapters prove.
Let \(G = (V, E)\) be a multigraph. A hinge-point assignment \(q\) of \(G\) gives each edge \(e\) a family \(q_e\) of \(d - 1\) points \(q_{e,1}, \dots , q_{e,d-1}\) of \(K^d\). Its framework \((G, q)\) is the body-hinge framework whose hinge at \(e\) has the supporting extensor \(C(q_e) = C(q_{e,1}, \dots , q_{e,d-1})\) (definition 18.8). The annihilator-row family of \(q\) is the family of linear forms
on screw assignments \(S\), indexed by an edge \(e\) of \(G\), with ends \(u\) and \(v\) taken in a fixed order, and a pair \((t, t')\) of indices of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Here \(y_t\) is the coordinate of \(y\) at the \(t\)-th basis vector. The assignment \(q\) is generic for row independence if every subfamily of the annihilator-row family that is linearly independent at some hinge-point assignment is linearly independent at \(q\).
The hinge of \(e\) in \((G, q)\) is the affine span of the points of \(q_e\). It is nondegenerate if \(C(q_e) \neq 0\) (the remarks after definition 23.5). This holds exactly when the points of \(q_e\) are affinely independent (the remark after definition 18.8). The forms are those of definition 28.5, with \(C(q_e)\) in place of the panel support extensor. Exchanging the ends of \(e\) changes the signs of the forms at \(e\), so genericity does not depend on the order of the ends. As a form at \(e\) reads only the points of \(q_e\), genericity depends only on the points that \(q\) gives the edges of \(G\). When the hinge of \(e\) is nondegenerate, the forms at \(e\) span the same space as the rows of \(R(G, q)\) at \(e\), by the argument in the proof of lemma 23.91. Genericity transfers linear independence only from hinge-point assignments. So a witness with a hinge at infinity has to be moved first, as the opening of this subsection explains.
The formalization writes \(d = k + 1\), as in the note after definition 19.3. As in formalization note 28.6, it indexes the family by all the edge labels, and reads the ends of each label from an endpoint selector, not from \(G\). A hinge-point assignment gives points to every label, not only to the edges of \(G\). A body-hinge framework has no selector of its own, so genericity over \(G\) asks about the subfamilies indexed by edges of \(G\) at every selector that gives each edge of \(G\) its two ends. The first pin is the family, and the third is genericity. The second identifies the family with the annihilator rows of the framework \((G, q)\), read with the same selector, for every multigraph \(G\); it holds by definition. The fourth shows that genericity is the condition at any one such selector, as exchanging the ends of an edge changes signs only, and the fifth that it reads only the points at the edges of \(G\). The pinned lemmas on abundance and existence take \(G\) and finite sets of bodies and labels. Their polynomial has \(d(d-1)\) variables for each label, and is a product over all the selectors, finitely many. The pinned lemma on nondegeneracy concludes at the edges of \(G\) with two distinct ends, not at every label.
Let \(G = (V, E)\) be a multigraph with \(E\) finite, let \(e\) be an edge of \(G\), and let \(t\) be an index of the standard basis of \(\bigwedge ^{d-1}K^{d+1}\). Then there is a polynomial in the \(d(d-1)|E|\) coordinates of a hinge-point assignment of \(G\) whose value at every hinge-point assignment \(q\) is the coordinate \(C(q_e)_t\) of \(C(q_e)\) at the \(t\)-th basis vector.
Let \(A(q_e)\) be the \((d-1) \times (d+1)\) matrix whose \(i\)-th row is the homogeneous coordinate vector \(\bar q_{e,i} = (q_{e,i}, 1)\) (definition 18.1). As \(C(q_e)\) is the join \(\bar q_{e,1} \vee \cdots \vee \bar q_{e,d-1}\), its coordinate at \(t\) is the minor of \(A(q_e)\) on the columns of \(t\) (lemma 18.6). Each entry of \(A(q_e)\) is a coordinate of \(q\) or the constant \(1\). So the same minor of the matrix of indeterminates is a polynomial, and its value at \(q\) is the minor of \(A(q_e)\).
The pins do not use the Plücker coordinates or lemma 18.6. The pin computes the coordinate at \(t\) directly, as the pairing of the join with the dual basis vector at \(t\), which a library lemma evaluates as the minor. Its polynomial is the minor of the matrix of indeterminates (hingeExtensorPoly), with \(d(d-1)\) variables for each edge label.
Let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then there is a nonzero polynomial \(P\) in the \(d(d-1)|E|\) coordinates of a hinge-point assignment such that every hinge-point assignment \(q\) with \(P(q) \neq 0\) is generic for row independence and gives each edge \(d - 1\) affinely independent points. In particular, the hinge-point assignments that are not generic, or that give some edge affinely dependent points, lie in the zero set of a nonzero polynomial.
Fix the standard basis of the space of screw assignments. In its dual basis, each coordinate of a member of the annihilator-row family at an edge \(e\) is \(0\) or \(\pm \) a coordinate of \(C(q_e)\). So it is a polynomial in the coordinates of \(q\) (lemma 28.29).
The argument of lemma 28.1 now applies. The family has finitely many indices, as \(E\) is finite. Let \(s\) be a set of indices whose members are linearly independent at some hinge-point assignment \(q^s\). Some \(|s| \times |s|\) minor of the coordinate matrix of these members is nonzero at \(q^s\). As a polynomial \(P_s\) in the coordinates of \(q\), it is nonzero, and the members indexed by \(s\) are linearly independent at every \(q\) with \(P_s(q) \neq 0\).
For the second property, let \(q^0\) give every edge the first \(d - 1\) standard basis vectors of \(K^d\). They are linearly independent, hence affinely independent. So \(C(q^0_e) \neq 0\) for every edge \(e\) (the remark after definition 18.8). Let \(t\) be an index with \(C(q^0_e)_t \neq 0\), the same for every \(e\). Let \(R_e\) be the polynomial of lemma 28.29 whose value at \(q\) is \(C(q_e)_t\). It is nonzero, as \(R_e(q^0) \neq 0\). If \(R_e(q) \neq 0\), then \(C(q_e) \neq 0\), so the points of \(q_e\) are affinely independent.
The product \(P\) of the polynomials \(P_s\) and \(R_e\) is nonzero, as a finite product of nonzero polynomials. Every \(q\) with \(P(q) \neq 0\) has both properties.
Let \(K\) be infinite, and let \(G = (V, E)\) be a multigraph with \(V\) and \(E\) finite. Then some hinge-point assignment of \(G\) is generic for row independence and gives each edge \(d - 1\) affinely independent points.
The polynomial \(P\) of lemma 28.31 is nonzero. Over an infinite field a nonzero polynomial has a non-root, and every non-root of \(P\) is such an assignment.
Let \(d \ge 2\), and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed. Let \(q\) be a hinge-point assignment of \(G\) that is generic for row independence. Then the hinge of \((G, q)\) at every edge with two distinct ends is nondegenerate.
Let \(e\) be an edge of \(G\), with ends \(u \neq v\). Let \(q^0\) give every edge the first \(d - 1\) standard basis vectors of \(K^d\). They are linearly independent, hence affinely independent, so \(C^0 = C(q^0_e)\) is not zero (the remark after definition 18.8). Let \(t\) be an index with \(C^0_t \neq 0\). As \(d \ge 2\), the screw space has dimension \(D \ge 3\), so there is an index \(t' \neq t\). As \(u \neq v\), there is a screw assignment \(S\) for which \(S(u) - S(v)\) is the \(t'\)-th basis vector. At \(S\) the member of the annihilator-row family of \(q^0\) at \((e, t, t')\) takes the value \(C^0_t \neq 0\).
So this member alone is a linearly independent family at \(q^0\). As \(q\) is generic, the member of the family of \(q\) at \((e, t, t')\) is not zero. If \(C(q_e)\) were zero, every member of the family of \(q\) at \(e\) would be zero. So the hinge of \(e\) in \((G, q)\) is nondegenerate.
Jackson and Jordán call a realization of \(G\) generic if its rigidity matrix, and the submatrix of the rows of every set of edges, have the largest rank over all realizations of \(G\) [ JJ10 , § 6 ] . This is the genericity of definition 19.16. Each hinge of a realization is a \((d-2)\)-dimensional affine subspace, the affine span of \(d - 1\) affinely independent points. A different choice of the points does not change the hinge constraint (the remark after definition 19.3). So the realizations of \(G\) are, up to this choice, the frameworks \((G, q)\) whose hinges are nondegenerate, and definition 19.16 asks this of the hinges at the links between distinct bodies.
Let \(d \ge 2\), let \(G\) be a multigraph with \(V\) and \(E\) finite, loops allowed, and let \(q\) be a hinge-point assignment of \(G\) that is generic for row independence. Then \((G, q)\) is generic in the sense of definition 19.16. If \(K\) is infinite, some hinge-point assignment of \(G\) is generic in this sense.
By lemma 28.33, every hinge of \((G, q)\) at a link between distinct bodies is nondegenerate. Let \(F\) be a set of edges, and let \((G, q')\) be a realization. Replace the points of each degenerate hinge of \(q'\), which lies at a loop, by a fixed affinely independent family. This changes no row, as the rows of a loop are zero, and gives every hinge a nondegenerate one. The members of the annihilator-row family of the new assignment at \(F\) span the rows of its rigidity matrix at \(F\). So some of these members, as many as the rank of these rows, are linearly independent. As \(q\) is generic, the members of the family of \(q\) with the same indices are linearly independent too. They lie in the span of the rows of \(R(G, q)\) at \(F\) (the remark after definition 19.5), whose dimension is therefore at least that rank. Over all hinge-point assignments with a degenerate hinge allowed, the rows at \(F\) can have a larger rank, as a degenerate hinge welds its two bodies together (the remarks after definition 23.5); this is why the realizations are required to be nondegenerate. Over an infinite field, a hinge-point assignment generic for row independence exists (lemma 28.32), and it is generic in this sense.
We now construct a hinge-point assignment at the target rank. For \(d = 3\), part (1) of theorem 25.7 shows that a linear automorphism of the screw space, applied to every hinge, does not change the rank of the rigidity matrix. The next lemma shows this in every dimension, by comparing the rows.
Let \((G, p)\) be a body-hinge framework in \(K^d\), and let \(\Lambda \) be a linear automorphism of the screw space \(\bigwedge ^{d-1}K^{d+1}\). Let \((G, \Lambda p)\) be the body-hinge framework on \(G\) whose supporting extensor at each edge \(e\) is \(\Lambda \, C(p(e))\). Then \(\operatorname {rank} R(G, \Lambda p) = \operatorname {rank} R(G, p)\).
Let \(e\) be an edge with ends \(u\) and \(v\). The rows of \(R(G, p)\) at \(e\) span the linear forms \(S \mapsto r(S(u) - S(v))\) on screw assignments, where \(r\) ranges over the linear forms on the screw space that vanish on \(C(p(e))\) (the remark after definition 19.5). A form \(r\) vanishes on \(C(p(e))\) if and only if \(r \circ \Lambda ^{-1}\) vanishes on \(\Lambda \, C(p(e))\). So the rows of \(R(G, \Lambda p)\) at \(e\) span the forms \(S \mapsto r(\Lambda ^{-1}(S(u) - S(v)))\). These are the forms at \(e\) for \((G, p)\), composed with the map \(\Phi \colon S \mapsto \Lambda ^{-1} \circ S\) of screw assignments.
The map \(\Phi \) is linear and invertible. So composition with \(\Phi \) is an invertible linear map of the space of linear forms on screw assignments. It maps the row space of \(R(G, p)\) onto that of \(R(G, \Lambda p)\), and the two have the same dimension. In lemma 28.23 the corresponding map sends the row of each bar to the row of the same bar. Here it sends the rows at each edge onto the rows at that edge, but not each form \(C_t\, x_{t'} - C_{t'}\, x_t\) of the annihilator-row family (definition 28.27) to such a form. These forms are indexed by pairs of coordinates of the screw space, and \(\Lambda \) does not preserve the coordinates.
Let \(u_1, \dots , u_{d-1} \in K^{d+1}\), and suppose that some \(u_i\) has nonzero last coordinate. Then there are points \(p_1, \dots , p_{d-1}\) of \(K^d\) and a nonzero scalar \(c\) with
Let \(\lambda \neq 0\) be the last coordinate of \(u_i\), and replace \(u_i\) by \(\lambda ^{-1} u_i\). As the join is linear in each vector, this multiplies it by \(\lambda ^{-1}\) (the remarks after definition 18.3). Now add to each other \(u_j\) the vector \((1 - \mu _j)\, u_i\), where \(\mu _j\) is the last coordinate of \(u_j\). Adding a multiple of one vector to another does not change the join, and \(u_j\) gets the last coordinate \(1\). So every vector now has last coordinate \(1\), and is the homogeneous coordinate vector \(\bar p_j\) of a point \(p_j\) of \(K^d\) (definition 18.1). Hence \(C(p_1, \dots , p_{d-1}) = \bar p_1 \vee \cdots \vee \bar p_{d-1}\) is \(\lambda ^{-1} (u_1 \vee \cdots \vee u_{d-1})\) (definition 18.8).
Let \(K\) be infinite, and let \(w_1, \dots , w_m\) be nonzero vectors of \(K^{d+1}\). Then there is an invertible linear map \(g\) of \(K^{d+1}\) such that every \(g(w_i)\) has nonzero last coordinate.
For each \(i\) the linear form \(x \mapsto w_i \cdot x\) is nonzero, as \(w_i \neq 0\). So the product of these forms is a nonzero polynomial in the coordinates of \(x\). As \(K\) is infinite, it has a non-root \(n\), and \(w_i \cdot n \neq 0\) for every \(i\). Let \(\varphi \) be the linear form \(x \mapsto n \cdot x\), and let \(\psi \) be the last coordinate. Both are nonzero, so their kernels have dimension \(d\). Extending a linear isomorphism of \(\ker \varphi \) onto \(\ker \psi \), we obtain an invertible linear map \(g\) of \(K^{d+1}\) with \(g(\ker \varphi ) = \ker \psi \). If \(g(w_i)\) had last coordinate \(0\), then \(g(w_i) \in \ker \psi \), so \(w_i \in \ker \varphi \), which is false.
Let \(d \ge 2\) and let \(C \neq 0\) be an extensor that lies in the panel with normal \(n\) (definition 23.24). Then \(C = x_1 \vee \cdots \vee x_{d-1}\) for some vectors \(x_1, \dots , x_{d-1}\) of \(K^{d+1}\), with \(x_1 \neq 0\).
By definition, \(C = x_1 \vee \cdots \vee x_{d-1}\) for some vectors of \(n^\perp \). As \(C \neq 0\), the vectors are linearly independent (the remark after definition 18.3), so \(x_1 \neq 0\).
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then there is a hinge-point assignment \(q\) of \(G\) at which some \(D(|V|-1) - \operatorname {def}(\tilde G)\) members of the annihilator-row family of \(q\) are linearly independent.
Let \(N = D(|V|-1) - \operatorname {def}(\tilde G)\). By KT Theorem 5.6 for multigraphs (theorem 23.66), \(G\) has a hinge-coplanar panel realization \((G, p)\) at the target rank \(N\). Its hinge \(C_e\) at every edge \(e\) is nonzero and lies in a panel, so \(C_e = w_{e,1} \vee \cdots \vee w_{e,d-1}\) for some vectors \(w_{e,i}\) of \(K^{d+1}\) with \(w_{e,1} \neq 0\) (lemma 28.38).
By lemma 28.37, there is an invertible linear map \(g\) of \(K^{d+1}\) such that \(g(w_{e,1})\) has nonzero last coordinate for every edge \(e\). Let \(\Lambda = \Lambda _g\) be the screw map of \(g\) (definition 25.5), a linear automorphism of the screw space. The hinge of \((G, \Lambda p)\) at \(e\) is \(g w_{e,1} \vee \cdots \vee g w_{e,d-1}\). The rigidity matrix of \((G, \Lambda p)\) has rank \(N\) (lemma 28.35), and its hinges are nondegenerate, as \(\Lambda \) is injective. By lemma 28.36, there are points \(q_{e,1}, \dots , q_{e,d-1}\) of \(K^d\) and a scalar \(c_e \neq 0\) with \(C(q_e) = c_e\, \Lambda \, C_e\). Let \(q\) be the hinge-point assignment that gives each edge \(e\) the points \(q_e\).
At each edge \(e\) of \((G, \Lambda p)\), consider the forms \(S \mapsto C_t\, x_{t'} - C_{t'}\, x_t\) of definition 28.27, with \(C = \Lambda \, C_e\). As the hinge is nondegenerate, they span the same space as the rows of \(R(G, \Lambda p)\) at \(e\) (the argument in the proof of lemma 23.91). So these forms, at all the edges, span the row space of \(R(G, \Lambda p)\), of dimension \(N\), and some \(N\) of them are linearly independent (lemma 23.110). The member of the annihilator-row family of \(q\) at an index \((e, t, t')\) is \(c_e\) times the form at \((e, t, t')\), as \(C(q_e) = c_e\, \Lambda \, C_e\). Multiplying the members of a family by nonzero scalars does not affect their linear independence. So the members of the family of \(q\) at these \(N\) indices are linearly independent.
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Let \(q\) be a hinge-point assignment of \(G\) that is generic for row independence. Then
The hinges of \((G, q)\) at the edges with distinct ends are nondegenerate (lemma 28.33), and lemma 20.16 asks nothing of a loop. So \(\operatorname {rank} R(G,q) \le D(|V|-1) - \operatorname {def}(\tilde G)\) (lemma 20.16).
For the reverse inequality, let \(q^0\) be a hinge-point assignment at which some \(D(|V|-1) - \operatorname {def}(\tilde G)\) members of the annihilator-row family are linearly independent (lemma 28.39). As \(q\) is generic, the members of the family of \(q\) with the same indices are linearly independent. Each of them lies in the row space of \(R(G, q)\). Indeed, a member at an edge \(e\) with ends \(u\) and \(v\) is a linear form in \(S(u) - S(v)\) that vanishes at \(C(q_e)\), and so a linear combination of the rows of \(R(G, q)\) at \(e\) (the remark after definition 19.5). Hence \(\operatorname {rank} R(G,q) \ge D(|V|-1) - \operatorname {def}(\tilde G)\).
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Let \(q\) be a hinge-point assignment of \(G\) that is generic in the sense of definition 19.16. Then \(\operatorname {rank} R(G,q) = D(|V|-1) - \operatorname {def}(\tilde G)\). So \((G,q)\) has \(\operatorname {def}(\tilde G)\) degrees of freedom.
Some \(q_0\) is generic for row independence (lemma 28.32), so by theorem 28.40, \(\operatorname {rank} R(G,q_0) = D(|V|-1) - \operatorname {def}(\tilde G)\). The hinges of \(q_0\) at the links between distinct bodies are nondegenerate, so \(q_0\) is a realization (lemma 28.33). As \(q\) is generic in the sense of definition 19.16, the rank of \(R(G,q)\) is at least that of \(R(G,q_0)\). It is at most \(D(|V|-1) - \operatorname {def}(\tilde G)\) by lemma 20.16, as the hinges of \(q\) at the links between distinct bodies are nondegenerate.
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Let \(q\) be a hinge-point assignment of \(G\) that is generic in the sense of definition 19.16, and let \(c\) be an integer. Then the following are equivalent, as Katoh and Tanigawa state [ KT11 , p. 655 ] , crediting Jackson and Jordán [ JJ10 ] :
\(\operatorname {rank} R(G,q) = D(|V|-1) - c\);
\(\operatorname {def}(\tilde G) = c\);
\(\operatorname {rank} M(\tilde G) = D(|V|-1) - c\).
The same holds at every \(q\) that is generic for row independence (definition 28.27), the form the rest of the development uses.
By corollary 28.41, \(\operatorname {rank} R(G,q) = D(|V|-1) - \operatorname {def}(\tilde G)\), which is (i) \(\Leftrightarrow \) (ii). By theorem 20.12, \(\operatorname {rank} M(\tilde G) = D(|V|-1) - \operatorname {def}(\tilde G)\), which is (ii) \(\Leftrightarrow \) (iii). A \(q\) that is generic for row independence is generic in this sense (lemma 28.34), and theorem 28.40 gives the formula there directly.
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every hinge-point assignment \(q\) of \(G\) that is generic in the sense of definition 19.16 if and only if \(\operatorname {def}(\tilde G) = 0\). The same holds with the assignments that are generic for row independence (definition 28.27) in place of these.
Suppose first that \(\operatorname {def}(\tilde G) = 0\), and let \(q\) be generic in the sense of definition 19.16. By corollary 28.41, \(\operatorname {rank} R(G,q) = D(|V|-1)\), so \(\dim Z(G,q) = D|V| - D(|V|-1) = D\). Hence every infinitesimal motion of \((G, q)\) is trivial (lemma 23.117, with \(W = V\)).
Conversely, suppose that \((G, q)\) is infinitesimally rigid at every such \(q\). As \(K\) is infinite, some hinge-point assignment \(q\) is generic in this sense (lemma 28.34). Then \((G, q)\) is infinitesimally rigid, so its motions are constant on \(V\), and \(\dim Z(G,q) = D\) (lemma 23.124, with \(W = V\)). As the screw assignments form a space of dimension \(D|V|\), \(\operatorname {rank} R(G,q) = D(|V|-1)\), and corollary 28.41 gives \(\operatorname {def}(\tilde G) = 0\).
At the assignments that are generic for row independence the argument is the same, with theorem 28.40 in place of corollary 28.41, and with an assignment that is generic for row independence, which exists as \(K\) is infinite (lemma 28.32).
Let \(d \ge 2\), let \(K\) be an infinite field, and let \(G = (V, E)\) be a multigraph, with parallel edges and loops allowed, with \(V\) finite and nonempty. Then \((G, q)\) is infinitesimally rigid at every hinge-point assignment \(q\) of \(G\) that is generic in the sense of definition 19.16 if and only if \(\tilde G = (D-1) \cdot G\) contains \(D\) edge-disjoint spanning trees. The same holds with the assignments that are generic for row independence (definition 28.27) in place of these.
By corollary 28.43, the condition on the generic hinge-point assignments, in either sense, holds if and only if \(\operatorname {def}(\tilde G) = 0\). As \(D \ge 3\), KT Proposition 2.2 (lemma 20.14) shows that this holds if and only if \(\tilde G\) contains \(D\) edge-disjoint spanning trees.
The formalization states proposition 28.42, corollary 28.43 and corollary 28.44 twice: first at the assignments that are generic in the sense of definition 19.16, Katoh and Tanigawa’s, then at those that are generic for row independence. The proposition’s second form follows from its first (lemma 28.34). It writes \(d = k + 1\), as in the note after definition 19.3. The pinned results of this subsection from lemma 28.39 on take the dimension in \(\operatorname {def}(\tilde G)\) as a separate parameter, as in the note after definition 23.1. They assume that every body is a vertex of \(G\), and state rigidity on \(V(G)\), which is then the set of all bodies. They assume nothing of the edge labels (remark 23.40): they apply to every multigraph on the bodies, a single edge, a tree or a double edge among them. The pinned witness lemma takes a selector that gives each edge of \(G\) its two ends. The rank formula and its corollaries take none, as genericity over \(G\) asks about every such selector (the note after definition 28.27).
Tay [ Tay89 , § 7 ] and Whiteley [ Whi88 , Theorem 10 ] characterized, independently, the multigraphs \(G\) that have an infinitesimally rigid body-and-hinge realization in \({\mathbb {R}}^d\): those for which \((D-1) \cdot G\) contains \(D\) edge-disjoint spanning trees. Jackson and Jordán state this as their Corollary 6.3, a consequence of their Theorem 6.1 [ JJ10 , § 6 ] . The body-hinge chapter proves the characterization in its existence form, for frameworks given by bundles of bars (theorem 17.5). Corollary 28.44 is its generic form for frameworks whose hinges are spanned by points, for multigraphs.