16 Body-bar Tay theorem
A body-bar framework consists of rigid bodies joined by bars, each bar attached to its two bodies by ball joints. Its graph is the multigraph with a vertex for each body and an edge for each bar. This chapter proves Tay’s theorem [ Tay84 ] , which characterizes the graphs of the independent and infinitesimally rigid body-bar frameworks. Let \(D = \binom {d+1}{2}\), the dimension of the space of infinitesimal motions of a rigid body in \({\mathbb {R}}^d\). Then a multigraph \(G\) is the graph of an independent and infinitesimally rigid body-bar framework in \({\mathbb {R}}^d\) if and only if \(|E(G)| = D|V(G)| - D\) and every non-empty set \(E'\) of bars satisfies \(|E'| \le D|V(E')| - D\), where \(V(E')\) is the set of bodies that the bars of \(E'\) meet. The graphs of the independent body-bar frameworks are the multigraphs that satisfy the inequalities (Whiteley [ Whi88 , Theorem 8 ] ). Tay and Whiteley write \(n\) for the dimension and \(d\) for \(n(n+1)/2\). We write \(d\) and \(D\), as Katoh and Tanigawa [ KT11 ] do, because section 17 and the chapters after it follow their paper.
Whiteley [ Whi88 ] gave another proof of Tay’s theorem, by matroid union, and we follow it. Section 16.1 shows that a set of bars is independent in the union of \(k\) copies of the cycle matroid if and only if each of its non-empty subsets \(E'\) satisfies \(|E'| \le k|V(E')| - k\). This follows from Edmonds’ theorem (section 15). Section 16.2 proves Whiteley’s Theorem 1: the general \(k\)-frame, a matrix whose nonzero entries are indeterminates, represents this union. Section 16.3 decomposes the bars of a multigraph that satisfies the count into \(k\) forests, which are spanning trees when the multigraph is connected and has \(k|V(G)| - k\) bars. Section 16.4 defines body-bar frameworks and shows that the rigidity matrix of a framework is the general \(D\)-frame with each indeterminate replaced by a coordinate of a bar. Section 16.5 proves Tay’s theorem. A decomposition of the bars into \(D\) forests gives an independent framework, in which each bar of the \(j\)-th forest gets the \(j\)-th standard basis vector of \({\mathbb {R}}^D\). Conversely, the rows of an independent framework satisfy the count, as those of the general \(D\)-frame do.
We prove the theorem in this existence form: some framework on \(G\) is independent, or independent and infinitesimally rigid. Whiteley also requires each bar to be a line. He shows, by an argument on irreducible varieties [ Whi88 , § 3.1 ] , that for a general choice of the lines the rows have the same independent sets as the rows of the general \(D\)-frame. Section 28 proves a generic form of the theorem instead, for bars given by their endpoints, by the coordinate argument of Jackson and Jordán [ JJ10 ] .
16.1 Sparsity and the union of cycle matroids
Throughout this chapter, \(G\) is a finite multigraph: two vertices may be joined by several edges, and loops are allowed. We call its vertices bodies and its edges bars, and write \(V(G)\) and \(E(G)\) for these sets. For a set \(E'\) of bars, \(V(E')\) is the set of bodies incident with a bar of \(E'\), and \(G \restriction E'\) is the multigraph with the bodies of \(G\) and the bars of \(E'\). In this subsection we characterize the sets of bars that are unions of \(k\) forests by a count.
A set of bars is a forest if it contains no cycle; a loop is a cycle, and so are two bars with the same ends. The forests are the independent sets of a matroid on \(E(G)\), the cycle matroid of \(G\) [ Oxl11 , § 1.1 ] . We write \(r\) for its rank function. Let \(c(E')\) be the number of connected components of the multigraph with bodies \(V(E')\) and bars \(E'\). Then [ Oxl11 , (1.3.8) ]
The union \(\bigcup _j M_j\) of matroids \(M_1, \dots , M_k\) on a common finite set was introduced by Nash-Williams [ NW67 ] . Section 15 defines it as the matroid induced from their direct sum by a bipartite graph (definition 15.6). A set is independent in the union if and only if it is a union \(I_1 \cup \dots \cup I_k\) of sets \(I_j\) independent in \(M_j\) (lemma 15.8). For \(k\) copies of one matroid \(M\), the rank of the union (theorem 15.10) shows that a set \(X\) is independent in the union if and only if \(|Y| \le k\, r_M(Y)\) for every \(Y \subseteq X\). This is Edmonds’ matroid-partition theorem [ Edm65 , Theorem 1 ] (theorem 15.11). We apply these results to \(k\) copies of the cycle matroid of \(G\), whose independent sets are the unions of \(k\) forests.
The count compares each non-empty set of bars with the bodies it meets. For simple graphs, definition 3.1 instead bounds the number of edges spanned by a set of vertices. Tay’s theorem (theorem 16.27) is about the case \(k = \ell \).
Let \(k\) and \(\ell \) be natural numbers. A multigraph \(G\) is \((k, \ell )\)-sparse if every non-empty set \(E'\) of bars of \(G\) satisfies \(|E'| \le k\, |V(E')| - \ell \). It is \((k, \ell )\)-tight if moreover \(|E(G)| = k\, |V(G)| - \ell \).
The next theorem is the part of Whiteley’s Corollary 3 [ Whi88 ] that we use, and we follow his proof.
Let \(G\) be a multigraph, let \(k\) be a natural number, and let \(E' \subseteq E(G)\). Then \(E'\) is independent in the union of \(k\) copies of the cycle matroid of \(G\) if and only if \(G \restriction E'\) is \((k, k)\)-sparse.
By Edmonds’ matroid-partition theorem (theorem 15.11), \(E'\) is independent in the union if and only if \(|Y| \le k\, r(Y)\) for every \(Y \subseteq E'\). On the other hand, \(G \restriction E'\) is \((k, k)\)-sparse if and only if \(|Y| \le k\, |V(Y)| - k\) for every non-empty \(Y \subseteq E'\).
Suppose that \(|Y| \le k\, r(Y)\) for every \(Y \subseteq E'\), and let \(Y \subseteq E'\) be non-empty. Then \(c(Y) \ge 1\), so \(r(Y) \le |V(Y)| - 1\) and \(|Y| \le k\, |V(Y)| - k\).
Conversely, let \(G \restriction E'\) be \((k, k)\)-sparse, and let \(Y \subseteq E'\) be non-empty. Sparsity alone gives \(|Y| \le k\, |V(Y)| - k\), which is weaker than \(|Y| \le k\, r(Y)\) when \(c(Y) {\gt} 1\). So we apply it to each component. Let \(c = c(Y)\), and let \(Y_1, \dots , Y_c\) be the sets of bars of the components of the multigraph with bodies \(V(Y)\) and bars \(Y\). Each \(Y_i\) is non-empty, as every body in \(V(Y)\) meets a bar of \(Y\). Its component is connected, so \(r(Y_i) = |V(Y_i)| - 1\), and sparsity gives \(|Y_i| \le k\, |V(Y_i)| - k = k\, r(Y_i)\). The sets \(Y_i\) partition \(Y\), and the sets \(V(Y_i)\) partition \(V(Y)\), so
16.2 The \(k\)-frame matroid as a union of cycle matroids
Whiteley represents the union of \(k\) copies of the cycle matroid of \(G\) by a matrix with indeterminate entries, the general \(k\)-frame on \(G\) [ Whi88 , Definition 2.2 ] . Its nonzero entries are indeterminates, placed in the pattern of an incidence matrix of \(G\) repeated \(k\) times. In this subsection we prove Whiteley’s Theorem 1: the matroid of the rows of this matrix is the union of \(k\) copies of the cycle matroid (theorem 16.16).
Fix an orientation of each bar. The signed incidence vector \(a_e\) of a bar \(e\) has one entry for each body: \(1\) at the head of \(e\), \(-1\) at its tail and \(0\) elsewhere, so that \(a_e = 0\) if \(e\) is a loop. Its entries are integers, so we may read it over any ring. Over every field the vectors \(a_e\) represent the cycle matroid: a set of bars is a forest if and only if its signed incidence vectors are linearly independent [ Oxl11 , Lemma 5.1.3 ] . Reversing a bar changes the sign of \(a_e\), so nothing below depends on the orientation. For a vector \(w\) with one entry for each body and for \(j \in \{ 1, \dots , k\} \), we write \(w^{(j)}\) for the vector with \(k\) blocks that has \(w\) in block \(j\) and \(0\) in the other blocks.
Let \(G\) be a multigraph and let \(k \ge 1\). Let \(R = {\mathbb {Q}}[X_{e,j}]\) be the polynomial ring over \({\mathbb {Q}}\) in one indeterminate \(X_{e,j}\) for each bar \(e\) and each \(j \in \{ 1, \dots , k\} \), and let \(K\) be its field of fractions. The \(k\)-frame row of a bar \(e\) is
where \(a_e\) is the signed incidence vector of \(e\). The \(k\)-frame matroid \(F(G, X)\) is the matroid on \(E(G)\) in which a set of bars is independent if and only if their \(k\)-frame rows are linearly independent over \(K\).
Whiteley’s matrix groups its columns by body. Grouped by block instead, as in the proof of his Theorem 1, its rows are the rows \(\rho _e\). By theorem 16.2, it suffices to show that a set \(E'\) of bars is independent in \(F(G, X)\) if and only if \(G \restriction E'\) is \((k, k)\)-sparse (lemma 16.15).
Suppose that the rows of \(E'\) are linearly independent, and let \(Y \subseteq E'\). The rows of the bars in \(Y\) lie in a subspace of dimension \(k\, r(Y)\), so \(|Y| \le k\, r(Y)\) (lemma 16.8). Conversely, suppose that \(G \restriction E'\) is \((k, k)\)-sparse. Then \(E'\) is the union of \(k\) disjoint forests. Setting \(X_{e,j} = 1\) when \(e\) lies in the \(j\)-th forest, and every other indeterminate to \(0\), turns the rows of \(E'\) into a block-diagonal matrix whose blocks are incidence matrices of forests. Its rows are linearly independent, and hence so are the rows of \(E'\) (lemma 16.14).
The first direction rests on three facts of linear algebra. For a subspace \(W\) of a vector space \(U\), we write \(W^k\) for the subspace of \(U^k\) of the vectors whose \(k\) blocks all lie in \(W\).
Let \(A\) be the span over \(K\) of the signed incidence vectors of the bars of \(G\). Then the \(k\)-frame row of every bar lies in \(A^k\), and hence so does the span of all \(k\)-frame rows.
Block \(j\) of \(\rho _e\) is \(X_{e,j}\, a_e\), which lies in \(A\).
The formalization proves the lemma for every set \(Y\) of bars, with the span \(A_Y\) of \(\{ a_e : e \in Y\} \) in place of \(A\): the \(k\)-frame row of every bar of \(Y\) lies in \(A_Y^k\), and so does the span of these rows. The statement is the case \(Y = E(G)\), and the proof of lemma 16.8 uses the general case. The first pinned theorem is the second statement, the second is the first, and the third pin defines \(A_Y^k\).
Let \(W\) be a finite-dimensional subspace of a vector space \(U\) over \(K\). Then \(\dim W^k = k \dim W\).
Taking a vector of \(W^k\) to its \(k\) blocks is a linear isomorphism from \(W^k\) onto the product of \(k\) copies of \(W\).
Let \(M\) be a matroid of finite rank, represented over a field by vectors \(v_e\): a set \(I\) is independent in \(M\) if and only if the vectors \(v_e\), \(e \in I\), are linearly independent. Then for every set \(Y\) of elements of \(M\), the span of \(\{ v_e : e \in Y\} \) has dimension \(r_M(Y)\). In particular, for every set \(Y\) of bars of \(G\), the span over \(K\) of \(\{ a_e : e \in Y\} \) has dimension \(r(Y)\).
Let \(I\) be a basis of \(Y\) in \(M\). For \(e \in Y \setminus I\) the set \(I \cup \{ e\} \) is dependent, so \(v_e\) lies in the span of \(\{ v_f : f \in I\} \). Hence this span is the span of \(\{ v_e : e \in Y\} \). The vectors \(v_f\), \(f \in I\), are linearly independent, so it has dimension \(|I| = r_M(Y)\).
Let \(E' \subseteq E(G)\) be a set of bars whose \(k\)-frame rows are linearly independent over \(K\). Then \(|Y| \le k\, r(Y)\) for every \(Y \subseteq E'\).
Let \(Y \subseteq E'\), and let \(A_Y\) be the span over \(K\) of \(\{ a_e : e \in Y\} \). The \(|Y|\) rows \(\rho _e\) with \(e \in Y\) are linearly independent. They lie in \(A_Y^k\), by lemma 16.4 with \(Y\) in place of \(E(G)\) (the note after it). By lemma 16.6 and lemma 16.7, \(\dim A_Y^k = k \dim A_Y = k\, r(Y)\). Hence \(|Y| \le k\, r(Y)\).
Whiteley proves this direction from a nonzero minor of order \(|E'|\). Some monomial of the minor is nonzero, and setting its indeterminates to \(1\) and the others to \(0\) exhibits \(E'\) as a union of \(k\) forests. The dimension bound gives the count without expanding the determinant.
Substituting numbers for the indeterminates is a ring homomorphism on \(R\), but it is not defined on all of \(K\). So for the converse we work over \(R\), which contains the entries of every \(k\)-frame row.
Let \(F_1, \dots , F_k\) be forests of \(G\). Then the vectors \(a_e^{(j)}\), one for each pair \((j, e)\) with \(e \in F_j\), are linearly independent over \(K\).
For each \(j\), the vectors \(a_e\) with \(e \in F_j\) are linearly independent, because \(F_j\) is a forest. A linear relation among the vectors \(a_e^{(j)}\) is, block by block, a linear relation among the vectors \(a_e\) with \(e \in F_j\) for each \(j\), so it is trivial.
Let \(E' \subseteq E(G)\) be a set of bars. Then the \(k\)-frame rows of the bars in \(E'\) are linearly independent over \(K\) if and only if they are linearly independent over \(R\).
A nontrivial linear relation over \(R\) is one over \(K\). Conversely, multiplying a nontrivial linear relation over \(K\) by a common denominator of its coefficients gives one over \(R\).
Let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((k, k)\)-sparse. Then \(E' = F_1 \cup \dots \cup F_k\) for some pairwise disjoint forests \(F_1, \dots , F_k\) of \(G\).
By theorem 16.2, \(E'\) is independent in the union of \(k\) copies of the cycle matroid. By lemma 15.8, it is the union of \(k\) sets independent in the cycle matroid, that is, of \(k\) forests \(F_1, \dots , F_k\). The sets \(F_j \setminus (F_1 \cup \dots \cup F_{j-1})\) are pairwise disjoint, have the same union, and are forests, since a subset of a forest is a forest.
Let \(F_1, \dots , F_k\) be pairwise disjoint forests of \(G\), and let \(\varphi \colon R \to {\mathbb {Q}}\) be the ring homomorphism with \(\varphi (X_{e,j}) = 1\) if \(e \in F_j\) and \(\varphi (X_{e,j}) = 0\) otherwise. Let \(e \in F_{j_0}\). Then applying \(\varphi \) to each entry of \(\rho _e\) gives \(a_e^{(j_0)}\).
Block \(j\) of \(\rho _e\) is \(X_{e,j}\, a_e\). The entries of \(a_e\) are \(0\) and \(\pm 1\), so \(\varphi \) maps this block to \(\varphi (X_{e,j})\, a_e\). Here \(\varphi (X_{e,j_0}) = 1\). For \(j \ne j_0\) we have \(e \notin F_j\), as the forests are disjoint, so \(\varphi (X_{e,j}) = 0\).
The formalization defines the \(k\)-frame row twice, with entries in \(R\) (Graph.kFrameRowR) and with entries in \(K\), and proves that the second is the image of the first under the inclusion of \(R\) in \(K\) (Graph.kFrameRow_eq_map_kFrameRowR).
Let \(E' \subseteq E(G)\) be a set of bars such that \(G \restriction E'\) is \((k, k)\)-sparse. Then the \(k\)-frame rows of the bars in \(E'\) are linearly independent over \(K\).
We follow the converse half of Whiteley’s proof [ Whi88 , Theorem 1 ] . By lemma 16.11, \(E'\) is the union of pairwise disjoint forests \(F_1, \dots , F_k\). Let \(\varphi \) be the homomorphism of lemma 16.12. It maps the row of each bar \(e \in F_j\) to \(a_e^{(j)}\). These vectors are linearly independent over \(K\) (lemma 16.9), and their entries are rational, so they are linearly independent over \({\mathbb {Q}}\).
Let \(P\) be the matrix over \(R\) whose rows are the \(k\)-frame rows of the bars in \(E'\). The matrix \(\varphi (P)\) has linearly independent rows, so it has a nonzero minor of order \(|E'|\). The same minor of \(P\) is a polynomial, and \(\varphi \) maps it to that nonzero minor of \(\varphi (P)\). Hence it is nonzero, and the rows of \(P\) are linearly independent over \(R\) (Matrix.linearIndependent_rows_of_specialized_submatrix_det_ne_zero). By lemma 16.10, they are linearly independent over \(K\).
Let \(E' \subseteq E(G)\) be a set of bars. Then \(E'\) is independent in \(F(G, X)\) if and only if \(G \restriction E'\) is \((k, k)\)-sparse.
The set \(E'\) is independent in \(F(G, X)\) if and only if its \(k\)-frame rows are linearly independent over \(K\). If they are, then \(|Y| \le k\, r(Y)\) for every \(Y \subseteq E'\) (lemma 16.8). So \(E'\) is independent in the union of \(k\) copies of the cycle matroid, by Edmonds’ matroid-partition theorem (theorem 15.11). Then \(G \restriction E'\) is \((k, k)\)-sparse by theorem 16.2. The converse is lemma 16.14.
Let \(G\) be a multigraph and let \(k \ge 1\). Then the \(k\)-frame matroid \(F(G, X)\) is the union of \(k\) copies of the cycle matroid of \(G\).
Both matroids have ground set \(E(G)\), so it suffices to show that they have the same independent sets. By lemma 16.15, a set \(E' \subseteq E(G)\) is independent in \(F(G, X)\) if and only if \(G \restriction E'\) is \((k, k)\)-sparse. By theorem 16.2, the same holds in the union.
In the formalization the bars of \(G\) form a subset \(E(G)\) of a type of edge labels, and the union of the cycle matroids is a matroid on all the labels, in which a label outside \(E(G)\) is a loop. This is how the formalization treats unions of matroids on different ground sets (definition 15.6). The formal theorem therefore states that \(F(G, X)\) is the restriction of that union to \(E(G)\).
16.3 Decompositions into forests and spanning trees
Applied to the set of all bars, theorem 16.2 characterizes the multigraphs whose bars form a union of \(k\) forests. Whiteley [ Whi88 , remark after Corollary 3 ] attributes this theorem to Tutte [ Tut61 ] and to Nash-Williams [ NW61 , NW64 ] , and its first proof by matroid union to Edmonds [ Edm65 ] . Oxley derives it from Edmonds’ theorem, as we do [ Oxl11 , Proposition 11.3.14 ] .
Let \(G\) be a multigraph and let \(k\) be a natural number. Then \(E(G)\) is the union of \(k\) pairwise disjoint forests if and only if \(G\) is \((k, k)\)-sparse.
If \(E(G)\) is the union of \(k\) forests, then it is independent in the union of \(k\) copies of the cycle matroid (lemma 15.8). As \(G \restriction E(G) = G\), the multigraph \(G\) is then \((k, k)\)-sparse (theorem 16.2). Conversely, if \(G\) is \((k, k)\)-sparse, then lemma 16.11, applied to \(E' = E(G)\), gives the \(k\) pairwise disjoint forests.
Let \(G\) be a connected \((k, k)\)-tight multigraph. Then \(E(G)\) is the union of \(k\) pairwise disjoint spanning trees of \(G\).
By theorem 16.18, \(E(G)\) is the union of pairwise disjoint forests \(F_1, \dots , F_k\). Since \(G\) is connected, \(r(E(G)) = |V(G)| - 1\), so the tightness of \(G\) gives \(|E(G)| = k\, r(E(G))\). Each \(F_i\) is independent in the cycle matroid, so \(|F_i| \le r(E(G))\), and the numbers \(|F_i|\) sum to \(|E(G)|\). Hence \(|F_i| = r(E(G))\) for every \(i\), so each \(F_i\) is a basis of the cycle matroid, that is, a maximal forest of \(G\) (Graph.isMaximalAcyclicSet_of_isForestPacking_of_isTight). A maximal forest of a connected multigraph is a spanning tree.
16.4 Body-bar frameworks and the rigidity matrix
An infinitesimal motion of a rigid body in \({\mathbb {R}}^d\) is a screw. The screws form a vector space of dimension \(D = \binom {d+1}{2}\), with \(d\) dimensions of translations and \(\binom {d}{2}\) of rotations. A bar \(e\) joining bodies \(u\) and \(v\) imposes one linear condition on their screws \(m(u)\) and \(m(v)\), of the form \(\langle b_e, m(u) - m(v) \rangle = 0\) for a vector \(b_e \in {\mathbb {R}}^D\). Whiteley [ Whi88 , § 3 ] takes for \(b_e\) the vector of Plücker coordinates of the line of the bar, with the screws written in dual coordinates. Following Tay [ Tay84 , Definition 5.1 ] , we allow an arbitrary vector \(b_e \in {\mathbb {R}}^D\) on each bar.
Let \(d\) be a natural number and let \(D = \binom {d+1}{2}\). A body-bar framework in \({\mathbb {R}}^d\) on a multigraph \(G\) is a pair \((G, b)\), where \(b\) assigns a vector \(b_e \in {\mathbb {R}}^D\) to each bar \(e\) of \(G\).
The formalization calls the dimension \(n\), as Tay and Whiteley do, and writes \(D\) as Graph.bodyBarDim \(n = n(n+1)/2\).
Let \((G, b)\) be a body-bar framework in \({\mathbb {R}}^d\), and let \(D = \binom {d+1}{2}\). Orient each bar \(e\) of \(G\) from a body \(u_e\), its tail, to a body \(v_e\), its head. A motion of \((G, b)\) assigns a vector \(m(v) \in {\mathbb {R}}^D\) to each body \(v\). The rigidity map of \((G, b)\) is the linear map from motions to \({\mathbb {R}}^{E(G)}\) given by
The row of a bar \(e\) is the linear functional \(m \mapsto \langle b_e, m(u_e) - m(v_e) \rangle \). Reversing \(e\) changes the sign of its row, so the rank of the rigidity map does not depend on the orientation. We identify a linear functional on motions with its vector of coefficients. This vector has \(D\) blocks, one for each coordinate of \({\mathbb {R}}^D\), and each block has one entry for each body. So we can use the notation \(a_e\) and \(w^{(c)}\) of section 16.2, with \(k = D\) and the orientation above. As \(a_e\) has \(1\) at \(v_e\) and \(-1\) at \(u_e\), the row of \(e\) is
(Graph.BodyBarFramework.rigidityRow_eq). Up to sign, it is the \(D\)-frame row \(\rho _e\) of definition 16.3 with each indeterminate \(X_{e,c}\) replaced by the coordinate \((b_e)_c\). In Whiteley’s terms, the rigidity matrix of \((G, b)\) is the \(D\)-frame on \(G\) at \(b\) [ Whi88 , § 3 ] .
Let \(G\) have at least one body. A motion that assigns the same vector to every body lies in the kernel of the rigidity map, and these constant motions form a space of dimension \(D\). Whiteley calls them trivial: each corresponds to one screw motion of the whole space. The motions form a space of dimension \(D|V(G)|\), so the rigidity map has rank at most \(D|V(G)| - D\), with equality exactly when every motion in its kernel is constant.
Let \(D = \binom {d+1}{2}\). A body-bar framework \((G, b)\) in \({\mathbb {R}}^d\) is infinitesimally rigid if its rigidity map has rank \(D|V(G)| - D\).
A body-bar framework \((G, b)\) is independent if its rigidity map has rank \(|E(G)|\), that is, if the rows of its bars are linearly independent.
Infinitesimal rigidity is the analogue for body-bar frameworks of infinitesimal rigidity for bar-joint frameworks (definition 6.5). Independence is the analogue of row-independence (definition 9.3). Following Whiteley [ Whi88 , § 2.3 ] , we call a framework that is independent and infinitesimally rigid isostatic. The rank of its rigidity map is then \(|E(G)| = D|V(G)| - D\).
16.5 Tay’s theorem
For the existence direction we follow Whiteley’s proof of his Theorem 8 [ Whi88 ] . Its framework comes from the specialization in the proof of lemma 16.14. For the converse, Whiteley derives the count from the independence of the rows of the general \(D\)-frame [ Whi88 , proof of Corollary 3 ] . We bound the dimension of the span of the rows directly instead, as in lemma 16.8.
Let \(D = \binom {d+1}{2}\), and let \(G\) be a \((D, D)\)-sparse multigraph. Then there is an independent body-bar framework in \({\mathbb {R}}^d\) on \(G\). If \(G\) is \((D, D)\)-tight, then there is a body-bar framework in \({\mathbb {R}}^d\) on \(G\) that is independent and infinitesimally rigid.
By theorem 16.18, \(E(G)\) is the union of pairwise disjoint forests \(F_1, \dots , F_D\). For a bar \(e\), let \(j(e)\) be the index with \(e \in F_{j(e)}\), and let \(b_e\) be the \(j(e)\)-th standard basis vector of \({\mathbb {R}}^D\). Up to sign, the row of \(e\) is then \(a_e^{(j(e))}\) (section 16.4). So the rows of the bars of \(F_j\) lie in block \(j\), where up to sign they are the signed incidence vectors of the bars of the forest \(F_j\), and these are linearly independent over \({\mathbb {R}}\). Hence all the rows are linearly independent, as in the proof of lemma 16.9, and \((G, b)\) is independent (Graph.BodyBarFramework.stdFramework_finrank_range). If \(G\) is \((D, D)\)-tight, the rank of the rigidity map is \(|E(G)| = D|V(G)| - D\), so \((G, b)\) is also infinitesimally rigid.
Let \(D = \binom {d+1}{2}\), and let \((G, b)\) be an independent body-bar framework in \({\mathbb {R}}^d\). Then \(G\) is \((D, D)\)-sparse.
Let \(E'\) be a non-empty set of bars. The rows of the bars in \(E'\) are linearly independent, so their span has dimension \(|E'|\). Let \(A_{E'}\) be the span over \({\mathbb {R}}\) 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\). As in the proof of lemma 16.8, with \({\mathbb {R}}\) in place of \(K\), the space \(A_{E'}^D\) has dimension \(D\, r(E')\) (Graph.BodyBarFramework.finrank_rigidityRow_span_le). Hence \(|E'| \le D\, r(E')\). As \(E'\) is non-empty, \(c(E') \ge 1\), so \(r(E') \le |V(E')| - 1\) and \(|E'| \le D|V(E')| - D\).
Let \(D = \binom {d+1}{2}\), and let \(G\) be a multigraph. Then there is an independent body-bar framework in \({\mathbb {R}}^d\) on \(G\) if and only if \(G\) is \((D, D)\)-sparse. There is a body-bar framework in \({\mathbb {R}}^d\) on \(G\) that is independent and infinitesimally rigid if and only if \(G\) is \((D, D)\)-tight.
If there is an independent framework on \(G\), then \(G\) is \((D, D)\)-sparse by lemma 16.26. If the framework is also infinitesimally rigid, then the rank of its rigidity map is both \(|E(G)|\) and \(D|V(G)| - D\), so \(G\) is \((D, D)\)-tight. The converses are proposition 16.25.
The first statement is Whiteley’s Theorem 8 [ Whi88 ] . The second is Tay’s Theorem 5.3 [ Tay84 ] in the existence form. By theorem 16.18, the multigraph \(G\) is \((D, D)\)-sparse if and only if \(E(G)\) is the union of \(D\) disjoint forests. By corollary 16.19, the bars of a connected \((D, D)\)-tight multigraph form the union of \(D\) disjoint spanning trees, and Tay states his theorem in this form.
Each standard basis vector of \({\mathbb {R}}^D\) satisfies the quadratic Plücker relations, so it is the vector of Plücker coordinates of a line in projective \(d\)-space [ Whi88 , proof of Theorem 8 ] . The frameworks of proposition 16.25 therefore have a line on each bar. So the theorem also holds for Whiteley’s body-bar frameworks, whose bars are lines.