19 The panel-hinge rigidity matrix \(R(G,p)\)
This chapter defines the rigidity matrix \(R(G,p)\) of a body-hinge framework \((G,p)\), following Katoh and Tanigawa [ KT11 , § § 2.2–2.4 ] , and proves the lemmas on its rank that their proof of the molecular conjecture uses. In section 17 a hinge was replaced by \(D - 1\) bars, where \(D = \binom {d+1}{2}\), and the rigidity of a body-hinge framework on \(G\) was that of the resulting body-bar framework on \(\tilde G = (D-1)\cdot G\). Here each edge \(e\) has a hinge \(p(e)\), an affine subspace of dimension \(d - 2\), and the hinge constrains the screw centers of the two bodies of \(e\) through its extensor (section 18.2). As in section 18, we work over an arbitrary field \(K\).
Section 19.1 defines \(R(G,p)\) and the space \(Z(G,p)\) of infinitesimal motions, and shows that \(\operatorname {rank} R(G,p) \le D(|V|-1)\). The next chapter defines the deficiency \(\operatorname {def}(\tilde G)\) and sharpens the bound to \(\operatorname {rank} R(G,p) \le D(|V|-1) - \operatorname {def}(\tilde G)\) at every realization (section 20.3). Equality holds at a generic realization. This rank formula is Jackson and Jordán’s [ JJ10 , Theorem 6.1 ] , which Katoh and Tanigawa state as their Proposition 2.3. We prove it in a conditional form, from a bound on the space of motions, in the chapter on the algebraic induction (proposition 23.19), and at every generic hinge-point assignment of a multigraph in a later chapter (theorem 28.40, proposition 28.42). By the theorem of Tutte and Nash-Williams [ Tut61 , NW61 ] , \(\operatorname {def}(\tilde G) = 0\) exactly when \(\tilde G\) contains \(D\) edge-disjoint spanning trees [ KT11 , p. 655 ] . So the formula implies Tay and Whiteley’s theorem in the form that KT Proposition 1.1 states (section 17.2).
Section 19.2 proves KT Lemmas 5.1–5.3 on the rank of \(R(G,p)\). Section 19.3 proves the rank-addition lemmas that the algebraic induction (section 23) and the induction of the pencil chapters (section 30) apply when they split a graph into smaller ones.
19.1 Body-hinge frameworks and the rigidity matrix
This subsection defines the rigidity matrix of a body-hinge framework, following Katoh and Tanigawa [ KT11 , § § 2.2–2.4 ] . They identify an infinitesimal motion of a rigid body in \({\mathbb {R}}^d\) with a vector of \({\mathbb {R}}^D\), its screw center, where \(D = \binom {d+1}{2}\). A hinge joining two bodies constrains the difference of their screw centers to the span of a \((d-1)\)-extensor supporting the hinge. We take this constraint as the definition, over a field \(K\). Screw centers lie in the following space, as do the supporting extensors of definition 18.8.
The screw space is \(\bigwedge ^{d-1}K^{d+1}\). It has dimension \(\binom {d+1}{d-1} = D\), where \(D = \binom {d+1}{2}\).
The dimension is written \(d = k + 1\), so that the screw space is \(\bigwedge ^k K^{k+2}\). The pins are the screw space, the number \(D\) and the dimension of the screw space.
A body-hinge framework \((G,p)\) in \(K^d\) is a multigraph \(G = (V,E)\) together with a map \(p\) that assigns to each edge \(e\) a \((d-2)\)-dimensional affine subspace \(p(e)\) of \(K^d\), the hinge of \(e\). Let \(C(p(e)) \in \bigwedge ^{d-1}K^{d+1}\) be a \((d-1)\)-extensor supporting \(p(e)\) (definition 18.8). A screw assignment is a map \(S\) from \(V\) to the screw space \(\bigwedge ^{d-1}K^{d+1}\). It satisfies the hinge constraint at an edge \(e\) with ends \(u\) and \(v\) if
The hinge \(p(e)\) is spanned by \(d - 1\) affinely independent points, so \(C(p(e)) \neq 0\), and \(p(e)\) determines \(C(p(e))\) up to a nonzero scalar (the remark after definition 18.8). So the hinge constraint does not depend on the choice of \(C(p(e))\). It is symmetric in \(u\) and \(v\), since \(S(v) - S(u) = -(S(u) - S(v))\).
The formalization records a body-hinge framework by its multigraph and, for each edge \(e\), an element \(C(e)\) of the screw space in place of \(C(p(e))\). It does not require \(C(e)\) to be nonzero or to come from points, so the same definitions apply to hinges given as the meet of two panels (definition 23.5). A lemma that needs \(C(e) \neq 0\) assumes it. Screw assignments are defined on a fixed set of bodies, which may contain bodies that lie on no edge of \(G\) (section 19.3).
Katoh and Tanigawa write the hinge constraint as linear equations [ KT11 , § 2.4 ] . For this we identify \(\bigwedge ^{d-1}K^{d+1}\) with \(K^D\) by the basis of the products \(e_{i_1} \wedge \cdots \wedge e_{i_{d-1}}\) with \(i_1 {\lt} \cdots {\lt} i_{d-1}\) (lemma 18.6), and write \(x \cdot y\) for the dot product of \(K^D\).
Let \((G,p)\) be a body-hinge framework and let \(e\) be an edge of \(G\). Let \(r_1(p(e)), \dots , r_{D-1}(p(e))\) be a basis of the orthogonal complement of \(\operatorname {span} C(p(e))\) in \(K^D\), and let \(r(p(e))\) be the \((D-1) \times D\) matrix with these rows. Then a screw assignment \(S\) satisfies the hinge constraint at \(e\), with ends \(u\) and \(v\), if and only if
The orthogonal complement has dimension \(D - 1\) because \(C(p(e)) \neq 0\). The equivalence holds because a subspace of \(K^D\) is the orthogonal complement of its orthogonal complement, as the dot product is nondegenerate. Through the dot product, the rows of \(r(p(e))\) form a basis of the linear forms on \(K^D\) that vanish on \(\operatorname {span} C(p(e))\). A linear form vanishes on \(\operatorname {span} C(p(e))\) if and only if it vanishes at \(C(p(e))\), as the span consists of the multiples of \(C(p(e))\); we then say that it vanishes on \(C(p(e))\).
The first pin is the space of linear forms on the screw space that vanish on \(\operatorname {span} C(p(e))\), with no basis chosen, and the second is the equivalence. The third gives this space the dimension \(D - 1\) when \(C(p(e)) \neq 0\), and the fourth says that a form lies in it if and only if it vanishes at \(C(p(e))\).
The rigidity matrix collects these equations for all the edges.
Let \((G,p)\) be a body-hinge framework. Its rigidity matrix \(R(G,p)\) is the \((D-1)|E| \times D|V|\) matrix with a block of \(D - 1\) rows for each edge and a block of \(D\) columns for each body. Orient each edge \(e\) from one end \(u\) to the other end \(v\). The rows of \(e\) have \(r(p(e))\) in the columns of \(u\), \(-r(p(e))\) in the columns of \(v\), and zeros elsewhere (definition 19.5). An infinitesimal motion of \((G,p)\) is a screw assignment that satisfies the hinge constraint at every edge, that is, a vector of \(\ker R(G,p) \subseteq K^{D|V|}\). We write \(Z(G,p)\) for the space of infinitesimal motions.
The space \(Z(G,p)\) depends neither on the choice of the rows of the matrices \(r(p(e))\) nor on the orientation of the edges [ KT11 , p. 654 ] . So neither does the rank of \(R(G,p)\), which is
The formalization fixes no basis of the screw space. A row of \(R(G,p)\) is the linear form \(S \mapsto r(S(u) - S(v))\) on screw assignments, for an edge \(e\) with ends \(u\) and \(v\) and a linear form \(r\) on the screw space that vanishes on \(C(p(e))\). The rank of \(R(G,p)\) is the dimension of the span of these forms, and \(Z(G,p)\) is the space on which they all vanish. The first two pins are the infinitesimal motions and \(Z(G,p)\), the next two the rows of \(R(G,p)\), and the last the description of \(Z(G,p)\) by the rows.
We record three facts about the rows of \(R(G,p)\). First, the rows of an edge with distinct ends are linearly independent.
Let \((G,p)\) be a body-hinge framework, let \(u \neq v\) be bodies, and let \(r_1, \dots , r_n \in K^D\) be linearly independent. Then the linear forms \(S \mapsto r_i \cdot (S(u) - S(v))\) on screw assignments are linearly independent. In particular, if \(e\) is an edge with ends \(u\) and \(v\) and \(C(p(e)) \neq 0\), then the \(D - 1\) rows of \(e\) are linearly independent.
The map \(S \mapsto S(u) - S(v)\) takes the screw assignments onto \(K^D\), as \(u \neq v\). So a linear relation among the forms gives the same relation among the \(r_i\), and its coefficients are zero. If \(C(p(e)) \neq 0\), the rows of \(e\) are the forms for \(r_i = r_i(p(e))\), \(1 \le i \le D - 1\), which are linearly independent (definition 19.5).
The first pin is the claim for linear forms, and the second its form for rows.
Second, the rows of several edges are jointly independent when each of the edges has an end of its own.
Let \((G,p)\) be a body-hinge framework. Let \(u_1, \dots , u_m\) be distinct bodies, and let \(w_1, \dots , w_m\) be bodies none of which is equal to any \(u_j\). For each \(j\), let \(r_{j,1}, \dots , r_{j,n_j} \in K^D\) be linearly independent. Then the linear forms \(S \mapsto r_{j,i} \cdot (S(u_j) - S(w_j))\) on screw assignments are linearly independent. In particular, if \(e_j\) is an edge with ends \(u_j\) and \(w_j\) and \(C(p(e_j)) \neq 0\) for each \(j\), then the \((D-1)m\) rows of \(e_1, \dots , e_m\) are linearly independent.
Take a linear combination of the forms that vanishes, and evaluate it at the screw assignment with value \(x\) at \(u_j\) and \(0\) elsewhere. A form of index \(j' \neq j\) vanishes there, as \(u_{j'} \neq u_j\) and \(w_{j'} \neq u_j\). So the coefficients \(c_i\) of the forms of index \(j\) give \(\sum _i c_i\, r_{j,i} \cdot x = 0\) for every \(x \in K^D\), and every \(c_i\) is zero, as the \(r_{j,i}\) are linearly independent. If \(C(p(e_j)) \neq 0\), the rows of \(e_j\) are the forms for \(r_{j,i} = r_i(p(e_j))\), \(1 \le i \le D - 1\), which are linearly independent (definition 19.5).
For example, the edges of a star at a body \(w\) satisfy the hypothesis if their other ends are distinct bodies other than \(w\).
The first pin is the claim for linear forms, the second its form for rows, and the third the case of a star.
Third, the rows of the edges of a forest are jointly independent. A forest need not satisfy the hypothesis of lemma 19.11: in a path with three edges, each end of the middle edge is also an end of another edge.
Let \((G,p)\) be a body-hinge framework, and let \(T\) be a forest with finitely many edges that is a subgraph of \(G\), with \(C(p(e)) \neq 0\) at each edge \(e\) of \(T\). Then \(R(G,p)\) has \((D-1)|E(T)|\) linearly independent rows.
We show that the rows of the edges of \(T\) are linearly independent, by induction on the number of edges of \(T\); there is nothing to prove when \(T\) has none. Otherwise \(T\) has a pendant edge \(e\): an edge with distinct ends \(x\) and \(y\), where \(x\) is an end of no other edge of \(T\) (the first edge of a longest path, say). Deleting \(e\) leaves a forest \(T - e\), whose rows are linearly independent by induction. Each of them is a form \(S \mapsto r \cdot (S(u) - S(w))\) for an edge of \(T - e\) with ends \(u\) and \(w\), neither of which is \(x\), so it vanishes on the screw assignments that vanish off \(x\). On such an assignment, with value \(s\) at \(x\), the \(D - 1\) rows of \(e\) take the values \(r_i(p(e)) \cdot s\), and these forms in \(s\) are linearly independent (definition 19.5). So the rows of \(e\) and those of \(T - e\) are linearly independent together (lemma 23.127), and they are the rows of \(T\).
The pin asks the set of edge labels to be finite, so that every forest in \(G\) has finitely many edges.
The next definitions are Katoh and Tanigawa’s [ KT11 , § § 2.3–2.4 ] , who take that of a generic framework from Jackson and Jordán [ JJ10 , § 6 ] . A body-hinge framework on \(G\) is also called a realization of \(G\).
Let \((G,p)\) be a body-hinge framework. A screw assignment \(S\) is trivial if \(S(u) = S(v)\) for all bodies \(u\) and \(v\), and the trivial screw assignments form the space of trivial motions. The framework \((G,p)\) is infinitesimally rigid if all its infinitesimal motions are trivial.
Katoh and Tanigawa call an infinitesimal motion trivial under the same condition [ KT11 , § 2.3 ] . By lemma 19.18 below, every trivial screw assignment is an infinitesimal motion.
Let \((G,p)\) be a body-hinge framework. The degree of freedom of \((G,p)\) is \(D(|V|-1) - \operatorname {rank} R(G,p)\). The framework \((G,p)\) is generic if \(R(G,p)\) and each of its edge-induced submatrices (the rows of the edges of a subset of \(E\)) have the largest rank over all realizations of \(G\).
The formalization writes \(d = k + 1\), as in the note after definition 19.3. The degree of freedom is formalized as stated, in the integers, with \(V\) the vertex set of \(G\); the screw assignments are defined on all the bodies, and the rows of \(R(G,p)\) involve only those of \(V(G)\). It is \(0\) exactly when \((G,p)\) is infinitesimally rigid on \(V(G)\), for \(V(G)\) nonempty (the second pin). Genericity is formalized for the frameworks whose hinges are spanned by points (the hinge-point assignments \(q\) of definition 28.27), as IsMaxRankHingePoints. The realizations of \(G\) compared with \(q\) are the hinge-point assignments whose hinge at every link between distinct bodies is nondegenerate, and \(q\) itself must have this property. Nondegeneracy is not asked at a loop, whose hinge constrains no motion, so a framework with a degenerate hinge at a loop counts as generic, where Katoh and Tanigawa’s multigraphs have no loops. The cheapest witness is a single loop, where every assignment is generic. Allowing degenerate hinges at the links between distinct bodies would not match the source, as a degenerate hinge welds its two bodies. Every assignment that is generic for row independence is generic in this sense, so one exists over an infinite field, and each has \(\operatorname {def}(\tilde G)\) degrees of freedom (lemma 28.34, corollary 28.41).
By the next lemma, the trivial motions form a \(D\)-dimensional subspace of \(Z(G,p)\) when \(V\) is nonempty. So the degree of freedom is \(\dim Z(G,p) - D \ge 0\), and it is \(0\) if and only if \((G,p)\) is infinitesimally rigid.
Let \((G,p)\) be a body-hinge framework with \(V\) nonempty, and for \(1 \le i \le D\) let \(S^*_i\) be the screw assignment whose value at every body is the \(i\)-th basis vector of \(K^D\). Then \(S^*_1, \dots , S^*_D\) are infinitesimal motions, and they form a basis of the space of trivial motions. Hence \(\operatorname {rank} R(G,p) \le D(|V|-1)\), with equality if and only if \((G,p)\) is infinitesimally rigid.
A constant screw assignment \(S\) has \(S(u) - S(v) = 0\) at every edge, so it is an infinitesimal motion. The trivial motions are the constant assignments (definition 19.15). Hence they form a subspace of \(Z(G,p)\) (trivialMotions_le_infinitesimalMotions). As \(V\) is nonempty, sending \(x \in K^D\) to the constant assignment with value \(x\) is an isomorphism from \(K^D\) onto them (trivialMotions_eq_range_const), and it sends the standard basis to \(S^*_1, \dots , S^*_D\). So the trivial motions form a \(D\)-dimensional subspace of \(Z(G,p)\). The screw assignments form a space of dimension \(D|V|\) (finrank_screwAssignment), so \(\operatorname {rank} R(G,p) = D|V| - \dim Z(G,p) \le D(|V|-1)\). Equality holds if and only if \(Z(G,p)\) is the space of trivial motions, that is, if and only if \((G,p)\) is infinitesimally rigid.
The first pin says that the trivial screw assignments are infinitesimal motions, the second that they form a space of dimension \(D\), and the third that \(Z(G,p)\) is this space exactly when \((G,p)\) is infinitesimally rigid. The fourth states the equality case for the dimension of \(Z(G,p)\), which is \(D|V| - \operatorname {rank} R(G,p)\): \(\dim Z(G,p) = D\) exactly when \((G,p)\) is infinitesimally rigid.
19.2 Rank lemmas
This subsection proves two rank lemmas of Katoh and Tanigawa [ KT11 , § 5 ] , and compares two frameworks on one graph. Deleting the columns of one body does not change the rank of \(R(G,p)\) (KT Lemma 5.1). Two edges between the same two bodies, with linearly independent supporting extensors, force the two bodies to have the same screw center in every infinitesimal motion (KT Lemma 5.3). The last lemma says that if every hinge of one framework has a supporting extensor in the span of the other’s, then every infinitesimal motion of the first is one of the second. Katoh and Tanigawa’s remaining lemma of their §5, KT Lemma 5.2, rotates a panel without decreasing the rank; the formalization takes its steps with the realizations of the algebraic induction (the passage before lemma 23.78).
Let \((G,p)\) be a body-hinge framework, let \(v\) be a body, and let \(\operatorname {pinned}(v) = \{ S \in Z(G,p) : S(v) = 0\} \). Then \(Z(G,p)\) is the direct sum of the space of trivial motions and \(\operatorname {pinned}(v)\), so \(\dim \operatorname {pinned}(v) + D = \dim Z(G,p)\). Equivalently, deleting the \(D\) columns of \(v\) from \(R(G,p)\) does not change its rank.
A trivial motion that vanishes at \(v\) vanishes everywhere. An infinitesimal motion \(S\) is the sum of the trivial motion with value \(S(v)\) and the screw assignment \(u \mapsto S(u) - S(v)\), which vanishes at \(v\). The latter is again an infinitesimal motion, since it has the same differences \(S(u) - S(w)\) as \(S\). So \(Z(G,p)\) is the direct sum, and the trivial motions have dimension \(D\) (lemma 19.18).
Deleting the columns of \(v\) leaves the matrix whose null space consists of the restrictions to \(V \setminus \{ v\} \) of the motions in \(\operatorname {pinned}(v)\). Its rank is therefore \(D(|V|-1) - \dim \operatorname {pinned}(v) = D|V| - \dim Z(G,p)\), the rank of \(R(G,p)\).
Katoh and Tanigawa prove the lemma by adding to \(R(G,p)\) the \(D\) rows that tie down the body \(v\) [ KT11 , p. 668 ] . They cite White and Whiteley [ WW87 , § 2 ] for the fact that fixing one body does not change the space of nontrivial motions. The direct sum above expresses that fact.
Let \((G,p)\) be a body-hinge framework, and let \(e\) and \(f\) be edges of \(G\) that both join the bodies \(u \neq v\), with \(C(p(e))\) and \(C(p(f))\) linearly independent. Then every screw assignment \(S\) that satisfies the hinge constraints at \(e\) and \(f\) has \(S(u) = S(v)\). Equivalently, the rows of \(R(G,p)\) at \(e\) and \(f\), restricted to the \(D\) columns of \(v\), have rank \(D\).
The difference \(S(u) - S(v)\) lies in \(\operatorname {span} C(p(e)) \cap \operatorname {span} C(p(f))\) (definition 19.3). Two lines spanned by linearly independent vectors meet only in \(0\), so \(S(u) = S(v)\). In the columns of \(v\), the rows at \(e\) and \(f\) are \(\pm r(p(e))\) and \(\pm r(p(f))\). Their common null space in \(K^D\) is the same intersection (definition 19.5), so they have rank \(D\).
Katoh and Tanigawa state the lemma for the graph with the two bodies \(u\) and \(v\) and the two edges \(e\) and \(f\), with distinct hinges \(p(e) \neq p(f)\), and their proof shows that distinct hinges satisfy the hypothesis above [ KT11 , p. 670 ] . By the remark after definition 18.8, \(C(p(e))\) is nonzero, it is determined by \(p(e)\) up to a nonzero scalar, and it determines \(p(e)\). So \(C(p(e))\) and \(C(p(f))\) are proportional only if \(p(e) = p(f)\), and two nonzero vectors that are not proportional are linearly independent. For example, two hinges spanned by \(d - 1\) of \(d + 1\) affinely independent points, omitting different pairs of them, have linearly independent extensors by KT Lemma 2.1 (lemma 18.9). Distinct hinges can lie in a common hyperplane, so the two-body graph has an infinitesimally rigid panel-hinge realization. This graph is the base case of the algebraic induction (lemma 23.30).
Let \((G,p)\) and \((G,p')\) be body-hinge frameworks on the same multigraph \(G\), and suppose that \(\operatorname {span} C(p'(e)) \subseteq \operatorname {span} C(p(e))\) at every edge \(e\). Then \(Z(G,p') \subseteq Z(G,p)\). In particular, \(\dim Z(G,p') \le \dim Z(G,p)\) and \(\operatorname {rank} R(G,p) \le \operatorname {rank} R(G,p')\).
Let \(S \in Z(G,p')\), and let \(e\) be an edge with ends \(u\) and \(v\). Then \(S(u) - S(v)\) lies in \(\operatorname {span} C(p'(e))\) (definition 19.3), hence in \(\operatorname {span} C(p(e))\), so \(S\) satisfies the hinge constraint of \((G,p)\) at \(e\). So \(Z(G,p') \subseteq Z(G,p)\), and \(\dim Z(G,p') \le \dim Z(G,p)\). The rank of \(R(G,p)\) is \(D|V| - \dim Z(G,p)\) (the remark after definition 19.7), and likewise for \(p'\), which gives the bound on the ranks.
The first pin is the inclusion, and the second the bound on the dimensions, for a finite set of bodies; the bound on the ranks follows by the remark after definition 19.7. Both pins assume the inclusion of spans at every edge label, also outside \(E(G)\). The formalization lets \(C(p(e))\) be zero (the note after definition 19.3), so the inclusion can be strict, at an edge with \(C(p'(e)) = 0 \neq C(p(e))\). When all the extensors are nonzero, the hypothesis says that the spans are equal, and then \(Z(G,p') = Z(G,p)\).
19.3 Rank-addition lemmas
This subsection computes or bounds the rank of \(R(G,p)\) from the ranks of pieces of \(G\). In the first lemmas the pieces share at most two bodies. If two sides are joined by at most one edge, the rank of the whole is at least the sum of their ranks plus \(D - 1\) for the joining edge; this is the rank step in the proof of KT Lemma 6.1. If two sides share one body, their ranks add. If they share two bodies \(u\) and \(v\), the rank of the whole is the sum of the ranks of the sides minus a correction, which depends on the motions of \(v\) relative to \(u\) that each side allows. We compute the correction for a path attached at its two ends. The next lemmas bound the rank from below when a rigid subgraph is contracted to one body (KT Lemma 6.2) and when a body of degree two is restored after splitting off (KT Lemmas 6.8 and 6.10), from the block-triangular shape of the rigidity matrix. The last one deletes the columns of the bodies of a contracted subgraph, which Case I of the algebraic induction does when it compares the rows outside the subgraph with a realization of the contraction (KT Claim 6.4, section 23.6).
Throughout, \((G,p)\) is a body-hinge framework. A subgraph \(H\) of \(G\) keeps the hinges of \(p\) at its edges and the bodies of \((G,p)\): its screw assignments are those of \((G,p)\), maps \(B \to \bigwedge ^{d-1}K^{d+1}\) on a finite set \(B\) of bodies that contains \(V(G)\). We write \(R(H,p)\) and \(Z(H,p)\) for its rigidity matrix and its space of infinitesimal motions, defined as before. A body of \(B \setminus V(H)\) lies on no edge of \(H\), so no hinge constraint of \(H\) involves it. Its columns in \(R(H,p)\) are zero, and the rank of \(R(H,p)\) does not depend on these bodies. As after definition 19.7, we regard the rows of \(R(H,p)\) as linear forms on screw assignments: the rows of an edge \(e\) with ends \(u\) and \(v\) are the forms \(S \mapsto r_i(p(e)) \cdot (S(u) - S(v))\). The row space of \(R(H,p)\) is the span of its rows, and its dimension is the rank of \(R(H,p)\). For a set \(V_1\) of bodies, \(G[V_1]\) is the subgraph of \(G\) induced on \(V_1\).
Let \((G,p)\) be a body-hinge framework with \(C(p(e)) \neq 0\) at every edge \(e\). Let \(V_1\) be a nonempty proper subset of \(V(G)\), let \(V_2 = V(G) \setminus V_1\), and let \(C\) be a set of at most one edge of \(G\), each with one end in \(V_1\) and the other in \(V_2\). Then
In particular, if an edge of \(G\) joins \(V_1\) to a body \(w \in V_2\), then
Let \(\mathcal R_1\), \(\mathcal R_2\) and \(\mathcal R\) be the row spaces of \(R(G[V_1],p)\), \(R(G[V_2],p)\) and \(R(G,p)\). The rows of \(G[V_1]\) and of \(G[V_2]\) are rows of \(G\), so \(\mathcal R_1 + \mathcal R_2 \subseteq \mathcal R\). A row of \(G[V_1]\) depends only on the screws at the bodies of \(V_1\), and a row of \(G[V_2]\) only on those at the bodies of \(V_2\). Let \(\varphi \in \mathcal R_1 \cap \mathcal R_2\), let \(S\) be a screw assignment, and let \(S'\) agree with \(S\) on \(V_1\) and vanish elsewhere. As \(\varphi \in \mathcal R_1\), it takes the same value at \(S\) and at \(S'\). As \(\varphi \in \mathcal R_2\) and \(S'\) vanishes on \(V_2\), that value is \(0\). Hence \(\mathcal R_1 \cap \mathcal R_2 = 0\), which proves the bound when \(C\) is empty.
Otherwise \(C = \{ e\} \), where \(e\) has ends \(u \in V_1\) and \(v \in V_2\). By lemma 19.9, the rows of \(e\) span a subspace \(\mathcal R_e\) of \(\mathcal R\) of dimension \(D - 1\). Its members are the forms \(S \mapsto r(S(u) - S(v))\), where \(r\) is a linear form on \(K^D\) that vanishes on \(C(p(e))\) (definition 19.5). For \(x \in K^D\), let \(S^x\) be the screw assignment equal to \(x\) on \(V_1\) and to \(0\) elsewhere. A row of an edge inside \(V_1\) or inside \(V_2\) vanishes at \(S^x\), and the member of \(\mathcal R_e\) given by \(r\) takes the value \(r(x)\) there. So a member of \(\mathcal R_e\) that lies in \(\mathcal R_1 + \mathcal R_2\) has \(r(x) = 0\) for every \(x\), and it is zero. Therefore \(\mathcal R_1\), \(\mathcal R_e\) and \(\mathcal R_2\) are independent. Their sum lies in \(\mathcal R\) and has dimension \(\operatorname {rank} R(G[V_1],p) + (D - 1) + \operatorname {rank} R(G[V_2],p)\).
For the particular case, apply the bound to \(G[V_1 \cup \{ w\} ]\), \(V_1\) and the given edge. The first side is \(G[V_1]\), and the rank of the second side, the single body \(w\), is at least \(0\).
Katoh and Tanigawa prove this bound for a cut edge \(uv\) in the proof of KT Lemma 6.1 [ KT11 , p. 672 ] . They delete the columns of \(u\) from the rows of \(G[V_1]\), which keeps the rank of these rows by KT Lemma 5.1 (lemma 19.20). They then read the bound off the block-triangular shape of the resulting matrix.
When two sides share a body, we compare their row spaces through their motion spaces, by the following lemma.
Let \((G,p)\) be a body-hinge framework with finitely many bodies. Then the row space of \(R(G,p)\) is the space of linear forms on screw assignments that vanish on \(Z(G,p)\). In particular, two body-hinge frameworks on the same bodies with the same infinitesimal motions have the same row space, and so the same rank.
The space \(Z(G,p)\) consists of the screw assignments at which every row of \(R(G,p)\) vanishes (definition 19.7). The screw assignments form a finite-dimensional space. In the dual of a finite-dimensional space, every subspace is the space of the forms that vanish wherever all its members vanish. Applied to the row space, this gives the first claim, and the second follows from it.
Let \((G,p)\) be a body-hinge framework, let \(v\) be a body, and let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 \subseteq \{ v\} \) such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Then
Every edge of \(G\) is an edge of \(G[V_1]\) or of \(G[V_2]\), so the row space of \(R(G,p)\) is the sum of the row spaces of \(R(G[V_1],p)\) and \(R(G[V_2],p)\). We show that these two row spaces meet in \(0\); then the ranks add. By lemma 19.25, a form in both vanishes on \(Z(G[V_1],p) + Z(G[V_2],p)\), so it suffices that this sum contains every screw assignment \(S\). Let \(T\) be the assignment equal to \(S(v)\) on \(V_1\) and to \(S\) elsewhere. It is constant on \(V_1\), so it is a motion of \(G[V_1]\). The difference \(S - T\) vanishes outside \(V_1\) and at \(v\), hence on \(V_2\), so it is a motion of \(G[V_2]\).
Two sides that share two bodies \(u\) and \(v\) interact through the motions of \(v\) relative to \(u\).
Let \((G,p)\) be a body-hinge framework and \(u, v\) two bodies. The relative screws of \(u, v\) in \((G,p)\) form the subspace
For a subspace \(U \subseteq K^{D}\), the joint rows at \(u, v\) confining the relative screw to \(U\) are the linear forms \(S \mapsto r\bigl(S(u) - S(v)\bigr)\) on screw assignments, one for each linear form \(r\) on \(K^D\) that vanishes on \(U\).
The joint rows at \(u, v\) confining the relative screw to \(U\) all vanish at a screw assignment \(S\) if and only if \(S(u) - S(v) \in U\), as for the hinge-row block (definition 19.5). For an edge \(e\) with ends \(u\) and \(v\), the joint rows confining the relative screw to \(\operatorname {span} C(p(e))\) span the same space as the rows of \(e\) in \(R(G,p)\). At \(U = 0\) the joint rows force \(S(u) = S(v)\). If \(u \neq v\), the map \(S \mapsto S(u) - S(v)\) takes the screw assignments onto \(K^D\), so the joint rows span a space of dimension \(D - \dim U\).
The next lemma glues two subgraphs that share two bodies. We state it for any two subgraphs whose edges together are those of \(G\), not only for induced subgraphs: lemma 19.32 below glues \(G[V_1]\) to a path, which is not an induced subgraph when its ends are adjacent.
Let \((G,p)\) be a body-hinge framework and let \(u \neq v\) be bodies. Let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 \subseteq \{ u, v\} \), and let \(G_1, G_2\) be subgraphs of \(G\) such that every edge of \(G\) is an edge of \(G_1\) or of \(G_2\), and every edge of \(G_i\) lies inside \(V_i\). Let \(\rho _i = \rho _{uv}(G_i, p)\) (definition 19.27). Then the row spaces of \(R(G_1,p)\) and \(R(G_2,p)\) meet in the span of the joint rows at \(u, v\) confining the relative screw to \(\rho _1 + \rho _2\), and
Let \(\mathcal R_1\) and \(\mathcal R_2\) be the row spaces of \(R(G_1,p)\) and \(R(G_2,p)\), and let \(\delta (S) = S(u) - S(v)\). By lemma 19.25, a form lies in \(\mathcal R_1 \cap \mathcal R_2\) if and only if it vanishes on \(Z(G_1,p) + Z(G_2,p)\).
This sum contains every screw assignment \(S\) with \(S(u) = S(v)\). Indeed, let \(T\) be the assignment equal to \(S(v)\) on \(V_2\) and to \(S\) elsewhere. It is constant on \(V_2\), so it is a motion of \(G_2\). The difference \(S - T\) vanishes outside \(V_2\), and on \(V_1 \cap V_2 \subseteq \{ u, v\} \) because \(S(u) = S(v)\). So it vanishes on \(V_1\), and it is a motion of \(G_1\). As \(\delta \) maps \(Z(G_i,p)\) onto \(-\rho _i = \rho _i\), the sum \(Z(G_1,p) + Z(G_2,p)\) is therefore the space of screw assignments \(S\) with \(\delta (S) \in \rho _1 + \rho _2\).
Since \(u \neq v\), \(\delta \) is onto \(K^D\), so every form that vanishes on the kernel of \(\delta \) is \(r \circ \delta \) for a linear form \(r\) on \(K^D\). Such a form vanishes on \(Z(G_1,p) + Z(G_2,p)\) exactly when \(r\) vanishes on \(\rho _1 + \rho _2\), that is, when it is a joint row at \(u, v\) confining the relative screw to \(\rho _1 + \rho _2\). This proves the first claim. These joint rows span a space of dimension \(D - \dim (\rho _1 + \rho _2)\), by the remarks after definition 19.27.
Every edge of \(G\) is an edge of \(G_1\) or of \(G_2\), with the same hinge, so the row space of \(R(G,p)\) is \(\mathcal R_1 + \mathcal R_2\). The rank formula follows from \(\dim (\mathcal R_1 + \mathcal R_2) = \dim \mathcal R_1 + \dim \mathcal R_2 - \dim (\mathcal R_1 \cap \mathcal R_2)\).
Let \((G,p)\) be a body-hinge framework, let \(u \neq v\) be bodies, and let \(V_1, V_2\) be sets of bodies with \(V_1 \cap V_2 = \{ u, v\} \) such that every edge of \(G\) lies inside \(V_1\) or inside \(V_2\). Let \(\rho _i = \rho _{uv}(G[V_i], p)\). Then the row spaces of \(R(G[V_1],p)\) and \(R(G[V_2],p)\) meet in the span of the joint rows at \(u, v\) confining the relative screw to \(\rho _1 + \rho _2\), and
Apply lemma 19.28 to \(G_i = G[V_i]\). The edges of \(G[V_i]\) lie inside \(V_i\), and every edge of \(G\) is an edge of \(G[V_1]\) or of \(G[V_2]\).
We apply lemma 19.28 to a path attached to \(G[V_1]\) at two bodies \(a \neq b\); definition 30.63 calls such a path an open ear on \(V_1\). The rank and the relative screws of a path come first.
Let \((P,p)\) be a body-hinge framework whose edges are those of a path \(a = x_0 - x_1 - \cdots - x_k - x_{k+1} = b\) (\(k \geq 0\)) on distinct bodies, and let \(C_i = C(p(x_i x_{i+1})) \neq 0\) for \(0 \le i \le k\). Then \(\operatorname {rank} R(P,p) = (D-1)(k+1)\).
The matrix \(R(P,p)\) has \(D - 1\) rows for each of its \(k + 1\) edges (definition 19.5), so its rank is at most \((D-1)(k+1)\). Conversely, for \(0 \le i \le k\) the edge \(x_i x_{i+1}\) is the only edge of \(P\) that joins \(x_{i+1}\) to \(\{ x_0, \dots , x_i\} \). So adding \(x_{i+1}\) to \(\{ x_0, \dots , x_i\} \) raises the rank of the subgraph of \(P\) induced on these bodies by at least \(D - 1\) (lemma 19.24). The subgraph induced on \(\{ x_0\} \) has no edge, and the subgraph induced on all the bodies of the path is \(P\).
Let \((P,p)\) be a body-hinge framework whose edges are those of a path \(a = x_0 - x_1 - \cdots - x_k - x_{k+1} = b\) (\(k \geq 0\)) on distinct bodies, and let \(C_i = C(p(x_i x_{i+1}))\) for \(0 \le i \le k\). Then \(\rho _{ab}(P,p) = \operatorname {span}(C_0, \dots , C_k)\).
Let \(S\) be an infinitesimal motion of \((P,p)\). Each difference \(S(x_{i+1}) - S(x_i)\) lies in \(\operatorname {span} C_i\) (definition 19.3), and these differences add up to \(S(b) - S(a)\), which therefore lies in \(\operatorname {span}(C_0, \dots , C_k)\). Conversely, fix \(i\) and let \(S\) be the screw assignment equal to \(C_i\) at \(x_{i+1}, \dots , x_{k+1}\) and to \(0\) elsewhere. Its difference across the edge \(x_i x_{i+1}\) is \(C_i\), and across every other edge of \(P\) it is \(0\). So \(S\) is an infinitesimal motion with \(S(b) - S(a) = C_i\), and the subspace \(\rho _{ab}(P,p)\) contains every \(C_i\).
Let \((G,p)\) be a body-hinge framework and \(V_1\) a set of bodies. Let \(a - x_1 - \cdots - x_k - b\) (\(k \geq 0\)) be a path in \(G\) with ends \(a \neq b\) in \(V_1\) and distinct bodies \(x_1, \dots , x_k\) outside \(V_1\), such that every edge of \(G\) off the path lies inside \(V_1\). Write \(x_0 = a\) and \(x_{k+1} = b\), suppose that \(C_i = C(p(x_i x_{i+1})) \neq 0\) for \(0 \le i \le k\), and let \(\Lambda = \operatorname {span}(C_0, \dots , C_k)\) and \(\rho = \rho _{ab}(G[V_1], p)\). Then
Let \(P\) be the path, as a subgraph of \(G\), and let \(V_2\) be the set of its bodies. Then \(V_1 \cap V_2 = \{ a, b\} \), and every edge of \(G\) is an edge of \(P\) or of \(G[V_1]\). By lemma 19.28 at \(u = a\) and \(v = b\), with \(G_1 = G[V_1]\) and \(G_2 = P\),
The path has rank \((D-1)(k+1)\) (lemma 19.30) and relative screws \(\rho _{ab}(P,p) = \Lambda \) (lemma 19.31).
We also need notation for deleting columns. For a set \(W\) of bodies and a screw assignment \(S\), let \(S^W\) agree with \(S\) off \(W\) and vanish on \(W\). For a linear form \(\varphi \) on screw assignments, let \(\pi _W(\varphi )\) be the form \(S \mapsto \varphi (S^W)\). If \(\varphi \) is a row of a rigidity matrix, then \(\pi _W(\varphi )\) is the same row with zeros in the columns of \(W\), and we say that the columns of \(W\) are deleted from it. The map \(\pi _W\) is linear.
In the proof of KT Lemma 6.2 [ KT11 , pp. 673–674 ] , where \(H\) is a rigid subgraph of \(G\), Katoh and Tanigawa read the rank of \(R(G,p)\) off its block-triangular shape (KT eq. (6.3)). They compare the rank of the rows of the edges of \(G\) not in \(H\), with the columns of \(V(H)\) deleted, with that of a realization of the contraction \(G/E(H)\), in which \(H\) becomes one body (definition 21.3; KT eqs. (6.4) and (6.5)). The next lemma is the count behind this comparison, for any linear map \(\pi \) in place of \(\pi _{V(H)}\).
Let \(F\), \(F_H\) and \(F_c\) be body-hinge frameworks on one set of bodies, with row spaces \(\mathcal R\), \(\mathcal R_H\) and \(\mathcal R_c\), and let \(\pi \) be a linear map from the space of linear forms on screw assignments to itself. Suppose that \(\mathcal R_H \subseteq \mathcal R \cap \ker \pi \), that \(\pi (\mathcal R_c) \subseteq \pi (\mathcal R)\), and that \(\pi \) is injective on \(\mathcal R_c\). Then
By rank-nullity for \(\pi \) on \(\mathcal R\), \(\dim \mathcal R = \dim \pi (\mathcal R) + \dim (\mathcal R \cap \ker \pi )\). The first hypothesis gives \(\dim \mathcal R_H \le \dim (\mathcal R \cap \ker \pi )\). The other two give \(\dim \mathcal R_c = \dim \pi (\mathcal R_c) \le \dim \pi (\mathcal R)\). Adding the two bounds proves the lemma.
In the proof of KT Lemma 6.2 (lemma 23.102), \(F\) realizes \(G\), \(F_H\) is its restriction to \(H\), \(F_c\) realizes the contraction \(G/E(H)\), and \(\pi = \pi _{V(H)}\). The first hypothesis holds because a row of an edge of \(H\) depends only on the screws at the bodies of \(V(H)\), so \(\pi _{V(H)}\) maps it to \(0\). The second holds because the edges of \(G \setminus E(H)\) have the same hinges in both realizations (KT eq. (6.4)), so that their rows agree once the columns of \(V(H)\) are deleted.
In KT Lemmas 6.8 and 6.10 a body \(v\) of degree two is restored after splitting off. Katoh and Tanigawa bring the rigidity matrix to a block-triangular form by column and row operations (KT eqs. (6.16) and (6.29), pp. 679 and 686). In this form a block of rows has nonzero entries only in the columns of \(v\), and they read the rank off it. The next lemma gives such a count for two families of linear forms in the row space of a rigidity matrix, which need not be its rows: one family is independent on the screws of \(v\), and the other vanishes on them.
Let \(F\) be a body-hinge framework, let \(v\) be a body, and let \((\varphi _i)_{i \in I}\) and \((\psi _j)_{j \in J}\) be finite families of linear forms in the row space of \(R(F)\). Suppose that the restrictions of the \(\varphi _i\) to the screw assignments that vanish off \(v\) are linearly independent, and that the \(\psi _j\) are linearly independent and vanish on these screw assignments. Then \(|I| + |J| \le \operatorname {rank} R(F)\). In particular, if \(\omega \) is a further form in the row space such that the restrictions of the \(\varphi _i\) and of \(\omega \) to these screw assignments are linearly independent, then \(|I| + 1 + |J| \le \operatorname {rank} R(F)\).
Suppose that \(\sum _i a_i \varphi _i + \sum _j b_j \psi _j = 0\). Every \(\psi _j\) vanishes on the screw assignments that vanish off \(v\), so \(\sum _i a_i \varphi _i\) vanishes on them, and every \(a_i\) is \(0\) by the first hypothesis. Then \(\sum _j b_j \psi _j = 0\), and every \(b_j\) is \(0\). So the \(|I| + |J|\) forms are linearly independent (lemma 23.127). They lie in the row space of \(R(F)\), whose dimension is therefore at least \(|I| + |J|\). The second claim is the first, applied to the family of the \(\varphi _i\) and \(\omega \) (lemma 23.159).
The independence of the two families is lemma 23.127 of the algebraic induction, for KT Lemma 6.8, and with \(\omega \) added it is lemma 23.159, for KT eq. (6.29). In Case II (KT Lemma 6.8) the \(\varphi _i\) are the \(D - 1\) rows of an edge at \(v\), and the \(\psi _j\) are rows of the graph obtained by splitting off \(v\), which lie in the row space of \(R(F)\) without being its rows. In KT Lemma 6.10, \(\omega \) is the further row that the row operations of eq. (6.29) produce.
Case I of the algebraic induction contracts a proper rigid subgraph \(H\) of \(G\) (definition 20.17). Let \(r\) be a body of \(H\). The contraction \(G/E(H)\) has the edges of \(G \setminus E(H)\), with every end in \(V(H)\) replaced by \(r\), so its bodies meet \(V(H)\) only in \(r\). Deleting the columns of \(V(H)\) from its rows therefore deletes those of \(r\). By KT Lemma 5.1 this does not change the rank, as Katoh and Tanigawa note at eq. (6.5) (p. 674). The next lemma states this in the form of the third hypothesis of lemma 19.33, for \(\pi = \pi _{V(H)}\).
Let \((G,p)\) be a body-hinge framework, and let \(t\) be a set of bodies with \(V(G) \cap t = \{ r\} \). Then every screw assignment is the sum of an infinitesimal motion of \((G,p)\) and a screw assignment that vanishes on \(t\). Hence \(\pi _t\) is injective on the row space of \(R(G,p)\), and deleting the columns of \(t\) from \(R(G,p)\) does not change its rank.
Let \(S\) be a screw assignment, and let \(T\) be equal to \(S(r)\) on \(V(G)\) and to \(S\) elsewhere. Both ends of every edge lie in \(V(G)\), where \(T\) is constant, so \(T\) is an infinitesimal motion. The difference \(S - T\) vanishes at \(r\) and off \(V(G)\). As \(t \setminus \{ r\} \) lies off \(V(G)\), the difference vanishes on \(t\). This proves the first claim.
Let \(\varphi \) be a form in the row space with \(\pi _t(\varphi ) = 0\). Then \(\varphi \) vanishes on the screw assignments that vanish on \(t\), and, like every row of \(R(G,p)\), on \(Z(G,p)\) (definition 19.7). By the first claim it vanishes everywhere, so \(\varphi = 0\). Hence \(\pi _t\) is injective on the row space, and the row space has the same dimension as its image, the row space of \(R(G,p)\) with the columns of \(t\) deleted.
The motion \(T\) plays the part of the trivial motion with value \(S(r)\) in the proof of KT Lemma 5.1 (lemma 19.20). In Case I the rows of \(G \setminus E(H)\) are compared with those of \(G/E(H)\) after this deletion (KT Claim 6.4 and eq. (6.9)), at every deficiency in lemma 23.96 and when \(G/E(H)\) is rigid in lemma 23.98.