Second-Order Theory

Definition 32 (Prestress Stability)

Let \(G=(V,E)\) be a graph and let \(F\) be a \(d\)-dimensional framework on \(G\). The framework \(F\) is called prestress stable if there exists an equilibrium stress \(\omega\) such that for every nontrivial infinitesimal flex \(q\) it holds that

\[\begin{equation*} \sum_{uv\in E} \omega_{uv}\cdot ||q_u-q_v||^2\,>\,0. \end{equation*} \]

PyRigi: is_prestress_stable()

Definition 33 (Second-order rigidity)

Let \(G=(V,E)\) be a graph and let \(F\) be a \(d\)-dimensional framework on \(G\). Let \(q\) denote an infinitesimal flex of \(F\). A second-order flex \(p''\) of \(F\) corresponding to \(q\) is defined by the equation

\[\begin{equation*} R(G, p)\cdot p'' + R(G, q)\cdot q = 0 \end{equation*} \]

for the rigidity matrix \(R(G, p)\) of \(F\). If there is no second-order flex \(p''\) for a nontrivial infinitesimal flex \(q\), we call \(F\) second-order rigid.

PyRigi: is_second_order_rigid()

Theorem 31 (Implications of the different types of rigidity)

Infinitesimal rigidity in \(\RR^d\) implies prestress stability in \(\RR^d\) which implies second-order rigidity in \(\RR^d\) which implies continuous rigidity in \(\RR^d\). None of these implications are reversible.

References: [CG17, Thm 2.6]

Theorem 32 (Equivalent criterion for second-order rigidity)

A framework \(F=(G,p)\) is second-order rigid in \(\RR^d\) if and only if for every nontrivial infinitesimal flex \(q\) of \(F\) there is an equilibrium stress \(\omega\) such that

\[\begin{equation*} \sum_{uv \in E} \omega_{uv}\cdot ||q_u-q_v||^2\,>\,0. \end{equation*} \]

References: [CG17, Thm 2.5]

While this theorem shows that second-order rigidity and prestress stability are distinguishable only by a swap of quantifiers, they are indeed separate concepts, as the following example highlights.

Example 1 (Second-order rigid framework that is not prestress stable)

Let \(G = (V, E)\) be the graph where \(V = \{1, \dots, 8\}\) and

\[\begin{equation*} E=\{\{1, 2\},\, \{1, 3\},\, \{1,4\},\, \{1, 6\},\, \{1, 7\},\, \{2,3\},\, \{2,5\},\, \{2, 7\},\, \{3, 4\},\, \{3, 5\},\, \{4,5\},\, \{4,6\},\, \{5,6\},\, \{5,7\},\, \{6, 7\}\}. \end{equation*}\]

We describe a framework on \(G\) by the realization \(p:V\rightarrow \RR^3\) defined by

\[\begin{equation*} p(1)=(0,0,0),~p(2)=p(6)=(0,1,0),~p(3)=(0,0,1),p(4)=p(7)=(1,0,0),~p(5)=(1,1,0). \end{equation*}\]

This framework has a two-dimensional set of nontrivial infinitesimal flexes and a two-dimensional set of equilibrium stresses. It is second-order rigid, but not prestress stable. References: [CW96, Exm 5.3.1]

PyRigi: SecondOrderRigid()

Checking prestress stability and second-order rigidity is generally computationally hard. In the case where there is a single stress or infinitesimal motion, the problem becomes easier:

If there is only one nontrivial infinitesimal flex \(q\), we check for a basis \((\omega^{(k)})_{k=1}^r\) of the stress space such that the stress energy \(\sum_{uv \in E} \omega^{(k)}_{uv} \cdot ||q(u)-q(v)||^2\) is always non-zero by verifying that not all of these energies become simultaneously 0 for all \(k=1,\dots,m\).

If there is only one equilibrium stress, denote a basis of the infinitesimal flex space by \((q^{(k)})_{k=1}^s\). Next, we consider the coefficients of the monomials \(({a_i}\cdot{a_j} \,:\, i,j=1,\dots,s)\) in the quadratic polynomial

\[\begin{equation*} E_{q,\omega}(a)=\sum_{uv \in E} \omega_{uv} \cdot ||\sum_{k=1}^s a_k \cdot (q^{(k)}(u)-q^{(k)}(v))||^2. \end{equation*}\]

A simple result about sums of nonnegative circuits (cf. [IdW16, Thm 3.8]) then lets us characterize the positivity of the stress energy. The SONC Criterion says that all faces on the boundary of the Newton polytope need to satisfy the SONC property. It simplifies to \(|c_{ij}| < \sqrt{4 \cdot c_{ii}\cdot c_{jj}}\) for all \(i,j\) for coefficients \(c_{ij}\) of the monomials \({a_i}\cdot{a_j}\). In addition, \(c_{ii}\) and \(c_{jj}\) need to have the same sign or be zero.

The following theorem then shows that in these two cases, prestress stability and second-order-rigidity are equivalent.

Theorem 33 (Second-order rigidity and prestress stability in the case of one-dimensional stresses or flexes)

Let \(F\) denote a \(d\)-dimensional second-order rigid framework with a one-dimensional space of nontrivial infinitesimal flexes or a one-dimensional space of equilibrium stresses. Then, \(F\) is prestress stable.

References: [CW96]

In the general case, we use the stress matrix criterion from [CW96, Prop 3.4.2].

Theorem 34 (Stress Matrix criterion for prestress stability)

A framework is prestress stable for the equilibrium stress \(\omega\) if and only if the associated stress matrix \(\Omega(\omega)\) is positive definite on any subspace of the nontrivial infinitesimal flexes.

References: [CW96]

In the method is_prestress_stable(), we examine the contraposition: If this stress matrix is globally negative definite or at least nonpositive, then the framework cannot be prestress stable.

For showing the second-order rigidity of a framework, we need to solve a semi-definite program (SDP).

Given a framework \(F\), parametrize the space of infinitesimal flexes by variables \((a_{i})_{i=1}^s\) and the space of stresses by variables \((b_{j})_{j=1}^r\). This turns the stress energy into a cubic polynomial that is homogeneous and quadratic in \(a_i\) and homogeneously linear in \(b_j\):

\[\begin{equation*} E_{q,\omega}(a,b)=\sum_{k=1}^s \sum_{uv \in E} b_k \cdot \omega^{(k)}_{uv} \cdot ||\sum_{\ell=1}^r a_\ell \cdot ( q^{(\ell)}(u)-q^{(\ell)}(v) )||^2 \end{equation*}\]

Corollary 2 (Polynomial criterion for second-order rigidity)

The framework \(F\) is second-order rigid if and only if the polynomial system in the variables \(a_i\) arising from the coefficients of \(E_{q,\omega}\) in the linear monomials \(b_j\) has only non-real nontrivial solutions.

References: equivalent second-order rigidity criterion

Otherwise, there would be an infinitesimal flex such that for any equilibrium stress it holds that the stress energy is zero.