# The Stress-Flex Conjecture

Robert Connelly  Steven J. Gortler  Louis Theran  Martin Winter

###### Abstract

Recently, it has been proven that a tensegrity framework that arises from
coning the one-skeleton of a convex polytope is rigid. Since such frameworks
are not always infinitesimally rigid, this leaves open the question as to
whether they are at least prestress stable. We prove here that this holds
subject to an intriguing new conjecture about coned polytope frameworks, that
we call the stress-flex conjecture. Multiple numerical experiments suggest
that this conjecture is true, and most surprisingly, seems to hold even beyond
convexity and also for higher genus polytopes.

##  1 Introduction

It was recently proven by Winter [9] that if one takes the one-skeleton of a
convex polytope in $\mathbb{R}^{d}$ and cones it over an interior point, the
resulting framework is rigid. It is rigid as a bar-framework, where the edge
lengths must stay constant, and it is even rigid as a tensegrity framework,
where the “polytope edges” are allowed to get shorter and the “cone edges” are
allowed to get longer.

As an example, consider the graph $G$ with $8$ vertices and $12$ edges
obtained from the one-skeleton of a cube in $\mathbb{R}^{3}$. Cone this graph
over a $9$th point to obtain the graph $G^{*}$. If we forget about the cube’s
geometry and just choose a generic placement $\hat{\bf p}$ of the $9$ vertices
in $\mathbb{R}^{3}$, the pair $(G^{*},\hat{\bf p})$, considered as a bar
framework, will be flexible; it will have a non-trivial infinitesimal flex and
no (non-zero) equilibrium stresses. Let us now consider the (non-generic)
frameworks $(G^{*},\hat{\bf p})$, where we use the original geometry of the
cube for the first $8$ vertices and place the the cone point anywhere in
$\mathbb{R}^{3}$. Such a bar framework will have a one dimensional equilibrium
stress space and a two dimensional space of infinitesimal flexes complementary
to the trivial flexes. The actual rigidity of such a bar-framework appears to
be a subtle phenomenon and depends on exactly where the cone point is placed.
For some placements of the cone point _outside_ of the cube, we have done
numerical experiments that suggest that the bar framework will be flexible.
For some other such placements outside of the cube, we find that the framework
is (certifiably) rigid. In this context, the result of [9] tells us that
whenever the cone point is _inside_ the cube, the framework must be rigid,
both as a bar framework and even as a (less constrained) tensegrity framework.

In the rigidity literature [2] there is a condition called prestress
stability, which is stronger than rigidity (though weaker than infinitesimal
rigidity). Prestress stability is the main property used to analyze frameworks
that are not infinitesimally rigid but that might be rigid. The property can
be efficiently tested by solving an appropriate semi-definite program.

After establishing rigidity for interior coned polytopes, in [9, Question
5.2.] the paper asks whether they are also always prestress stable.
Establishing prestress stability would place the rigidity of coned polytope
frameworks more clearly within the understood rigidity landscape. There are
also practical implications. When a framework is prestress stable, one can
also use eigen-analysis to obtain certain bounds on the robustness of this
rigidity to slight violations of the length constraints of the tensegrity and
slight alterations to the original configuration (see e.g., [4, Corollary
3.3]).

In this note we explore this question, and show that it will be answered in
the affirmative if one is able to prove a conjecture we pose below, that we
call the _stress-flex conjecture_. This perhaps odd-looking conjecture is of
intrinsic interest and appears to hold under numerous numerical experiments in
three dimensions, even beyond the scope needed for prestress stability. So we
are fairly hopeful that the stress-flex conjecture, and thereby prestress
stability, can be verified.

In terms of techniques, [9] relies on a result of Izmestiev [5] that
generalizes a three-dimensional result of Lovász [7]. This result associates a
special $n$-by-$n$ matrix $M$ to a convex polytope $P$ (with $n$ vertices) in
$\mathbb{R}^{d}$ that contains the origin in its interior. Among other things,
$M$ has a single negative eigenvalue. In this note, we add an extra row and
column to $M$ to obtain $(n+1)$-by-$(n+1)$ matrix $\Omega$ with a single
negative eigenvalue. By construction, this matrix will be a stress matrix for
the framework of the coned polytope. This stress matrix is then used in our
exploration of prestress stability.

### Acknowledgements

We thank Dylan Thurston for help simplifying Lemma 4.1. We thank Miranda
Holmes-Cerfon for the use of her numerical rigidity-simulation code.

##  2 Preliminaries

Here we quickly review the basic rigidity definitions that we will need. The
key reference is [2].

######  Definition 2.1.

A _configuration_ ${\bf p}$ of $n$ points in $\mathbb{R}^{d}$ is an ordered
set of $n$ points, ${\bf p}_{i}\in\mathbb{R}^{d}$.

######  Definition 2.2.

A _tensegrity framework_ $(G,{\bf p})$ in $\mathbb{R}^{d}$ is a configuration
${\bf p}$ of $n$ points $\mathbb{R}^{d}$, and a labeled graph $G$ on $n$
vertices. The edges of $G$ are labeled as “cables”, “struts” and “bars”. We
denote by $(\bar{G},{\bf p})$ the associated _bar framework_ , where all of
the labels in $G$ are changed to be “bars”.

######  Definition 2.3.

A tensegrity framework $(G,{\bf p})$ is (locally) _rigid_ if for every
configuration ${\bf q}$ of $n$ points in $\mathbb{R}^{d}$ that is sufficiently
close to ${\bf p}$111Formally, there exists an $\epsilon$ so that for every
${\bf q}$ within this distance to ${\bf p}$, the property holds. and such that
${\bf q}$ is not congruent to ${\bf p}$, we have the property that the
Euclidean lengths of the cables are not decreased, the lengths of the struts
are not increased and the lengths of the bars are not changed.

######  Definition 2.4.

Let $(\bar{G},{\bf p})$ be a bar framework in $\mathbb{R}^{d}$. We say that a
configuration ${\bf p}^{\prime}$ of $n$ vectors in $\mathbb{R}^{d}$ is an
_infinitesimal flex_ for the framework if for all edges $ij$, we have $({\bf
p}_{i}-{\bf p}_{j})\cdot({\bf p}^{\prime}_{i}-{\bf p}^{\prime}_{j})=0$.

An infinitesimal flex is _trivial_ if there is a $d$-by-$d$ skew symmetric
matrix $S$ and a vector ${\bf t}$ such that for all $i$, ${\bf
p}^{\prime}_{i}=S{\bf p}_{i}+{\bf t}$. (Such a flex arises as the time
derivative of a continuous isometry of $\mathbb{R}^{d}$.)

If the only infinitesimal flexes for $(\bar{G},\hat{{\bf p}})$ are trivial
ones, then the bar framework is said to be _infinitesimally rigid_ which
implies that it must be rigid. The converse is not necessarily true. (There is
also an infinitesimal notion in the context of tensegrity frameworks, but we
will not go into this.)

Next we develop the idea of prestress stability. The rough idea is to
establish rigidity by defining a certain energy function over ${\bf p}$ that
only depends on the edge lengths, and then show that ${\bf p}$ is a critical
point such that the energy has a positive definite Hessian. When all of the
dust settles, we are left with the following definitions and theorem.

######  Definition 2.5.

Let $(G,{\bf p})$ be a tensegrity with $n$ vertices. An (equilibrium) _stress
matrix_ $\Omega$ of $(G,{\bf p})$ is an $n$-by-$n$ symmetric matrix with the
following properties:

  1. (i)

$\Omega_{ij}=0$ when $i\neq j$ and $ij$ is not an edge of $G$.

  2. (ii)

$\Omega{\bf p}=0$, where we think of ${\bf p}$ as an $n$-by-$d$ matrix.

  3. (iii)

$\Omega{\bf 1}=0$, where ${\bf 1}$ is a vector of all ones.

The stress is called _strictly proper_ if $\Omega_{ij}<0$ when $ij$ is a cable
and $\Omega_{ij}>0$ when $ij$ is a strut.

######  Definition 2.6 (See [2, Proposition 3.4.2].).

A tensegrity framework $(G,{\bf p})$ in $\mathbb{R}^{d}$ is _prestress stable_
if it has a strictly proper equilibrium stress matrix $\Omega$, such that for
every non-trivial infinitesimal flex ${\bf p}^{\prime}$ of its bar-framework
$(\bar{G},{\bf p})$, we have

$\displaystyle\operatorname{tr}({\bf p}^{\prime t}\Omega{\bf p}^{\prime})>0$
(1)

where we think of ${\bf p}^{\prime}$ as an $n$-by-$d$ matrix.

Finally, we recall the following.

######  Theorem 2.7 ([2, Proposition 3.3.2]).

If a tensegrity framework is prestress stable, then it is rigid.

The converse does not always hold.

##  3 Izmestiev Stress

Let $P\subset\mathbb{R}^{d}$ be a convex polytope with $n$ vertices, with a
full affine span and with the origin in its interior. Let ${\bf p}$ be its
vertex configuration and let $G$ be the graph of its one-skeleton. Izmestiev
[5] constructs an $n$-by-$n$ symmetric matrix $M$, that we call the _Izmestiev
matrix_ , with the following properties:

  1. (i)

$M_{ij}=0$ when $i\neq j$ and $ij$ is not an edge of $G$.

  2. (ii)

$M_{ij}<0$ when $ij$ is an edge of $G$.

  3. (iii)

$M{\bf p}=0$, where we think of ${\bf p}$ as an $n$-by-$d$ matrix.

  4. (iv)

$M$ has rank $n-d$.

  5. (v)

$M$ has exactly one negative eigenvalue.

Our goal is to use $M$ to construct an equilibrium stress $\Omega$ for the
framework $(G^{*},\hat{\bf p})$ obtained by coning the one-skeleton of $P$
over the origin. Let $\alpha^{t}:=-{\bf 1}^{t}M$ and
$b:=-\sum_{i}\alpha_{i}={\bf 1}^{t}M{\bf 1}$. The $\alpha_{i}$ are also known
as the (unnormalized) Wachspress coordinates of the origin with respect to $P$
[9], and so each is greater than $0$, and $b$ is negative. We define the
$(n+1)$-by-$(n+1)$ matrix in block form as follows:

$\displaystyle\Omega:=\begin{pmatrix}M&\alpha\\\ \alpha^{t}&b\end{pmatrix}$

The added row/column are linearly dependent on $M$, and thus the rank of
$\Omega$ is also $n-d$, and its nullity is $d+1$. Since $M$ has one negative
eigenvalue, and $\Omega$ just has an extra $0$ eigenvalue, from the eigenvalue
interlacing theorem, $\Omega$ must also have exactly one negative eigenvalue.

Let ${\bf p}_{n+1}$ be placed at the origin and let $\hat{\bf p}:=[{\bf
p},{\bf p}_{n+1}]$ be the configuration of $n+1$ points in $\mathbb{R}^{d}$.
Then, since ${\bf p}_{n+1}=0$ we have $\Omega\hat{\bf p}=0$. By our definition
of $\alpha$ and $b$, we have $\Omega{\bf 1}=0$. Let us label the edges of
$G^{*}$ from the polytope as cables and the coned edges as struts. We see that
$\Omega$ is a strictly proper equilibrium stress for $(G^{*},\hat{\bf p})$. We
call this an _Izmestiev stress_.

Finally we note that the space of stresses for a framework does not change
under translation in $\mathbb{R}^{d}$. Thus we can start with $P$ as any
convex polytope with $n$ vertices and a full affine span in $\mathbb{R}^{d}$
and with ${\bf p}_{n+1}$ any point in the interior of $P$. We can create its
associated coned tensegrity, and it must have an Izmestiev stress.

##  4 One Negative Eigenvalue

Prestress stability, and in particular Equation (1), is based on positivity of
a quadratic energy. Our stress matrix $\Omega$ has one negative eigenvalue
that we need to work around. Our main tool for doing this is the following
lemma.

######  Lemma 4.1.

Let $\Omega$ be an $(n+1)$-by-$(n+1)$ real symmetric matrix. Assume the
following:

  1. (i)

$\Omega$ has exactly one negative eigenvalue.

  2. (ii)

$\Omega_{n+1,n+1}<0$.

If $\hat{\bf x}\in\mathbb{R}^{n+1}$ has the property that the $(n+1)$st entry
of $\Omega\hat{\bf x}$ equals $0$, then $\hat{\bf x}^{t}\Omega\hat{\bf x}\geq
0$.

###### Proof.

Let ${\bf e}$ be the $(n+1)$st indicator vector. By assumption ${\bf
e}^{t}\Omega{\bf e}<0$, so the vector, ${\bf e}$ is in the negative cone of
$\Omega$. Meanwhile, since the last entry of $\Omega\hat{\bf x}$ equals $0$,
we have ${\bf e}^{t}\Omega\hat{\bf x}=0$, i.e., $\hat{\bf x}$ is
$\Omega$-orthogonal to ${\bf e}$. Together, since $\Omega$ has only a single
negative eigenvalue, this implies $\hat{\bf x}^{t}\Omega\hat{\bf x}\geq 0$. ∎

Similar ideas to Lemma 4.1 are used in [6].

##  5 The Stress-Flex Conjecture

The Izmestiev stress $\Omega$ satisfies the assumptions of Lemma 4.1. If we
can show that each of the $d$ spatial coordinates of $\hat{\bf p}^{\prime}$
have the properties of the vector $\hat{\bf x}$ in that lemma, then we can
apply this to establish prestress stability. The following conjectures just
that:

######  Conjecture 5.1 (The _stress-flex conjecture_).

Let $P$ be a convex polytope with $n$ vertices with a full dimensional span in
$\mathbb{R}^{d}$. Let $(G^{*},\hat{\bf p})$ be the tensegrity framework on
$n+1$ vertices defined by putting cables on the one-skeleton of $P$ and struts
from the vertices of $P$ to a selected cone point in the interior of $P$. Let
$\Omega$ be its Izemstiev stress. Let $\hat{\bf p}^{\prime}$ be an
infinitesimal flex of its bar framework. Then the last row of $\Omega\hat{\bf
p}^{\prime}$ equals zero.

When the last row of $\Omega\hat{\bf p}^{\prime}$ equals zero, we say that the
_stress-flex condition_ is satisfied. Note that this condition is always
satisfied for trivial infinitesimal flexes, since in this case $\hat{\bf
p}^{\prime}$ is an affine image of $\hat{\bf p}$ and so $\Omega\hat{\bf
p}^{\prime}=0$.

We have done many numerical experiments in 3D whose results support this
conjecture. These results included (simple) convex polytopes defined by the
intersection of random planes as well a number of polytopes from the wonderful
library at [8].

In fact, this appears to be an even more robust property than stated by the
conjecture. First of all, the stress-flex condition experimentally holds even
when we place the cone point outside of the polytope. We have also looked at
polytopes where the equilibrium stress space of $(G^{*},\hat{\bf p})$ has
dimension larger than one. For example, when $P$ is the cuboctahedron, the
coned framework has a $4$ dimensional stress space and it has a non-trival
infinitesimal flex. When $P$ is the rhombic dodecahedron, the coned framework
has a $2$ dimensional stress space and it has a $3$ dimensional space of
flexes complementary to the trivial flexes. In these cases, the stress-flex
condition holds for any of the stresses, not just the Izmestiev stress.

We have also looked at non-convex polyhedra and non-embedded polyhedra where
there are stresses and non-trivial infinitesimal flexes, and the stress-flex
condition continues to hold. We have looked at higher genus polyhedra, such as
Szilassi Polyhedron. We have even looked at non-orientable polyhedra such as
the cubohemioctahedron. In all of these cases, the stress-flex condition still
holds. Moreover, the stress-flex condition holds for the hypercube in
$\mathbb{R}^{4}$, coned anywhere.

In light of these experiments, we propose the following _strong stress-flex
conjecture_.

######  Conjecture 5.2.

Let $P$ be any “polytope” with a full dimensional affine span in
$\mathbb{R}^{d}$. Let ${\bf p}_{n+1}$ be placed anywhere in $\mathbb{R}^{d}$.
Let $\Omega$ be _any_ stress for the bar framework defined using one-skeleton
of $P$ coned over ${\bf p}_{n+1}$. Let $\hat{\bf p}^{\prime}$ be any
infinitesimal flex of the bar framework. Then the the stress-flex condition
holds.

In this conjecture, we have chosen to not exactly pin-down what we mean by
“polytope”, but it seems that we need nothing more than a closed surface with
flat faces.

We note that if one starts with a convex polytope coned from inside, and then
slides the vertices along their lines to the cone vertex, even though the
face-flatness is not maintained, the dimension of the stress space and
infinitesimal flex space is maintained. It also can be shown that the property
of prestress stability is maintained under such sliding. But we observe that
for generic sliding the stress-flex condition is not maintained. So the face-
flatness appears to be crucial for the stress-flex condition.

###  5.1 Another Point of View

It can also be shown that the strong stress-flex conjecture is equivalent to
the following: Start with any polytope $P$ with full affine span in
$\mathbb{R}^{d}$. Let $(G,{\bf p})$ be the bar framework of its one-skeleton.
Let $(G,{\bf q})$ be the orthogonal projection to $\mathbb{R}^{d-1}$ by
forgetting the last coordinate. Let $\Psi$ be any equilibrium stress matrix
for $(G,{\bf q})$. Let ${\bf q}^{\prime}$ be any infinitesimal flex of
$(G,{\bf q})$ in $\mathbb{R}^{d-1}$. Then the following two conditions must
hold:

$\displaystyle({\bf p}^{d})^{t}\Psi{\bf q}^{\prime}=0$

where ${\bf p}^{d}$ is the $d$th spatial coordinate of ${\bf p}$ and we think
of ${\bf q}^{\prime}$ as an $n$-by-$(d-1)$ matrix and

$\displaystyle({\bf p}^{d})^{t}\Psi({\bf q}^{\prime}\cdot{\bf q})=0$

where $({\bf q}^{\prime}\cdot{\bf q})_{i}:={\bf q}^{\prime}_{i}\cdot{\bf
q}_{i}$.

##  6 Prestress Stability of a Convex Polytope, Coned From Inside

Finally we tie things together, and prove that under the (weak) stress-flex
conjecture, we must have prestress stability. There is not much to do here,
other than use the properties of the Izmestiev stress and Lemma 4.1. This will
tell us that any infinitesimal flex must be an affine flex. All that is left
is to string together some previous results that let us conclude that this
affine flex must be a trivial flex.

######  Theorem 6.1.

Let $P$ be a convex polytope with $n$ vertices with a full dimensional span in
$\mathbb{R}^{d}$. Let $(G^{*},\hat{\bf p})$ be the tensegrity framework on
$n+1$ vertices defined by putting cables on the one-skeleton of $P$ and struts
from the vertices of $P$ to a selected cone point in the interior of $P$.

Assume the (weak) stress-flex conjecture (Conjecture 5.1) is true, then the
resulting framework is prestress stable.

###### Proof.

From Section 3, $(G^{*},\hat{\bf p})$ must have an Izmestiev stress. This
stress has exactly one negative eigenvalue and its lower-right entry is
negative. Under the stress-flex conjecture, for any infinitesimal flex
$\hat{\bf p}^{\prime}$ of of $(\bar{G},\hat{\bf p})$, we have the last row of
$\Omega\hat{\bf p}^{\prime}$ is equal to zero. Using Lemma 4.1 we must have
$\operatorname{tr}({\bf p}^{\prime t}\Omega{\bf p}^{\prime})\geq 0$.

Next we show that if $\operatorname{tr}({\bf p}^{\prime t}\Omega{\bf
p}^{\prime})=0$, then ${\bf p}^{\prime}$ must be a trivial flex. From Lemma
4.1, if $\operatorname{tr}({\bf p}^{\prime t}\Omega{\bf p}^{\prime})=0$ then
we must have (each of the $d$ spatial coordinates of) ${\bf p}^{\prime}$ in
the kernel of $\Omega$. From the structure of the kernel of $\Omega$, this
makes ${\bf p}^{\prime}$ an “affine flex” of ${\bf p}$, i.e. for all $i$,
${\bf p}^{\prime}_{i}=A{\bf p}_{i}+{\bf t}$ for some matrix $A$ and vector
${\bf t}$.

Suppose this affine flex is not trivial. From [1, Lemmas A.3, A.7], this
implies that $(\bar{G^{*}},\hat{\bf p})$ has its “edges on a conic at
infinity” (see that paper for definitions). Since this is a coned framework,
from [3, Lemma 4.10] the framework must be “ruled” (see that paper for
definitions). But the one skeleton of a convex polytope cannot be ruled ([3,
Prop 3.4].)

Thus for a non-trivial flex $\hat{\bf p}$, the inequality of Equation (1) must
hold, making $(G^{*},\hat{\bf p})$ prestress stable.

∎

## References

  * Connelly and Gortler [2017] R. Connelly and S. J. Gortler.  Prestress stability of triangulated convex polytopes and universal second-order rigidity.  _SIAM Journal on Discrete Mathematics_ , 31(4):2735–2753, 2017.
  * Connelly and Whiteley [1996] R. Connelly and W. Whiteley.  Second-order rigidity and prestress stability for tensegrity frameworks.  _SIAM J. Discrete Math._ , 9(3):453–491, 1996\.  ISSN 0895-4801.
  * Connelly et al. [2018] R. Connelly, S. J. Gortler, and L. Theran.  Affine rigidity and conics at infinity.  _International Mathematics Research Notices_ , 2018(13):4084–4102, 2018.
  * Holmes-Cerfon et al. [2021] M. Holmes-Cerfon, L. Theran, and S. J. Gortler.  Almost-rigidity of frameworks.  _Communications on Pure and Applied Mathematics_ , 74(10):2185–2247, 2021.
  * Izmestiev [2010] I. Izmestiev.  The colin de verdiere number and graphs of polytopes.  _Israel Journal of Mathematics_ , 178(1):427–444, 2010.
  * Izmestiev [2014] I. Izmestiev.  Infinitesimal rigidity of convex polyhedra through the second derivative of the hilbert–einstein functional.  _Canadian Journal of Mathematics_ , 66(4):783–825, 2014.
  * Lovász [2001] L. Lovász.  Steinitz representations of polyhedra and the colin de verdiere number.  _Journal of Combinatorial Theory, Series B_ , 82(2):223–236, 2001.
  * [8] D. I. McCooey.  Visual polyhera.  http://dmccooey.com/polyhedra/.
  * Winter [2023] M. Winter.  Rigidity, tensegrity, and reconstruction of polytopes under metric constraints.  _International Mathematics Research Notices_ , 2023.