The next time it's pouring rain and you're clinging to that umbrella like it's your most prized possession, take the opportunity to look up and see the beauty of the mathematics above you.

Grasping the Math That's Over Your Head

Jessica Sidman
Amherst College

Audrey St. John
Mount Holyoke College

How does your umbrella transform from its folded state (roughly a line segment) to a protective portable shelter?  Using ideas from calculus, linear algebra, and combinatorics, "rigidity theory" provides a theoretical framework for analyzing structures like your umbrella.  Perhaps unexpectedly, it can also be used to study settings that do not involve physical structures, such as sensor network localization and the computation of maximum likelihood thresholds in statistics.  

As researchers, we see applications of rigidity theory all around us, and we highlight some examples below.   

 

As educators, we appreciate the opportunity rigidity theory brings to highlight the power of mathematics for students.  Coupling topics seen early in an undergraduate curriculum (calculus and linear algebra) with a physical application can help build intuition for synthesizing ideas that may be siloed by individual courses in a student's mind.  We hope to convince you of this through our discussion of a small example that may seem like a toy yet exhibits surprisingly complicated behavior and appears as a substructure in many other real-world designs. 

What can we learn from an umbrella?

Take a closer look at an umbrella and you'll notice that, although its design is 3-dimensional, its underlying framework consists of 2-dimensional subframeworks. This same design principle appears in many real-world frameworks composed of bars connected by joints, such as folding chairs, tent frameworks, and scissor lifts.  In what follows, we'll restrict ourselves to studying planar frameworks in which bars are attached at their endpoints via rotational joints.

The cross-section of an umbrella shown below highlights the part that controls its motion: a cycle of four fixed-length bars attached at rotational joints that we call a "4-bar" framework. 

When the umbrella opens, joint 1 stays fixed while joint 3 slides up; this causes joints 2 and 4 to move away from each other.  Locking joint 3 into place fixes its distance to joint 1 so that the umbrella maintains a rigid shape.

As the umbrella is moving, we see a flexible 4-bar framework.  By locking it in place we have essentially added a fifth bar, and we obtain a framework that is composed of two triangles glued together.  Physical intuition tells us that a framework built from triangles in this way should be rigid.

This prompts more general questions:  How do we build a framework with a desired motion?  What makes a framework rigid?  What mathematics can we develop to determine if a framework is rigid or not?

What is possible with just 4 bars?

As engineers have known for hundreds of years, a 4-bar framework can exhibit a large range of interesting and useful behaviors.  For example, producing linear motion from the rotational motion of a motor is well-studied.  The animations in Figure 3 show how the Watt and Chebyshev linkages approach this.  A node P placed on the bars between joints 2 and 3 follows a nearly linear motion.  The path traced out by this node is called a "coupler curve."

You may wonder what other coupler curves arise as we vary the lengths of the bars. The figures below illustrate some possibilities.

What is the mathematics of a framework?

In rigidity theory, we define a framework as a finite collection of $n$ joints, where some pairs are connected by bars that fix the distance between them.  If we know the bar lengths and want to understand the possible motions of the framework, a reasonable starting point is to construct the system of quadratic equations capturing these distance constraints.  Each joint has two unknown coordinates $(x_i, y_i)$ while each bar is expressed via a quadratic equation.

For example, a triangle with bar lengths 3, 4, and 5 gives rise to a system of three equations in six unknowns:  

$$\begin{align*}
(x_1-x_2)^2+(y_1-y_2)^2 & = 9\\
(x_1-x_3)^2+(y_1-y_3)^2 & = 16\\
(x_2-x_3)^2+(y_2-y_3)^2 & = 25.
\end{align*}$$

This system has a 3-dimensional solution set.  Below, we depict one solution in (a), together with a solution (b) obtained by translation and another (c) that is both a translation and a rotation of (a).  The triangle (d) is another solution, but cannot be obtained by moving the triangle (a) within the plane—it is a reflection of the original triangle.  In fact the solution set has two components, one consisting of rotations and translations of (a) and the other consisting of rotations and  translations of (d).

You'll notice all solutions display the same shape, as the triangle is intuitively "rigid."  What is the physical intuition for the 3 dimensions of the solution space, then? In the plane, every object has "trivial motions" that can arise from two translational degrees of freedom and one rotational degree of freedom.  If we don't want to be distracted by these trivial motions, we can specify three joint coordinates to eliminate them, say $(x_1,y_1) = (0,0)$, and $x_2 = 3$.  We are left with the system of equations

$$\begin{align*}
9+y_2^2 & = 9\\
x_3^2+y_3^2 & = 16\\
(3-x_3)^2+(y_2-y_3)^2 & = 25,
\end{align*}$$

which has a 0-dimensional solution set containing only two solutions: the triangles shown in (a) and (d) above.

Let's return to our analysis of the 4-bar framework from the umbrella.  All of the bars have length 1.  As with the triangle, we choose 3 coordinates to remove the trivial motions. By fixing joint 1 at $(0,0)$ and constraining joint 3 to move along the $y$-axis, we obtain the following quadratic system with a 1-dimensional solution space: 

$$\begin{align*}
9+y_2^2 & = 9\\
x_3^2+y_3^2 & = 16\\
(3-x_3)^2+(y_2-y_3)^2 & = 25,
\end{align*}$$

This matches what we know about umbrellas—they move with a single degree of freedom!  

In fact, using only high school algebra, we can solve for the trajectories of the four points explicitly:

$$\begin{align*}
(x_1, y_1) & = (0,0)\\
(x_2, y_2) &= (-\sqrt{1-t^2/4}, t/2)\\
(x_3, y_3) &= (0,t)\\
(x_4, y_4) &= (\sqrt{1-t^2/4}, t/2)
\end{align*}$$

where we’ll take $-2 \leq t \leq -1$.  Here, we see that as the parameter $t$ varies, vertices 2, 3, and 4 each trace out a curve as in our animation of the umbrella framework.

However, given the complexity of the possible coupler curves we've already seen, one can imagine that solving for joint trajectories may be difficult for an arbitrary 4-bar.  In general, solving a system of nonlinear equations is computationally and theoretically challenging, taking us into the realm of algebraic geometry.  So where can we turn to develop effective tools to analyze frameworks?

How can we simplify the analysis? Enter, calculus and linear algebra!

As is often the case in mathematics, when we have a difficult problem, we can make it more tractable through a linearization step.  In doing so we lose some information to gain the theory and computational efficiency of linear algebra.  This step can be an “aha” moment for students as it allows them to see how to use calculus to pass from a hard problem to an easier one, and connects both subjects to a concrete physical problem.

Assuming the coordinates of the vertices are smooth functions of time $x_i(t)$ and $y_i(t)$ allows us to use implicit differentiation and the chain rule to linearize our system of quadratic equations.  For example, if there is a bar of length $\ell_{ij}$ joining the $i$th and $j$th joints, we have the quadratic equation

$$(x_i-x_j)^2+(y_i-y_j)^2 = \ell_{ij}^2.$$

Differentiating both sides, we have

$$\begin{align*}
\frac{d\left( (x_i-x_j)^2+(y_i-y_j)^2 \right)}{dt} &= \frac{d (\ell_{ij}^2)}{dt}\\
2(x_i-x_j)(x_i'-x_j') +2(y_i-y_j)(y_i'-y_j') & = 0\\
\Leftrightarrow (x_i-x_j, y_i-y_j) \cdot (x_i'-x_j', y_i'-y_j') & = 0.
\end{align*}$$

Instead of trying to solve for the functions $x_i(t)$ and $y_i(t)$ parameterizing the motion of the curves, let us now turn our attention to solving for the vectors $x_i'(t)$ and $y_i'(t)$ satisfying these linear equations.  Recognizing that the final equation has a geometric interpretation—the vector pointing from the $j$th joint to the $i$th joint must be orthogonal to the difference of the velocity vectors of the joints—lets us connect to the intuition that, at this instant, the velocity vectors are not stretching or compressing the bar.

In rigidity theory, a solution of this homogenous linear system is an "infinitesimal motion," and we package these linear equations into an $m \times 2n$ matrix called the "rigidity matrix."  Each bar is associated to one row, and each joint to two columns.  For any fixed values of the joint coordinates, the rigidity matrix has entries that are real numbers.  For example, the rigidity matrix for the first triangle with bars of length 3, 4, and 5 that we drew, with vertices at the origin and on the positive $x$ and $y$ axes, has columns corresponding to the coordinates $x_1$, $y_1$, $x_2$, $y_2$, and $x_3$, $y_3$:

$$R =
\begin{bmatrix} -3 & 0 & 3 & 0 & 0 & 0\\
0 & -4 & 0 & 0 & 0 & 4\\
0 & 0 & 3 & -4 & -3 & 4 \end{bmatrix}
$$

This linearization puts us in the realm of material encountered by sophomore math majors.  We especially appreciate the opportunity to give physical interpretations to objects from linear algebra that often feel abstract to a novice.  The null space of the rigidity matrix has an interpretation in terms of kinematics as the set of infinitesimal motions.  The row space also has an interpretation in terms of statics (that we do not have space to develop here) as the set of forces that can be applied at the vertices for which the framework remains in equilibrium.  

Using linear algebra, we can investigate the space of infinitesimal motions of a framework.  For example, one can check that the matrix $R$ has nullspace with basis

$$\begin{bmatrix}
1\\
0 \\
1\\
0\\
1\\
0
\end{bmatrix}, \begin{bmatrix}
0 \\
1\\
0\\
1\\
0\\
1
\end{bmatrix},
\begin{bmatrix}
0\\
0 \\
0\\
1\\
-\frac43\\
0
\end{bmatrix}$$

corresponding to trivial infinitesimal motions, as depicted in the figure below.

Returning to our analysis of the motion of an umbrella, suppose that the 4-bar has joint coordinates $(0,0)$, $(-\sqrt{3}/2,-1/2)$, $(\sqrt{3}/2,-1/2)$, $(0,-1)$. We obtain this rigidity matrix and a basis for its null space: 

$$\begin{bmatrix}
x_1-x_2 & y_1-y_2 & x_2-x_1 & y_2 - y_1 & 0 & 0\\
x_1-x_3 & y_1-y_3 & 0 & 0 & x_3-x_1 & y_3 - y_1 \\
0 & 0 &x_2-x_3 & y_2-y_3 & x_3-x_2 & y_3 - y_2
\end{bmatrix}.$$  

As with the triangle, the first three vectors for the null space correspond to translation and rotation.  The last vector corresponds to the nontrivial infinitesimal motion illustrated below.

Here is a snapshot showing vectors at a fixed time $t=-1$:

You'll notice that, since joint 1 is not moving, the velocity vectors for joints 2 and 4 are orthogonal to the bars connecting them to joint 1. This matches the intuition that the motion must instantaneously not be stretching or shrinking the bar. For a bar where both endpoints are moving, we can illustrate the fact that the relative instantaneous velocity is orthogonal. 

Where can we go next? Enter, combinatorics!

The rigidity matrix has a distinct combinatorial pattern in general, which we can observe for an arbitrary triangle with joint coordinates $(x_, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$:

$$R = \begin{bmatrix}
\frac{\sqrt{3}}2 & \frac12 & -\frac{\sqrt{3}}2 & -\frac12 & 0 & 0 & 0 & 0\\
0 & 0 & -\sqrt{3} & 0 & \sqrt{3} & 0 & 0 & 0\\
0 & 0 & 0 & 0 & \frac{\sqrt{3}}2 & \frac12 & -\frac{\sqrt{3}}2 & -\frac12 \\
\frac{\sqrt{3}}2 & \frac12 & 0 & 0 & 0 & 0 & -\frac{\sqrt{3}}2& -\frac12
\end{bmatrix}, \ \ \ \ \
\begin{bmatrix}
1\\
0 \\
1\\
0\\
1\\
0\\
1\\
0
\end{bmatrix}, \begin{bmatrix}
0 \\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{bmatrix},
\begin{bmatrix}
0\\
0 \\
1/2\\
-\sqrt{3}/2\\
1/2\\
\sqrt{3}/2\\
1\\
0
\end{bmatrix},
\begin{bmatrix}
0\\
0\\
\sqrt{3}/12\\
1/4\\
0\\
1/2\\
-\sqrt{3}/12\\
1/4
\end{bmatrix}.$$

The nonzero entries in a row appear only in columns associated with the endpoints of the bar, suggesting that combinatorics plays an important role in rigidity.  Indeed, for almost all "generic" choices of triangle coordinates, this matrix has rank 3.  When its rank is less than 3, then the three joints lie on a line.  Paradoxically, this "flattened triangle" has a nontrivial infinitesimal motion as in the figure below but is still rigid, highlighting that combinatorial results in rigidity theory only match our intuition for generic frameworks.

We leave you with one of the foundational results in rigidity theory, proved independently by Geiringer and Laman: a combinatorial characterization of minimally rigid generic frameworks, where minimality means using the fewest possible bars needed for rigidity.  For a 2-dimensional framework with $n$ joints, there must be $2n-3$ bars in total, distributed so that no $n' \geq 2$ joints have more than $2n'-3$ bars among them. Intriguingly, this result does not generalize to dimension 3, and a combinatorial characterization of 3-dimensional rigidity is arguably the biggest open problem in rigidity theory. We encourage the reader interested in further exploration to check out the resources below!

For further exploration

• Jack Graver, Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures, Dolciani Math. Exp., 25, MAA, Washington D.C., 2001.
• Jack Graver, Brigitte Servatius, Herman Servatius, Combinatorial Rigidity Theory, Grad. Stud. Math., AMS, Providence, RI, 1993.
• Jessica Sidman and Audrey St. John. Frameworks in Motion: resources for learning rigidity theory.