10 The planar rigidity matroid
In section 9 we proved one half of the characterization of the independent sets of the rigidity matroid in the plane by Pollaczek-Geiringer [ PG27 ] and Laman [ Lam70 ] : an edge set that is row-independent at a framework in the plane with no three points collinear forms a \((2,3)\)-sparse graph (lemma 9.12). In this section we prove the other half: the edge set of every \((2,3)\)-sparse graph is row-independent at some framework in the plane, which Pollaczek-Geiringer proves in her §8 (p. 70). The two halves together are Jordán’s [ Jor16 ] Theorem 2.2.1, which he credits to Laman, and we follow his proof (p. 45). We then describe the rigidity matroid in the plane as a matroid on the edges of a complete graph.
The proof is an induction that removes a vertex and puts it back by a Henneberg move (section 5). A vertex whose removal leaves a smaller \((2,3)\)-sparse graph exists by the reverse decomposition at the end of section 3 (theorem 3.19). We show in section 10.1 that putting it back preserves row-independence at a suitable framework, and we complete the induction in section 10.2.
For a finite set \(V\), let \(K_V\) be the complete graph on \(V\). In section 10.3 we define the planar rigidity matroid \(\mathcal{R}(V)\) by counting: its independent sets are the sets of edges of \(K_V\) that form \((2,3)\)-sparse graphs. By the characterization, these are the edge sets that are row-independent at some framework in the plane. In section 10.4 we show that \(\mathcal{R}(V)\) is the rigidity matroid of a suitable framework of \(K_V\).
Throughout, frameworks and the rigidity map \(R(G, p)\) are as in section 6, and we write \(uv\) for the edge with endpoints \(u\) and \(v\). The rows \(r_e\) of \(R(G, p)\) and row-independent edge sets are defined in section 9.
The reverse decomposition (theorem 3.19) describes the smaller graphs \(G - v\) and \(G - v + ab\) directly, and not as graphs from which a move rebuilds \(G\). In the formalization the difference matters. A move produces a graph on a new vertex set (formalization note 5.3), so the move applied to \(G - v\) gives a graph isomorphic to \(G\), not \(G\) itself. A reverse decomposition starts from \(G\), and it is stated in terms of \(G\). The lifts of section 10.1, like the results of section 7, are statements about what a move does, and they are stated for the graph that the move produces. Where a proof uses both kinds of result, as in theorem 10.9, we pass between them by an isomorphism from \(G\) to the graph obtained by the move, built from the neighbours of \(v\).
10.1 Lifting row-independence through Henneberg moves
In this subsection we prove the inductive step of the induction in section 10.2: if \(E(G)\) is row-independent at a framework \(p\), and \(G'\) is obtained from \(G\) by a move, then \(E(G')\) is row-independent at some framework. For the Type I move at \(a\) and \(b\) we assume that \(p_a \ne p_b\). In Jordán’s proof the step is his Lemmas 1.2.2 and 1.2.3 (p. 38): if the points involved are in general position, a \(0\)-extension or a \(1\)-extension in the plane raises the rank of the rigidity matrix by two. As in section 7, we first prove the statement for the framework \(\hat p\) that extends a given framework \(p\) by placing the new vertex \(v\) at a given point \(q\), and then choose \(q\).
Let \(G\) be a graph on a set \(V\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent. Let \(a, b \in V\), and let \(G'\) be obtained from \(G\) by the Type I move at \(a\) and \(b\), with new vertex \(v\). Let \(q \in {\mathbb {R}}^{2}\) be a point such that \(q - p_a\) and \(q - p_b\) are linearly independent, and let \(\hat p\) be the framework on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and places \(v\) at \(q\). Then \(E(G')\) is row-independent at \(\hat p\).
For an edge \(e\) of \(G\), let \(r_e\) be the rigidity row of \(G\) at \(p\) indexed by \(e\), and for an edge \(e\) of \(G'\), let \(\hat r_e\) be the rigidity row of \(G'\) at \(\hat p\) indexed by \(e\) (definition 9.4). Since \(q - p_a\) and \(q - p_b\) are linearly independent, \(a \ne b\). So the edges of \(G'\) are the edges of \(G\) and the two new edges \(va\) and \(vb\) (lemma 5.4). Suppose that
We show that every coefficient is zero.
For \(\alpha \in {\mathbb {R}}^{2}\), let \(x^{\alpha } \in ({\mathbb {R}}^{2})^{V \cup \{ v\} }\) give \(v\) the velocity \(\alpha \) and every vertex of \(G\) the velocity zero. If \(e\) is an edge of \(G\), then \(\hat r_e(x^{\alpha }) = 0\), since both ends of \(e\) have velocity zero (lemma 6.4). At a new edge, \(\hat r_{va}(x^{\alpha }) = \langle q - p_a,\, \alpha \rangle \). Evaluating the relation at \(x^{\alpha }\) therefore gives \(\langle c_a (q - p_a) + c_b (q - p_b),\, \alpha \rangle = 0\) for every \(\alpha \). Hence \(c_a (q - p_a) + c_b (q - p_b) = 0\), and \(c_a = c_b = 0\), since \(q - p_a\) and \(q - p_b\) are linearly independent.
It remains to show that \(\sum _e c_e\, \hat r_e = 0\) forces every \(c_e\) to be zero. Let \(\rho : ({\mathbb {R}}^{2})^{V \cup \{ v\} } \to ({\mathbb {R}}^{2})^{V}\) be the restriction \(x \mapsto x|_V\). If \(e = uw\) is an edge of \(G\), then both \(\hat r_e(x)\) and \(r_e(\rho (x))\) equal \(\langle p_u - p_w,\, x_u - x_w \rangle \), so \(\hat r_e = r_e \circ \rho \). Hence \(\bigl(\sum _e c_e\, r_e\bigr) \circ \rho = 0\). Since \(\rho \) is surjective, \(\sum _e c_e\, r_e = 0\). So every \(c_e\) is zero, because \(E(G)\) is row-independent at \(p\) (lemma 9.6).
Let \(G\) be a graph on a set \(V\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent. Let \(a, b \in V\) with \(p_a \ne p_b\), and let \(G'\) be obtained from \(G\) by the Type I move at \(a\) and \(b\), with new vertex \(v\). Then there is a framework \(\hat p\) on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and at which \(E(G')\) is row-independent.
Since \(p_a \ne p_b\), there is a unique line through \(p_a\) and \(p_b\). Choose a point \(q\) off this line. Then \(q - p_a\) and \(q - p_b\) are linearly independent. Let \(\hat p\) extend \(p\) by placing \(v\) at \(q\). Then \(E(G')\) is row-independent at \(\hat p\) (lemma 10.2).
A vertex of degree one, a pendant vertex, is put back by the Type I move at \(a\) and \(a\), which adds a new vertex \(v\) and the single edge \(va\) (definition 5.1). Jordán’s proof treats this case together with the Type I move.
Let \(G\) be a graph on a set \(V\), let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent, and let \(a \in V\). Let \(G'\) be obtained from \(G\) by the Type I move at \(a\) and \(a\), with new vertex \(v\). Then there is a framework \(\hat p\) on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and at which \(E(G')\) is row-independent.
Choose a point \(q \ne p_a\), and let \(\hat p\) extend \(p\) by placing \(v\) at \(q\). Let \(r_e\), \(\hat r_e\) and \(x^{\alpha }\) be as in the proof of lemma 10.2. The edges of \(G'\) are the edges of \(G\) and the new edge \(va\). Suppose that \(\sum _{e \in E(G)} c_e\, \hat r_e + c_a\, \hat r_{va} = 0\). Evaluating this relation at \(x^{\alpha }\) with \(\alpha = q - p_a\) gives \(c_a |q - p_a|^{2} = 0\), so \(c_a = 0\). Then \(\sum _e c_e\, \hat r_e = 0\), and every \(c_e\) is zero, as in the proof of lemma 10.2.
Let \(G\) be a graph on a set \(V\), let \(ab\) be an edge of \(G\), and let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent. Let \(c \in V\), and let \(G'\) be obtained from \(G\) by the Type II move on \(ab\) and \(c\), with new vertex \(v\). Let \(q = p_a + s\, (p_b - p_a)\) for a real number \(s \ne 0, 1\), suppose that \(q - p_a\) and \(q - p_c\) are linearly independent, and let \(\hat p\) be the framework on \(V \cup \{ v\} \) that agrees with \(p\) on \(V\) and places \(v\) at \(q\). Then \(E(G')\) is row-independent at \(\hat p\).
Let \(r_e\), \(\hat r_e\), \(x^{\alpha }\) and \(\rho \) be as in the proof of lemma 10.2. The vertices \(a\), \(b\) and \(c\) are distinct: \(a \ne b\) since \(ab\) is an edge, and \(c \ne a, b\) since \(q - p_a\) and \(q - p_c\) are linearly independent. So the edges of \(G'\) are the edges of \(G\) other than \(ab\) and the three new edges \(va\), \(vb\) and \(vc\) (lemma 5.6). Suppose that
where \(e\) runs over the edges of \(G\) other than \(ab\).
Let \(\delta = p_b - p_a\), so that \(q - p_a = s\, \delta \) and \(q - p_b = (s - 1)\, \delta \). Evaluating the relation at \(x^{\alpha }\) gives
for every \(\alpha \), so \((s c_a + (s - 1) c_b)\, \delta + c_c\, (q - p_c) = 0\). Since \(s \ne 0\), the vector \(\delta \) is a multiple of \(q - p_a\), and \(q - p_a\) and \(q - p_c\) are linearly independent. Hence \(s c_a + (s - 1) c_b = 0\) and \(c_c = 0\).
We use the first equation to recover the row of the deleted edge \(ab\), as in the proof of theorem 7.3. For every \(x\) we have, by lemma 6.4 and the first equation,
and \(\langle \delta ,\, x_b - x_a \rangle = \langle p_a - p_b,\, x_a - x_b \rangle = r_{ab}(\rho (x))\). So \(c_a\, \hat r_{va} + c_b\, \hat r_{vb} = s c_a\, (r_{ab} \circ \rho )\). The other rows satisfy \(\hat r_e = r_e \circ \rho \), so the relation becomes
Since \(\rho \) is surjective, \(\sum _e c_e\, r_e + s c_a\, r_{ab} = 0\). As \(E(G)\) is row-independent at \(p\), every \(c_e\) is zero and \(s c_a = 0\). So \(c_a = 0\), since \(s \ne 0\), and then \(c_b = 0\), since \(s \ne 1\).
For the Type II move we move one point of the framework slightly, as in the proof of theorem 7.5. This needs row-independence to be an open condition on the framework, as infinitesimal rigidity is (lemma 6.17). In the induction we also transport row-independence along graph isomorphisms, as we did for infinitesimal rigidity (lemma 6.14).
Let \(G\) be a graph on a finite set \(V\), let \(I \subseteq E(G)\), and let \(p_0\) be a framework on \(V\) in \({\mathbb {R}}^{d}\) at which \(I\) is row-independent. Then \(I\) is row-independent at every framework in some neighbourhood of \(p_0\) in \(({\mathbb {R}}^{d})^{V}\).
Fix a basis \(\xi _1, \dots , \xi _n\) of \(({\mathbb {R}}^{d})^{V}\). A linear functional \(\ell \) on \(({\mathbb {R}}^{d})^{V}\) is determined by the vector \((\ell (\xi _1), \dots , \ell (\xi _n)) \in {\mathbb {R}}^{n}\), and the map sending \(\ell \) to this vector is a linear isomorphism. For a framework \(p\), let \(r_e\) be the rigidity row of \(G\) at \(p\) indexed by \(e\) (definition 9.4). By lemma 9.6 and this isomorphism, \(I\) is row-independent at \(p\) if and only if the vectors \((r_e(\xi _1), \dots , r_e(\xi _n))\), for \(e \in I\), are linearly independent in \({\mathbb {R}}^{n}\).
For \(e = uw\), the entry \(r_e(\xi _k)\) is the inner product of \(p_u - p_w\) with \((\xi _k)_u - (\xi _k)_w\) (lemma 6.4), so it depends continuously on \(p\). Linear independence of finitely many vectors in \({\mathbb {R}}^{n}\) is an open condition. Hence it holds for every \(p\) in some neighbourhood of \(p_0\).
Let \(G\) and \(H\) be graphs on sets \(V\) and \(W\), let \(\varphi \) be an isomorphism from \(G\) to \(H\), and let \(q\) be a framework on \(W\) in \({\mathbb {R}}^{d}\). If \(E(H)\) is row-independent at \(q\), then \(E(G)\) is row-independent at \(q \circ \varphi \).
Let \(L : ({\mathbb {R}}^{d})^{V} \to ({\mathbb {R}}^{d})^{W}\) be the linear isomorphism \(x \mapsto x \circ \varphi ^{-1}\). For an edge \(e = uv\) of \(G\), let \(r_e\) be the rigidity row of \(G\) at \(q \circ \varphi \) indexed by \(e\), and let \(r^{H}_{\varphi (e)}\) be the rigidity row of \(H\) at \(q\) indexed by the edge \(\varphi (u)\varphi (v)\) (definition 9.4). Both \(r_e(x)\) and \(r^{H}_{\varphi (e)}(L(x))\) equal \(\langle q_{\varphi (u)} - q_{\varphi (v)},\, x_u - x_v \rangle \), so \(r_e = r^{H}_{\varphi (e)} \circ L\).
Suppose that \(\sum _e c_e\, r_e = 0\). Then \(\bigl(\sum _e c_e\, r^{H}_{\varphi (e)}\bigr) \circ L = 0\), and so \(\sum _e c_e\, r^{H}_{\varphi (e)} = 0\), since \(L\) is surjective. The map \(e \mapsto \varphi (e)\) is a bijection from the edges of \(G\) to those of \(H\), and \(E(H)\) is row-independent at \(q\). So every \(c_e\) is zero.
Let \(G\) be a graph on a finite set \(V\), let \(ab\) be an edge of \(G\), and let \(c \in V\) be distinct from \(a\) and \(b\). Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent, and let \(G'\) be obtained from \(G\) by the Type II move on \(ab\) and \(c\), with new vertex \(v\). Then there is a framework on \(V \cup \{ v\} \) at which \(E(G')\) is row-independent.
We shall place \(v\) on the line through \(p_a\) and \(p_b\), which needs \(p_c\) off this line (lemma 10.5). So we first move \(p\), keeping \(E(G)\) row-independent, until \(p_a\), \(p_b\) and \(p_c\) are not collinear. The row \(r_{ab}\) of \(R(G, p)\) is not zero, since \(E(G)\) is row-independent at \(p\). Hence \(p_a \ne p_b\) (lemma 6.4). If \(p_b - p_a\) and \(p_c - p_a\) are linearly independent, we keep \(p\).
Otherwise \(p_c - p_a = \gamma \, (p_b - p_a)\) for some \(\gamma \in {\mathbb {R}}\). Choose a vector \(w \in {\mathbb {R}}^{2}\) such that \(w\) and \(p_b - p_a\) are linearly independent. For \(t \in {\mathbb {R}}\), let \(p^{t}\) be the framework that agrees with \(p\) except at \(c\), where \(p^{t}_c = p_c + t\, w\). The map \(t \mapsto p^{t}\) is continuous, and \(p^{0} = p\). So \(E(G)\) is row-independent at \(p^{t}\) for every \(t\) close enough to \(0\) (lemma 10.6). Since \(c\) is neither \(a\) nor \(b\), we have \(p^{t}_b - p^{t}_a = p_b - p_a\) and \(p^{t}_c - p^{t}_a = \gamma \, (p_b - p_a) + t\, w\). For \(t \ne 0\) these two vectors are linearly independent, because \(w\) and \(p_b - p_a\) are. Choose \(t \ne 0\) close enough to \(0\), and replace \(p\) by \(p^{t}\).
Now let \(q = p_a + \tfrac {1}{2}(p_b - p_a)\), the midpoint of \(p_a\) and \(p_b\). Then \(q - p_a = \tfrac {1}{2}(p_b - p_a)\) and \(q - p_c = \tfrac {1}{2}(p_b - p_a) - (p_c - p_a)\). These two vectors are linearly independent, because \(p_b - p_a\) and \(p_c - p_a\) are. So lemma 10.5 applies with \(s = \tfrac {1}{2}\), and \(E(G')\) is row-independent at the framework that extends \(p\) by placing \(v\) at \(q\).
10.2 Row-independent edge sets in the plane
We now complete the induction. Together with lemma 9.12, its result characterizes the edge sets that are row-independent at some framework in the plane.
Let \(V\) be finite, and let \(G\) be a \((2, 3)\)-sparse graph on \(V\). Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent.
We use induction on \(|V|\); Jordán’s proof inducts on the number of edges instead. If \(G\) has no edges, for instance if \(|V| \le 1\), then \(E(G)\) is row-independent at every framework, since the empty family of rows is linearly independent.
Suppose that \(G\) has an edge. By theorem 3.19, \(G\) has a vertex \(v\) of degree one, two or three for which the following graph \(H\) on \(V \setminus \{ v\} \) is \((2,3)\)-sparse. If \(v\) has degree one or two, with neighbour \(a\) or neighbours \(a\) and \(b\), then \(H = G - v\). If \(v\) has degree three, with neighbours \(a\), \(b\) and \(c\), where \(a\) and \(b\) are not adjacent, then \(H = G - v + ab\). By induction, \(E(H)\) is row-independent at some framework \(p\) on \(V \setminus \{ v\} \) in \({\mathbb {R}}^{2}\).
Let \(H'\) be obtained from \(H\) by the move that puts \(v\) back: the Type I move at \(a\) and \(a\) if \(v\) has degree one, the Type I move at \(a\) and \(b\) if \(v\) has degree two, and the Type II move on \(ab\) and \(c\) if \(v\) has degree three. The map \(\varphi \) that sends \(v\) to the new vertex of \(H'\) and fixes every other vertex is an isomorphism from \(G\) to \(H'\) (formalization note 10.1). If \(E(H')\) is row-independent at a framework \(\hat p\), then \(E(G)\) is row-independent at \(\hat p \circ \varphi \) (lemma 10.7). So it remains to find such a framework \(\hat p\).
If \(v\) has degree one, then lemma 10.4 gives \(\hat p\). If \(v\) has degree three, then \(ab\) is an edge of \(H\) and \(c\) is distinct from \(a\) and \(b\), so lemma 10.8 gives \(\hat p\).
Let \(v\) have degree two. If \(p_a \ne p_b\), then lemma 10.3 gives \(\hat p\). Otherwise we first move the point \(p_a\). Choose a nonzero vector \(w \in {\mathbb {R}}^{2}\), and for \(t \in {\mathbb {R}}\) let \(p^{t}\) be the framework that agrees with \(p\) except at \(a\), where \(p^{t}_a = p_a + t\, w\). The map \(t \mapsto p^{t}\) is continuous, and \(p^{0} = p\). So \(E(H)\) is row-independent at \(p^{t}\) for every \(t\) close enough to \(0\) (lemma 10.6). Since \(a \ne b\), we have \(p^{t}_a - p^{t}_b = t\, w\), which is not zero for \(t \ne 0\). Choose \(t \ne 0\) close enough to \(0\). Then lemma 10.3 applies to \(p^{t}\) and gives \(\hat p\).
Let \(V\) be finite, let \(G\) be a graph on \(V\), and let \(I \subseteq E(G)\). Then \(I\) is row-independent at some framework on \(V\) in \({\mathbb {R}}^{2}\) if and only if the spanning subgraph of \(G\) with edge set \(I\) is \((2, 3)\)-sparse.
Suppose first that \(I\) is row-independent at a framework \(p_0\). Then \(I\) is row-independent at every framework in some neighbourhood of \(p_0\) (lemma 10.6). So there is a framework \(p\) at which \(I\) is row-independent and no three of the points \(p_v\) are collinear (lemma 9.11 at \(d = 2\)). Hence the spanning subgraph of \(G\) with edge set \(I\) is \((2, 3)\)-sparse (lemma 9.12).
Conversely, let \(H\) be the spanning subgraph of \(G\) with edge set \(I\), and suppose that \(H\) is \((2, 3)\)-sparse. Then \(E(H) = I\) is row-independent at some framework \(p\) (theorem 10.9). For an edge \(e = uv\) in \(I\), the rigidity rows of \(H\) and of \(G\) at \(p\) indexed by \(e\) are the same functional \(x \mapsto \langle p_u - p_v,\, x_u - x_v \rangle \) (lemma 6.4). So \(I\), as a set of edges of \(G\), is row-independent at \(p\).
Let \(V\) be finite, and let \(G\) be a Laman graph on \(V\). Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) at which \(E(G)\) is row-independent.
A Laman graph is \((2, 3)\)-sparse (definition 4.1), so theorem 10.9 applies.
10.3 The rigidity matroid as a count matroid
Let \(V\) be finite. For \(\ell {\lt} 2k\), the sets of edges of \(K_V\) that form \((k, \ell )\)-sparse graphs are the independent sets of a matroid on \(E(K_V)\), the \((k, \ell )\)-count matroid. We prove this in the next section (section 11), and use it here for \((k, \ell ) = (2, 3)\), where \(3 {\lt} 4\). We take the \((2, 3)\)-count matroid as the definition of the rigidity matroid in the plane, and then identify its independent sets with the edge sets that are row-independent at some framework.
Let \(V\) be finite. The planar rigidity matroid \(\mathcal{R}(V)\) is the \((2, 3)\)-count matroid on \(V\) (definition 11.7): the matroid on \(E(K_V)\) whose independent sets are the sets \(I \subseteq E(K_V)\) for which the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse.
Let \(V\) be finite, and let \(I \subseteq E(K_V)\). Then \(I\) is independent in \(\mathcal{R}(V)\) if and only if \(I\) is row-independent at some framework on \(V\) in \({\mathbb {R}}^{2}\).
Since \(I \subseteq E(K_V)\), the set \(I\) is independent in \(\mathcal{R}(V)\) if and only if the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse (theorem 11.9). This graph is the spanning subgraph of \(K_V\) with edge set \(I\). So the claim is theorem 10.10 at \(G = K_V\).
10.4 The rigidity matroid of a framework
Jordán (p. 39) defines the rigidity matroid of a framework \((G, p)\) as the matroid on \(E(G)\) whose independent sets are the edge sets that are row-independent at \(p\), and notes that all generic frameworks of \(G\) have the same rigidity matroid. By theorem 10.13, a set of edges of \(K_V\) is independent in \(\mathcal{R}(V)\) exactly when it is row-independent at some framework, which may depend on the set. Rather than define genericity, we find a single framework \(p\) at which every independent set of \(\mathcal{R}(V)\) is row-independent. This identifies \(\mathcal{R}(V)\) with the rigidity matroid of the framework \((K_V, p)\).
We now define the rigidity matroid of a framework of \(K_V\), in any dimension. Its formal construction starts from the rigidity rows of \(K_V\), extended to all unordered pairs of vertices.
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(r_e\), for \(e \in E(K_V)\), be the rigidity rows of \(K_V\) at \(p\) (definition 9.4). The extended rigidity rows at \(p\) are the functionals \(\tilde r_e \in (({\mathbb {R}}^{d})^{V})^{*}\), for unordered pairs \(e\) of elements of \(V\), given by \(\tilde r_e = r_e\) if \(e \in E(K_V)\) and \(\tilde r_e = 0\) if \(e = \{ v, v\} \) for some \(v \in V\).
The extension is needed only for the formal construction of the matroid in the next definition. That construction, Matroid.ofFun in Nelson’s matroid library, takes a function defined on all unordered pairs of vertices, together with a ground set. The pairs \(\{ v, v\} \) lie outside the ground set \(E(K_V)\), so the values \(\tilde r_{\{ v, v\} } = 0\) do not affect the matroid.
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\). The linear rigidity matroid \(\mathcal{L}_p(V)\) at \(p\) is the matroid on \(E(K_V)\) represented by the extended rigidity rows at \(p\): a set \(I \subseteq E(K_V)\) is independent if the functionals \(\tilde r_e\), for \(e \in I\), are linearly independent.
Let \(p\) be a framework on \(V\) in \({\mathbb {R}}^{d}\), and let \(I \subseteq E(K_V)\). Then \(I\) is independent in \(\mathcal{L}_p(V)\) if and only if \(I\) is row-independent at \(p\).
For \(e \in E(K_V)\), the extended row \(\tilde r_e\) is the rigidity row \(r_e\) of \(K_V\) at \(p\). So \(I\) is independent in \(\mathcal{L}_p(V)\) if and only if the rows \(r_e\), for \(e \in I\), are linearly independent, that is, if and only if \(I\) is row-independent at \(p\) (lemma 9.6).
So \(\mathcal{L}_p(V)\) is the rigidity matroid of the framework \((K_V, p)\), and it remains to choose \(p\).
Let \(V\) be finite. Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) such that every \(I \subseteq E(K_V)\) is row-independent at \(p\) whenever the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse.
Let \(\mathcal{S}\) be the family of sets \(I \subseteq E(K_V)\) for which the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse. It is finite, since \(E(K_V)\) is. We show, by induction on \(n\), that for any \(n\) sets in \(\mathcal{S}\) there is a framework at which all of them are row-independent; for \(n = |\mathcal{S}|\) this is the lemma. For \(n = 0\) any framework will do.
Let \(\mathcal{F} \subseteq \mathcal{S}\) have \(n\) elements, let \(p_0\) be a framework at which every set in \(\mathcal{F}\) is row-independent, and let \(I_0 \in \mathcal{S} \setminus \mathcal{F}\). Then \(I_0\) is row-independent at some framework \(q\) (theorem 10.10 at \(G = K_V\)). For \(t \in {\mathbb {R}}\), let \(p^{t} = p_0 + t\, (q - p_0)\), so that \(p^{0} = p_0\) and \(p^{1} = q\). The rigidity row of an edge \(uv\) at a framework \(p'\) is \(x \mapsto \langle p'_u - p'_v,\, x_u - x_v \rangle \) (lemma 6.4), which depends linearly on \(p'\). So the row \(r^{t}_e\) of an edge \(e\) at \(p^{t}\) is \(r^{0}_e + t\, s_e\), where \(s_e\) is the row of \(e\) at \(q - p_0\).
Let \(I\) be a set in \(\mathcal{F}\), or \(I_0\), and let \(t_0\) be \(0\) or \(1\) accordingly, so that the rows \(r^{t_0}_e\), for \(e \in I\), are linearly independent. Fix a basis of \((({\mathbb {R}}^{2})^{V})^{*}\). The coordinate vectors of the rows \(r^{t}_e\), for \(e \in I\), are the rows of a matrix \(A + t\, B\), where \(A\) and \(B\) do not depend on \(t\). Since the rows of \(A + t_0 B\) are linearly independent, some \(|I| \times |I|\) submatrix of \(A + t_0 B\) has nonzero determinant. The determinant of the same submatrix 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 \(r^{t}_e\), for \(e \in I\), are linearly independent.
Hence there are only finitely many \(t \in {\mathbb {R}}\) at which some set in \(\mathcal{F}\), or \(I_0\), fails to be row-independent at \(p^{t}\). Choose \(t\) outside these finitely many values. Then every set in \(\mathcal{F}\), and \(I_0\), is row-independent at \(p^{t}\).
Let \(V\) be finite. Then there is a framework \(p\) on \(V\) in \({\mathbb {R}}^{2}\) such that \(\mathcal{L}_p(V) = \mathcal{R}(V)\).
Let \(p\) be a framework as in lemma 10.18. Both matroids have ground set \(E(K_V)\), so it suffices to show that they have the same independent sets. Let \(I \subseteq E(K_V)\). If \(I\) is independent in \(\mathcal{L}_p(V)\), then \(I\) is row-independent at \(p\) (lemma 10.17), and so \(I\) is independent in \(\mathcal{R}(V)\) (theorem 10.13). Conversely, if \(I\) is independent in \(\mathcal{R}(V)\), then the graph on \(V\) with edge set \(I\) is \((2, 3)\)-sparse (definition 10.12). So \(I\) is row-independent at \(p\), by the choice of \(p\), and it is independent in \(\mathcal{L}_p(V)\).