In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn - k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.[1] [2] [3]
A framework is an undirected graph, embedded into d-dimensional Euclidean space by providing a d-tuple of Cartesian coordinates for each vertex of the graph. From a framework with n vertices and m edges, one can define a matrix with m rows and nd columns, an expanded version of the incidence matrix of the graph called the rigidity matrix. In this matrix, the entry in row e and column (v,i) is zero if v is not an endpoint of edge e. If, on the other hand, edge e has vertices u and v as endpoints, then the value of the entry is the difference between the ith coordinates of v and u.[1] [3]
The rigidity matroid of the given framework is a linear matroid that has as its elements the edges of the graph. A set of edges is independent, in the matroid, if it corresponds to a set of rows of the rigidity matrix that is linearly independent. A framework is called generic if the coordinates of its vertices are algebraically independent real numbers. Any two generic frameworks on the same graph G determine the same rigidity matroid, regardless of their specific coordinates. This is the (d-dimensional) rigidity matroid of G.[1] [3]
A load on a framework is a system of forces on the vertices (represented as vectors). A stress is a special case of a load, in which equal and opposite forces are applied to the two endpoints of each edge (which may be imagined as a spring) and the forces formed in this way are added at each vertex. Every stress is an equilibrium load, a load that does not impose any translational force on the whole system (the sum of its force vectors is zero) nor any rotational force. A linear dependence among the rows of the rigidity matrix may be represented as a self-stress, an assignment of equal and opposite forces to the endpoints of each edge that is not identically zero but that adds to zero at every vertex. Thus, a set of edges forms an independent set in the rigidity matroid if and only if it has no self-stress.[3]
The vector space of all possible loads, on a system of n vertices, has dimension dn, among which the equilibrium loads form a subspace of dimension
dn-\binom{d+1}{2}
dn-\binom{d+1}{2}
If the vertices of a framework are in a motion, then that motion may be described over small scales of distance by its gradient, a vector for each vertex specifying its speed and direction. The gradient describes a linearized approximation to the actual motion of the points, in which each point moves at constant velocity in a straight line. The gradient may be described as a row vector that has one real number coordinate for each pair
(v,i)
v
i
d
If the edges of the framework are assumed to be rigid bars that can neither expand nor contract (but can freely rotate) then any motion respecting this rigidity must preserve the lengths of the edges: the derivative of length, as a function of the time over which the motion occurs, must remain zero. This condition may be expressed in linear algebra as a constraint that the gradient vector of the motion of the vertices must have zero inner product with the row of the rigidity matrix that represents the given edge. Thus, the family of gradients of (infinitesimally) rigid motions is given by the nullspace of the rigidity matrix.[1] [3] For frameworks that are not in generic position, it is possible that some infinitesimally rigid motions (vectors in the nullspace of the rigidity matrix) are not the gradients of any continuous motion, but this cannot happen for generic frameworks.[2]
A rigid motion of the framework is a motion such that, at each point in time, the framework is congruent to its original configuration. Rigid motions include translations and rotations of Euclidean space; the gradients of rigid motions form a linear space having the translations and rotations as bases, of dimension
\binom{d+1}{2}
dn-\binom{d+1}{2}
e
S
e
S
Although defined in different terms (column vectors versus row vectors, or forces versus motions) static rigidity and first-order rigidity reduce to the same properties of the underlying matrix and therefore coincide with each other. In two dimensions, the generic rigidity matroid also describes the number of degrees of freedom of a different kind of motion, in which each edge is constrained to stay parallel to its original position rather than being constrained to maintain the same length; however, the equivalence between rigidity and parallel motion breaks down in higher dimensions.[3]
A framework has a unique realization in d-dimensional space if every placement of the same graph with the same edge lengths is congruent to it. Such a framework must necessarily be rigid, because otherwise there exists a continuous motion bringing it to a non-congruent placement with the same edge lengths, but unique realizability is stronger than rigidity. For instance, the diamond graph (two triangles sharing an edge) is rigid in two dimensions, but it is not uniquely realizable because it has two different realizations, one in which the triangles are on opposite sides of the shared edge and one in which they are both on the same side. Uniquely realizable graphs are important in applications that involve reconstruction of shapes from distances, such as triangulation in land surveying,[4] the determination of the positions of the nodes in a wireless sensor network,[5] and the reconstruction of conformations of molecules via nuclear magnetic resonance spectroscopy.[4]
Bruce Hendrickson defined a graph to be redundantly rigid if it remains rigid after removing any one of its edges. In matroidal terms, this means that the rigidity matroid has the full rank
dn-\binom{d+1}{2}
(d+1)
define a graph as being
(k,l)
n
kn-l
(k,l)
(k,l)
kn-l
(d,\binom{d+1}{2})
(d,\binom{d+1}{2})
In two dimensions, showed that the same characterization is true: the independent sets form the edge sets of (2,3)-sparse graphs and the independent rigid sets form the edge sets of (2,3)-tight graphs.[11] Based on this work the (2,3)-tight graphs (the graphs of minimally rigid generic frameworks in two dimensions) have come to be known as Laman graphs. The family of Laman graphs on a fixed set of
n
G
G
G
However, in higher dimensions not every
(d,\binom{d+1}{2})