Rigidity matroid

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.

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.

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.

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.

...
Wikipedia