1. Introduction
A simplicial complex X is a family of subsets of some finite set V, such that if
$\sigma \in X$
, then
$\tau \in X$
for all
$\tau \subset \sigma $
. The elements of X are called the simplices or faces of X. The dimension of a face
$\sigma \in X$
is defined as
$|\sigma |-1$
. The dimension of the complex X is the maximum dimension of a simplex in X. For a k-dimensional simplicial complex X and
$i=0,1,\ldots ,k$
, we denote by
$X_i$
the set of i-dimensional faces of X. The set
$X_0$
of
$0$
-dimensional faces of X is called the vertex set of X.
Let X be a k-dimensional simplicial complex, and let
$\mathbf {{p}}\in (\mathbb {R}^d)^{|X_0|}$
be an embedding of its vertex set
$X_0$
in
$\mathbb {R}^d$
. For
$0\le i\le k$
and
$\tau \in X_i$
, we denote by
$\mathbf {{p}}(\tau )$
the convex hull of the image of
$\tau $
under
$\mathbf {{p}}$
, and by
$\mathrm {vol}_{i}(\tau )$
its i-dimensional volume.
Let
$v_X:(\mathbb {R}^d)^{|X_0|}\to \mathbb {R}^{|X_k|}$
map an embedding of
$X_0$
in
$\mathbb {R}^d$
to the vector of squared k-volumes of its k-dimensional simplices. That is, for
$\mathbf {{p}}\in (\mathbb {R}^d)^{|X_0|}$
,
$v_X(\mathbf {{p}})\in \mathbb {R}^{|X_k|}$
is defined by
$$\begin{align*}v_X(\mathbf{{p}})_{\sigma}= \mathrm{vol}_k(\sigma)^2 \end{align*}$$
for all
$\sigma \in X_k$
. We define the
$(k,d)$
-volume rigidity matrix of X at an embedding
$\mathbf {{p}}\in (\mathbb {R}^d)^{|X_0|}$
to be
$$ \begin{align*}{\cal B}(X,\mathbf{{p}}):=J_{v_X}(\mathbf{{p}}),\end{align*} $$
the Jacobian matrix of
$v_X$
at the point
$\mathbf {{p}}$
, which is an
$|X_k|\times d|X_0|$
matrix.
We index the rows of
${\cal B}(X,\mathbf {{p}})$
by simplices in
$X_k$
, and every d consecutive columns of
${\cal B}(X,\mathbf {{p}})$
by the vertices in
$X_0$
. Using the fact that for every
$\sigma \in X_k$
and
$v\in \sigma $
,
$\mathrm {vol}_k(\sigma )=\mathrm {vol}_{k-1}(\sigma \setminus \{v\})\cdot h/k$
, where h is the altitude of
$\mathbf {{p}}(\sigma )$
with respect to
$\mathbf {{p}}(v)$
, it is easy to check that
$$ \begin{align} {\cal B}(X,\mathbf{{p}})_{\sigma,v}= \begin{cases} \frac{2 \mathrm{vol}_k(\sigma)}{k}\cdot \mathrm{vol}_{k-1}(\sigma\setminus\{v\}) N_{\sigma,v}& \quad v\in \sigma,\\ 0& \quad \text{otherwise}, \end{cases} \end{align} $$
for all
$\sigma \in X_k$
and
$v\in X_0$
, where
$N_{\sigma ,v}\in \mathbb {R}^d$
stands for the unit vector parallel to the altitude of
$\mathbf {{p}}(\sigma )$
with respect to
$\mathbf {{p}}(v)$
(pointing from the
$(k-1)$
-flat spanned by
$\mathbf {{p}}(\sigma \setminus \{v\})$
to
$\mathbf {{p}}(v)$
).
We define the
$(k,d)$
-volume rigidity matroid of X, denoted by
${\cal M}_{k,d}(X)$
, to be the matroid whose elements are the k-simplices of X and its independent sets correspond to linearly independent sets of rows of the matrix
${\cal B}(X,\mathbf {{p}})$
, for a genericFootnote 1
$\mathbf {{p}}$
. Note that
${\cal M}_{1,d}(X)$
is the standard d-rigidity matroid of the graph
$G=(X_0,X_1)$
; see, for example, [Reference Connelly and Guest5, Reference Graver, Servatius and Servatius9, Reference Jordán11, Reference Asimow and Roth1, Reference Asimow and Roth2] for relevant background. The matroid
${\cal M}_{d,d}(X)$
, corresponding to the case
$k=d$
, was introduced in ([Reference Lubetzky and Peled13], Appendix A) (see also [Reference Borcea and Streinu3]) and further studied in [Reference Bulavka, Nevo and Peled4].
Let
$\Delta _{n,k}$
denote the complete k-dimensional simplicial complex on n vertices. We introduce the following definition of k-volume rigidity in
$\mathbb {R}^d$
.
Definition 1.1. Let X be a k-dimensional simplicial complex on n vertices, and let
$d\ge k$
. We say that X is k-volume rigid in
$\mathbb {R}^d$
if
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(X))=\mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k})).\end{align*} $$
The following is our main result.
Theorem 1.2. Let
$d\ge 2$
. Let
$k,n$
such that either (i)
$k=d-1$
and
$n\ge d+2$
, or (ii)
$1\le k\le d-2$
and
$n\ge d+1$
. Then,
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k}))=dn-\binom{d+1}{2}. \end{align*} $$
The proof of Theorem 1.2 consists of two main steps. First, we apply an inductive argument to reduce the problem to the case
$n=d+2$
(when
$k=d-1$
) or
$n=d+1$
(when
$1\le k\le d-2$
). Then, we analyze these base cases by showing, in each case, that the corresponding
$(k,d)$
-volume rigidity matrix (for a specific choice of embedding
$\mathbf {{p}}$
) is tightly related to certain “subset inclusion matrix,” introduced by Gottlieb in [Reference Gottlieb8] (and independently by Graver and Jurkat in [Reference Graver and Jurkat10], and by Wilson in [Reference Wilson20]).
Remarks.
-
1. The case
$k=1$
is a well-known result about the standard d-rigidity matroid (see, e.g., [Reference Jordán11]). The case
$k=d$
behaves differently. Indeed, it was shown by Lubetzky and Peled ([Reference Lubetzky and Peled13], Appendix A) that, for all
$n\ge d+1$
,
$$ \begin{align*}\mathrm{rank}({\cal M}_{d,d}(\Delta_{n,d}))=dn-(d^2+d-1).\end{align*} $$
-
2. The case
$k=d-1$
and
$n=d+1$
, excluded from Theorem 1.2, follows by similar arguments. Indeed, it is easy to show that in this case we have
$\mathrm {rank}({\cal M}_{d-1,d}(\Delta _{d+1,d-1}))=d+1$
(see Proposition 3.3). -
3. Let us mention that a related, but different, notion of rigidity for simplicial complexes was studied by Lee in [Reference Lee12] (building on previous unpublished work by Filliman), and further developed by Tay, White, and Whiteley in [Reference Tay, White and Whiteley15, Reference Tay, White and Whiteley16] (see also [Reference Tay and Whiteley17]).
The paper is organized as follows. In Section 2 we prove some preliminary results that will be used later. In Section 3 we present the proof of our main result, Theorem 1.2. In Section 4 we propose a conjecture providing a characterization for the rank of the
$(k,d)$
-volume rigidity matroid of a complex in terms of the standard rigidity matroid of its
$1$
-skeleton, and discuss some of its consequences.
2. Preliminary results
2.1. Adding a vertex
Let X be a simplicial complex, and let
$v\in X_0$
. We denote by
$X\setminus v$
the simplicial complex on vertex set
$X_0\setminus \{v\}$
whose simplices are all the simplices of X that do not contain v. We define the link of v in X to be the subcomplex of X consisting of all simplices of the form
$\sigma \setminus \{v\}$
, where
$v\in \sigma \in X$
.
Lemma 2.1 (Vertex addition lemma).
Let
$1\le k\le d-1$
and let
$n\ge d+1$
. Let X be a k-dimensional simplicial complex on n vertices and let
$v\in X_0$
be a vertex whose link in X contains a complete
$(k-1)$
-dimensional complex on at least d vertices. Then,
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(X)) \ge \mathrm{rank}({\cal M}_{k,d}(X\setminus v))+d.\end{align*} $$
Proof. Let
$\mathbf {{p}}$
be a generic embedding of
$X_0$
in
$\mathbb {R}^d$
. Consider the matrices
${\cal B}={\cal B}(X,\mathbf {{p}})$
and
${\cal B}'={\cal B}(X\setminus v, \mathbf {{p}}|_{X_0\setminus \{v\}})$
. Our goal is to show that
$$ \begin{align*}\mathrm{rank}({\cal B})\ge\mathrm{rank}({\cal B}')+d. \end{align*} $$
By assumption, the link of v in X contains a complete
$(k-1)$
-dimensional complex Y with at least d vertices. Let
$v_1,\ldots ,v_d\in X_0\setminus \{v\}$
be distinct vertices in Y. Let
$$\begin{align*}\Sigma= \{ \eta\cup\{v\} :\, \eta\subset\{v_1,\ldots,v_d\},\,|\eta|=k\}. \end{align*}$$
That is,
$\Sigma $
is the set of k-simplices that are the union of v with a k-subset of
$\{v_1,\ldots ,v_d\}$
. Note that all the elements of
$\Sigma $
are simplices of X. Let
$\hat X$
be the subcomplex of X defined by
$\hat {X}_i=X_i$
for
$0\le i\le k-1$
, and
$$ \begin{align*}\hat X_k:=(X\setminus v)_k\cup \Sigma.\end{align*} $$
Let
$\hat {\cal B}= {\cal B}(\hat {X},\mathbf {{p}})$
. As
$\hat {X}_k\subset X_k$
and
$\hat {X}_0 = X_0$
, we obtain
$\hat {\cal B}$
from
${\cal B}$
by removing some of its rows. Hence,
$$\begin{align*}\mathrm{rank}({\cal B})\ge\mathrm{rank}(\hat{{\cal B}}). \end{align*}$$
Fixing an ordering on the rows of
$\hat {\cal B}$
so that the rows corresponding to the k-simplices in
$\Sigma $
are last, and an ordering on its columns so the d columns corresponding to the vertex v are last, we get that
$\hat {\cal B}$
is a block lower-triangular matrix, consisting of two diagonal blocks: one of them is
${\cal B}'$
, and the other, which we denote by
${\cal B}"$
, is the
$\binom {d}{k}\times d$
submatrix of
${\cal B}$
corresponding to the rows of
$\Sigma $
and to the d columns associated with v. Note that, by our assumption on k, we have that
$\binom {d}{k}\ge d$
.
We claim that
$\mathrm {rank}({\cal B}")=d$
. Indeed, in view of (1.1), the rows of
${\cal B}"$
correspond to a scaling of the vectors
$N_{\sigma ,v}(\mathbf {{p}})$
, for
$\sigma \in \Sigma $
. For
$\sigma \in \Sigma $
, let
$y_{\sigma }(\mathbf {{p}})$
be the foot of the altitude of
$\mathbf {{p}}(\sigma )$
with respect to
$\mathbf {{p}}(v)$
. Note that, assuming that
$\mathbf {{p}}(v)$
does not lie in the affine span of
$\mathbf {{p}}(v_1),\ldots ,\mathbf {{p}}(v_d)$
, the vectors
$\{N_{\sigma ,v}(\mathbf {{p}})\}_{\sigma \in \Sigma }$
linearly span
$\mathbb {R}^d$
if and only if the affine span of
$\{y_{\sigma }(\mathbf {{p}})\}_{\sigma \in \Sigma }$
in
$\mathbb {R}^d$
has dimension
$d-1$
. Now, consider a special embedding
$\mathbf {{p}}'\in (\mathbb {R}^d)^{|X_0|}$
that maps the vertices
$v,v_1,\ldots ,v_d$
to the vertices of a regular d-simplex in
$\mathbb {R}^d$
. Observe that for each
$\sigma \in \Sigma $
,
$y_{\sigma }(\mathbf {{p}}')$
is the barycenter of
$\mathbf {{p}}'(\sigma \setminus \{v\})$
. It is easy to see that the convex hull of
$\{y_{\sigma }(\mathbf {{p}}')\}_{\sigma \in \Sigma }$
has dimension
$d-1$
, thus the vectors
$\{N_{\sigma ,v}(\mathbf {{p}}')\}_{\sigma \in \Sigma }$
linearly span
$\mathbb {R}^d$
. Finally, the entries of
${\cal B}"$
are algebraic expressions in the entries of the embedding
$\mathbf {{p}}$
, and thus, as
$\mathbf {{p}}$
is generic, the vectors
$\{N_{\sigma ,v}(\mathbf {{p}})\}_{\sigma \in \Sigma }$
also linearly span
$\mathbb {R}^d$
, or equivalently,
$\mathrm {rank}({\cal B}")=d$
. Thus, we obtain
$$\begin{align*}\mathrm{rank}({\cal B})\ge\mathrm{rank}(\hat{{\cal B}}) \ge \mathrm{rank}({\cal B}') +d, \end{align*}$$
as wanted.
2.2. Cayley–Menger formula
Consider a k-dimensional simplex,
$\sigma $
, with vertices
$\{0,1,\ldots ,k\}$
, embedded in
$\mathbb {R}^d$
(for some
$d\ge k$
). For
$0\le i<j\le k$
, let
$d_{ij}$
denote the distance between the vertices i and j. Recall that by the Cayley–Menger formula (see, for example, [Reference Fiedler7, Chapter 1]), we have
$$ \begin{align} \mathrm{vol}_k^2(\sigma)= g(d_{01},d_{02},\ldots,d_{k-1,k}):= \frac{(-1)^{k+1}}{(k!)^22^k}\det\begin{bmatrix} 0 & d_{01}^2 & d_{02}^2 & \dots & d_{0k}^2&1 \\ d_{01}^2 &0 & d_{12}^2 & \dots & d_{1k}^2&1 \\ d_{02}^2 &d_{12}^2 & 0 & \dots & d_{2k}^2&1 \\ \vdots &\vdots & \vdots & \ddots & \vdots&\vdots \\ d_{0k}^2 &d_{1k}^2 & d_{2k}^2 & \dots & 0&1 \\ 1 &1 & 1 & \dots & 1&0 \end{bmatrix}. \end{align} $$
Lemma 2.2. Let
$f(t)=g(\sqrt {t},d_{02},\ldots ,d_{k-1,k})$
denote the squared k-volume of a k-dimensional simplex on
$\{0,1,\ldots ,k\}$
whose edge lengths
$d_{ij}>0$
are fixed, except for the edge
$\{0,1\}$
whose squared length is a parameter t. Assume that the
$(k-2)$
-simplex on vertices
$\{2,\ldots ,k\}$
is nondegenerate. Let
$t_0,t_{\pi /2},t_{\pi }$
be the values of t for which the angle between the simplices
$\{0\}\cup \{2,\ldots ,k\}$
and
$\{1\}\cup \{2,\ldots ,k\}$
is
$0$
,
$\pi /2$
, and
$\pi $
, respectively. Note that the domain of f is the closed interval
$[t_0,t_{\pi }]$
. Then, for
$t\in (t_0,t_{\pi })$
,
$f'(t)\ne 0$
unless
$t=t_{\pi /2}$
.
Proof. Using the Cayley–Menger formula (2.1) and setting
$t=d_{01}^2$
, we get
$$ \begin{align*}f(t)= At^2+Bt+C, \end{align*} $$
for some constants
$A,B,C$
. It is easy to verify that
$$ \begin{align*}A= \begin{cases} \tfrac{-1}{16}& \quad k=2,\\ \tfrac{-1}{4k^2(k-1)^2}\mathrm{vol}_{k-2}^2(\sigma_{01})&\quad k>2,\end{cases} \end{align*} $$
where
$\sigma _{01}$
stands for the
$(k-2)$
-dimensional simplex spanned by
$\{2,\ldots ,k\}$
. In particular, (by the assumption that
$\sigma _{01}$
is nondegenerate) we have
$A\neq 0$
.
Thus,
$f'(t)=2At+B$
, and we have
$f'(t)=0$
for
$t=\frac {-B}{2A}$
. In particular,
$f(t)$
has at most one local extremum. On the other hand, we know that f has local maximum when the
$(k-1)$
-dimensional simplices spanned by
$\{0\}\cup \{2,\ldots ,k\}$
and
$\{1\}\cup \{2,\ldots ,k\}$
are orthogonal to one another, that is, when
$t=t_{\pi /2}$
. The lemma then follows.
Remark. In the proof of Lemma 2.2, it follows that
$B=-2A(d_{01}^*)^2$
and
$C=A(d_{01}^*)^4+(v^*)^2$
where
$d_{01}^*$
is the edge-length when the volume is maximized (that is, when the two faces
$\{0\}\cup \{2,\ldots ,k\}$
and
$\{1\}\cup \{2,\ldots ,k\}$
are orthogonal), and
$v^*$
is this maximal volume. However, we do not use these facts.
Definition 2.3. Let X be a k-dimensional simplicial complex. Let
$h_X:\mathbb {R}^{|X_1|}\to \mathbb {R}^{|X_k|}$
map squared edge lengths to squared k-volumes, using the Cayley–Menger formula (2.1). Let
$$ \begin{align*}{\cal C}(X,\mathbf{{d}}):=J_{h_{X}}(\mathbf{{d}})\end{align*} $$
denote the Jacobian matrix of
$h_X$
, evaluated for a given vector
$\mathbf {{d}}$
of squared edge lengths, arising from some embedding
$\mathbf {{p}}$
of
$X_0$
in
$\mathbb {R}^d$
.
Note that
${\cal C}(X,\mathbf {{d}})$
is an
$|X_k|\times |X_1|$
matrix, whose
$(\sigma ,e)$
-entry, for
$\sigma \in X_k$
and
$e\in X_1$
, is the partial derivative of the square of the k-volume of the simplex
$\sigma $
with respect to the variable
$\mathbf {{d}}_e$
, evaluated at the point
$\mathbf {{d}}$
. Observe that
$$ \begin{align*}v_X=h_{X}\circ f_{X_1},\end{align*} $$
where
$f_{X_1}:(\mathbb {R}^{d})^{|X_0|}\to \mathbb {R}^{|X_1|}$
is the squared edge length map. That is,
$f_{X_1}$
is the map defined by
$$\begin{align*}f_{X_1}(\mathbf{{p}})_e= \|\mathbf{{p}}(u)-\mathbf{{p}}(v)\|^2 \end{align*}$$
for all
$e=\{u,v\}\in X_1$
. By the chain rule, we have
$$ \begin{align} {\cal B}(X,\mathbf{{p}})={\cal C}(X,\mathbf{{d}}) \cdot R(G,\mathbf{{p}}),\end{align} $$
where
$R(G,\mathbf {{p}})=J_{f_{X_1}}(\mathbf {{p}})$
is the standard rigidity matrix of the graph
$G=(X_0,X_1)$
and
$\mathbf {{d}}:=f_{X_1}(\mathbf {{p}})$
.
3. Proof of main result
Our main result, Theorem 1.2, follows immediately from the next two statements.
Proposition 3.1. Let
$d\ge 2$
,
$k=d-1$
, and
$n\ge d+2$
. Then,
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k}))=dn-\binom{d+1}{2}. \end{align*} $$
Proposition 3.2. Let
$d\ge 3$
,
$1\le k\le d-2$
, and
$n\ge d+1$
. Then,
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k}))=dn-\binom{d+1}{2}. \end{align*} $$
Proof of Proposition 3.1.
First note that, for any
$n\ge d+1$
, we have
$$ \begin{align} \mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k}))\le dn-\binom{d+1}{2}. \end{align} $$
Indeed, by (2.2), we have, for any
$\mathbf {{p}}$
,
$$\begin{align*}\mathrm{rank}({\cal B}(\Delta_{n,k},\mathbf{{p}}))\le \mathrm{rank}(R(\Delta_{n,1},\mathbf{{p}}))\le dn-\binom{d+1}{2}, \end{align*}$$
where the last inequality is a standard result on the rigidity of graphs (see, e.g., [Reference Jordán11, Lemma 1.2.1]). Hence, the inequality (3.1) follows.
Note also that it suffices to prove the theorem for
$n=d+2$
. That is, it suffices to prove that
$$ \begin{align} \mathrm{rank}({\cal M}_{k,d}(\Delta_{d+2,k}))=d(d+2)-\binom{d+1}{2} .\end{align} $$
Indeed, given (3.2), we can then repeatedly apply Lemma 2.1 to add the
$n-(d+2)$
remaining vertices of
$\Delta _{n,k}$
one by one. At each step, when we add a vertex v, the rank of the resulting matrix is increased by at least d, hence
$$ \begin{align*}\mathrm{rank}({\cal M}_{k,d}(\Delta_{n,k})) \ge d(d+2)-\binom{d+1}{2}+d(n-(d+2))=dn-\binom{d+1}{2}.\end{align*} $$
Together with the reverse inequality (3.1), this proves the theorem.
Thus, we only need to prove (3.2). Recall that for a matrix whose entries are algebraic expressions in the entries of
$\mathbf {{p}}$
, its generic rank is also its maximal one. So, to prove (3.2), it suffices to find an embedding
$\mathbf {{p}}$
for which
$$ \begin{align} \mathrm{rank}({\cal B}(\Delta_{d+2,k},\mathbf{{p}})) =d(d+2)- \binom{d+1}{2}. \end{align} $$
Write
$X=\Delta _{d+2,k}$
. For convenience, assume
$X_0=[d+2]$
. Let
$\mathbf {{p}}$
be an embedding of
$X_0$
in
$\mathbb {R}^{d}$
for which
$\mathbf {{p}}(2),\ldots ,\mathbf {{p}}(d+2)$
are the vertices of a regular d-simplex, and
$\mathbf {{p}}(1)$
is the centroid of this simplex. We claim that (3.3) holds for this choice of
$\mathbf {{p}}$
.
Using (2.2), we may write
$$ \begin{align*}{\cal B}(\Delta_{d+2,k},\mathbf{{p}}) ={\cal C}(\Delta_{d+2,k},\mathbf{{d}}) \cdot R(K_{d+2},\mathbf{{p}}), \end{align*} $$
where
$K_{d+2}$
stands for the complete graph on
$d+2$
vertices, and
$\mathbf {{d}}$
is the vector of squared edge lengths induced by
$\mathbf {{p}}$
. It is well-known and easy to check that
$$ \begin{align*}\mathrm{rank}(R(K_{d+2},\mathbf{{p}}))=d(d+2)-\binom{d+1}{2}. \end{align*} $$
Note also that, as
$k=d-1$
and
$n=d+2$
, we have
$$ \begin{align*}|X_1|=|X_k|=\binom{d+2}{2},\end{align*} $$
and so
${\cal C}(\Delta _{d+2,k},\mathbf {{d}})$
is a
$\binom {d+2}{2}\times \binom {d+2}{2}$
square matrix. Thus, to prove (3.3), it suffices to prove that
$$ \begin{align} {\cal C}={\cal C}(\Delta_{d+2,k},\mathbf{{d}}) \text{ is invertible.} \end{align} $$
Index the rows of
${\cal C}$
by the elements of
$X_k$
and its columns by the elements of
$X_1$
. Observe that, for
$e\in X_1$
and
$T\in X_{k}$
, the
$(T,e)$
-entry of
${\cal C}$
is
$0$
if
$e\not \subset T$
. Moreover, by symmetry, we have
$$ \begin{align*}{\cal C}_{T,e}= \begin{cases} 0& \quad e\not\subset T,\\ \alpha&\quad e\subset T,\;\;1\not\in T,\\ \beta&\quad e\subset T,\;\;1\in T\cap e,\\ \gamma&\quad e\subset T,\;\;1\in T\setminus e, \end{cases} \end{align*} $$
for some three real numbers
$\alpha , \beta , \gamma $
. By Lemma 2.2, we have that
$\alpha $
,
$\beta $
, and
$\gamma $
are nonzero.
We apply the following row- and column- scaling: for every
$T\in X_k$
, we multiply the T-row by
$\frac 1\alpha $
if
$1\not \in T$
, and by
$\frac {1}{\gamma }$
otherwise. Then, for every
$e\in X_1$
such that
$1\in e$
, we multiply the e-column by
$\frac {\gamma }{\beta }$
. The resulting matrix, which we denote by
$A_{k+1,2}^{d+2}$
, satisfies
$$\begin{align*}\left(A_{k+1,2}^{d+2}\right)_{T,e}=\begin{cases} 0 & e\not\subset T,\\ 1 & e\subset T, \end{cases} \end{align*}$$
for all
$e\in X_1$
and
$T\in X_k$
. That is,
$A_{k+1,2}^{d+2}$
is the incidence matrix between
$(k+1)$
-subsets and
$2$
-subsets of
$X_0=[d+2]$
. By Gottlieb [Reference Gottlieb8, Corollary 2] (or alternatively, by [Reference Graver and Jurkat10, Reference Wilson20]),
$A_{k+1,2}^{d+2}$
is invertible. Since
$A_{k+1,2}^{d+2}$
was obtained from
${\cal C}$
by row and column operations,
${\cal C}$
is invertible as well. This completes the proof of the proposition.
Proof of Proposition 3.2.
By an argument similar to the one at the beginning of the proof of Proposition 3.1, it suffices to prove the proposition for
$n=d+1$
. Indeed, for
$n>d+1$
, we can then add the remaining
$n-(d+1)$
vertices one by one, using Lemma 2.1.
Write
$X=\Delta _{d+1,k}$
, and assume for convenience
$X_0=[d+1]$
. Let
$\mathbf {{p}}$
be an embedding of
$X_0$
in
$\mathbb {R}^{d}$
for which
$\mathbf {{p}}(1),\ldots ,\mathbf {{p}}(d+1)$
are the vertices of a regular d-simplex. We claim that, for
$1\le k\le d-2$
, one has
$$ \begin{align} \mathrm{rank}({\cal B}(\Delta_{d+1,k},\mathbf{{p}}))=d(d+1)-\binom{d+1}{2}. \end{align} $$
Using (2.2), we may write
$$ \begin{align} {\cal B}(\Delta_{d+1,k},\mathbf{{p}}) ={\cal C}(\Delta_{d+1,k},\mathbf{{d}}) \cdot R(K_{d+1},\mathbf{{p}}), \end{align} $$
where
$K_{d+1}$
stands for the complete graph on
$d+1$
vertices, and
$\mathbf {{d}}$
is the vector of squared edge lengths induced by
$\mathbf {{p}}$
. Namely,
$\mathbf {{d}}$
is the all-ones vector. Note that
$$ \begin{align*}\mathrm{rank}(R(K_{d+1},\mathbf{{p}}))=d(d+1)-\binom{d+1}{2}=\binom{d+1}{2}. \end{align*} $$
Since the number of rows of
$R(K_{d+1},\mathbf {{p}})$
is exactly
$\binom {d+1}{2}$
,
$R(K_{d+1},\mathbf {{p}})$
has a full rank, and its image is all of
$\mathbb {R}^{\binom {d+1}{2}}$
. In view of (3.6), this implies that
$$ \begin{align*}\mathrm{rank}({\cal B}(\Delta_{d+1,k},\mathbf{{p}})) =\mathrm{rank}({\cal C}(\Delta_{d+1,k},\mathbf{{d}})). \end{align*} $$
So, in order to prove (3.5), we need to show that
$$ \begin{align} \mathrm{rank}({\cal C}(\Delta_{d+1,k},\mathbf{{d}}))=\binom{d+1}{2}. \end{align} $$
Write
${\cal C}={\cal C}(\Delta _{d+1,k},\mathbf {{d}})$
. We index the rows of
${\cal C}$
by the elements of
$X_k$
and the columns of
${\cal C}$
by the elements of
$X_1$
. Observe that for
$e\in X_1$
and
$T\in X_{k}$
, the
$(T,e)$
-entry of
${\cal C}$
is
$0$
if
$e\not \subset T$
. Moreover, by symmetry, we have
$$ \begin{align*}{\cal C}_{T,e}= \begin{cases} 0& \quad e\not\subset T,\\ \alpha&\quad e\subset T, \end{cases} \end{align*} $$
for some real number
$\alpha $
. By Lemma 2.2, we have
$\alpha \neq 0$
.
Thus
${\cal C}=\alpha A_{k+1,2}^{d+1}$
, where
$A_{k+1,2}^{d+1}$
is the incidence matrix between
$(k+1)$
-subsets and
$2$
-subsets of
$X_0=[d+1]$
. By [Reference Gottlieb8, Corollary 2], the matrix
$A_{k+1,2}^{d+1}$
has maximal rank. Since
$1\le k\le d-2$
, we get
$$ \begin{align*}\mathrm{rank}({\cal C}) = \mathrm{rank}(A_{k+1,2}^{d+1}) =\binom{d+1}{2},\end{align*} $$
as needed. This proves (3.7), and hence (3.5), and thus completes the proof of the proposition.
Finally, let us note that the case
$k=d-1$
and
$n=d+1$
, excluded from Theorem 1.2, follows easily by similar arguments, as detailed next.
Proposition 3.3. Let
$d\ge 2$
. Then,
$$\begin{align*}\mathrm{rank}({\cal M}_{d-1,d}(\Delta_{d+1,d-1}))=d+1. \end{align*}$$
Proof. Let
$\mathbf {{p}}$
map
$(\Delta _{d+1,d-1})_{0}$
to the vertices of a regular d-simplex in
$\mathbb {R}^d$
. Then, following the same arguments as in Proposition 3.2, we obtain
$$\begin{align*}\mathrm{rank}(\mathcal{B}(\Delta_{d+1,d-1},\mathbf{{p}}))= \mathrm{rank}(A_{d,2}^{d+1}), \end{align*}$$
where
$A_{d,2}^{d+1}$
is the incidence matrix between d-subsets and
$2$
-subsets of the set
$[d+1]$
. By [Reference Gottlieb8, Corollary 2], this matrix has maximal rank, namely
$\mathrm { rank}(A_{d,2}^{d+1})=d+1$
. Therefore,
$$\begin{align*}\mathrm{rank}({\cal M}_{d-1,d}(\Delta_{d+1,d-1}))\ge \mathrm{rank}(\mathcal{B}(\Delta_{d+1,d-1},\mathbf{{p}}))=d+1. \end{align*}$$
On the other hand, since
$\mathcal {M}_{d-1,d}$
has exactly
$\binom {d+1}{d}=d+1$
elements, we must have
$$\begin{align*}\mathrm{rank}({\cal M}_{d-1,d}(\Delta_{d+1,d-1}))=d+1,\end{align*}$$
as wanted.
4. Discussion
For a complex X, we call the graph
$G=(X_0,X_1)$
the
$1$
-skeleton of X. Combining (2.2) with Theorem 1.2, we obtain that if a simplicial complex on
$n\ge d+2$
vertices is k-volume rigid in
$\mathbb {R}^d$
, for some
$d>k\ge 1$
, then its
$1$
-skeleton must be d-rigid as a graph. The converse does not hold (see Example 4.3 below). However, we propose the following conjecture, which gives a characterization for the rank of the
$(k,d)$
-volume rigidity matroid of a complex in terms of the standard d-rigidity matroid of its
$1$
-skeleton.
For two disjoint families of sets
${\cal A},{\cal B}$
, let
$H_{{\cal A},{\cal B}}$
be the bipartite graph on vertex set
${\cal A}\cup {\cal B}$
with edge set
$\{\{A,B\}:\, A\in {\cal A},\, B\in {\cal B},\, A\subset B\}$
. For a graph
$G=(V,E)$
, let
$\nu (G)$
be its matching number, that is, the size of a maximum matching in G.
Conjecture 4.1. Let
$d\ge 3$
,
$1\le k\le d-1$
, and let X be a k-dimensional simplicial complex on
$n\ge d+2$
vertices. Then,
$$\begin{align*}\mathrm{rank}({\cal M}_{k,d}(X))= \max_{E} \nu(H_{E,X_k}), \end{align*}$$
where the maximum is taken over all
$E\subset X_1$
that are independent in the standard d-rigidity matroid.
In particular, if
$|X_k|=dn-\binom {d+1}{2}$
, then Conjecture 4.1 would imply that X is k-volume rigid in
$\mathbb {R}^d$
if and only if there exists
$E\subset X_1$
of size
$dn-\binom {d+1}{2}$
such that
$G=(X_0,E)$
is minimally rigid in
$\mathbb {R}^d$
, and there exists a perfect matching between E and
$X_k$
in the bipartite incidence graph
$H_{E,X_k}$
. By a classical result of Rado ([Reference Rado14]; see also [Reference Welsh18, Reference Welsh19]), this is equivalent to the following statement.
Conjecture 4.2. Let
$d\ge 3$
,
$1\le k\le d-1$
, and let X be a k-dimensional simplicial complex on
$n\ge d+2$
vertices. Assume that
$|X_k|=dn-\binom {d+1}{2}$
. Then, X is k-volume rigid in
$\mathbb {R}^d$
if and only if for every
$S\subset X_k$
, the 1-skeleton of the restriction
$X[S]=\{\tau \in X:\, \tau \subset \sigma \text { for some } \sigma \in S\}$
has rank at least
$|S|$
in the standard d-rigidity matroid.
Note that the “only if” direction of the conjecture holds. Indeed, for a subset
$S\subset X_k$
and a generic
$\mathbf {{p}}$
, consider the
$|S|\times d|X_0|$
submatrix Q of
${\cal B}(X,\mathbf {{p}})$
corresponding to the rows of S. On the one hand,
$\left ({\cal C}(X,f_{X_1}(\mathbf {{p}}))\right )_{\sigma ,e}=0$
for every edge
$e\notin X[S]$
and every k-simplex
$\sigma \in S$
. Therefore, using (2.2), we find that Q is a product of a submatrix of
${\cal C}(X,f_{X_1}(\mathbf {{p}})))$
and the standard d-rigidity matrix of the
$1$
-skeleton of
$X[S]$
. On the other hand, assuming that
$|X_k|=dn-\binom {d+1}{2}$
and X is k-volume rigid in
$\mathbb {R}^d$
, we have
$\mathrm { rank}(Q)=|S|$
. The “only if” direction follows since matrix multiplication does not increase the rank.
Example 4.3. Let Y be the simplicial complex obtained from the complete two-dimensional complex on five vertices by removing a single triangle. Let Z be obtained by gluing together two copies of Y along an edge. Any such Z has eight vertices and 18 triangles. Note that the graph
$G=(Z_0,Z_1)$
is not generically rigid in
$\mathbb {R}^3$
, as one can fix one copy of Y and rotate the other copy along the common edge. The same motion also shows that Z is not 2-volume rigid in
$\mathbb R^3$
. Let
$a,b,c$
be the vertices in Z unique to the first copy of Y, and let
$a',b',c'$
be the vertices in Z unique to the second copy. Let v be a new vertex not in Z, and let X be the union of Z and the three triangles
$\{a,a',v\}, \{b,b',v\}$
, and
$\{c,c',v\}$
. Let
$\mathbf {{p}}$
be a generic embedding of
$X_0$
in
$\mathbb {R}^3$
, and let
$G'=(X_0,X_1)$
. Then, it is not hard to verify that
$\mathrm {rank}(R(G',\mathbf {{p}}))=21=\mathrm {rank}( {\cal C}(X,f_{X_1}(\mathbf {{p}})))$
, but
$\mathrm {rank}({\cal B} (X,\mathbf {{p}}))=20$
, so while the
$1$
-skeleton of X is generically rigid in
$\mathbb {R}^3$
, X is not 2-volume rigid in
$\mathbb {R}^3$
. The Hall condition mentioned above indeed fails here: letting S be the collection of triangles in X not containing v, it is easy to check that the
$1$
-skeleton of
$X[S]$
, which is the graph
$G=(Z_0,Z_1)$
, has rank 17 in the standard
$3$
-rigidity matroid, but
$|S|=18>17$
.
It is natural to wonder about the rank of the matrix
${\cal C}(X,\mathbf {{d}})$
for a generic vector
$\mathbf {{d}}\in \mathbb {R}^{|X_1|}$
. The following is a special case of Conjecture 4.1.
Conjecture 4.4. Let
$2\le k\le n-2$
, and let X be a k-dimensional simplicial complex on n vertices. Then, for generic
$\mathbf {{d}}\in \mathbb {R}^{|X_1|}$
,
$$\begin{align*}\mathrm{rank}({\cal C}(X,\mathbf{{d}}))=\nu(H_{X_1,X_k}). \end{align*}$$
To see that this is indeed a special case, suppose that Conjecture 4.1 is true for
$d=n-1$
. Let
$G=(X_0,X_1)$
be the
$1$
-skeleton of X. Then, for a generic embedding
$\mathbf {{p}}$
of
$X_0$
in
$\mathbb {R}^{n-1}$
, we have
$\mathrm {rank}(R(G,\mathbf {{p}}))=|X_1|$
, and therefore the image of
$R(G,\mathbf {{p}})$
is
$\mathbb {R}^{|X_1|}$
. Combined with (2.2), we see that in this case
$$ \begin{align*}\mathrm{rank}({\cal B}(X,\mathbf{{p}}))=\mathrm{rank}({\cal C}(X,\mathbf{{d}})),\end{align*} $$
where
$\mathbf {{d}}=f_{X_1}(\mathbf {{p}})$
. Note that
$f_{X_1}((\mathbb {R}^d)^{n})$
is an open subset of
$\mathbb {R}^{|X_1|}$
, and so in fact we have
$$ \begin{align*}\max_{\mathbf{{p}}\in(\mathbb{R}^d)^n}\mathrm{rank}({\cal B}(X,\mathbf{{p}})) = \max_{\mathbf{{d}}\in\mathbb{R}^{|X_1|}}\mathrm{rank}({\cal C}(X,\mathbf{{d}})). \end{align*} $$
In other words, the generic rank of
${\cal C}(X,\mathbf {{d}})$
is equal to the generic rank of
${\cal B}(X,\mathbf {{p}})$
. Finally, the claim follows from Conjecture 4.1, noting again that, since
$d=n-1$
, every
$E\subset X_1$
is independent in the standard d-rigidity matroid.
Lastly, let us mention a relation between the
$(k,d)$
-volume rigidity matrix
$\mathcal {B}(X,\mathbf {{p}})$
studied here and a similar matrix studied by Lee in [Reference Lee12]. Let
$L(X,\mathbf {{p}})$
be the
$|X_k|\times d|X_{k-1}|$
matrix defined byFootnote 2
$$ \begin{align} L(X,\mathbf{{p}})_{\sigma,\tau}=\begin{cases} h_{\sigma,\tau} & \tau\subset \sigma,\\ 0 & \text{otherwise,} \end{cases} \end{align} $$
for every
$\sigma \in X_k$
and
$\tau \in X_{k-1}$
, where for
$\tau \subset \sigma $
, denoting the unique vertex in
$\sigma \setminus \tau $
by v,
$h_{\sigma ,\tau }\in \mathbb {R}^d$
is the altitude vector of the simplex
$\mathbf {{p}}(\sigma )$
with respect to
$\mathbf {{p}}(v)$
(pointing from
$\mathbf {{p}}(\tau )$
to
$\mathbf {{p}}(v)$
). Note that, for
$\tau =\sigma \setminus \{v\}$
,
$h_{\sigma ,\tau }=(\mathrm {vol}_{k}(\sigma ) k/\mathrm {vol}_{k-1}(\tau )) N_{\sigma ,v}$
. It is then not hard to check, using (4.1), (1.1), and the fact that for every k-simplex
$\sigma $
we have
$$\begin{align*}\sum_{v\in \sigma} \mathrm{vol}_{k-1}(\sigma\setminus \{v\}) N_{\sigma,v}=0, \end{align*}$$
that
$$\begin{align*}\mathcal{B}(X,\mathbf{{p}})= -\frac{2}{k^2} L(X,\mathbf{{p}}) \cdot D(X,\mathbf{{p}})\cdot P(X), \end{align*}$$
where
$D(X,p)\in \mathbb {R}^{d|X_{k-1}|\times d|X_{k-1}|}$
is the diagonal matrix defined by
$ D(X,\mathbf {{p}})_{\tau ,\tau }= \mathrm {vol}_{k-1}(\tau )^2 I_d $
for all
$\tau \in X_{k-1}$
(where
$I_d$
is the
$d\times d$
identity matrix), and
$P(X)$
is the
$d|X_{k-1}|\times d|X_0|$
matrix where the
$d\times d$
block indexed by
$(\tau ,v)$
equals
$I_d$
if
$v\in \tau $
and
$0$
otherwise, for every
$\tau \in X_{k-1}$
and
$v\in X_0$
. We do not pursue this relation further in this work.
Remark. Let us mention that the notion of
$(k,d)$
-volume rigidity was recently and independently introduced by James Cruickshank, Bill Jackson and Shin-ichi Tanigawa in [Reference Cruickshank, Jackson and Tanigawa6]. In particular, our Proposition 3.2 was independently proven in [Reference Cruickshank, Jackson and Tanigawa6, Theorem 5], by different techniques. We thank Bill, James, and Shin-ichi for sharing a draft of their preprint just before both articles were submitted to arXiv, and for suggesting a better name for Lemma 3.
Acknowledgments
We thank the anonymous referee for their helpful remarks, and in particular for pointing out a few minor mistakes in the previous version of our manuscript.
Competing interests
The authors have no competing interests to declare.
Financial support
E. Nevo was partially supported by the Israel Science Foundation grants ISF-2480/20 and ISF-687/24. Y. Peled was partially supported by the Israel Science Foundation grant ISF-3464/24. O. E. Raz was partially supported by the Charles Simonyi Endowment.
Open access
