Guest post by Daniel Irving Bernstein. Click here for the pdf version.
Many questions in applied algebraic geometry boil down to asking which polynomial functions within some family are generically finite-to-one. When the family consists of the coordinate projections of an irreducible variety, matroids arise. Two particular applications that have driven much research include matrix completion and rigidity theory. The ground sets of the matroids that appear therein are the edge sets of graphs.
Low rank matrix completion.
In a low-rank matrix completion problem, one is given access to a subset of entries of a matrix, and hopes to fill in the missing entries in a way that minimizes rank, or that achieves a particular low rank. For example, given any partial matrix of the following form
$$\begin{pmatrix}
a & b \\
c & \cdot
\end{pmatrix},$$
one can fill in the missing entry so that the resulting matrix has rank one. Namely, plug in $\frac{bc}{a}$ . Of course, this won’t work if $a=0$, but we can safely ignore this issue, and similar ones, by working over $\mathbb{C}$ and invoking a genericity assumption on the visible entries. In this setup, whether or not a particular partial matrix can be completed to a particular rank $r$ depends only on which entries are observed, and not their actual values. Thus, one can ask: given an integer $r \ge1$ and a subset E of entries of an $m\times n$ matrix – which is naturally encoded by the bipartite graph $([m],[n],E)$, see the figure below – can the resulting partial matrices be completed to rank $r$? The subsets of entries, i.e. bipartite graphs, for which the answer to this question is “yes” form the independent sets of a matroid. When $r=1$, this is the graphic matroid of the complete bipartite graph. When $r=2$, the independent sets of this matroid consist of all bipartite graphs that admit an edge two-coloring with no monochromatic cycle, nor any cycle whose edge colors alternate. More on this later.
The subset of known entries of the matrix to the left correspond to the graph on the right. If $a,b,c,d,e,f$ are sufficiently generic, then the partial matrix can be completed to rank two, but not rank one.
Rigidity Theory
If one were to physically build a graph $G$ in $d$-dimensional space, using rigid struts for the edges, and universal joints for the vertices (i.e. joints that the struts can move freely around) would the resulting structure be rigid, or flexible? Consider, for example, the four-cycle. If we build it in the plane as a square, then the resulting structure is flexible, since we can deform the square into a rhombus without stretching, compressing, or breaking any of the edges — see the figure below. However, if we add a chord to the four-cycle, then it becomes rigid in the plane.
The four-cycle is not rigid in the plane, but becomes rigid after adding a chord.
Whether or not a graph is rigid in $d$-dimensional space depends not only on the combinatorics of the graph, but also on the specific positions we place the vertices. For example, we can build the four-cycle in the plane so that it becomes rigid by placing all four vertices on a line. However, just as in the matrix completion example, we can safely ignore such issues by invoking a genericity assumption. Then, every graph will either be rigid or flexible in $d$-dimensional space, and we can ask to characterize those that are rigid. Moreover, the graphs on a fixed number of vertices that are rigid in $d$-dimensional space form the spanning sets of a matroid. When $d=1$, this is the graphic matroid of the complete graph (see if you can convince yourself of this). When $d=2$, the independent sets of this matroid consist of graphs such that every subgraph on $k$ vertices has at most $2k-3$ edges. More on this later.
Matroids from varieties
We will now describe how the two aforementioned matroids arise from the same construction from algebraic geometry.
A variety will refer to a subset of a finite-dimensional vector space that is defined by the simultaneous vanishing of a system of polynomial equations. We will be particularly concerned with irreducible varieties, which are varieties that cannot be expressed as a union of two proper subsets which are themselves varieties.
Let $E$ be a finite set, let $\mathbb{F}$ be a field, and let $\mathbb{F}^E$ denote the $\mathbb{F}$-vector space whose coordinates are indexed by elements of $E$. Each subset $S\subseteq E$ defines a coordinate projection $\pi_S:\mathbb{F}^E\rightarrow \mathbb{F}^S$. Given a variety $V$, the dimension of the image of $V$ under these coordinate projections gives us an integer valued set function
\[
\rho_V: 2^E \rightarrow \mathbb{N} \qquad {\rm given \ by} \qquad S\mapsto \dim(\pi_S(V)).
\] I claim that when $V$ is irreducible, $\rho_V$ is the rank function of a matroid. This matroid will be denoted by $\mathcal{M}(V)$, and it is known as the algebraic matroid of $V$.
I will briefly explain why $\mathcal{M}(V)$ is a matroid when $V$ is irreducible in the case that $\mathbb{F}$ is an uncountable field of characteristic zero (e.g. $\mathbb{R}$ or $\mathbb{C}$). First consider the case that $V$ is a linear space. Then, $V$ is an irreducible variety that can be obtained as the row-span of some matrix $A$ whose columns are indexed by $E$. Letting $A_S$ denote the column-submatrix of $A$ obtained by restricting to the columns indexed by $S\subseteq E$, we see that $\pi_S(V)$ is the row-span of $A_S$ and thus $\rho_V(S) = \dim(\pi_S(V)) = {\rm rank}(A_S)$. So $\rho_V$ is the rank function of the column-matroid of $A$. If $V$ is an arbitrary irreducible variety, then since $\mathbb{F}$ is an uncountable field of characteristic zero, it follows from some basic algebraic geometry that $\rho_V = \rho_L$ where $L$ is the tangent space to $V$ at a generic1 point. Translating $L$ so that it contains the origin gives us a linear space $L’$ such that $\rho_L = \rho_{L’}$. It now follows from the linear case that $\rho_V$ is the rank function of a matroid. Note that our proof implies that any matroid of the form $\mathcal{M}(V)$ is representable over $\mathbb{F}$ when $\mathbb{F}$ is uncountable of characteristic zero (this is no longer true for $\mathbb{Q}$ nor fields of prime characteristic [4]).
Some readers might be more familiar with a seemingly different definition of algebraic matroid. Namely, if $\mathbb{K}$ is a field extension of $\mathbb{F}$ and $E \subseteq \mathbb{K}$ is finite, then the subsets of $E$ that are algebraically independent over $\mathbb{F}$ form the independent subsets of a matroid. Matroids arising in this way are said to be algebraic matroids (over $\mathbb{F}$). There is no conflict in terminology here, and this stems from the fact that for any variety $W\subseteq \mathbb{F}^k$, the dimension of $W$ is defined to be the transcendence degree over $\mathbb{F}$ of the fraction field of $\mathbb{F}[x_1,\dots,x_k]/I$, where $I$ is the ideal of polynomials that vanish on $W$. When $\mathbb{F} = \mathbb{R}$ or $\mathbb{C}$, this definition is equivalent to the more intuitive notion of dimension from differential geometry, i.e. the dimension of a tangent space at a smooth point (and I will not discuss this further since the proof is quite deep, and requires a good bit of commutative algebra).
Determinantal varieties and matrix completion
Let ${\rm M}(m\times n,r) \subseteq \mathbb{C}^{m\times n}$ denote the set of $m\times n$ complex matrices of rank at most $r$. Since a matrix has rank $r$ or less if and only if all $(r+1)\times(r+1)$ submatrices have zero determinant, ${\rm M}(m\times n,r)$ is a variety. Moreover, it is irreducible so we can talk about its algebraic matroid. The ground set of this matroid is the set of entries of an $m\times n$ matrix, which we identify with the edge set of the complete bipartite graph $K_{m,n}$. Subsets of the ground set can therefore be described as bipartite graphs on partite sets of size $m$ and $n$.
Given a bipartite graph $G$, let $\mathbb{C}^G$ denote the vector space whose coordinates are indexed by edges of $G$, and let $\Omega_G:\mathbb{C}^{m\times n}\rightarrow \mathbb{C}^G$ be the map that projects a matrix $M$ onto its entries corresponding to the edges of $G$. Elements of $\mathbb{C}^G$ are called $G$-partial matrices. Given a $G$-partial matrix $A$, elements of $\Omega_G^{-1}(A)$ are called completions of $A$. A fundamental problem in low-rank matrix completion is to determine whether a given partial matrix $A \in \mathbb{C}^{G}$ has a completion to a particular rank. The following proposition tells us that assuming $A$ is generic, whether or not $A$ can be completed to rank $r$ depends only on $G$.
Proposition. Let $G = ([m],[n],E)$ be a bipartite graph and let $A \in \mathbb{C}^G$ be a $G$-partial matrix. If $A$ is generic, then $A$ has a completion to rank $r$ if and only if $G$ is independent in the algebraic matroid $\mathcal{M}({\rm M}(m\times n,r))$.
proof. Given any irreducible variety $V \subseteq \mathbb{C}^E$, $S\subseteq E$ is independent in $\mathcal{M}(V)$ if and only if $\dim(\pi_S(V)) = |S|$. This means that the set $\{x \in \mathbb{C}^S : x \notin \pi_S(V)\}$ is contained in a subvariety of $\mathbb{C}^{S}$, and in particular, has dimension strictly less than $|S|$. Thus given any generic $x \in \mathbb{C}^S$, there exists $y \in V$ such that $\pi_S(y) = x$. The proposition is now the special case where $V = {\rm M}(m\times n,r)$. ◊
The above proposition motivates the following general problem: for each positive integer $r$, give a combinatorial description of the (independent sets of) the matroid $\mathcal{M}({\rm M}(m\times n,r))$. This is open in all cases aside from $r=1$ and $r=2$. For $r=1$, it is relatively easy to show that $\mathcal{M}({\rm M}(m\times n,1))$ is the graphic matroid of $K_{m,n}$; we do this below.
Proposition. The matroid $\mathcal{M}({\rm M}(m\times n,1))$ is the graphic matroid of $K_{m,n}$. In other words, a bipartite graph $G = ([m],[n],E)$ is independent in $\mathcal{M}({\rm M}(m\times n,1))$ if and only if $G$ is a forest.
proof. Assume $G$ has no cycles. Let $X$ be a generic $G$-partial matrix. By the previous proposition, it suffices to show that $X$ can be completed to a rank-one matrix. Let $G’$ be obtained from $G$ by removing a vertex of degree zero or one; without loss of generality, assume it was the row-vertex $m$. Let $X’$ be the $G’$-partial matrix obtained from $X$ by removing the last row. By induction, $X’$ can be completed to a rank-one matrix $Y$. If the degree of $m$ was zero, then we can further complete $X$ to a rank-one matrix by plugging in zeros for the entries in the last row. If the degree of $m$ was $1$, then assuming the unique known entry of the $m^{\rm th}$ row of $X$ is in the first column, then multiply the $(m-1)^{\rm th}$ row of $Y$ by $X_{m,1}/Y_{m-1,1}$ and adjoining it to $Y$ gives a rank-one completion of $X$.
Now assume $G$ has a cycle $x_1,x_2,\dots,x_{2k}$ ($G$ is bipartite, so the cycle must have even length). Then $\pi_G({\rm M}(m\times n,1))$ must satisfy the equation $$x_1x_3\cdots x_{2k-1} = x_2x_4\cdots x_{2k}.$$ In particular, $\pi_G({\rm M}(m\times n,1))$ has dimension less than the number of edges of $G$. ◊
The characterization of $\mathcal{M}({\rm M}(m\times n,2))$ is more complicated. I will state it below; the interested reader is invited to read my paper [1] for the proof, which uses tropical geometry.
Theorem. Let $G = ([m],[n],E)$ be a bipartite graph. Then $G$ is independent in $\mathcal{M}({\rm M}(m\times n,2))$ if and only if there exists a two-coloring of the edges of $G$ with no monochromatic cycle, and no cycle whose edge-colors alternate.
Cayley-Menger varieties and rigidity theory
Consider the function $\phi_n^d:(\mathbb{R}^{d})^n\rightarrow \mathbb{R}^{\binom{n}{2}}$ that sends a configuration of $n$ points in $d$-dimensional space to their vector of squared pairwise distances. For example, if $d = 2$, this map would send the $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ to the vector $$((x_i-x_j)^2 + (y_i-y_j)^2)_{1\le i < j \le n}.$$ The image of $\phi_n^d$ is subset of $\mathbb{R}^{\binom{n}{2}}$, and taking its Zariski closure in $\mathbb{C}^{\binom{n}{2}}$ (i.e. the smallest variety in $\mathbb{C}^{\binom{n}{2}}$ containing it) yields an irreducible variety ${\rm CM}_n^d$ called the Cayley-Menger variety of $n$ points in $\mathbb{R}^d$ (and yes, this is the Menger of Menger’s theorem). We can identify the coordinate indices of $\mathbb{C}^{\binom{n}{2}}$, i.e. the ground set of the matroid $\mathcal{M}({\rm CM}_n^d)$, with the edges of the complete graph $K_n$.
Proposition. A graph $G$ is spanning in $\mathcal{M}({\rm CM}_n^d)$ if and only if it is rigid in $d$-dimensional space.
proof sketch. Given any varieties $V$ and $W$ and any polynomial map $f: V\rightarrow W$, the following relationship holds for generic $x \in V$
\[
\dim(V) = \dim(f(V)) + \dim(f^{-1}(f(x))).
\] When $\dim(V) = \dim(f(V))$, this implies $\dim(f^{-1}(f(x))) = 0$ and since $\dim(f^{-1}(f(x))$ is a variety, this is equivalent to $\dim(f^{-1}(f(x))$ being a finite set. In particular, if $V \subseteq \mathbb{C}^E$ then $S \subseteq E$ is spanning in $\mathcal{M}(V)$ if and only if $\pi_S^{-1}(\pi_S(x)) \cap V$ is a finite set. So it remains to see that $G$ is rigid if and only if $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is finite for generic $x \in {\rm CM}_n^d$.
We now need to be more formal in our definition of rigidity. Suppose we build a graph $G$ in $\mathbb{R}^d$ by putting the vertices at points $p^{(1)},\dots,p^{(n)}$. A (nontrivial) \emph{flex} of $G$ is a curve in the space of configuration of $n$ points in $\mathbb{R}^d$, i.e. a function ${\bf p}:[0,1]\rightarrow (\mathbb{R}^d)^n$, such that
- the curve starts at the original configuration, i.e. ${\bf p}(0) = (p^{(1)},\dots,p^{(n)})$
- all configurations along the curve preserve edge lengths, i.e. for each $t \in [0,1]$ and edge $\{i,j\}$ of $G$, $\|{\bf p}(t)^{(i)}-{\bf p}(t)^{(j)}\|^2 = \|{\bf p}(0)^{(i)}-{\bf p}(0)^{(j)}\|^2$, and
- somewhere along the curve, the framework on $G$ actually gets deformed, i.e. for some $t \in [0,1]$ and some non-edge $\{i,j\}$ of $G$, $\|{\bf p}(t)^{(i)}-{\bf p}(t)^{(j)}\|^2 \neq \|{\bf p}(0)^{(i)}-{\bf p}(0)^{(j)}\|^2$.
This formalizes our intuitive notion of what it would mean to deform our particular construction of a graph. A graph is then (generically) rigid if for any generic point configuration $p^{(1)},\dots,p^{(n)}$, the corresponding framework on $G$ does not have any flex.
To see that the absence of a flex of $G$ is equivalent to the statement that $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is generically finite, first note that if ${\bf p}:[0,1]\rightarrow (\mathbb{R}^d)^n$ is a curve satisfying the second condition required for ${\bf p}$ to be a flex of $G$, then $\pi_G\circ \phi_n^d \circ {\bf p}([0,1])$ is a single point $y$ in $\pi_G({\rm CM}_n^d)$, and $\pi_G^{-1}(y)\cap {\rm CM}_n^d$ contains $\phi_n^d \circ {\bf p}([0,1])$. The curve ${\bf p}$ additionally satisfies the third condition if and only if $\phi_n^d \circ {\bf p}([0,1])$ is one-dimensional, thus exhibiting infinitely many points in $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ for some $x \in \pi_G^{-1}(y) \cap {\rm CM}_n^d$. Conversely, since $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is a variety, then if it has infinitely many points, it must contain a curve. In this case, we can find such a curve that also lies in the image of $\phi_n^d$ (this is me ignoring the issues that can arise when passing from a semi-algebraic set to its complex Zariski closure). Such a curve is a flex. ◊
The above proposition motivates the following general problem: for each $d \ge 1$, find a combinatorial description of $\mathcal{M}({\rm CM}_n^d)$, the algebraic matroid of the Cayley-Menger variety of $n$ points in $d$-dimensional space. For $d \ge 3$, this problem is open, and has been for at least a century. The $d = 1$ case is quite simple: $\mathcal{M}({\rm CM}_n^1)$ is the graphic matroid of the complete graph $K_n$, and you might be able to see this intuitively. There are a handful of characterizations for the $d=2$ case; perhaps the most famous, and elegant, due to Hilda Polaczek-Geiringer, is the following.
Theorem. A graph $G$ is independent in $\mathcal{M}({\rm CM}_n^d)$ if and only if every subgraph of $G$ on $k$ vertices has at most $2k-3$ edges.
The above theorem is known as Laman’s theorem, based on the mistaken, but previously widespread, belief that this result originated with Gerard Laman’s 1970 paper [3]. Recently however, it was noticed that Hilda Pollaczek-Geiringer had actually proven this result much earlier in 1927 [5].
Concluding remarks
Applied algebraic geometry is full of families of varieties whose algebraic matroids are worth understanding. As in the two examples above, the ground set of each such matroid is usually a graph, though sometimes the ground set is something slightly more complicated, like a gain graph as in [2]. There are many open problems, as well as opportunities to develop general theory that could be used to solve them.
References
[1] Daniel Irving Bernstein. Completion of tree metrics and rank 2 matrices. Linear Algebra and its Applications, 533:1–13, 2017. arxiv:1612.06797.
[2] Daniel Irving Bernstein. Generic symmetry-forced infinitesimal rigidity: translations and rotations. arXiv preprint arXiv:2003.10529, 2020.
[3] Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engi-neering mathematics, 4(4):331–340, 1970.
[4] Bernt Lindström. A non-linear algebraic matroid with infinite characteristic set. Discrete Mathematics, 59(3):319–320, 1986.
[5] Hilda Pollaczek-Geiringer. Über die gliederung ebener fachwerke. ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 7(1):58–72, 1927.
- When applied algebraic geometers say “property $P$ is satisfied by a generic point of $V$,” it means that the set of points in $V$ where $P$ is not satisfied is contained in a subvariety of $V$. We use the word “generic” to avoid explicitly writing down what that variety is. When $V$ is irreducible, any subvariety of $V$ has lower dimension than $V$. Therefore, when $\mathbb{F} = \mathbb{C}$ or $\mathbb{R}$, if $V$ is irreducible and a generic point of $V$ satisfies property $P$, then a point randomly sampled from $V$ with respect to a reasonable probability distribution will satisfy $P$ with probability one.
