User:MWinter4/framework (rigidity theory)

In mathematics, specifically in rigidity theory, a framework (often synonymous with bar-joint framework) models a physical structure composed of rigid bars of fixed length connected at universal joints at which the bars can move freely. Intuitively, a framework is flexible if it can change its shape (i.e. the relative position of its joints), whithout changing the length of a bar or detaching a bar from a joint. If this is not possible, the framework is rigid. Frameworks are fundamental objects of study in structural rigidity, where one aims to characterize and quantify their rigidity properties. A main mathematical tool employed in their analysis is graph theory. If the focus is on the flexibility and possible motions of the structure it is more common to use the term linkage instead of framework.

Mathematically, a framework is a pair $(G,{\boldsymbol {p}})$ composed of a graph $G=(V,E)$ and a straight-line embedding ${\boldsymbol {p}}:V\to {\mathbb {R}}^{n}$ which to each vertex $v\in V$ assigns a point $p_{v}\in {\mathbb {R}}^{n}$ . Due to their immediate applicability, the cases $n=2$ and $n=3$ are of primary interest.

Rigidity and flexibility

Two frameworks $(G,{\boldsymbol {p}})$ and $(G,{\boldsymbol {q}})$ on the same graph are equivalent if corresponding edges are of the same length:

\|p_{v}-p_{w}\|=\|q_{v}-q_{w}\|,\quad

for all edges

vw\in E

.

The two frameworks are congruent (or isometric) if all pairwise vertex distances are the same, not only pairs that form an edge:

\|p_{v}-p_{w}\|=\|q_{v}-q_{w}\|,\quad

for all vertices

v,w\in V

.

In other words, two frameworks are congruent if and only if one can be transformed into the other by a rigid motion or reflection.

A motion of $(G,{\boldsymbol {p}})$ is a continuous function ${\boldsymbol {p}}_{t}:[0,1]\times V\to {\mathbb {R}}^{n}$ with ${\boldsymbol {p}}_{0}={\boldsymbol {p}}$ so that the framework $(G,{\boldsymbol {p}}_{t})$ is equivalent to $(G,{\boldsymbol {p}})$ for all $t\in [0,1]$ . A motion is trivial if $(G,{\boldsymbol {p}}_{t})$ is congruent to $(G,{\boldsymbol {p}})$ for all $t\in [0,1]$ . A non-trivial motion is called a flex.^[a]

A framework for which there exists a flex is said to be flexible. If there is no flex, then it is said to be rigid. This notion flexibility models the idea of a continuous deformation that preserves edge lengths. Especially with view towards other forms of rigidity discussed below, it is common to also use the term locally rigid. Other notions of rigidity are common, such as infinitesimal rigidity (see the section of first-order analysis) and the following:

A framework is said to be globally rigid if every equivalent framework embedded in a space of the same dimension is congruent. This means that there is only a single way to embed this framework with these edge lengths in the space of the given dimension. A globally rigid framework is necessarily rigid, but the converse might not hold.
A framework is said to be universally rigid if every equivalent framework embedded in a space of any dimension is congruent. This means that there is only a single way to embed this framework in any Euclidean spacen, irrespective of the dimension. A universally rigid framework is necessarily globally rigid and hence rigid, but the converse might not hold.

superstable $\,\longrightarrow \,$ universally rigid $\,\longrightarrow \,$ globally rigid $\,\longrightarrow \,$ rigid

first-order rigid $\,\longrightarrow \,$ prestress stable $\,\longrightarrow \,$ second-order rigid $\,\longrightarrow \,$ rigid

In general, determining whether a framework is locally/globally/universally rigid or flexible comes down to the analysis of its configuration space:

{\mathcal {C}}(G,{\boldsymbol {p}}):=\{{\boldsymbol {q}}:V\to {\mathbb {R}}^{n}\,\mid (G,{\boldsymbol {p}})

and

(G,{\boldsymbol {q}})

are equivalent

\}\;/\;{\text{Euclidean motions}}

.

The configuaration space of a framework is a real algebraic variety defined by a number of quadratic polynomials. A framework is locally rigid if and only if it is an isolated point in its configuration space. A framework is globally rigid if and only if its configuration space consists of a single point. Analysing the configuration space directly is often not possible in any generality and restricted to time consuming computations on particular examples. Thus, either special classes of frameworks are studied (low-dimensional frameworks, planar frameworks, braced grids, etc.), or approximations of rigidity are studied (e.g. first- or higher-order analysis).

First-order analysis

The rigidity matrix of the framework $(G,{\boldsymbol {p}})$ is a matrix ${\mathcal {R}}={\mathcal {R}}(G,{\boldsymbol {p}})\in {\mathbb {R}}^{|E|\times n|V|}$ that has one column per edge of $G$ , and $n$ rows per vertex of $G$ . For each edge $e=vw\in E$ the $(1\times n)$ -submatrix of ${\mathcal {R}}$ that spans row $e$ and the $2n$ columns corresponding to $v$ and $w$ are

{\mathcal {R}}_{e,v}=p_{v}-p_{w}

,

\quad {\mathcal {R}}_{e,w}=p_{w}-p_{v}

,

where $p_{v}-p_{w}$ and $p_{w}-p_{v}$ are here interpreted as $n$ -dimensional row vectors. All other entries are zero.

First-order motions

An element of the kernel of the rigidity matrix is called a first-order motion or infinitesimal motion of the framework. A first-order motion ${\dot {\boldsymbol {p}}}$ is given by one vector ${\dot {p}}_{v}\in {\mathbb {R}}^{n}$ per vertex $v\in V$ . Being in the kernel of ${\mathcal {R}}$ means

(p_{v}-p_{w})^{\top }({\dot {p}}_{v}-{\dot {p}}_{w})=0,\quad

whenever

vw\in E.

Each differentiable motion ${\boldsymbol {p}}_{t}$ of the framework gives rise to a first-order motion. Setting

{\dot {p}}_{v}:={\tfrac {\mathrm {d} }{\mathrm {d} t}}(p_{t})_{v}|_{t=0}

(the derivative at $t=0$ ) yields a first-order motion. A first-order motion is trivial if it is obtained from a trivial motion. A non-trivial first-order motion is called a first-order flex or infinitesimal flex of the framework. In the context of first-order analysis it is not uncommon to use the term finite flex when referring to a usual flex in the sense of this article.

A framework is first-order rigid if it has no first-order flex. It is called first-order flexible otherwise. First-order rigidity is a strengthening of rigidity. Every first-order rigid framework is rigid, yet not every rigid framework is first-order rigid.

Computing the first-order motions of a framework is comparatively easy and usually one of the first steps in the analysis of its rigidity. If all first-order motions are trivial, one can already conclude that the framework is rigid. If there are first-order flexes one proceeds to determine which first-order flexes extend to a finite flexes. This is generally a hard task.

Stresses and equilibrium stresses

The elements of the cokernel of the rigidity matrix (i.e. the kernel of the transpose ${\mathcal {R}}^{\top }$ ) are called equilibrium stresses of the framework. An equilibrium stress is given by one real number $\omega _{e}\in {\mathbb {R}}$ per edge $e\in E$ . Being in the cokernel of ${\mathcal {R}}$ means that they satisfy