1 Introduction↩︎

In applications of algebraic geometry, one is often given a polynomial map or, more generally, a rational map \(\varphi\colon {\mathbb{C}}^m \dashrightarrow{\mathbb{C}}^n\), and wants to compute properties of the image closure \[X \coloneq \overline{\{\varphi(p) \mid p \in {\mathbb{C}}^m \text{ and } \varphi \text{ is defined at } p\}.}\] The closure and other topological notions throughout the paper refer to the Zariski topology; in this setting, the closure coincides with that in the Euclidean topology. This framework yields a large class of (irreducible) algebraic varieties, called unirational varieties.

Let \(\operatorname{GL}\nolimits_n \coloneq \operatorname{GL}\nolimits_n({\mathbb{C}})\) and \({\mathfrak{gl}}_n\coloneq {\mathfrak{gl}}_{n}({\mathbb{C}})\) be the general linear group and its Lie algebra, respectively. An important invariant of the embedded variety \(X\) is the group \[G_X \coloneq \{g \in \operatorname{GL}\nolimits_n \mid gX = X \}\] of linear symmetries of \(X\), often called the symmetry group or the linear preserver subgroup of \(X\). Knowledge of \(G_X\) can be exploited in the computation of other properties of \(X\). For instance, the vanishing ideal of \(X\) in the polynomial ring \({\mathbb{C}}[y_1 ,\ldots, y_n]\) is a \(G_X\)-module, and thus knowledge of the representation theory of \(G_X\) may help in determining (interesting subspaces of) that vanishing ideal.

By construction, \(G_X\) is a Zariski closed subgroup of \(\operatorname{GL}\nolimits_n\), and hence the union of finitely many connected components, which by standard algebraic group theory are also irreducible. Let \(G_X^0\) be the connected component containing the identity element \({{\mathrm{Id}_n}} \in \operatorname{GL}\nolimits_n\). This is a closed normal subgroup of \(G_X\), and \(G_X/G_X^0\) is a finite group; see, e.g., [1]. The identity component \(G_X^0\) is uniquely determined by the Lie algebra \({\mathfrak{g}}_X\) of \(G_X\). We call \({\mathfrak{g}}_X\) the symmetry Lie algebra of \(X\).

The problem of determining the symmetry group of an algebraic variety appears in several contexts [2], [3], in particular in the setting of varieties of matrices, tensors, or operators with special structure [4]–[6]. The symmetry Lie group of varieties of matrices of bounded rank was determined in [2], and [7] determined the symmetry group of the variety of rank-one tensors. More recently, [8] generalized this result to a wide range of secant varieties of tensors and other related varieties. In [9], the symmetry Lie algebra of an algebraic variety \(X\) is computed from the polynomials vanishing on \(X\), and in [9], [10], \({\mathfrak{g}}_X\) is used to test whether the vanishing ideal of \(X\) is binomial after an invertible linear change of variables.

The purpose of this paper is to show that the Lie algebra \({\mathfrak{g}}_X\) of \(G_X\) can be computed directly from the parametrization \(\varphi\) without first computing the defining ideal of \(X\). We give practical polynomial-time Monte Carlo algorithms for computing \({\mathfrak{g}}_X\) and detecting binomiality after an invertible linear change of variables. We show that this insight is useful to derive theoretical results as well: we apply it to varieties of staged tree models and colored Gaussian graphical models, to rational curves and to secant varieties.

The following paragraphs briefly highlight the main contributions of this paper.

Computing the symmetry Lie algebra↩︎

We characterize the symmetry Lie algebra of the parametrized variety \(X\) as the algebra of linear maps that send each point of \(X\) into its tangent space at that point (4), and consequently, into the span of the columns of the Jacobian of \(\varphi\) (5). For dimensionality reasons, only a finite number of points of \(X\) are needed for the computation. We implement this in the probabilistic 1 and the deterministic 3.

In all our algorithms we assume that \(\varphi\) is defined over the field of rational numbers \({\mathbb{Q}}\); in this case, \({\mathfrak{g}}_X\) is the \({\mathbb{C}}\)-linear span of \({\mathfrak{g}}_{X,{\mathbb{Q}}} \coloneq {\mathfrak{g}}_X \cap {\mathfrak{gl}}_n({\mathbb{Q}})\), and our algorithm computes a basis for \({\mathfrak{g}}_{X,{\mathbb{Q}}}\). This restriction on the coefficients is very mild: on the one hand, in many applications \(\varphi\) is indeed defined over \({\mathbb{Q}}\); and on the other hand, the algorithms can easily be extended to computations in a fixed finite-degree extension of \({\mathbb{Q}}\). They can also be extended to transcendental extensions, but they may no longer run in polynomial time, as rational-function coefficients can become super-polynomial in size.

The input \(\varphi\) can be given in either of two ways:

1. the standard encoding, where each \(f_i\) is given as an explicit rational function \(a_i/b_i\), with \(a_i\) and \(b_i\) polynomials in \({\mathbb{Q}}[x_1 ,\ldots, x_m]\) represented as a list of pairs \((c_\alpha,\alpha)\) with \(\alpha \in {\mathbb{Z}}_{\geq 0}^m\) representing the exponent vector of the monomial \(x^\alpha\) and \(c_\alpha \in {\mathbb{Q}}\) recording its coefficient;

2. the circuit encoding, where each \(f_i\) is given as an algebraic circuit in the sense of [11]: nodes with in-degree \(0\) are labelled by a constant or a variable \(x_i\), nodes with in-degree \(1\) compute the inversion \(a \mapsto a^{-1}\), and nodes with in-degree \(2\) compute addition or multiplication. We assume that the inversion gates never receive as input a function that is identically \(0\). Such an algebraic circuit would not define any rational function.

The running time of 1 is polynomial in the bit length of the input \(\varphi\), given in either of the two encodings, and in \(\log(1/\epsilon)\) (11).

The result extends to more powerful models of computation. In the BSS model [12] extended with, say, sampling random real numbers from the uniform distribution on \([0,1]\), one may allow \(\varphi\) to be defined over \({\mathbb{R}}\) or even \({\mathbb{C}}\). In this case, 1 runs in polynomial time in the size of the input and returns a basis for \({\mathfrak{g}}_{X}\) with probability \(1\).

For a deterministic approach, we give 3, obtained by derandomizing 1. In this case, we lose polynomiality of the running time as rational function expressions can potentially become large.

Testing \(\operatorname{GL}\nolimits\)-binomiality↩︎

In [9], [10], the problem of determining the symmetry Lie algebra is studied within the context of toric varieties, particularly to establish necessary conditions for a variety \(X \subseteq \mathbb{C}^n\) to have a \(\operatorname{GL}\nolimits\)-binomial ideal—that is, for there to exist matrix \(g\in \operatorname{GL}\nolimits_n\) such that \(gX\) is the vanishing set of an ideal generated by polynomials with at most two terms. The condition \(\dim {\mathfrak{g}}_X\geq \dim X\) is presented as a necessary one in [9]. This result is generalized in [10], which presents an algorithm for deciding whether \(X\) has a binomial ideal after a coordinate change. This algorithm requires access to the defining ideal \(I(X)\): first it computes the symmetry Lie algebra \(\mathfrak{g}_X\), then identifies the Lie algebra of a maximal torus \(T\) within \(G_X\), and finally verifies whether \(T\) has a dense orbit in \(X\). We discuss a Monte Carlo variant of this approach which does not require access to the defining ideal \(I(X)\) and it is applicable directly on a parametrization of \(X\).

We give a deterministic variant of this algorithm in 4.

Applications to staged tree models↩︎

Staged tree models are discrete models that represent dependency relations among events and are realized by a staged tree, that is, a rooted directed tree with colored nodes and labeled edges. Algebraically, the model is the image closure of the polynomial map in 2 given by the product of edge labels along root-to-leaf paths.

Binary one-stage tree models are all \(\operatorname{GL}\nolimits\)-binomial by [13]. However, not all binary staged trees have \(\operatorname{GL}\nolimits\)-binomial ideal by [9] of a binary tree model with \(4\) stages whose ideal is not \(\operatorname{GL}\nolimits\)-binomial, and not all ternary one-stage trees have \(\operatorname{GL}\nolimits\)-binomial ideal by [9] which shows that the ternary one-stage tree \(\mathcal{C}_{3,4}\) of depth \(4\) (the first tree in 2) does not have \(\operatorname{GL}\nolimits\)-binomial ideal.

We prove (24) that \(\operatorname{GL}\nolimits\)-binomiality breaks as soon as two stages are involved: we test this property for all \(127\) binary staged tree models with \(2\) stages of depth at most \(3\), and find that the \(4\) models in 1 are not \(\operatorname{GL}\nolimits\)-binomial. We also tested \(\operatorname{GL}\nolimits\)-binomiality for the \(33\) extensions of the stage tree \(\mathcal{C}_{3,4}\) by at most two internal nodes (25): exactly \(16\) of them, listed in 2, are not \(\operatorname{GL}\nolimits\)-binomial.

Applications to colored Gaussian graphical models↩︎

These are generalizations of Gaussian graphical models, with symmetries in the entries of the concentration (precision) matrix, encoded in colorings of the graph. Its reciprocal variety is the image closure of the parametrization in 3 given by maximal minors of these symmetric matrices. We say that a model is \(\operatorname{GL}\nolimits\)-binomial when its reciprocal variety has a \(\operatorname{GL}\nolimits\)-binomial ideal.

Experimental results of [10] on graphical Gaussian models, imply that Gaussian graphical models are \(\operatorname{GL}\nolimits\)-binomial if and only if the graph is a block graph if and only if it is binomial in the original coordinates. Other works [14]–[16] provide classes of colored Gaussian graphical models on block graphs that are binomial in the original coordinates. In particular, in [14] is proven that a colored Gaussian graphical model is binomial in the original coordinates if and only if the graph is vertex regular, edge regular, and vertex triangle regular.

We show that colors in a graph can make or break \(\operatorname{GL}\nolimits\)-binomiality by testing all colorings of the (block) complete graph \(K_4\) and of the (non-block) cycle \(C_4\) on \(4\) nodes. More precisely, we find there are \(8\) colorings of \(C_4\) (28), recorded in 3, that give \(\operatorname{GL}\nolimits\)-binomial models, and that only \(40\) out of the \(215\) colorings of \(K_4\) give \(\operatorname{GL}\nolimits\)-binomial models (26). Moreover, among these \(40\) colorings of \(K_4\) there are \(6\) colored graphs that are non-vertex regular, non-edge regular and not triangle regular (¿tbl:fig:K4?), one serving as a counterexample to [16], which conjectures that \(\operatorname{GL}\nolimits\)-binomial BMT-derived models derived from phylogenetic trees with colored nodes must be vertex regular (27).

Lastly, we prove that in the extreme case when all vertices have one color and all edges have one color, the model is always \(\operatorname{GL}\nolimits\)-binomial, with reciprocal variety realized by a rational normal curve (29).

Symmetry Lie algebras of curves↩︎

We treat the case of parametrized curves, that is, when \(\varphi= (f_1 ,\ldots, f_n)\) is an \(n\)-tuple of univariate rational functions. In this case, Luroth’s Theorem guarantees that the curve is rational: in particular, up to reparameterization, the generic fiber of \(\varphi\) is a single point.

We completely classify the possible symmetry Lie algebras of \(X\) in 31. More precisely, we show that \({\mathfrak{g}}_X\) is either trivial, the span of a diagonalizable matrix, or a \(2\)-dimensional parabolic subalgebra of \(\mathfrak{sl}_2\). In the last case, \(X\) is an affine rational normal curve. In particular, whenever \({\mathfrak{g}}_X \neq \{0\}\), \(X\) has a \(\operatorname{GL}\nolimits\)-binomial ideal, and up to a linear change of coordinates, the components of the parametrization of \(X\) are powers of a fixed rational function.

Symmetry Lie algebras of secant varieties↩︎

Let \(X \subseteq {\mathbb{C}}^n\) be an irreducible variety that is closed under scalar multiplication, that is, \(\lambda q \in X\) for \(q \in X\) and \(\lambda \in {\mathbb{C}}\). The \(r\)-th secant variety of \(X\) is \(\sigma_r(X) \coloneq \overline{\{q_1+\cdots+q_r \mid q_i \in X\}} \subseteq {\mathbb{C}}^n.\) Note that \(\dim(\sigma_r(X)) \leq \min\{n,r \dim X \}\). The symmetry Lie group of \(X\) is contained in that of \(\sigma_r(X)\) and this containment may be strict: for instance, if \(X\) is not a linear space and \(r\) is large enough that \(\sigma_r(X)\) is the linear span of \(X\).

We show (33) that when \(\sigma_{r+1}(X)\) has the expected dimension \((r+1)\dim X\), the symmetry Lie algebras of \(X\) and \(\sigma_r(X)\) coincide, and consequently so do the identity components of their symmetry Lie groups. The proof of 33 does not require \(X\) to be unirational. It relies on the natural “parametrization” from \(X^r\) to the \(r\)-th secant variety \(\sigma_r(X)\) of \(X\), sending an \(r\)-tuple of points to their sum.

Organization of this paper↩︎

The paper is organized as follows. In 2 we prove a geometric characterization of \({\mathfrak{g}}_X\) via the tangent spaces at points of \(X\), which underlies 1 and many other results in this paper. In 3 we prove 1, and in 4 we prove 2. In 5 we derandomize 1 and 2. In 6 we report on computational experiments with staged tree models and colored Gaussian graphical models, and prove 29. In 7 we characterize rational curves \(X\) that satisfy \({\mathfrak{g}}_X \neq \{0\}\), showing that this occurs precisely when, up to a linear change of coordinates, the components of the parametrization are powers of a fixed rational function. Finally, in 8 we prove 33 and apply it to secant varieties of Segre-Veronese embeddings.

We implemented 1 and 2 in SageMath. The implementation, together with the computational experiments from 6, is available at

2 A geometric characterization of the symmetry Lie algebra↩︎

We provide a characterization of the symmetry Lie algebra of a variety \(X\) as the algebra of linear maps that map each point of \(X\) into its tangent space to \(X\). Geometrically, this means that elements of the Lie algebra define vector fields on \(X\), and the corresponding complex-analytic one-parameter subgroups will define the integral curves of such vector fields, hence mapping \(X\) to itself.

In order to stay within the purely algebraic framework, rather than working with integral curves, we prove the result using a different characterization of the symmetry group and hence of its Lie algebra. We recall the following result which is a combination of [8] Lemma 3.1 and [1]; see also the discussion of [8].

Here \(A.f\) stands for the usual action of \({\mathfrak{gl}}_n\) on the polynomial ring \({\mathbb{C}}[y_1, \ldots, y_n]\) via derivations; explicitly, \((A.f)(q)\) is the coefficient of \(\epsilon\) in \(f((Id_n - \epsilon A).q)\); see also [9]. Using this characterization at the level of ideals, we obtain the following infinitesimal characterization in terms of tangent spaces.

We use 4 to give a more practical characterization of \({\mathfrak{g}}_X\) via the Jacobian of \(\varphi\). For rational map \(\varphi=(f_1 ,\ldots, f_n )\colon {\mathbb{C}}^m \dashrightarrow{\mathbb{C}}^n\), the Jacobian map of \(\varphi\) is \[\begin{align} J_\varphi\colon {\mathbb{C}}^m &\dashrightarrow{\mathbb{C}}^{n \times m} \\ p &\mapsto \left( \frac{\partial f_i}{\partial x_j}(p) \right)_{i,j}. \end{align}\] Define \(U_\varphi\coloneq \{p \in {\mathbb{C}}^m \mid \operatorname{rk}J_\varphi(p) = \dim X\}\).

For each \(p \in U_\varphi\), the condition that \(A.\varphi(p)\) lies in the column space of \(J_\varphi(p)\) defines a system of linear equations for the entries of \(A\). 5 shows that, as \(p\) varies over any dense subset \(S\) of \(U_\varphi\), these linear equations cut out \({\mathfrak{g}}_X\). Since any nonempty Zariski open subset of \({\mathbb{C}}^m\) contains rational points, we may take \(S = U_\varphi\cap {\mathbb{Q}}^m\). In particular, if the coefficients of the \(f_i\) all lie in \({\mathbb{Q}}\), then the linear system for \({\mathfrak{g}}_X\) is defined over \({\mathbb{Q}}\). Moreover, since \({\mathfrak{g}}_X\) is a finite-dimensional vector space, the system stabilizes after finitely many points: there exist \(p_1,\ldots,p_M \in U_\varphi\cap {\mathbb{Q}}^m\) such that the equations at \(p_1,\ldots,p_M\) alone already cut out \({\mathfrak{g}}_X\). This observation is used to design 1 in the next section.

The characterization of \({\mathfrak{g}}_X\) in 4 applies to any variety \(X\). Special geometric features of \(X\) can however simplify the computation considerably. We record two such cases: when \(X\) is linearly degenerate, that is, contained in a proper linear subspace of \({\mathbb{C}}^n\), and when \(X\) is a cylinder, that is, \(X = \pi^{-1}\pi(X)\) where \(\pi\colon {\mathbb{C}}^n \to {\mathbb{C}}^n/L\) is the quotient by some linear subspace \(L\).

6 and 7 are dual to each other in a precise sense, which we record here.

We conclude this section with a remark about affine symmetries, that is the group of transformations on \({\mathbb{C}}^n\) generated by \(\operatorname{GL}\nolimits_n\) and translations; see also [10].

3 A polynomial-time algorithm for computing the symmetry Lie algebra↩︎

This section presents 1, a polynomial-time probabilistic algorithm that computes \({\mathfrak{g}}_X\) of a variety \(X\) given a rational parametrization \(\varphi=(f_1,\ldots,f_n)\) of \(X\).

To ensure the input is nontrivial and that all variables appear, we make the following technical assumptions on the encoding of the input of 1.

1. If the \(f_i\) are given in a standard encoding as lists of pairs \((c,\alpha)\) of coefficients and exponent vectors, then at least one \(f_i\) is nonzero, that is, represented by a nonempty list.

2. If the \(f_i\) are given as arithmetic circuits, then every variable \(x_j\) appears as the label of at least one node in at least one of the \(n\) circuits.

Under these technical assumptions, 1 runs in polynomial time. This is the content of the next result.

This concludes the proof of 1.

4 Testing \(\operatorname{GL}\nolimits\)-binomiality↩︎

We say that an ideal \(I \subseteq {\mathbb{C}}[y_1 ,\ldots, y_n]\) is \(\operatorname{GL}\nolimits\)-binomial if there exists \(g \in \operatorname{GL}\nolimits_n\) such that \(g I\) is generated by binomials, that is, polynomials of the form \(y^\alpha - cy^\beta\) where \(\alpha,\beta \in {\mathbb{Z}}_{\geq 0}^n\) and \(c \in {\mathbb{C}}\). A variety \(X \subseteq {\mathbb{C}}^n\) is \(\operatorname{GL}\nolimits\)-binomial if \(I(X)\) is a \(\operatorname{GL}\nolimits\)-binomial ideal. Note that we allow \(c = 0\), consistent with [18].

This section presents 2, a polynomial-time probabilistic algorithm that decides, given a parametrization of a variety \(X \subseteq {\mathbb{C}}^n\), whether \(X\) is \(\operatorname{GL}\nolimits\)-binomial. The algorithm combines 1 with ideas from [10] and known facts about algebraic groups.

The correctness of 2 uses 16. For a matrix \(A \in {\mathfrak{gl}}_n\), the adjoint map \(\operatorname{ad}\nolimits(A)\colon {\mathfrak{gl}}_n \to {\mathfrak{gl}}_n\) is defined by \(\operatorname{ad}\nolimits(A)(B) = [A,B] = AB - BA\). The Jordan decomposition guarantees that any \(A\) can be written uniquely as \(A = A_s + A_n\), where \(A_s\) is semisimple, \(A_n\) is nilpotent, and \(A_s\) has the same eigenvalues as \(A\).

The following result completes the proof of 2.

Now we share some remarks on 2.

5 Derandomising↩︎

1 and 2 can be derandomized at the cost of losing polynomial running time. Throughout this section we assume that the input of \(\varphi\) is given in the standard encoding, and we carry out symbolic computations with rational functions.

6 Computational experiments↩︎

A recurring theme in algebraic statistics is to determine when a statistical model is \(\operatorname{GL}\nolimits\)-binomial, that is, it can be realized as the solution set of binomial equations, possibly after a linear change of variables. One then uses these binomials, together with monomial parametrizations of the variety and the geometry of the associated polytope, to address statistical questions, particularly in model selection and the study of likelihood geometry. In this spirit, we apply 2 to two families of models defined by rational parametrizations: staged tree models and colored Gaussian graphical models.

Staged tree models↩︎

Staged tree models are discrete models that represent dependency relations among events and are realized in a staged tree \(\mathcal{T}\), that is, a rooted directed tree with colored nodes and labeled edges. Nodes represent events, and edge labels are conditional probabilities between events. Let the stages or colors in the internal nodes of \(\mathcal{T}\) be \(1 ,\ldots, S\). Nodes of the same color \(s\in [S]\), must have the same number of outgoing edges \(m_s\) and the same labels \(\theta_{s,1} ,\ldots, \theta_{s,m_s}\) in their outgoing edges.

Given that the labels represent probabilities, the last parameter is an expression in terms of the other parameters, that is, \(\theta_{s,m_s}=1-(\theta_{s,1}+\ldots +\theta_{s,m_s-1})\). So, the dimension of the model is \(\prod_{i=1}^S(m_i-1)\). Let the leaves of \(\mathcal{T}\) be \(1 ,\ldots, n\). The leaves of the tree represent the final events. Their probability is the product of the edge labels along the path from the root to the leaf. Let \(\lambda(\ell)\) be the sequence of edges on the path from root to leaf \(\ell\), and \(\theta(e)\) denote the label for edge \(e\). The depth of \(\mathcal{T}\) is the maximum among all \(\#\lambda(\ell)\). In algebraic terms, the staged tree model for \(\mathcal{T}\) is the image of parametrization \[\begin{align} \label{eq:parametrization95for-staged95trees} \varphi\colon {\mathbb{C}}^{m_1+\cdots+m_S-S+1} \dashrightarrow{\mathbb{C}}^{n}, \quad (\theta_{s,i} \mid s=1 ,\ldots, S, i=1,\ldots m_s-1) \mapsto (\prod\limits_{e\in \lambda(\ell)}\theta(e))_{\ell=1}^n. \end{align}\tag{2}\] For illustration, consider the first binary staged tree in 1 which has two stages, stage one red and stage two green. The model has parametrization given by polynomials: \[\begin{align}f_1 &= \theta_{1,1} \theta_{2,1} \\ f_4 &= (1-\theta_{1,1}) \theta_{1,1} \\\quad \begin{aligned} f_2 &= \theta_{1,1} (1- \theta_{2,1}) \theta_{2,1}\\ f_5 &= (1-\theta_{1,1}) (1-\theta_{1,1}) \theta_{2,1} \\ \end{aligned} \quad \begin{align} f_3 &= \theta_{1,1} (1- \theta_{2,1}) (1-\theta_{2,1})\\ f_6 &= (1-\theta_{1,1}) (1-\theta_{1,1}) (1-\theta_{2,1}).\\ \end{align} \end{align}\] By [13], all binary one-stage tree models, that is when \(S=1\), are \(\operatorname{GL}\nolimits\)-binomial given by Veronese embeddings. Ternary one-stage tree models of depth at most \(3\) also are \(\operatorname{GL}\nolimits\)-binomial by [13], while in depth \(4\), the caterpillar tree \(\mathcal{C}_{3,4}\), the first tree in 2, is not \(\operatorname{GL}\nolimits\)-binomial by [9]. Binary staged trees are not all \(\operatorname{GL}\nolimits\)-binomial either: an example with \(4\) stages is given in [9] and one with \(10\) stages in [24].

To understand when \(\operatorname{GL}\nolimits\)-binomiality fails, we undertake a systematic study of binary tree models in two stages. We find that non-\(\operatorname{GL}\nolimits\)-binomial staged tree models already occur for trees of depth as low as \(3\).

To better understand one-stage tree models, we also consider extensions of the caterpillar tree model \(\mathcal{C}_{3,4}\), the first tree in 2, the smallest one-stage tree model which is not \(\operatorname{GL}\nolimits\)-binomial. Since the set of all ternary one-stage trees is quite large, we restrict to extensions of \(\mathcal{C}_{3,4}\) by at most \(3\) internal nodes within the set of ternary one-stage trees of depth \(4\).

Colored Gaussian graphical models↩︎

Colored Gaussian graphical models are linear concentration models used to model dependency relations among i.i.d. Gaussian random variables, encoded in a colored graph. The nodes represent the variables, a missing edge implies that the associated entry in the concentration matrix \(K\) must be zero, and nodes and edges that share a color imply that the corresponding entries in \(K\) must be the same. These models generalize Gaussian graphical models, which are defined solely by the missing-edge conditions. More precisely, let \(G\) be a colored graph on the vertex set \(\{1 ,\ldots, n\}\), color set \(\{1 ,\ldots, m\}\) and edge set \(E\), where edges and vertices do not share colors. Let \(\theta_1 ,\ldots, \theta_m\) be parameters associated to each color. Consider the \(m\)-dimensional linear space of \(n\times n\) symmetric matrices \(\mathcal{L}_G\cong {\mathbb{C}}^m\) with constraints for \(K \in {\mathbb{C}}^{n \times n}\) given by \[K\in \mathcal{L}_G \quad \text{ if and only if } \quad \begin{array}{l} k_{ii} = \theta_{\mathrm{color}(i)} \text{ for } 1\leq i\leq n,\\ k_{ij} = 0 \text{ if } i \neq j \text{ and } \{i,j\}\not \in E, \\ k_{ij} = \theta_{\mathrm{color}(\{i,j\})} \text{ if } \{i,j\} \in E. \end{array}\] The reciprocal variety \(\mathcal{L}_G^{-1}\) of \(\mathcal{L}_G\) is the Zariski closure of the image of the rational map \[\begin{align} \label{eq:colored32graph} \varphi_G: {\mathbb{C}}^{m} \dashrightarrow{\mathbb{C}}^{\binom{n+1}{2}},\;(\theta_i)_{i=1}^m \mapsto ((K(\theta)^{-1})_{ij})_{1\leq i\leq j\leq n}. \end{align}\tag{3}\] This variety can equivalently be given by the image of the map defined by the maximal minors of \(K(\theta)\). The intersection of \(\mathcal{L}_G^{-1}\) with the cone of positive definite matrices \(PD_n\) determines the set of covariance matrices of the colored Gaussian graphical model. We say that the colored Gaussian graphical model for \(G\) is \(\operatorname{GL}\nolimits\)-binomial if \(\mathcal{L}_G^{-1}\) is \(\operatorname{GL}\nolimits\)-binomial.

Reciprocal varieties of linear spaces of matrices have been studied in different contexts, both in algebraic statistics in [16], [25], [26], and in other areas of mathematics such as Schubert calculus [27], and the study of tensors [28], [29].

The key takeaway of the experiments in [10] is that a Gaussian graphical model is \(\operatorname{GL}\nolimits\)-binomial if and only if it is binomial in the original variables, which occurs if and only if the graph is a block graph. This does not hold for colored graphs: [14] shows that triangle-regular block graphs, that is, block graphs that are vertex-regular, edge-regular, and vertex-triangle-regular, are exactly those graphs for which \(I(\mathcal{L}^{-1}_{G})\) is binomial in the original variables. Furthermore, [16] shows that there are colored Gaussian graphical models on block graphs outside this class that are \(\operatorname{GL}\nolimits\)-binomial.

It is natural to ask whether all colorings of block graphs give a binomial model, and whether certain colorings of non-block graphs can also give binomial models. To investigate this, we tested \(\operatorname{GL}\nolimits\)-binomiality for all colorings of the complete graph \(K_4\) and the cycle \(C_4\) on \(4\) nodes. We found that most colorings of block graphs give non-\(\operatorname{GL}\nolimits\)-binomial models, while some colorings of non-block graphs do yield \(\operatorname{GL}\nolimits\)-binomial models.

BMT-derived graphs are colored graphs whose coloring is induced by a phylogenetic tree with colored and zeroed nodes, introduced in [16]. More precisely, \(k_{ii}\) is the parameter corresponding to the color of leaf \(i\) in the colored tree, \(k_{ij}=0\) when the internal node corresponding to the least common ancestor of \(i\) and \(j\) is labeled \(0\), and \(k_{ij}=k_{uv}\) when leaves \(i,j\) and \(u,v\) share the same least common ancestor. The paper proves that all vertex-regular BMT-derived graphical models are \(\operatorname{GL}\nolimits\)-binomial, and conjectures that the converse also holds. We provide a counterexample.

Finally, we record the fact that colored Gaussian graphical models with the minimal trivial coloring, that is, with \(2\) colors, one for the vertices and one for the edges, are all \(\operatorname{GL}\nolimits\)-binomial. To see this, we realize \(\mathcal{L}^{-1}_G\) as the affine cone over the \((n-1)\)-th collineation variety of a pencil of matrices, that is, the closure of the image of the rational map sending a matrix to its tuple of \((n-1)\times (n-1)\) minors. By [29], collineation varieties of matrix pencils are rational normal curves whose degree is controlled by the intersection of the pencil with the varieties of matrices of bounded rank; in particular, they are \(\operatorname{GL}\nolimits\)-binomial.

29 implies in particular that all colored Gaussian graphical models on cycles with \(2\) colors are \(\operatorname{GL}\nolimits\)-binomial. This also occurs for other colorings, as shown in 28. It would be interesting to use 2 to classify all colorings of the cycle \(C_n\) for \(n\geq 5\) that yield \(\operatorname{GL}\nolimits\)-binomial models. Since most of these models are linearly degenerate, the analysis can be simplified by using results on their linear relations [30], [31].

7 Symmetry Lie algebras of curves↩︎

In this section, we use 4 and material from 4 to characterize when a rational curve \(X\) given by a parametrization has \({\mathfrak{g}}_X \neq \{0\}\).

We first establish some terminology. The leading coefficient of a nonzero rational function \(r=a/b\) for polynomials \(a,b \in {\mathbb{C}}[t]\) is by definition the leading coefficient of \(a\) divided by that of \(b\). If the leading coefficient of \(r\) equals \(1\), we call \(r\) monic. The degree of \(r\) equals \(\deg(a)-\deg(b) \in {\mathbb{Z}}\), the order of the pole at infinity, and we set \(\deg(0) \coloneq -\infty\). These notions behave similarly to the case of polynomials. In particular, if \(r,s\) are rational functions of different degrees, then \(\deg(r+s)=\max\{\deg(r),\deg(s)\}\) and if \(r,s\) are monic rational functions of the same degree, then \(\deg(r-s)<\max\{\deg(r),\deg(s)\}\). Also, if \(r\) is a monic rational function of degree \(d\), then its derivative \(r'\) has degree \(d-1\) and leading coefficient \(d\), unless \(d=0\), in which case \(\deg(r')\) is a value between \(-\infty\) (if \(r\) is a constant) and \(d-2\).

If \(X\) is parametrized by Laurent monomials \(t^{e_i}\), then \({\mathfrak{g}}_X\) is easy to characterize.

The situation analyzed in 30 is the general situation whenever \({\mathfrak{g}}_X\neq \{0\}\).

In the case \((e_1,\ldots,e_n) = (0,\ldots,n-1)\), consider the affine space \(\{y_1 = 1\} \subseteq {\mathbb{C}}^n\) as an affine chart of \({\mathbb{P}}^{n-1}\). The projective closure \(\overline{X} \subseteq {\mathbb{P}}^{n-1}\) is then a rational normal curve, and its intersection with the hyperplane at infinity is a single point \(q\). In this case, the symmetry Lie algebra of \(\overline{X} \subseteq {\mathbb{P}}^{n-1}\) is a copy of \({\mathfrak{sl}}_2\), and the two-dimensional algebra \({\mathfrak{g}}_X = \langle D, B\rangle\) of 31 is the Borel subalgebra of \({\mathfrak{sl}}_2\) stabilizing \(q\).

More generally, when \((e_1,\ldots,e_n) = (e_1, e_1+1,\ldots,e_1+n-1)\) with \(-n+2 \leq e_1 \leq -1\), the curve \(X\) is the complement of a hyperplane section of a rational normal curve \(\overline{X}\). In this case, the hyperplane section consists of two points \(\overline{X}\), and \({\mathfrak{g}}_X\) is the one-dimensional subalgebra of \({\mathfrak{sl}}_2\) stabilizing both points, namely the Cartan subalgebra spanned by \(D\).

We illustrate 31 in the case of the binary one-stage tree models from 6.

8 Secant varieties↩︎

Let \(X \subseteq {\mathbb{C}}^n\) be an algebraic variety invariant under rescaling, that is if \(q \in X\) then \(\lambda q \in X\) for all \(\lambda \in {\mathbb{C}}\). Note that in this case \(T_q X = T_{\lambda q} X\) for all \(\lambda \neq 0\). The variety \[\sigma_r (X) = \overline{\{ q_1 + \cdots + q_r \mid q_i \in X\}}\] is called the \(r\)-th secant variety of \(X\). It is immediate that \(G_X \subseteq G_{\sigma_r(X)}\). There are examples for which the inclusion is strict, see, e.g., [8]. In this section, we provide a sufficient condition for which, instead, equality holds at least at the level of the Lie algebra. Note that a standard parameter count provides \[\dim \sigma_r(X) \leq r \dim X ;\] we say that \(X\) has the expected dimension if equality holds. Terracini’s Lemma describes the tangent space to \(\sigma_r(X)\) at a point \(z = q_1 + \cdots + q_r\) with \(q_i \in X\) sufficiently general as: \[T_z \sigma_r(X) = T_{q_1} X + \cdots + T_{q_r} X.\] Note that \(\sigma_r(X)\) has the expected dimension if and only if the sum above is a direct sum. In particular, if \(\sigma_r(X)\) has the expected dimension, the same holds for \(\sigma_s(X)\) if \(s \leq r\).

The study of dimension of secant varieties is a classical theme in algebraic geometry. Extensive research is done especially on the case of Segre-Veronese varieties. Let \(V_1 ,\ldots, V_k\) be vector spaces and let \(d_1 ,\ldots, d_k\) be positive integers. Let \(S^{d_i}V_i \subseteq V_i^{\otimes d_i}\) be the \(d_i\)-th symmetric power of \(V_i\), that is the space of tensors which are invariant under the action of \({\mathfrak{S}}_{d_i}\) on \(V_i^{\otimes d_i}\) which permutes the tensor factors. The Segre-Veronese variety is \[X = \{v_1^{\otimes d_1} \otimes \cdots \otimes v_k ^{\otimes d_k} \mid v_i \in V_i \} \subseteq S^{d_1} V_1 \otimes \cdots \otimes S^{d_k} V_k.\] When \(k =1\), \(X\) is the Veronese variety, whose secant varieties have the expected dimension except for a small number of classical exceptions [32]; the classification of secant varieties having dimension smaller than expected is almost complete for the case of Segre varieties, that is when \(d_1 = \cdots = d_k = 1\) [33]; partial results in several regimes are known for the general setting [34]–[36].

The symmetry Lie group of Segre-Veronese varieties in \(\operatorname{GL}\nolimits( S^{d_1} V_1 \otimes \cdots \otimes S^{d_k} V_k)\) is the image of the subgroup \((\operatorname{GL}\nolimits(V_1) \times \cdots \times \operatorname{GL}\nolimits(V_k)) \rtimes {\mathfrak{S}}\) where \(\operatorname{GL}\nolimits(V_i)\) acts on the factor \(S^{d_i}V_i\) and \({\mathfrak{S}}\subseteq {\mathfrak{S}}_k\) is the subgroup that permutes the factors of the same dimension that have the same degree [8]. The following result is a direct application of 33.

We point out that in many cases the symmetry Lie algebra of an \(r\)-th secant variety coincides with that of the base variety, even if the \((r+1)\)-th (and often even the \(r\)-th) secant variety has dimension smaller than expected. A classical example are secant varieties of Segre varieties with two factors, that is, varieties of matrices of bounded rank, which have the expected symmetry Lie algebra whenever they do not fill the ambient space [2]. The Segre varieties of \(3\) factors of dimension \(3\), and of \(4\) factors of dimension \(2\) have defective secant variety for \(r = 4\) and \(r=3\) respectively; however, the results of [8] show that all secant varieties of these Segre varieties have the expected symmetry group. In fact, the only examples that we know for which a secant variety of a Segre-Veronese variety has symmetry Lie algebra larger than the one of the base variety are pencils of matrices [8].

References↩︎