Combinatorial Rigidity

24 The generic bar-joint rigidity matroid

Jordán  [ Jor16 ] (§1.3.1, p. 39) defines the \(d\)-dimensional rigidity matroid \(\mathcal{R}_d(G)\) of a graph \(G\) as the rigidity matroid of a generic framework of \(G\), one whose coordinates satisfy no algebraic dependency (p. 36), and writes \(r_d(G)\) for its rank. At \(d = 3\), \(r_3\) is the rank function \(r\) of KT Corollary 5.7: for a graph \(G\) of minimum degree at least two,

\[ r(G^2) \; =\; 3|V| - 6 - \operatorname {def}(\tilde G), \]

where the square \(G^2\) joins every two vertices at distance one or two in \(G\) (definition 25.1), and \(\operatorname {def}(\tilde G)\) is the deficiency of definition 20.3 at \(D = 6\). Jackson and Jordán  [ JJ08a ] proved the inequality \(\le \) (their Theorem 4.1), and showed that equality is equivalent to the molecular conjecture (their Theorem 4.3). We prove the formula as corollary 26.8. In this chapter we construct the matroid and its rank function, in every dimension \(d\).

In the plane we needed no notion of genericity (section 10.4). There we found one framework at which every \((2,3)\)-sparse edge set is row-independent, using Pollaczek-Geiringer’s and Laman’s characterization of these edge sets as the ones that are row-independent at some framework. No combinatorial characterization of this kind is known in dimension three or more (Jordán, p. 39; KT §7), and none is needed here. We work with placements that are generic for row independence: every edge set that is row-independent at some placement is row-independent at them. Such placements exist in every dimension, by the argument of the planar case (section 24.1). We define the matroid \(\mathcal{R}_d(V)\) on the edges of the complete graph \(K_V\) as the linear rigidity matroid at one of them. Its independent sets are the edge sets that are row-independent at some placement, so it does not depend on the placement, and in the plane it is the planar rigidity matroid. Finally, for a graph \(H\) on \(V\), the rank of \(E(H)\) in \(\mathcal{R}_d(V)\) is the rank of the rigidity map of \(H\) at any generic placement (section 24.2).

Throughout, \(V\) is a finite set and \(d \in {\mathbb {N}}\). As in section 6, a placement of \(V\) in \({\mathbb {R}}^{d}\) is a framework on \(V\) in \({\mathbb {R}}^{d}\), and \(R(G, p)\) is the rigidity map. The rigidity rows \(r_e\) and row-independent edge sets are defined in section 9.

24.1 Generic placements

Jackson and Jordán  [ JJ08a ] (§2) call a framework generic when its rigidity matrix and all of its submatrices have the largest rank among all placements of the graph. The entries of the rigidity matrix are polynomials with integer coefficients in the coordinates (Jordán, p. 39), so a placement whose coordinates are algebraically independent over \({\mathbb {Q}}\) is generic in this sense. We ask this of the rigidity matrix of \(K_V\) and its submatrices formed by sets of rows: every set of edges of \(K_V\) that is row-independent at some placement must be row-independent at the generic one. This is all that the construction of the matroid uses, and placements with this property exist by an argument that needs no algebraic independence.

Definition 24.1 Generic placement for row independence
✓

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\). We say that \(p\) is generic for row independence if every set \(I \subseteq E(K_V)\) that is row-independent at some placement of \(V\) in \({\mathbb {R}}^{d}\) is row-independent at \(p\) (definition 9.3, at \(G = K_V\)).

Lemma 24.2 Existence of generic placements
✓

Let \(V\) be finite and \(d \in {\mathbb {N}}\). Then there is a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence.

Proof ▶

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, and a placement at which every member of \(\mathcal{F}\) is row-independent is generic. We find one as in the proof of lemma 10.18. There each \((2,3)\)-sparse edge set is row-independent at some framework by Pollaczek-Geiringer’s and Laman’s characterization (theorem 10.10); here each member of \(\mathcal{F}\) is row-independent at some placement by definition.

We show, by induction on \(|\mathcal{F}'|\), that for every \(\mathcal{F}' \subseteq \mathcal{F}\) there is a placement at which every member of \(\mathcal{F}'\) is row-independent. For \(\mathcal{F}' = \emptyset \) any placement will do. Otherwise let \(I_0 \in \mathcal{F}'\), let \(p_0\) be a placement at which every member of \(\mathcal{F}' \setminus \{ I_0\} \) is row-independent, and let \(q\) be a placement at which \(I_0\) is row-independent. For \(t \in {\mathbb {R}}\), let \(p^{t} = p_0 + t\, (q - p_0)\). 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'\).

Let \(I\) be a member of \(\mathcal{F}' \setminus \{ I_0\} \), or \(I_0\), and let \(t_0\) be \(0\) or \(1\) accordingly. A set of edges is row-independent at a placement exactly when its rigidity rows there are linearly independent (lemma 9.6). Fix a basis of \((({\mathbb {R}}^{d})^{V})^{*}\). The coordinate vectors of the rows at \(p^{t}\) of the edges in \(I\) are the rows of a matrix \(A + t\, B\), where \(A\) and \(B\) do not depend on \(t\). These rows are linearly independent at \(t_0\), so some \(|I| \times |I|\) minor of \(A + t_0 B\) is nonzero. The same minor of \(A + t\, B\) is a polynomial in \(t\) that is nonzero at \(t_0\), so it has finitely many roots. At every other \(t\), the rows at \(p^{t}\) of the edges in \(I\) are linearly independent. Choose \(t\) outside the roots of these finitely many polynomials, one for each member of \(\mathcal{F}'\). Then every member of \(\mathcal{F}'\) is row-independent at \(p^{t}\).

24.2 The matroid and its rank function

In the plane we defined \(\mathcal{R}(V)\) by counting, and showed that the linear rigidity matroid at one framework equals it (theorem 10.19). In general dimension there is no count to start from, and we take the linear rigidity matroid at a generic placement as the definition.

Definition 24.3 The generic rigidity matroid \(\mathcal{R}_d(V)\)
✓

Fix a placement \(p\) of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence (lemma 24.2). The generic rigidity matroid \(\mathcal{R}_d(V)\) is the linear rigidity matroid \(\mathcal{L}_p(V)\) at \(p\) (definition 10.16), a matroid on \(E(K_V)\).

Lemma 24.4 Independence in \(\mathcal{R}_d(V)\)
✓

Let \(I \subseteq E(K_V)\). Then \(I\) is independent in \(\mathcal{R}_d(V)\) if and only if \(I\) is row-independent at some placement of \(V\) in \({\mathbb {R}}^{d}\).

Proof ▶

Let \(p\) be the placement in the definition of \(\mathcal{R}_d(V)\). A set is independent in \(\mathcal{R}_d(V) = \mathcal{L}_p(V)\) if and only if it is row-independent at \(p\) (lemma 10.17). If \(I\) is row-independent at \(p\), then it is row-independent at some placement, namely \(p\). Conversely, if \(I\) is row-independent at some placement, then it is row-independent at \(p\), since \(p\) is generic (definition 24.1).

Lemma 24.5 Placement independence
✓

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence. Then \(\mathcal{L}_p(V) = \mathcal{R}_d(V)\).

Proof ▶

Both matroids have ground set \(E(K_V)\), so it suffices to show that they have the same independent sets. A set \(I \subseteq E(K_V)\) is independent in \(\mathcal{L}_p(V)\) if and only if it is row-independent at \(p\) (lemma 10.17). Since \(p\) is generic, this holds if and only if \(I\) is row-independent at some placement, that is, if and only if \(I\) is independent in \(\mathcal{R}_d(V)\) (lemma 24.4).

Lemma 24.6 Dimension two: the planar rigidity matroid
✓

The generic rigidity matroid \(\mathcal{R}_2(V)\) is the planar rigidity matroid \(\mathcal{R}(V)\), the \((2,3)\)-count matroid on \(V\) (definition 10.12).

Proof ▶

Both matroids have ground set \(E(K_V)\). A set \(I \subseteq E(K_V)\) is independent in \(\mathcal{R}_2(V)\) if and only if it is row-independent at some placement in \({\mathbb {R}}^{2}\) (lemma 24.4). The same holds in \(\mathcal{R}(V)\) (theorem 10.13), so the two matroids are equal.

Jordán’s \(r_d(G)\) is the rank of the rigidity matroid of a generic framework of \(G\) (p. 39). The rows of \(R(G, p)\) are the rows of \(R(K_V, p)\) indexed by \(E(G)\), so this matroid is the restriction of the rigidity matroid of \(K_V\) to \(E(G)\). We therefore define the rank of a graph on \(V\) through \(\mathcal{R}_d(V)\).

Definition 24.7 Generic rank
✓
#

Let \(H\) be a graph on \(V\). The generic rank \(r_d(H)\) of \(H\) in dimension \(d\) is the rank of \(E(H)\) in \(\mathcal{R}_d(V)\).

Lemma 24.8 Row-space form of the generic rank
✓

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence, and let \(H\) be a graph on \(V\). Then

\[ r_d(H) \; =\; \dim \operatorname {span} \{ \, r_e \mid e \in E(H) \, \} , \]

where \(r_e\) is the rigidity row of \(K_V\) at \(p\) indexed by \(e\) (definition 9.4).

Proof ▶

The matroid \(\mathcal{R}_d(V)\) is \(\mathcal{L}_p(V)\) (lemma 24.5). It is represented by the extended rigidity rows \(\tilde r_e\) at \(p\) (definition 10.16), and \(\tilde r_e = r_e\) for every edge \(e\) of \(K_V\) (definition 10.14). In a represented matroid, the vectors of a set span a space whose dimension is the rank of the set (lemma 16.7). For the set \(E(H)\), this is the claim.

Lemma 24.9 The rank of the rigidity map at a generic placement
✓

Let \(p\) be a placement of \(V\) in \({\mathbb {R}}^{d}\) that is generic for row independence, and let \(H\) be a graph on \(V\). Then \(\operatorname {rank} R(H, p) = r_d(H)\).

Proof ▶

The map \(R(H, p)\) has the same rank as its transpose, whose image is spanned by the rigidity rows of \(H\) at \(p\) (lemma 9.5). For an edge \(uv\) of \(H\), the rigidity row of \(H\) at \(uv\) is \(x \mapsto \langle p_u - p_v,\, x_u - x_v \rangle \) (lemma 6.4), which is also the row of \(K_V\) at \(uv\). So the rank of \(R(H, p)\) is the dimension of the span in lemma 24.8, which is \(r_d(H)\).