arXiv:1710.07175v1 [math.CO] 19 Oct 2017

The Geometry of Gaussoids
Tobias Boege, Alessio D’Alı̀, Thomas Kahle and Bernd Sturmfels
Abstract
A gaussoid is a combinatorial structure that encodes independence in probability and
statistics, just like matroids encode independence in linear algebra. The gaussoid axioms of Lněnička and Matúš are equivalent to compatibility with certain quadratic
relations among principal and almost-principal minors of a symmetric matrix. We develop the geometric theory of gaussoids, based on the Lagrangian Grassmannian and its
symmetries. We introduce oriented gaussoids and valuated gaussoids, thus connecting
to real and tropical geometry. We classify small realizable and non-realizable gaussoids.
Positive gaussoids are as nice as positroids: they are all realizable via graphical models.

1

Introduction

Gaussoids are combinatorial structures that arise in statistics and are reminiscent of matroids. They were introduced by Lněnička and Matúš [23] to represent conditional independence relations among n Gaussian random variables. The theory of matroids is ubiquitous in
the mathematical sciences, as it captures the combinatorial essence of many objects in algebra and geometry. Matroids of rank d on [n] = {1, 2, . . . , n} are possible supports of Plücker
coordinates on the Grassmannian of d-dimensional linear subspaces in a vector space K n .
This article develops the geometric theory of gaussoids, with focus on parallels to matroid
theory. The role of the Grassmannian is played by a natural projection of the Lagrangian
Grassmannian, namely the variety of principal and almost-principal minors of a symmetric
n × n-matrix Σ. Gaussoids aim to characterize which almost-principal minors can simultaneously vanish provided Σ is positive definite. This issue is important in statistics, where
Σ is the covariance matrix of a Gaussian distribution on Rn , and almost-principal minors
measure partial correlations. The sign of a minor indicates whether the partial correlation
is positive or negative. The minor is zero if and only if conditional independence holds.
Our goal in this paper is to carry out the program that was suggested in [34, §4]. We
assume that our readers are familiar with the geometric approach to matroids, including
oriented matroids and valuated matroids, as well as basic concepts in algebraic statistics.
Introductory books for the former include [3, 5, 24]. Sources for the latter include [9, 33, 34].
Let Σ = (σij ) be a symmetric n × n-matrix whose n+1
entries are unknowns. A minor
2
of Σ is the determinant of a square submatrix. The projective variety parametrized by all
minors of Σ is the Lagrangian Grassmannian LGr(n, 2n). It is obtained by intersecting the

1

2n
usual Grassmannian Gr(n, 2n) in its Plücker embedding in P( n )−1 with a linear subspace.
An affine chart of LGr(n, 2n) consists of all row spaces of rank n matrices of the form


1 0 0 ··· 0
σ11 σ12 σ13 · · · σ1n
0 1 0 · · · 0
σ12 σ22 σ23 · · · σ2n 




σ13 σ23 σ33 · · · σ3n 
(1)
Idn Σ
= 0 0 1 · · · 0
.
 .. .. .. . . ..
.. 
..
..
..
.
.
. . .
.
. .
. 
.
.
.
0 0 0 ··· 1
σ1n σ2n σ3n · · · σnn

The right n × n-block is symmetric. The quadratic Plücker relations for Gr(n, 2n) restrict to
quadrics that define LGr(n, 2n). It is known that those quadrics form a Gröbner basis. For
more information we refer to Oeding’s dissertation [27, § III.A] and the references therein.
A minor of Σ is principal if its row indices and its column indices coincide, and it is
almost-principal if its row and column indices differ in exactly one
 element. We introduce
unknowns that represent the 2n principal minors and the 2n−2 n2 almost-principal minors:


P = pI : I ⊆ [n]
and
A = aij|K : i, j ∈ [n] distinct and K ⊆ [n]\{i, j} .
To simplify notation, we write p for p∅ , p12 for p{1,2} , a12|3 for a12|{3} , etc. These unknowns
correspond respectively to the vertices and 2-faces of the n-cube, as shown in Figure 1.
p3

p13
p23

a12|3
p123
a13|2

a23

p2

a23|1

a13

p12
a12

p

p1

Figure 1: The vertices and 2-faces of the n-cube are labeled by the set of unknowns P ∪ A.

Consider the homomorphism R[P ∪A] → R[Σ] from a polynomial ring in 2n−2 (4 + n2 )
unknowns, where pI is mapped to the minor of Σ
unknowns to a polynomial ring in n+1
2
with row indices I and column indices I, and aij|K is mapped to the minor of Σ with row
indices {i} ∪ K and column indices {j} ∪ K. Here, the row indices are sorted so that i comes
first and is followed by K, and the column indices are sorted so that j comes first and is
followed by K, where the elements of K are listed in increasing numerical order. For instance,
a12|3 maps to σ12 σ33 − σ13 σ23 whereas a13|2 maps to −(σ12 σ23 − σ13 σ22 ). Maintaining this sign
convention is important to keep the algebra consistent with its statistical interpretation.
2

Let Jn denote the ideal generated by all homogeneous polynomials in the kernel of the map
above. This defines an irreducible variety V (Jn ) of dimension n+1
in the projective space
2
)−1
2n−2 (4+(n
)
2
whose coordinates are P ∪ A. There is a natural projection from LGr(n, 2n)
P
onto V (Jn ), obtained by deleting all minors that are neither principal nor almost-principal.
This is analogous to [27, Observation III.12], where the focus was on principal minors pI .

Proposition 1.1. The degree of the projective variety of principal and almost-principal
minors coincides with the degree of the Lagrangian Grassmannian. For n ≥ 2, it equals

n+1
!
2
.
degree(V (Jn )) = degree(LGr(n, 2n)) = n n−1 n−2
1 ·3
·5
· · · (2n − 1)
Proof. The degree of LGr(n, 2n) is due to Hiller [15, Corollary 5.3]. We learned this formula
from Totaro’s comment on the sequence A005118 in the OEIS: 2, 16, 768, 292864, . . .
It suffices to show that the birational map from LGr(n, 2n) onto V (Jn ) is base-point
n+2
n
n−2
free. Indeed, the center of the map P2 (4+( 2 ))−1 99K P( 2 ) consists of the points whose
coordinates indexed by principal and almost-principal minors are all zero. No such point (1)
can arise from a nonzero matrix Σ = (σij ). Hence the center is disjoint from LGr(n, 2n).
There are two natural symmetry classes of trinomials in Jn . First,
 there is one trinomial
for each 2-face of the n-cube. The cardinality of that class is 2n−2 n2 . A representative is
a212 − p1 p2 + p12 p.

(2)

Second, there is one trinomial for each inclusion of an edge in a 3-cube, in the boundary of
the n-cube. The number of these edge trinomials is 12 · 2n−3 n3 . One representative is
pa23|1 − p1 a23 + a12 a13 .

(3)

In Section 2 we review the axiom system for gaussoids found in [23], and we show in
Theorem 2.4 that these axioms are equivalent to compatibility with the edge trinomials (3).
In Section 3 we examine a natural action of the group G = SL2 (R)n on the polynomial
ring R[P ∪ A]. This fixes the ideal Jn . Certain finite subgroups of G serve as symmetry
groups for the combinatorial structures in this paper. In Section 4 we classify gaussoids up
to n = 5, taking into account the various symmetry groups in G. Our computations make
extensive use of state-of-the-art SAT solvers. In Section 5 we introduce and classify oriented
gaussoids. Theorem 5.6 asserts that every positive gaussoid is realizable by an undirected
graphical model. In Section 6 we determine all quadrics in Jn , and we conjecture that they
generate. Section 7 focuses on valuated gaussoids and tropical geometry, and Section 8
addresses the realizability problem for gaussoids and oriented gaussoids. Our supplementary
materials website www.gaussoids.de contains various classifications reported in this paper.

2

Gaussians and Axioms

A symmetric n × n-matrix Σ = (σij ) is the covariance matrix of an n-dimensional normal
distribution (or Gaussian) if Σ is positive definite, i.e., if the 2n principal minors pI of Σ are
3

all positive. Let X1 , X2 , . . . , Xn be random variables whose joint distribution is Gaussian
with covariance matrix Σ. For any subset K ⊆ [n] we write XK for the random vector
(Xi : i ∈ K) in R|K| . The variable Xi is independent of the variable Xj given the variable
XK if and only if the almost-principal minor aij|K of Σ is zero. See [9, Proposition 3.1.13].
This conditional independence (CI) statement is usually denoted by Xi ⊥
⊥ Xj | XK and also
known as an elementary CI statement. Restriction to only these statements is justified in
[33, § 2.2.3]. Other notations found in the literature include i ⊥ j|K, hi, j|Ki, and (ij|K).
We shall keep things simple by identifying all of these symbols with our unknown aij|K ∈ A.
Reasoning and inference with conditional independence statements plays a fundamental
role in statistics, especially in the study of graphical models [10, 23, 26, 33, 36]. A guiding
problem has been to characterize collections of conditional independence statements that
can hold simultaneously within some class of distributions. This led to the theory of semigraphoids; see e.g. [26, § 2]. We here focus on the class of Gaussian distributions on Rn .
The guiding problem now takes the following algebraic form: which sets of almost-principal
minors aij|K can be simultaneously zero for a positive definite symmetric n × n-matrix Σ?
To study this question, Lněnička and Matúš [23] introduced the following axiom system,
which we present here in our notation. As before, A is the set of all symbols aij|K where i, j
are distinct elements
in [n] = {1, 2, . . . , n} and K is a subset of [n]\{i, j}. Thus the set A

n n−2
consists of 2 2
symbols aij|K . We identify these symbols with the 2-faces of the n-cube.
Following [23, Definition 1], a subset G of A is a gaussoid on [n] if it satisfies:
(G1) {aij|L , aik|jL } ⊂ G implies {aik|L , aij|kL} ⊂ G,
(G2) {aij|kL , aik|jL} ⊂ G implies {aij|L , aik|L } ⊂ G,
(G3) {aij|L , aik|L } ⊂ G implies {aij|kL , aik|jL} ⊂ G,


(G4) {aij|L , aij|kL } ⊂ G implies aik|L ∈ G or ajk|L ∈ G .

Axiom (G1) is the definition of a semigraphoid, and (G2) is known as the intersection axiom.
Axiom (G3) is a converse to intersection, and axiom (G4) is called weak transitivity.
Being a gaussoid is a necessary condition for a subset G ⊆ A to comprise the vanishing
almost-principal minors of a positive definite symmetric n × n-matrix Σ. The gaussoid G is
called realizable if such a matrix Σ exists. All gaussoids are realizable for n = 3. This is no
longer true for n ≥ 4, as shown in [10, 23]. For an explicit example see Remark 4.3 below.

Example 2.1. Let n = 3. The set A has 6 elements, and hence it has 26 = 64 subsets.
Among these 64 subsets, precisely 11 are gaussoids. They are
{}, {a12 }, {a13 }, {a23 }, {a12|3 }, {a13|2 }, {a23|1 }, {a12 , a12|3 , a13 , a13|2 },
{a12 , a12|3 , a23 , a23|1 }, {a13 , a13|2 , a23 , a23|1 }, {a12 , a12|3 , a13 , a13|2 , a23 , a23|1 }.

(4)

Each of these gaussoids G is realizable by a positive definite symmetric 3 ×3-matrix. Equivalently, the variety V (J3 ) contains a real point (p, a) whose coordinates pI are all positive and
whose coordinates that vanish are precisely the elements aij|K in G. We invite the reader to
check that all 11 gaussoids G arise from an appropriate point (p, a) in the variety V (J3 ). ♦
4

Gaussoids are analogous to matroids. In matroid theory, one asks which sets of maximal
minors of a rectangular matrix can be simultaneously zero. Being a matroid is necessary but
not sufficient for this to hold. Vámos [39] showed that there is no finite axiom system for
realizability of matroids. Sullivant [36] established the same result for gaussoids.
One of the many axiom systems for matroids is the combinatorial compatibility with the
quadratic Plücker relations that define the Grassmannian [8, § 4]. Our aim is to derive the
analogous result for gaussoids. The role of the Grassmannian Gr(n, 2n) is now played by a
projection of the Lagrangian Grassmannian LGr(n, 2n), namely the variety V (Jn ).
Let f ∈ Jn be any polynomial relation among principal and almost-principal minors.
A subset G of A is incompatible with f if precisely one monomial in f has no unknown in G.
Otherwise G is compatible with f . Hilbert’s Nullstellensatz implies that G is compatible with
all f in Jn if and only if it is realizable by a symmetric n × n-matrix Σ with complex entries.
The ideal Jn contains two classes of distinguished trinomials of degree two, namely the
square trinomials (2), one for each 2-cube in the n-cube, and the edge trinomials (3), one for
each 1-cube in a 3-cube in the n-cube. The total number of these trinomials equals
 
 
n−3 n
n−2 n
= 2n−3 n(n − 1)(2n − 3).
(5)
+ 12 · 2
2
3
2

To represent the gaussoid axioms algebraically, we use the 12 · 2n−3 n3 edge trinomials.
Example 2.2. Fix n = 3. There are 12 edge trinomials, one for each edge in Figure 1:

p1 a23 − pa23|1 − a12 a13 , p2 a13 − pa13|2 − a12 a23 , p3 a12 − pa12|3 − a23 a13 ,
p12 a13 − p1 a13|2 − a12 a23|1 , p12 a23 − p2 a23|1 − a12 a13|2 , p13 a12 − p1 a12|3 − a13 a23|1 ,
p13 a23 − p3 a23|1 − a13 a12|3 , p23 a12 − p2 a12|3 − a23 a13|2 , p23 a13 − p3 a13|2 − a23 a12|3 ,
p123 a12 − p12 a12|3 − a23|1 a13|2 , p123 a13 − p13 a13|2 − a23|1 a12|3 , p123 a23 − p23 a23|1 − a12|3 a13|2 .
The subsets G of A that are compatible with these quadrics are precisely the sets in (4). The
full list of all 21 generators of J3 , clustered by symmetry class, appears in Example 3.3. ♦
The edge trinomials for n ≥ 4 are obtained by replicating these 12 quadrics on every
3-face of the n-cube. We can replace the indices 1, 2, 3 in the first quadric by i, j, k and then
add any set L ⊆ [n]\{i, j, k} to get the trinomial piL · ajk|L − pL · ajk|iL − aij|L · aik|L in Jn .
Example 2.3. Fix n = 4. The 4-cube has 24 two-dimensional faces, so A has 224 = 16777216
subsets. Only 679 of these are gaussoids. This was found in [23, Remark 6]. The gaussoids
on [4] are precisely the subsets G of A that are compatible with the 96 edge trinomials. ♦
The following is our main result in Section 2. It generalizes the previous two examples.
Theorem 2.4. The following conditions are equivalent for a set G of 2-faces of the n-cube:
(a) G is a gaussoid, i.e. the four axioms (G1)–(G4) are satisfied for G;
(b) G is compatible with all edge trinomials (3).
5

Proof. We begin by showing the implication from (b) to (a). For each of the four gaussoid
axioms we list either one or two of the edge trinomials that are relevant:
(G1) aij|L ajk|iL + aik|jL piL − aik|L pijL and aij|L pijkL − aik|jLajk|iL − aij|kL pijL ,

(G2) aij|kL pijL + aik|jL ajk|iL − aij|L pijkL and aik|jL pikL + aij|kL ajk|iL − aik|L pijkL ,
(G3) aij|L pkL − aik|L ajk|L − aij|kL pL and aij|L ajk|L − aik|L pjL + aik|jLpL ,
(G4) aij|L pkL − aij|kLpL − aik|L ajk|L .

Compatibility with these quadrics implies the axiom. For instance, consider axiom (G1).
Suppose that aij|L and aik|jL are in G. Then the first two terms of aij|L ajk|iL + aik|jL piL −
aik|L pijL have an unknown in G. Since pijL cannot be an element of G, we conclude that aik|L
is in G. Similarly, if the set G is compatible with the edge trinomial aij|L pijkL − aik|jL ajk|iL −
aij|kL pijL then we can conclude that aij|kL is in G. The other three axioms are shown similarly.
For the implication from (a) to (b) we first note that the statement was already shown
for n = 3. Namely, each of the 11 gaussoids is compatible with the 12 edge trinomials. Now,
suppose n ≥ 4. Each of the gaussoid axioms only refers to collections of unknowns aij|K that
lie within a particular 3-face of the n-cube. This means that a subset G of A is a gaussoid
if and only if the restriction of G to any 3-face is one of the 11 gaussoids on 3 symbols. The
same restriction property holds for compatibility with the edge trinomials.
Among the 679 gaussoids for n = 4, precisely 629 are realizable. The other 50 are
eliminated by the higher axioms in [10, Lemma 2.4] and [23, Lemma 10]. In Section 8 we
initiate a similar analysis for n = 5. Of course, by [36], we cannot hope for a complete axiom
system for Gaussian realizability, and it makes sense to focus on gaussoids and their relation
to the combinatorics of quadrics in Jn . This relation has a striking similarity to matroid
theory. It can be derived from the combinatorics of the the Grassmann–Plücker relations.
This approach was initiated thirty years ago by Dress and Wenzel [8] and extended recently
by Baker and Bowler [2]. The extent to which matroid theory and gaussoid theory can
be further developed in parallel remains to be investigated. It seems promising to study
gaussoids over hyperfields. Here is one concrete conjecture that points in such a direction.
Conjecture 2.5. Every gaussoid is compatible with all quadrics in Jn , not just trinomials.
A proof for n ≤ 4 is given in Corollary 4.4, but that proof technique does not generalize.
To prove Conjecture 2.5 for n ≥ 5, it suffices to check compatibility with those quadrics
that are circuits in the subspace (Jn )2 of the space of all quadrics. Each circuit lies in one
of the weight components described in Section 3. However, that check would amount to a
prohibitive computation, even for n = 5, because there are too many circuits.
As support for Conjecture 2.5 we verified compatibility with the quadrics in Theorem 6.4
for n = 5, 6. In general, quadrics with two or more terms that are products of only p
variables, such as the square trinomials in (2), need not be checked, as every subset of A is
compatible with them. This situation changes for the valuated gaussoids of Section 7.
Minors and duality play an important role in matroid theory. The minors of a matroid
are obtained by the iterated application of deletions and contractions. These two operations
6

are reversed under matroid duality. For gaussoids, the roles of deletion and contraction are
played by marginalization and conditioning. These statistical operations are also swapped
by the duality Σ ↔ Σ−1 . Let G be any gaussoid on [n]. The dual gaussoid G ∗ of G is

G ∗ = aij|[n]\(K∪{i,j}) : aij|K ∈ G .
(6)
For any element u ∈ [n], the marginal gaussoid G\u is the gaussoid on [n]\{u} given by

G\u =
aij|K ∈ G : u 6∈ {i, j} ∪ K .
Similarly, the conditional gaussoid G/u is the gaussoid on [n]\{u} given by

G/u =
aij|K\{u} ∈ G : u ∈ K .
We have the following basic result relating these minors and duality:

Proposition 2.6. If G is a gaussoid on [n] and u ∈ [n] then both G\u and G/u are gaussoids.
If G is realizable then so are G ∗ , G\u, and G/u. The following duality relation holds:
∗
∗
G\u = G ∗ /u and
G/u = G ∗ \u.
(7)

Proof. The set of edge trinomials in Jn is invariant under the duality operation that swaps
pK with p[n]\K and also swaps aij|K with aij|[n]\(K∪{i,j}). Theorem 2.4 hence ensures that G ∗
is a gaussoid. The duality operation preserves realizability: if a positive definite matrix Σ
realizes G, then its inverse Σ−1 realizes G ∗ by [23, Corollary 1 and Lemma 2].
A similar argument works for marginalization and conditioning. The edge trinomials for
[n]\{u} appear among those for [n], and similarly if we augment the index set K with u. That
realizability is preserved under these operations is [31, Lemma 1]. Indeed, if Σ realizes G,
then we obtain a realization of G\u by deleting row u and column u from Σ, and we obtain
a realization of G/u by taking the Schur complement of Σ with respect to u.
The duality relations (7) are verified by a direct check, bearing in mind that two of the
duals in this formula are taken with respect to the index set [n]\{u} instead of [n].
Kenyon and Pemantle [21] initiated the study of the ideal Jn from the perspective of
cluster algebras. They conjectured a formula for the entries of Σ in terms of principal and
almost-principal minors whose index sets are connected. That conjecture was proved by
Sturmfels, Tsukerman, and Williams in [35]. As explained in [35, § 5], this is closely related
to formulas for partial correlations in statistics [18]. If Σ is a covariance matrix, the associated
√
correlation matrix has ones on the diagonal and off-diagonal entries ρij = aij / pi pj . More
generally, the partial correlations of the Gaussian distribution given by Σ are the quantities
ρij|K = √

aij|K
.
piK pjK

(8)

Joe and his collaborators discuss the algebraic relations among the ρij|K and construct subsets
that serve as convenient transcendence bases modulo these relations. Their d-vines in [18]
correspond precisely to the standard networks of Kenyon and Pemantle in [21]. Our results
on gaussoids and the ideal Jn immediately imply new constraints on partial correlations.
7

3

Symmetry

We are interested
in the ideal Jn of algebraic relations among the 2n principal minors pL

and the n2 2n−2 almost-principal minors aij|K of a symmetric n × n-matrix of unknowns.
The analogous problem for principal minors alone was solved (set-theoretically) by Oeding
[27, 28]. He showed that the variety of the elimination ideal Jn ∩ R[P] is defined by quartics.
Example 3.1. Eliminating the six unknowns in A from J3 , we obtain the principal ideal
J3 ∩ R[P] = h p2p2123 + p21 p223 + p22 p213 + p23 p212 + 4pp12 p13 p23 + 4p1 p2 p3 p123 − · · · − 2p1 p3 p12 p23 i.
The quartic generator is the 2 × 2 × 2 hyperdeterminant. This fact was first found in [16]. ♦
Oeding’s result is based on the representation theory of the group G = SL2 (R)n . We aim
to understand Jn by using this technique. The point of departure is the observation that G
acts on the space W spanned by the principal and almost-principal minors. This action is
induced by the G-action on the space of n × 2n-matrices. Here, the group SL2 (R) in the ith
factor acts by replacing columns i and n + i by linear combinations of these two columns. If
we apply this to (1) and then multiply by the inverse of the left n × n-block then the right
n × n-block is again symmetric. See [16, Lemma 13] for a proof of this crucial observation.
In this section we study the structure of the G-module W . Let Vi ≃ R2 denote the
defining representation of the i-th factor SL2 (R). Let Wpr be the space spanned by all
ij
principal minors and Wap
the space spanned by the almost-principal minors aij|K where i, j
are fixed and K runs over subsets of [n]\{i, j}. The following is similar to [28, Theorem 1.1]:
Lemma 3.2. We have the following isomorphisms of irreducible G-modules:
Wpr ≃

n
O

Vi

i=1

and

ij
≃
Wap

O

Vk

k∈[n]\{i,j}

for 1 ≤ i < j ≤ n.

We use the unknown xi to refer to the highest weight of the G-module Vi . The highest
weight of a tensor product of such modules is the product of the corresponding xi . For
instance, Sym2 (V1 ) ⊗ V2 has highest weight x21 x2 . The formal character of a G-module is
the sum
Lof theij Laurent monomials representing the weights in a weight basis. Let W =
Wpr ⊕ i,j Wap be the G-module of principal and almost-principal minors. The set A ∪ P
is a distinguished weight basis of W . By Lemma 3.2, the formal character of W equals
n
Y
i=1

(xi + x−1
i ) +

X

Y

(xk + x−1
k ).

(9)

1≤i<j≤n k∈[n]\{i,j}

L
Our prime ideal Jn lives in the polynomial ring Sym∗ (W ) = ∞
d=0 Symd (W ) = R[P ∪ A].
It is invariant under the G-action. The weight of a monomial in R[P ∪ A] is a vector in Zn ,
namely, the exponent vector of the corresponding Laurent monomial in x1 , . . . , xn .
We focus on the G-module of all quadrics, Sym2 (W ). Its dimension equals
 
 


n−1
n−3 n
n
n−2 n
.
+1 · 2
+2
dim(Sym2 (W )) = 2 + 2
2
2
8

The formal character
 of Sym2 (W ) is the sum of all pairs of products (with repetition allowed)
n
n−2 n
of the 2 + 2
Laurent monomials that appear in the expansion of (9).
2
Each irreducible G-module has the form
Sd1 d2 ···dn =

n
O

Symdi (Vi ),

i=1

where d1 , d2, . . . , dn are nonnegative integers. In Oeding’s work [27, 28], this module was
written as Sd1 0 Sd2 0 · · · Sdn 0 . The formal character of the irreducible G-module Sd1 d2 ···dn equals
di
n X
Y
i=1 ℓ=0

xidi −2ℓ = xd11 xd22 · · · xdnn + lower terms.

(10)

Our task is to express the formal character of Sym2 (W ) as a sum of Laurent polynomials
(10), and to identify the submodule (Jn )2 in terms of the irreducible G-modules in Sym2 (W ).
Example 3.3. Let n = 3. The 8 principal and 6 almost-principal minors span the G-module
W = S111 ⊕ S100 ⊕ S010 ⊕ S001 .
This space of quadrics has dimension 105. It decomposes into irreducible G-modules as
Sym2 (W ) = S222 ⊕ S211 ⊕ S121 ⊕ S112 ⊕ 2S200 ⊕ 2S020 ⊕ 2S002 ⊕ 2S110 ⊕ 2S101 ⊕ 2S011 .
The ring Sym∗ (W ) = R[P ∪A] has 8 unknowns pI and 6 unknowns aij|K . They are identified
with the vertices and facets of the 3-cube (cf. Figure 1). The weights of the 14 unknowns are
unknown
weight

a12
a12|3
···
a23|1
p
p1
···
p123
(0, 0, 1) (0, 0, −1) · · · (−1, 0, 0) (1, 1, 1) (−1, 1, 1) · · · (−1, −1, −1)

The 21-dimensional space of quadrics in J3 generates the ideal. As a G-module,
(J3 )2 = S200 ⊕ S020 ⊕ S002 ⊕ S110 ⊕ S101 ⊕ S011 .
We display an explicit weight basis for each summand, beginning with the 12 edge trinomials:


(1, 1, 0)
a13 a23 + a12|3 p − a12 p3
 (1, −1, 0)
a13|2 a23 + a12|3 p2 − a12 p23 


S110
 (−1, 1, 0)
a13 a23|1 + a12|3 p1 − a12 p13 
(−1, −1, 0)
a13|2 a23|1 + a12|3 p12 − a12 p123
S101


a12 a23 + a13|2 p − a13 p2
a12|3 a23 + a13|2 p3 − a13 p23 

a12 a23|1 + a13|2 p1 − a13 p12 
a12|3 a23|1 + a13|2 p13 − a13 p123



(1, 0, 1)
 (1, 0, −1)

 (−1, 0, 1)
(−1, 0, −1)

9


a12 a13 + a23|1 p − a23 p1
a12|3 a13 + a23|1 p3 − a23 p13 

a12 a13|2 + a23|1 p2 − a23 p12 
a12|3 a13|2 + a23|1 p23 − a23 p123



(0, 1, 1)
 (0, 1, −1)

 (0, −1, 1)
(0, −1, −1)

S011

See Example 2.2. The last three G-modules account for the square trinomials:


(2, 0, 0)
a223 + pp23 − p2 p3
 (0, 0, 0)
2a23 a23|1 + pp123 + p1 p23 − p2 p13 − p12 p3 
S200
(−2, 0, 0)
a223|1 + p1 p123 − p12 p13


(0, 2, 0)
a213 + pp13 − p1 p3
 (0, 0, 0)
2a13 a13|2 + pp123 + p2 p13 − p1 p23 − p12 p3 
S020
(0, −2, 0)
a213|2 + p2 p123 − p12 p23


(0, 0, 2)
a212 + pp12 − p1 p2
 (0, 0, 0)
2a12 a12|3 + pp123 + p3 p12 − p1 p23 − p13 p2 
S002
(0, 0, −2)
a212|3 + p3 p123 − p13 p23

The case n = 3 is so small that every minor of Σ is either principal or almost-principal.
Hence J3 is the ideal defining the Lagrangian Grassmannian LGr(3, 6) ⊂ P13 . This variety
has dimension 6 and degree 16 = 6!/(1332 5). The following code in Macaulay2 [14] computes
the 21 quadrics from the 35 quadrics that cut out the Grassmannian Gr(3, 6) in P19 :
R = QQ[p123,p124,p134,p234,p125,p135,p235,p145,p245,p345,
p126,p136,p236,p146,p246,p346,p156,p256,p356,p456];
I = Grassmannian(2,5,R) + ideal(p124-p236,p125+p136,p134+p235,
p346+p245,p356-p145,p256+p146);
J3 = eliminate({p124,p134,p125,p356,p256,p346},I)
From the free resolution (computed with res J3) it can be verified that J3 is Gorenstein.
Each of the 20 generators of the polynomial ring R equals (up to sign) one of the 14
variables in P∪A. The precise identification is given by the following ordered list of length 20:
p a13 −a12 p1
a23 −p2 a12 a13|2 −a23|1 p12
p3 −a23 a13 a12|3 −p13 a23|1 p23 −a12|3 a13|2 p123

(11)

One comment for algebraic geometers: canonical curves of genus 9 are obtained by intersecting V (J3 ) = LGr(3, 6) with subspaces P8 in P13 . This was shown by Mukai and further
developed by Iliev and Ranestad [17], who derive the 21 quadrics explicitly in [17, § 2.3]. ♦
Example 3.4. Let n=4. There are 16 principal and 24 almost-principal minors. They span
W = S1111 ⊕ S1100 ⊕ S1010 ⊕ S1001 ⊕ S0110 ⊕ S0101 ⊕ S0011 .
The space of quadrics has dimension 820. It decomposes into irreducible G-modules as
Sym2 (W ) =

S2222 ⊕ S2211 ⊕ S2121 ⊕ S2112 ⊕ S1221 ⊕ S1212 ⊕ S1122 ⊕ 2S2200 ⊕ 2S2020
⊕ 2S2002 ⊕ 2S0220 ⊕ 2S0202 ⊕ 2S0022 ⊕ 2S2110 ⊕ 2S2101 ⊕ 2S2011 ⊕ 2S1210
⊕ 2S1201 ⊕ 2S0211 ⊕ 2S1120 ⊕ 2S1021 ⊕ 2S0121 ⊕ 2S1102 ⊕ 2S1012 ⊕ 2S0112
⊕ 3S1111 ⊕ 3S1100 ⊕ 3S1010 ⊕ 3S1001 ⊕ 3S0110 ⊕ 3S0101 ⊕ 3S0011 ⊕ 7S0000 .
10

The 226-dimensional submodule of quadrics that vanishes on our variety equals
(J4 )2 = S2200 ⊕ S2020 ⊕ S2002 ⊕ S0220 ⊕ S0202 ⊕ S0022 ⊕ S2110 ⊕ S2101 ⊕ S2011
⊕ S1210 ⊕ S1201 ⊕ S0211 ⊕ S1120 ⊕ S1021 ⊕ S0121 ⊕ S1102 ⊕ S1012
⊕ S0112 ⊕ S1100 ⊕ S1010 ⊕ S1001 ⊕ S0110 ⊕ S0101 ⊕ S0011 ⊕ 4S0000 .

(12)

Each of the four copies of the one-dimensional module S0000 is spanned by a G-invariant
quadric in the ideal J4 . Here is one such invariant that involves none of the principal minors:
a14 a14|23 − a14|2 a14|3 − a23 a23|14 + a23|1 a23|4 .
This quadric can be derived from the quadrics in Theorem 6.4 (iv). It is instructive to locate
the 24 square trinomials and the 96 edge trinomials inside the summands seen in (12). ♦
In Section 6 we study the quadrics in Jn . This uses the action of the Lie algebra g of the
group G. The situation differs from that in [27, 28]. Oeding’s hyperdeterminantal ideal is
generated by a single irreducible module for the action of G ⋊ Sn on Sym4 (Wpr ). In our case,
there are many irreducibles even modulo the action of Sn . The space (J3 )2 in Example 3.3
decomposes into two irreducible G ⋊ S3 -modules, and (J4 )2 in Example 3.4 decomposes into
five irreducible G ⋊ S4 -modules. This complexity accounts for the difficulties in Section 6.
We now shift gears and discuss a collection of finite groups that act on the combinatorial
structures studied in this paper. These finite groups arise from the following inclusions:
Sn ⊂ (Z/2Z)n ⋊ Sn ⊂ (Z/4Z)n ⋊ Sn ⊂ G ⋊ Sn .

(13)

The symmetric group Sn acts by permuting indices in the unknowns pI and aij|K , and by
simultaneously permuting the rows and columns of the matrix Σ in (1). The third group in
(13) is obtained by taking the following cyclic subgroup in each factor SL2 (R):

 
 
 

0 −1
−1 0
0 1
1 0
.
,
,
,
Z/4Z ≃
1 0
0 −1
−1 0
0 1
Remark 3.5. The action of (Z/4Z)n on the Lagrangian Grassmannian LGr(n, 2n) takes
symmetric matrices to symmetric matrices, but it changes their signatures. It thus does not
preserve the property that Σ is positive definite. In fact, already the induced action by the
hyperoctahedral group (discussed below) does not preserve realizability of gaussoids.

Consider the subgroup (Z/2Z)n = (±Id2 , ±Id2 , . . . , ±Id2 ) of SL2 (R)n . Each element
in this group corresponds to an n × n-diagonal matrix D with entries in {−1, +1}. Reorientation is the action of (Z/2Z)n that maps Σ to DΣD. This does not change the principal
minors of Σ. In particular, if Σ is positive definite, then so is DΣD. Under this action, the
almost-principal minor aij|K transforms into Dii Djj aij|K = ±aij|K . This action is trivial for
gaussoids, but it is non-trivial for oriented gaussoids, as we shall see in Section 5.
In order to get a faithful action on the set of gaussoids we need to take the quotient of
(Z/4Z)n ⋊Sn modulo its normal subgroup (Z/2Z)n ⋊{Id}. The resulting group (Z/2Z)n ⋊Sn
is the hyperoctahedral group. It acts on the set of gaussoids as the symmetry group of the
11

n-cube. The quotient (Z/2Z)n acts by swapping indices in and out from the index sets
I and K in the quantities pI and aij|K . When expressed in terms of Σ, the latter action
looks like a fusion of matrix inversion and Schur complements. Consider the subgroup of the
0 1
0 1
n
hyperoctahedral group given by Z/2Z = {(Id2 , . . . , Id2 ), (( −1
0 ), . . . , ( −1 0 ))} inside (Z/2Z) :
Sn ⊂ (Z/2Z) ⋊ Sn ⊂ (Z/2Z)n ⋊ Sn .

(14)

The group Z/2Z in the middle of (14) acts on the set of gaussoids by the duality in (6).
Algebraically, this is the involution on LGr(n, 2n) that maps Σ to its negative inverse −Σ−1 .
In summary, these finite group actions are subtle. In particular, the distinction between
reorientation and the hyperoctahedral group (both isomorphic to (Z/2Z)n ⋊ Sn ) is crucial.

4

Census of Small Gaussoids

In this section we derive and discuss the following result. The proof for n = 5 is by computation. It rests on using state-of-the-art software from the field of SAT solvers [37, 38].
Theorem 4.1. For n = 3, 4, 5, the number of gaussoids G is as follows, up to symmetries:
n
3
4
5

all gaussoids
11
679
60,212,776

orbits for Sn
5
58
508,817

Z/2Z ⋊ Sn
4
42
254,826

(Z/2Z)n ⋊ Sn
4
19
16,981

The second, third, and fourth column report the number of orbits under the group
actions described in (14). Theorem 4.1 for n = 3 is Example 2.1, where the 11 gaussoids
are listed. There are five orbits under permuting the indices 1, 2, 3. The two singleton orbits
fuse to a single orbit under the group Z/2Z ⋊ S3 . For instance, the gaussoids {a12 } and
{a12|3 } are swapped under duality. The same four orbits persist under the action of the
hyperoctahedral group (Z/2Z)3 ⋊ S3 , since |G| is an invariant of that action. For n = 4,
Lněnička and Matúš [23] showed that there are 679 gaussoids, of which 629 are realizable.
Their computation was confirmed by Drton and Xiao [10]. The action by the hyperoctahedral
group (Z/2Z)4 ⋊ S4 was not used in [10, 23], but we find this to be natural in our setting.
Lemma 4.2. The 679 gaussoids for n = 4 are organized into orbits as follows:
• The symmetric group S4 of order 24 acts on the gaussoids by permuting indices. There
are 58 orbits under that action. Five of these orbits consist of non-realizable gaussoids.
• The twisted symmetric group Z/2Z ⋊ S4 of order 48 acts on the gaussoids by duality
and permuting indices. This action preserves realizability, and it has 42 orbits. Five
of these orbits consist of non-realizable gaussoids.
• Under the action of the hyperoctahedral group (Z/2Z)4 ⋊ S4 of order 384, there are 19
orbits. Three of the orbits contain non-realizable gaussoids.
12

The difference between the three group actions can already be seen for the 24 singleton
gaussoids. These correspond to the 2-faces of the 4-cube. The symmetric group S4 has three
distinct orbits on the set A: the six 1 × 1-minors aij , the twelve 2 × 2-minors aij|k , and the
six 3 × 3-minors aij|kl . The 1 × 1-minors and the 3 × 3-minors are swapped under duality.
So, there are two orbits of size 12 for the group Z/2Z ⋊ S4 . Finally, the full symmetry group
of the 4-cube acts transitively on the 2-faces. Hence that group has only one orbit of size 24.
The following 19 items are the orbits of the hyperoctahedral group (Z/2Z)4 ⋊ S4 . The
symbol ℓm at the beginning indicates that the orbit consists of m gaussoids G, each of cardinality |G| = ℓ. This is followed by a list of Z/2Z⋊S4 -orbits, each given by its lexicographically
first representative. For instance, the fourth item, marked 248 , is a hyperoctahedral orbit
of size 48 that consists of two-element gaussoids G. If we restrict to permuting indices and
duality then this orbit breaks into four smaller orbits, of cardinalities 6, 6, 12 and 24.
Five of the small orbits are distinguished by double-brackets [[ ]] instead of single curly
brackets { }. The 50 = 8 + 6 + 6 + 6 + 24 elements in these five Z/2Z ⋊ S4 -orbits are the nonrealizable gaussoids. For instance, the eight triple gaussoids in the orbit [[a12|3 , a13|4 , a14|2 ]]8
are non-realizable. We discuss the issue of realizability in more detail after our list.
01
124
212
248
296
332
348
348
3192

:
:
:
:
:
:
:
:
:

412 :
424 :
448 :
548
68
748
124

:
:
:
:

1424 :
163 :
206 :
241 :

∅1
{a12 }12
{a12|3 }12
{a12 , a12|34 }6
{a12|3 , a12|4 }6
{a12 , a34 }6 {a12 , a34|12 }6 {a12|3 , a34|1 }12 {a12 , a34|1 }24
{a12 , a13|24 }24 {a12 , a13|4 }48 {a12|3 , a13|4 }24
{a12 , a13|24 , a14|3 }24 [[a12|3 , a13|4 , a14|2 ]]8
{a12 , a12|34 , a34 }12 {a12 , a12|34 , a34|1 }12 {a12 , a34|1 , a34|2 }12 {a12|3 , a12|4 , a34|1 }12
{a12 , a12|34 , a34 }12 {a12 , a12|34 , a34|1 }12 {a12 , a34|1 , a34|2 }12 {a12|3 , a12|4 , a34|1 }12
{a12 , a13|24 , a24|13 }24 {a12 , a13|4 , a24|3 }24 {a12 , a13|4 , a34|12 }24
{a12|3 , a13|4 , a24|1 }24 {a12 , a13|24 , a24|3 }48 {a12 , a13|4 , a34|2 }48
{a12 , a12|34 , a34 , a34|12 }3
{a12|3 , a12|4 , a34|1 , a34|2 }3
[[a12 , a12|34 , a34|1 , a34|2 ]]6
{a12 , a12|3 , a13 , a13|2 }24
{a12 , a13|4 , a24|3 , a34|12 }12 [[a12 , a13|24 , a24|13 , a34 ]]6
[[a12|3 , a13|4 , a24|1 , a34|2 ]]6 [[a12 , a13|24 , a24|3 , a34|1 ]]24
{a12 , a12|3 , a13 , a13|2 , a23|14 }24
{a12 , a12|3 , a13 , a13|2 , a23|4 }24
{a12 , a12|3 , a13 , a13|2 , a23 , a23|1 }8
{a12 , a12|3 , a12|34 , a13 , a13|2 , a24|13 , a24|3 }24
{a12 , a12|3 , a12|4 , a13 , a13|2 , a24 , a24|1 }24
{a12 , a12|3 , a12|34 , a12|4 , a13 , a13|2 , a13|24 , a13|4 , a14 , a14|2 , a14|23 , a14|3 }4

A\{a23|14 , a23|4 , a24 , a24|1 , a24|13 , a24|3 , a34 , a34|1 , a34|12 , a34|2 } 24

A\{a14 , a14|2 , a14|23 , a14|3 , a23 , a23|1 , a23|14 , a23|4 } 3

A\{a34 , a34|1 , a34|12 , a34|2 } 6

A 1
13

It is instructive to look at the list above through the lens of Remark 3.5. The action
of (Z/2Z)4 ⋊ S4 on the variety V (J4 ) and on the 679 gaussoids can be understood via the
39
Lagrangian Grassmannian
 LGr(4, 8) ⊂ P . Here a symmetric 4 × 4-matrix Σ corresponds to
the 4 × 8-matrix Id4 Σ , where Id4 is the 4 × 4 identity matrix. The group S4 acts on this
4 × 8-matrix by simultaneously permuting rows and columns of Σ and of Id4 . Each factor of
(Z/2Z)4 switches a column of Id4 with the corresponding column of Σ and changes the sign
of one of the columns. If one multiplies the 4 ×8-matrix on the left by the inverse of its left
4 × 4-block, then the result is a matrix Id4 Σ′ , where Σ′ is symmetric by [16, Lemma 13].
After swapping one column and switching the sign, the signatures of the symmetric
matrices Σ′ and Σ differ by one. Thus, if Σ is positive definite, then Σ′ is not positive definite.
After having performed this operation for all four columns, the resulting matrix Σ′ is negative
definite. We then replace Σ′ by its negative −Σ′ to get a positive definite matrix. Including
this last step, this group action represents gaussoid duality, which retains realizability.
Because of this change in signature, the action of (Z/2Z)4 ⋊ S4 on gaussoids does not
preserve realizability in the Gaussian sense where all pI are to remain positive. However it
does retain a weaker notion of realizability which only requires that the pI remain nonzero.
Remark 4.3. The non-realizability of the five Z/2Z ⋊ S4 -orbits that were highlighted above
can be certified by polynomials in the ideal J4 . The existence of such certificates is guaranteed
by the Real Nullstellensatz. For example, to show that the gaussoid G = {a12|3 , a13|4 , a14|2 }
has no Gaussian realization, we can use the following algebraic relation which lies in J4 :

a14 a234 p2 p4 p23 +a223 a234 p24 +p22 p3 p4 p34 − (a23 a24 a34 +p2 p3 p4 )(a24 p4 a12|3 + a24 a23 a13|4 + p3 p4 a14|2 ).

Indeed, in any realization the second summand is zero. However, the first summand is
nonzero because the three terms in the left parenthesis are strictly positive. Starting from
the proofs in [23, Corollary 4], we can derive similar certificates for the other four gaussoids.
Corollary 4.4. Conjecture 2.5 is true for n = 4.

Proof. Each of the five non-realizable gaussoids G has a realizable gaussoid in its orbit under
the group (Z/2Z)4 ⋊ S4 . Hence G admits a realization where all pI are nonzero, but some
are negative. The existence of such a non-Gaussian realization shows that G is compatible
with every polynomial in J4 . In particular, G is compatible with every quadric in J4 .
We now come to the census of gaussoids for n = 5. This is the main result in Theorem 4.1.
It is derived by direct computation using SAT solvers. Here SAT stands for the satisfiability
problem of propositional logic. This problem is NP-complete. However, there have been
considerable advances in solving SAT problems in practice. We believe that these techniques
can be useful for a wide range of problems in applied algebraic geometry.
All SAT solvers use the same input: a Boolean formula in conjunctive normal form (cnf).
A cnf formula is a conjunction of clauses, where a clause is a disjunction of variables or
negated variables. Every Boolean formula can be brought into cnf. A standard file format
is the DIMACS cnf file format. There are three natural problems for a given cnf formula:
SAT: Is the formula satisfiable?
#SAT: How many satisfying assignments are there?
14

AllSAT: Enumerate all satisfying assignments.
The three problems are listed by increasing difficulty. The third is the most relevant for us.
For example, gaussoid enumeration is an instance of AllSAT. To show this, we introduce
one Boolean variable for each element aij|K of A. The gaussoid G consists of those variables
that take the value zero. This convention is consistent with the assignment of zero to the
variables in the gaussoid, when checking compatibility with the edge trinomials. The gaussoid
axioms can be formulated as Boolean formulas. Specifically, (G1)-(G3) can be written as
A ∧ B ⇒ C ∧ D where A, B, C, D are statements of the form aij|K ∈ G, or aij|K = 0. The
implication above can be brought into cnf with two disjunctions as follows:
{A ∧ B ⇒ C ∧ D}

⇐⇒

(C ∨ ¬A ∨ ¬B) ∧ (D ∨ ¬A ∨ ¬B).

The weak transitivity axiom (G4) is of the form A ∧ B ⇒ C ∨ D. It has the simple cnf
C ∨ D ∨ ¬A ∨ ¬B.
These axioms in cnf need to be specified for all possible choices of i, j, k, L in (G1)-(G4).
Lemma 4.5. The enumeration of all gaussoids on [n] is an instance of
 the AllSAT problem,
n n−3
where the Boolean formula in conjunctive normal form (cnf ) has 7 3 2 3! clauses.
Proof. For each choice of an ordered triple (i, j, k) from [n] and a subset L of [n]\{i, j, k},
we have introduced seven clauses: two for each axiom (G1)-(G3) and one for (G4).

Proof of Theorem 4.1. For n ≤ 4 see the discussion above. The proof for n = 5 consists of the
following computation. Using Lemma 4.5, we expressed the gaussoid axioms as an AllSAT
instance with 1680 clauses. The formula was then solved using the solver bdd_minisat_all
due to Toda and Takehide [38]. The output is the list of all 60212776 gaussoids. This count
was verified independently using Thurley’s #SAT solver sharpSAT [37] on the same input.
To group the gaussoids into orbits under the actions of the three finite groups in (14) we
wrote our own code in sage [30]. The numbers of orbits we found are those in the table.
Our homepage www.gaussoids.de contains this data and the code to reproduce it.

5

Oriented Gaussoids and Positivity

Theorem 2.4 establishes a strong parallel between matroids and gaussoids. An important
feature of matroid theory is its numerous extensions, notably to oriented matroids [3],
positroids [1], and valuated matroids [7]. The analogues in our setting are oriented gaussoids,
positive gaussoids, and valuated gaussoids. This section is devoted to the first two of these.
Given any gaussoid G ⊂ A, we can assign orientations + or − to the unknowns aij|K
in A\G. These represent inequalities aij|K > 0 and aij|K < 0 that express the sign of the
partial correlation (8) among the random variables Xi and Xj given XK . Not all assignments
are compatible with the edge relations, which is a necessary condition for representability.
An oriented gaussoid is a map A → {0, ±1} with the following property for each edge
trinomial: after setting elements in P to +1 and elements in A to their images, the set of
15

resulting terms is either {0} or {−1, +1} or {−1, 0, +1}. A positive gaussoid is an assignment
A → {0, 1} satisfying the same compatibility requirement. For any oriented gaussoid, the
inverse image of 0 is a gaussoid G. This is analogous to the chirotope axiom for oriented
matroids [3, § 1.2], which expresses compatibility with the Grassmann–Plücker relations. An
oriented gaussoid with G = ∅, so that A → {±1}, is called a uniform oriented gaussoid.
Positroids are oriented matroids all of whose bases are positively oriented. They play an
important role in representation theory and algebraic combinatorics, and they have desirable
geometric properties. Ardila, Rincón, and Williams proved a longstanding conjecture of Da
Silva by showing that all positroids are realizable [1]. In Theorem 5.6 we prove the same fact
for gaussoids. Positive gaussoids are important for statistics, because they correspond to the
MTP2 distributions, which have received a lot of attention in the recent literature [11, 22].
We begin by discussing the enumeration of oriented gaussoids. We start with an ordinary
gaussoid G. The aim is to list all of its orientations. According to Theorem 2.4, when setting
P to 1 and G to 0 in the edge trinomials, each trinomial either vanishes, stays a trinomial,
or becomes a binomial. The resulting nonzero polynomials are the mutilated edge relations.
They combinatorially constrain the possible orientations. Here is a simple example:
Example 5.1. Fix n = 4 and consider the singleton gaussoid G = {a34|2 }. The edge
trinomial p12 a34|2 − p2 a34|12 − a13|2 a14|2 is mutilated to −a34|12 − a13|2 a14|2 . This binomial
forbids four of the eight possible assignments to its three unknowns. In particular, assigning
all + is forbidden. Hence G is not positively orientable. Still, G has 576 orientations.
♦
Enumerating all orientations of a gaussoid G can be formulated as an AllSAT instance.
We use one binary variable Va for each element a ∈ A\G. We set Va = 1 when a 7→ −1 and
Va = 0 when a 7→ +1. With this convention, the addition Va ⊕ Vb in the field F2 gives the
sign of the product ab. Consider a non-mutilated edge trinomial a − b − cd, where a, b, c, d
are elements in A. Compatibility means: whenever one term is positive, another term must
be negative, and vice versa. This translates into the following Boolean formula:
(¬Va ∨ Vb ∨ (Vc ⊕ Vd )) ⇔ (Va ∨ ¬Vb ∨ ¬(Vc ⊕ Vd )).

(15)

The formula (15) has a fairly short conjunctive normal form (cnf):
(Va ∨ ¬Vb ∨ Vc ∨ ¬Vd ) ∧ (Va ∨ ¬Vb ∨ ¬Vc ∨ Vd ) ∧ (¬Va ∨ Vb ∨ Vc ∨ Vd ) ∧ (¬Va ∨ Vb ∨ ¬Vc ∨ ¬Vd ).
If the trinomial is mutilated, then we omit from (15) all variables which appear no longer.
Example 5.2. Consider the cnf above for the empty gaussoid G = ∅ with n = 4. Applying
a #SAT solver yields the number 5376 for the uniform oriented gaussoids on n = 4.
♦
Here is our main result on the classification of small oriented gaussoids.
Theorem 5.3. For n = 3, 4, 5, the numbers of oriented gaussoids are as follows:
n
3
4
5

ordinary
oriented
positive
11
51
8
679
34,873
64
60,212,776 54,936,241,913
1,024
16

uniform
20
5,376
878,349,984

Proof. Our count of oriented gaussoids is the result of a #SAT computation. Each variable
in A can assume three values 0, +1, or −1. We modeled one such ternary variable with two
Boolean variables Va1 , Va2 and the surjection η : F22 → {0, +, −}, forbidding one configuration
of (Va1 , Va2 ) so that η becomes a bijection on all allowed configurations. Formula (15) can be
adapted to describe all oriented gaussoids. The results are summarized in the table.
The symmetries of oriented gaussoids differ in two ways from the symmetries of gaussoids.
On the one hand, there are fewer symmetries coming from the groups in (14). The two groups
on the right change the signs of the principal minors of Σ, so their action on gaussoids does
not lift to oriented gaussoids. Only the action by the permutation group Sn survives.
On the other hand, certain new symmetries arise, namely those given by reorientations.
We discussed this point after Remark 3.5. They are analogous to reorientations of oriented
matroids [3, § 1.2]. Reorientations act on the signs of the almost-principal minors aij|K as
follows. If φ : A → {0, ±1} is an oriented gaussoid, and L is any subset of [n], then the
reorientation of φ along L is the oriented gaussoid φL : A → {0, ±1} given by φL (aij|K ) =
(−1)|{i,j}∩L| · φ(aij|K ). The group of all reorientations has order 2n−1 since φL = φ[n]\L .
The symmetry classes of oriented gaussoids are the orbits of oriented gaussoids under the
semidirect product of Sn and the group of reorientations. That group has order 2n−1 n!.

Example 5.4. Let n = 3 and consider the S3 -orbit of gaussoids {a12 }, {a13 }, {a23 } . Each
gaussoid {aij } is the support of four oriented gaussoids that are related by reorientation.
Altogether, this results in a symmetry class of size 12 = 3 × 4. We display each of these 12
oriented gaussoids by listing the six signs for A in the order a12 , a13 , a23 , a12|3 , a13|2 , a23|1 :
0− − − −−
−0− − − −
− − 0− −−

0 − + + −+
+0− + + −
− +0 − ++

0 + − + +−
−0 + − + +
+ − 0 + −+

0 + + − ++
+0 + + −+
+ + 0 + +−

The first oriented gaussoid 0 − − − − − is realized by the symmetric 3 × 3-matrix Σ with
(p1 , p2 , p3 , a12 , a13 , a23 ) = (2, 2, 2, 0, −1, −1). Matrices for the other 11 oriented gaussoids in
this class are obtained by relabeling and setting Σ 7→ DΣD, where D = diag(±1, ±1, ±1). ♦
Corollary 5.5. For n = 3 there are 51 oriented gaussoids, in 7 symmetry classes. These
are all realizable. Among them are 20 uniform oriented gaussoids, in 3 symmetry classes.
Among these 20, there are 8 positive gaussoids.
The following table exhibits the seven classes. The first column gives a positive definite
symmetric 3 × 3-matrix Σ that realizes the first oriented gaussoid in that symmetry class.
(p1 , p2 , p3 , a12 , a13 , a23 )
(2, 2, 2, 1, 1, 1)
(3, 5, 1, 1, 1, 2)
(6, 9, 6, −1, −1, −7)
(4, 3, 3, 2, 2, 1)
(2, 2, 2, 0, −1, −1)
(3, 2, 2, 0, 0, 1)
(1, 1, 1, 0, 0, 0)

Symmetry class of oriented gaussoids
Size
++++++, +−−+−−, −−+−−+, −+−−+−
4
+++−++, +−−−−−, −−++−+, . . . , −−+−−−
12
−−−−−−, ++−++ −, −++−++, +−++−+
4
+++++0, ++++0+, +++0++, . . . , −−+−−0
12
12
0−−−−−, 0−++−+, . . .
(Example 5.4)
00+00+, 00−00−, −00−00, +00+00, 0−00−0, 0+00+0
6
000000
1

17

See Theorem 8.1 for the classification in the n = 4 case.
We now shift gears and focus on positive gaussoids. In analogy to the situation for
positroids [1], all positive gaussoids are realizable and their realization spaces are very nice.
Let Γ = ([n], E) be an undirected simple graph with vertex set [n] = {1, 2, . . . , n}. This
defines a gaussoid GΓ by taking all the conditional independence statements that hold for
the graphical model Γ. To be precise, an unknown aij|K lies in GΓ if and only if every path
from vertex i to vertex j in Γ uses at least one of the vertices in K. Thus aij ∈ GΓ when i
and j are in separate connected components of Γ, and aij|[n]\{i,j} ∈ GΓ when {i, j} 6∈ E.
n
Theorem 5.6. Fix a positive integer n. There are exactly 2( 2 ) positive gaussoids GΓ , one for
each of the graphs Γ = ([n], E). These gaussoids are all realizable. The space of covariance
matrices Σ that realize GΓ is homeomorphic to an open ball of dimension |E| + n.

Proof. We first show that GΓ supports a positive gaussoid. Our argument follows [11, Proposition 6.3]. Let A = (aij ) be the adjacency matrix of Γ, with aij = 1 if {i, j} ∈ E and aij = 0
otherwise. Take Σ = (t · Idn − A)−1 for sufficiently large t > 0. Then Σ is positive definite
and all its almost-principal minors are nonnegative. Indeed, Σ−1 is an M-matrix, i.e. it is
a positive definite matrix whose off-diagonal entries are nonpositive. By [19, Theorem 2],
all partial correlations of the associated Gaussian distribution are nonnegative. Following
[22], this is precisely what it means for a distribution to be MTP2 . Hence, all aij|K are
nonnegative for our matrix Σ. Moreover, by [11, Theorem 6.1], the distribution given by Σ
is faithful to the graph Γ, i.e. a principal minor aij|K is zero if and only if it lies in GΓ .
Using the same line of reasoning, we can show that the realization space of GΓ is homeomorphic to an open ball of dimension |E| + n. Indeed, if Σ is any covariance matrix with
gaussoid GΓ , then Σ−1 is an M-matrix with support Γ. The set of all such matrices is a
(relatively open) convex cone of dimension |E| + n. It is the face indexed by Γ of the cone of
all M-matrices. That cone is denoted by Mp in [22, § 2]. It has dimension n2 + n, and it is
open in the ambient space of symmetric matrices. Note that the cone Mp is the realization
space of the strictly positive gaussoid ++++ · · · +, for the complete graph Γ = Kn .
Matrix inversion defines a homeomorphism from the aforementioned relatively open face
of Mp onto a subset of RP∪A that is topologically a ball of dimension |E| + n. Its image in
the positive part of the variety V (Jn ) is a semialgebraic stratum of dimension |E| + n.
To complete the proof, let us now assume that G is an arbitrary positive gaussoid. A priori we do not know that G is realizable. We must prove that G equals GΓ for some graph
Γ = ([n], E). By [29, Theorem 1], it suffices to check that G is a singleton-transitive compositional graphoid. Equivalently, by [29, Corollary 7], we must verify that the edge trinomials
imply the three axioms singleton-transitivity, intersection, and upward-stability. Singletontransitivity is equivalent to the gaussoid axiom (G4). Intersection is (G2) and thus these
two axioms hold for G. Upward stability says that aij|L ∈ G implies aij|kL ∈ G. This follows
from the trinomial aij|L pkL − aik|L ajk|L − aij|kL pL in Jn . Indeed, since pkL and pL are positive
and the middle product is nonnegative, we see that aij|L = 0 implies aij|kL = 0.
Remark 5.7. The oriented gaussoids that result from positive ones by reorientation correspond to signed MTP2 distributions. We refer to [22, § 5] and the references given there.
18

6

Quadratic Relations

In this section we return to the ideal Jn of relations among principal and almost-principal
minors, and we derive a conjectural characterization of its minimal generators. We begin by
discussing the extent to which the trinomials suffice to generate. Let Tn denote the ideal in
R[P ∪ A] that is generated by all square trinomials (2) and all edge trinomials (3).
Example 6.1. The ideal T3 is generated by 18 = 6 + 12 quadratic trinomials, displayed in
Example 3.3. It is radical and its prime decomposition has five components:
T3 = J3 ∩ P∅,123 ∩ P1,23 ∩ P2,13 ∩ P3,12 .
Each associated prime PI,J is generated by 12 of the 14 unknowns in P ∪ A. The two
unknowns not in PI,J are pI and pJ . The variety V (PI,J ) is a coordinate line P1 in P13 . ♦
At present we do not know the primary decomposition of Tn for n ≥ 4. However, we
next show that Tn becomes equal to the prime ideal Jn after inverting all unknowns in P.
Proposition 6.2. The ideal Jn is an associated prime of the trinomial ideal Tn . Every other
associated prime of Tn contains at least one of the 2n unknowns pI ∈ P.
Proof. Let R = R[A ∪ P ±1 ] denote the partial Laurent polynomial ring obtained from R[A ∪
P] by adjoining p−1
I for all I ⊆ [n]. Consider the ideal Tn R in R. Modulo this ideal,
2
−1
pijK = piK pjK p−1
K − aij|K pK

−1
and aij|kL = pkL aij|L p−1
L − aik|L ajk|L pL .

These relations express each principal or almost-principal minor of size ≥ 2 as a Laurent
polynomial in the entries of the symmetric matrix
Σ. This shows that R/Tn R is isomorphic

to a partial Laurent polynomial ring in n+1
+
1
unknowns.
The same reduction argument
2
works for the ideal Jn . In symbols, we have the following isomorphism of R-algebras:


±1
±1
R/Tn R ≃ R/Jn R ≃ R p±1 , p±1
1 , p2 , . . . , pn , a12 , a13 , . . . , an−1,n .
We conclude that Tn R equals the prime ideal Jn R in R, and this proves the assertion.

In Theorem 6.4 we describe all quadrics in the ideal Jn , which we also conjecture to
generate Jn . The proof of Theorem 6.4 appears after Example 6.6.
Conjecture 6.3. The ideal Jn is generated by its quadrics, listed explicitly in Theorem 6.4.
n
# quadrics in Jn

2
1

3
4
5
6
7
8
21 226 1810 12261 74613 421716

Table 1: The number of quadratic generators of Jn .

19

Theorem 6.4. The space of all quadrics in the ideal Jn is a G-module of dimension
⌊n
⌋
 
  
 
n
2
X
X

m
n
n−2k
n−m n
n−2 n
+
.
2k · 3
+ 4
3
dim (Jn )2
= 3
2
2k
m
2
m=3
k=2

(16)

The following four classes of quadrics and their images under Sn are the highest weight
vectors for the distinct irreducible representations occurring in the G-module (Jn )2 :
X

(−1)|L| pL a12|Lc +

j=3 K⊆[m]\{1,2,j}

L⊆[m]\{1,2}

X

m
X

m
X

X

(−1)|K| a1j|K a2j|K c

j=3 K⊆[m]\{1,2,j}
m
X

(−1)|L| pL pL′ + 2 ·

(L,L′ ) partition
of [m]

p12 p − p1 p2 + a212
X
(−1)|K| a1j|K a2j|K c

X

(i)
for 3 ≤ m ≤ n, m odd

for 4 ≤ m ≤ n, m even

(ii)
(iii)

(−1)|K|a1j|K a1j|K ′ for 3 < m ≤ n, m even. (iv)

j=2 (K,K ′ ) partition
of [m]\{1,j}

To find these quadrics, we used the Lie algebra g = sl(2, R)⊕n of the group G = SL2 (R)n .
As n increases, so does the number of quadrics. However, just a small fraction is new: most
come from earlier ones via lowering operators in g. These are described in [27, Remark
L III.16].
ij
The k-th lowering operator ℓk is the following endomorphism of W = Wpr ⊕ i,j Wap
:
(
(
aij|L∪{k} if k ∈
/ L ∪ {i, j}
pL∪{k} if k ∈
/L
aij|L 7→
pL 7→
0
otherwise
0
otherwise
Similarly, the k-th raising operator rk acts on W as follows:
(
(
aij|L\{k}
pL\{k} if k ∈ L
aij|L 7→
pL 7→
0
0
otherwise

if k ∈ L
otherwise

These operators are extended to Sym2 (W ) by the Leibniz rule [13, §8.1]:
ℓk (vw) = ℓk (v) · w + v · ℓk (w)

and

rk (vw) = rk (v) · w + v · rk (w).

These endomorphisms of Sym2 (W ) restrict to the G-submodule (Jn )2 .
Remark 6.5. A polynomial of weight ω is a highest (respectively, lowest) weight vector
precisely when it lies in the kernel of all possible raising (respectively, lowering) operators.
Example 6.6. Consider the square trinomial p12 p − p1 p2 + a212 in (i). If n = 2, then
it has weight 00. For n > 2 the weight is 0022 . . . 2. The quadric (i) is a highest weight
vector since it is annihilated by the raising operators rk . It generates the 3n−2 -dimensional
G-module S002...2 inside (Jn )2 . To get an R-basis of this G-module, we apply all lowering
operators, which yields 3n−2 quadrics. For instance, if n = 4 then
lowering via ℓ3 yields

n
p3 p12 + pp123 − p13 p2 − p1 p23 + 2a12 a12|3 . Taking into account all 2 permutations of 002 . . . 2,
we find 3n−2 n2 quadrics originating from (i). This explains the first summand in (16). ♦
20

(0, 0, 2, 2)
ℓ3

ℓ4

(0, 0, 0, 2)

(0, 0, 2, 0)

ℓ3

(0, 0, −2, 2)

ℓ4

ℓ3

ℓ4

(0, 0, 0, 0)
ℓ4

ℓ3

(0, 0, −2, 0)

ℓ4

ℓ4

ℓ3

ℓ3

(0, 0, 2, −2)

(0, 0, 0, −2)

(0, 0, −2, −2)

Figure 2: A visualization of the G-module S0022 inside (J4 )2 . Arrows pointing down and left
represent lowerings via ℓ3 , while arrows pointing down and right represent lowerings via ℓ4 .
Proof of Theorem 6.4. The proposed quadrics lie in the kernel of the raising operators and
hence are highest weight vectors by Remark 6.5. The count in (16) is explained
by working

n
through the action of the lowering operators on (i)-(iv). Each ofthe 2 quadrics in (i)
n
m
contributes 3n−2 quadrics to Jn . For fixed m, each of the m
quadrics of types
(ii)
2

n
and (iii) contributes 4 · 3n−m quadrics. Similarly, for fixed m, each of the m m
highest
weight quadrics of type (iv) gives rise to 3n−m linearly independent quadrics in Jn .
We next prove that quadrics of type (iv) lie in Jn , i.e. they map to zero in R[Σ] =
R[σ11 , σ12 , . . . , σnn ]. The proofs for (ii) and (iii) are similar, but simpler. Without loss of
generality we assume that m = n (and hence n is even). Any monomial in the quadrics (iv)
maps to some monomial of det Σ. Specifically, pL pL′ and each a1j|K a1j|K ′ map to monomials
σπ := σ1,π(1) σ2,π(2) · · · σn,π(n) where π ∈ Sn . To show this for the a monomials, it is helpful to
arrange the rows of Σ as (1, K, j, K ′ ) and the columns as (j, K, 1, K ′ ). With this arrangement,


Σ1K×jK Σ1K×1K ′
Σ =
(17)
ΣjK ′×jK ΣjK ′×1K ′
Then a1j|K a1j|K ′ maps to a monomial in the expansion of det Σ1K×jK · det ΣjK ′×1K ′ .
Fix a monomial σπ and let C1 C2 · · · Cs be the cycle decomposition of π. Assume 1 ∈ C1 .
Let r be the number of cycles of length ≥ 3. Since Σ is symmetric, replacing a cycle Ci
in π by its inverse does not change σπ . The monomial σπ appears in the image of pL pL′
whenever (C1 , . . . , Cs ) refines the partition (L, L′ ), and it appears with the same sign as in
det Σ. The monomial σπ appears in the image of a1j|K a1j|K ′ only if C1 contains j, as seen
from (17). Additionally, each of C2 , C3 , . . . , Cs must be contained in either K or K ′ . Finally,
if C1 = (1, i2 , . . . , il , j, il+2 , . . . , it ), then {i2 , . . . , il } ⊆ K and {il+2 , . . . , it } ⊆ K ′ . These
three properties together characterize the monomials σπ that appear in the image of (iv).
According to our sign convention for the aij|K , the product a1j|K a1j|K ′ has a global minus
with respect to det Σ, again visible from (17) as the columns 1 and j have been exchanged.
e Since n is even, there is another even cycle in
Assume first that π has an even cycle C.
21

e Consider the following matching of terms of (iv):
π, and we can assume 1 ∈
/ C.
e * L,
(pL pL′ , pL∪Ce pL′ \Ce ) if C

e * K,
(a1j|K a1j|K ′ , a1j|K∪Ce a1j|K ′\Ce ) if C

(pL pL′ , pL\Ce pL′ ∪Ce ) otherwise,

(a1j|K a1j|K ′ , a1j|K\Ce a1j|K ′∪Ce ) otherwise.

e has odd cardinality, the matched terms differ in signs and cancel in the image.
Since C
Let now π be a product of odd cycles and denote C1 = {1, i2 , i3 , . . . , i2w }. We can again
produce cancellations by matching the following terms for any 1 < u ≤ w:

a1i2u−1 |K a1i2u−1 |K ′ , a1i2u |K∪{i2u−1 } a1i2u |K ′\{i2u−1 } .

After subtraction of the matched terms, the remaining terms are of the form a1i2 |K a1i2 |K ′ .
We now count the occurrences of σπ in the images of these. For the p-part, there are 2s−1
partitions (L, L′ ) of [n] that coarsen the cycles of π. For each of these, there are 2r copies
of σπ becauseP
there are r cycles with cardinality ≥ 3. In total, the coefficient of σπ in
s−1+r
the image of
. For the a-part, we distinguish two cases. First, if
(L,L′ ) pL pL′ is 2
s−2
C1 is a transposition, there are 2
partitions (K, K ′ ) that coarsen (C2 , . . . , Cs ). Again,
σπ appears 2r times from reorientations of cycles of length ≥ 3. Thus the total count is
2(s−2)+r = 2s+r−2. Now, if C1 is not a transposition, then there are r − 1 cycles in C2 , . . . , Cs
with cardinality ≥ 3. Then 2r−1 copies of σπ appear for each of the 2s−1 coarsenings. Again,
the total count is 2(r−1)+(s−1) = 2s+r−2 . In (iv), the coefficient 2 corrects the count, and the
sign of the monomials in the a terms has a global minus relative to the determinant of Σ.
We now show that the G-module (Jn )2 is spanned by the quadrics (i)-(iv). Let f be any
quadric in Jn . We can assume that f ∈
/ Jm for m < n and f is a highest weight vector.
A priori the weight of f is an element of {−2, −1, 0, 1, 2}n. We claim that it is in {0, 1}n .
To see this, assume first that −2 or −1 appears in the weight. In this case, raising f at the
corresponding index yields a nonzero quadric of higher weight. Moreover, an entry 2 can
only appear if the corresponding index appears in no variable of f and thus f ∈ Jn−1 .
Given the weights of aij|K and pL , the only possible weights for f (up to permutation)
are 111100 . . . 0, 1100 . . . 0, and 00 . . . 0. The following are general quadrics for these weights:
X
111100 . . . 0 :
dK · a12|K a34|K c
K⊆[n]\{1,2,3,4}

1100 . . . 0 :

X

L⊆[n]\{1,2}

00 . . . 0 :

X

cL · pL a12|Lc +

(L,L′ ) partition
of [n]

cL · p L p L′ +

n
X

X

j=3 K⊆[n]\{1,2,j}

X

X

(j)

dK · a1j|K a2j|K c
(ij)

dK · aij|K aij|K ′ .

i,j∈[n] (K,K ′ ) partition
i<j
of [n]\{i,j}

That f lies in the kernel of all raising operators imposes conditions on the coefficients c, d.
(j)
In particular, all coefficients in an inner sum (like cL or dK for a fixed j) differ by at most
a sign, in an alternating fashion. More precisely, for each i ∈ L one has cL\{i} + cL = 0
and hence, inductively, cL = (−1)|L| c∅ . This implies that c∅ = c[n] = (−1)n c∅ , and a similar
22

(ij)

statement holds for each d∅ . We conclude that, when n is odd, there can be no quadric of
weight 00 . . . 0 that lies in Jn and satisfies our hypotheses.
By the first part of the proof, the quadrics of types (i)-(iv) do arise. It is therefore enough
to prove that there are no further linearly independent quadrics in each weight. To do this,
we look at the image of f in R[Σ] and there at the coefficients of certain monomials:
Qn−1
σi,i+1 )σn,4 is among the terms in the image
• 111100 . . . 0: The monomial σ1,2 σ3,5 ( i=5
of a12 a34|5...n only and thus d∅ = 0. Hence no quadrics arise.
Qn−1
(3)
σi,i+1 )σn,4 yields c∅ = d∅ . Permuting suit• 1100 . . . 0, n odd: Similarly, σ1,3 σ2,3 ( i=4
(j)
ably we find c∅ = d∅ for each j, and hence there is at most one quadric of this weight.
Qn−1
Qn−1
• 1100 . . . 0, n even: σ1,2 ( i=3
σi,i+1 )σn,3 and σ1,3 σ3,4 σ4,2 ( i=5
σi,i+1 )σn,5 give that c∅ = 0
(3)
(4)
(i)
(j)
and d∅ = d∅ ; permuting the indices suitably we get that d∅ = d∅ for all i, j and
hence there is at most one quadric with this weight.
Q
2
• 00 . . . 0, n ≥ 4 even: When n ≥ 4, the preimage of the monomial n/2
i=1 σ2i−1,2i gives that
(12)
(34)
(n−1,n)
2c∅ = d∅ + d∅ + · · · + d∅
. From this relation and its permutations one derives
(ij)
(kl)
(ik)
(jl)
that d∅ + d∅ = d∅ + d∅ for any four distinct indices i, j, k, l. Consequently, all
(1j)
(23)
coefficients in f can be expressed in terms of d∅ (where j ranges from 2 to n) and d∅ .
Thus, the dimension of the associated vector subspace of (Jn )2 is at most n.

7

Tropical Geometry

In recent years, the theory of matroids has been linked tightly to the emerging field of tropical
geometry [2, 24]. Every matroid defines a tropical linear space, and conversely, every tropical
linear space corresponds to a valuated matroid. First introduced by Dress and Wenzel [7, 8]
as a generalization of matroids, valuated matroids are now best understood as vectors of
tropical Plücker coordinates. For a textbook introduction to this topic see [24, Chapter 4].
Tropical geometry is a combinatorial shadow of algebraic geometry over a field with valuation. The field of real Puiseux series, R{{ǫ}}, is our primary example. This field is ordered
and it contains the rational functions R(ǫ). The unknown ǫ is positive but smaller than any
positive real number. Covariance matrices with entries that contain ǫ can be found in the realizations of gaussoids by Lněnička and Matúš [23, Table 1]. Indeed, statisticians frequently
consider Gaussian distributions that depend on a perturbation parameter ǫ. The development in this section represents a systematic approach to the analysis of such distributions.
A valuated gaussoid on [n] is a map ν : P ∪ A → R such that the minimum of
ν(m1 ), ν(m2 ), ν(m3 ) is attained at least twice for every quadratic trinomial m1 + m2 + m3
in Tn . Here ν(mi ) is the sum of the values of ν on the two terms in mi . In other words, a
valuated gaussoid is a point ν in the tropical prevariety defined by the trinomials (2) and (3).
Recall that V (Jn ) = V (Tn ) in the torus by Proposition 6.2. Every point ν in the tropical
variety trop(V (Jn )) = trop(V (Tn )) is a realizable valuated gaussoid. The distinction between
valuated gaussoids and those that are realizable mirrors the distinction in [24, § 4.4] between
23

tropical linear spaces and tropicalized linear spaces. The former are parametrized by the
Dressian whereas the latter are parametrized by the tropical Grassmannian. This is the
distinction between the tropical prevariety and tropical variety defined by our trinomials.
In Section 8 we encounter non-realizable valuated gaussoids for n ≥ 5. Here we focus on
the case n = 3. The variety V (J3 ) equals the Lagrangian Grassmannian LGr(3, 6) ⊂ P13 .
That 6-dimensional variety has a 3-dimensional torus action. Modulo lineality, the tropical
variety trop(LGr(3, 6)) is a 3-dimensional fan, hence a 2-dimensional polyhedral complex.
Recall that LGr(3, 6) is a linear section of the classical Grassmannian Gr(3, 6) ⊂ P19 .
That 9-dimensional variety has a 5-dimensional torus action. Modulo its lineality space, the
tropical Grassmannian trop(Gr(3, 6)) is a 4-dimensional fan, hence a 3-dimensional polyhedral complex. It is glued from 990 tetrahedra and 15 bipyramids [24, Example 4.3.15]. This
complex is well-known to tropical geometers. A detailed description is found in [24, § 5.4].
The following is our main result in this section. In the course of proving it, we also
describe the inclusion of trop(LGr(3, 6)) inside trop(Gr(3, 6)), and we compute Khovanskii
bases and Newton–Okounkov bodies as in [20]. In Corollary 7.3 we connect to statistics by
explaining the MTP2 distributions encoded in the positive tropical variety trop+ (LGr(3, 6)).
Theorem 7.1. For n = 3, all valuated gaussoid are realizable, so they are precisely the points
in the tropical Lagrangian Grassmannian trop(LGr(3, 6)). The underlying 2-dimensional
polyhedral complex has 35 vertices, 151 edges, and 153 facets. The facets come in nine
symmetry classes: there are 12 + 8 + 48 + 24 + 6 + 24 + 24 + 1 triangles and 6 quadrilaterals.
Seven of the nine facet classes represent prime cones in the sense of Kaveh–Manon [20, § 5].
Proof and Explanation. These results are obtained by computation. The tropical variety of
J3 is a pure 7-dimensional fan in R14 whose lineality space L has dimension 4. One dimension
comes from the usual grading, since J3 is a homogeneous ideal. The others come from the
maximal torus of G = SL2 (R)3 . Hence trop(V (J3 )) = trop(LGr(3, 6)) is a pure 3-dimensional
fan in R14 /L. The coordinates on R14 are dual to a distinguished spanning set of R14 /L:

a12 , a12|3 , a13 , a13|2 , a23 , a23|1 , p, p1 , p12 , p123 , p13 , p2 , p23 , p3 .
(18)
With this ordering of the

1
0
L = rowspace 
0
−1

14 generators, the lineality space of trop(J3 ) equals
1 1 1 1 1 1
1
1
0 0 0 −1 1 −1 1
1
0 −1 1 0 0 −1 −1 1
1 0 0 0 0 −1 −1 −1


1 1
1
1
1
1 1 −1 −1 −1
.
1 −1 1
1 −1
1 1 −1 1
1

(19)

We use the symbols in (18) to denote the corresponding spanning vectors of R14 /L ≃ R10 .
The 35 = 6 + 8 + 3 + 12 + 6 rays of the fan trop(V (J3 )) come in five symmetry classes:
• 6 of type a: {a12 , a13 , a23 , a12|3 , a13|2 , a23|1 }
• 8 of type p: {p, p1 , p2 , p3 , p12 , p13 , p23 , p123 }

• 3 of type A: {a12 + a12|3 + a13 + a13|2 , a12 + a12|3 + a23 + a23|1 , a13 + a13|2 + a23 + a23|1 }

24

• 12 of type B: { a12 +a12|3 +a13 +a13|2 +2p+2p1 , a12 +a12|3 +a23 +a23|1 +2p+2p2 , a13 +a13|2
+a23 +a23|1 +2p+2p3 , a12 +a12|3 +a23 +a23|1 +2p1 +2p12 , a13 +a13|2 +a23 +a23|1 +2p1 +2p13 ,
a12 +a12|3 +a13 +a13|2 +2p2 +2p12 , a13 +a13|2 +a23 +a23|1 +2p2 +2p23 , a12 +a12|3 +a13 +a13|2
+2p3 +2p13 , a12 +a12|3 +a23 +a23|1 +2p3 +2p23 , a13 +a13|2 +a23 +a23|1 +2p12 +2p123 ,
a12 +a12|3 +a23 +a23|1 +2p13 +2p123 , a12 +a12|3 +a13 +a13|2 +2p23 +2p123 }

• 6 of type C: {a12 +a13|2 +2p2 +2p12 , a23 +a12|3 +2p3 +2p23 , a23 +a13|2 +2p2 +2p23 ,
a13|2 +a23|1 +2p12 +2p123 , a12|3 +a13|2 +2p23 +2p123 , a12|3 +a23|1 +2p13 +2p123 }

Each of the sums in the lists above is a vector in R14 /L. For instance, the last sum in type
C represents the vector (0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 2, 0, 0, 0) + L if we use the ordering in (18).
The tropical Lagrangian Grassmannian trop(V (J3 )) is the intersection of the tropical
Grassmannian trop(Gr(3, 6)) with a linear space. This intersection is computed in the 20
Plücker coordinates with the Macaulay2 code in Example 3.3. We shall use the identification
of the 20 Plücker coordinates with the 14 principal and almost-principal minors given in (11).
The tropical variety trop(V (J3 )) has a unique coarsest fan structure with 153 facets.
These come in 9 orbits under the symmetries of the 3-cube. In what follows we list these
orbits. Each facet in eight of the orbits lies in a unique facet of trop(Gr(3, 6)). We name
that facet in the notation of [24, § 5.4]. Facets of type ppp lie in triangles of trop(Gr(3, 6)).
Here is now the list of all 153 = 12 + 8 + 48 + 24 + 6 + 24 + 24 + 1 + 6 facets of trop(V (J3 )):
• 12 triangles of type app, like { a12 , p3 , p123 }. They lie in tetrahedra EEEE.

• 8 triangles of type ppp, like { p1 , p2 , p3 }. They lie in triangles EEE.

• 48 triangles of type apB, like { a12|3 , p, a12 +a12|3 +a13 +a13|2 +2p+2p1 }.
They lie in tetrahedra EEEG of the tropical Grassmannian trop(Gr(3, 6)).
• 24 triangles of type ppC, like { p, p12 , a13|2 +a23|1 +2p12 +2p123 }.
Twelve lie in tetrahedra EEFFa, and others lie in tetrahedra EEFFb.
• 6 triangles of type aAA, like { a12 , a12 +a12|3 +a13 +a13|2 , a12 +a12t3 +a23 +a23|1 }.
They lie in tetrahedra EEFFb.
• 24 triangles of type aAB, like {a12 , a12 +a12|3 +a13 +a13|2 ,
a12 +a12|3 +a13 +a13|2 +2(p23 +p123 )}. They lie in tetrahedra EEFG.
• 24 triangles of type pBC: { p , a12 +a12|3 +a13 +a13|2 +2(p + p1 ),
a12|3 + a13|2 + 2(p23 + p123 )}. They lie in tetrahedra EEFG.
• 1 triangle of type AAA: {a12 +a12|3 +a13 +a13|2 , a12 +a12|3 +a23 +a23|1 ,
a13 +a13|2 +a23 +a23|1 }. This triangle lies in a bipyramid FFFGG.

• 6 squares of type ABCB, like {a13 +a13|2 +a23 +a23|1 + 2(p1 +p13 ), a13 +a13|2 +a23 +a23|1 ,
a13 +a13|2 +a23 +a23|1 +2(p2 +p23 ), a13|2 +a23 +2(p2 +p23 )}, lying in bipyramids FFFGG.

We conclude that all 7 combinatorial types of valuated matroids in trop(Gr(3, 6)) are realized
by valuated gaussoids. This is similar to the result of Brodsky, Ceballos, and Labbé in [6].
Each of our 153 facets supports a monomial-free initial ideal inν (J3 ). Here ν ∈ R14 is a
vector in the relative interior of that 7-dimensional cone, and the initial ideal is understood in
the sense of [24, § 2.4]. For the facets of type ppp and ABCB, the initial ideal inν (J3 ) is not
a prime ideal. For the other seven types, the initial ideal inν (J) is toric and hence prime. In
those cases the 14 coordinates form a Khovanskii basis of our algebra, by the results of [20].
25

The list of types above thus classifies the toric degenerations of the Lagrangian Grassmannian
V (J3 ) in P13 , and from inν (J3 ) we can identify the corresponding Newton-Okounkov bodies.
We illustrate this for type app in the example that follows.
p12

a23|1

a13|2

p1
p13

a12|3

a13

p23

p2

a23

p
Figure 3: Schlegel diagram of a 3-polytope. Its join with the triangle {a12 , p3 , p123 } is a
6-polytope. This is the Newton-Okounkov body for a toric degeneration of LGr(3, 6) in P13 .
Example 7.2. Consider the app triangle {a12 , p3 , p123 }. The corresponding 7-dimensional
cone in trop(V (J3 )) ⊂ R14 consists of all vectors ν = µ + (a, 0, 0, 0, 0, 0, 0, 0, 0, b, 0, 0, 0, c),
where a, b, c > 0 and µ is in the subspace L in (19). Each of these ν is a valuated gaussoid.
The initial ideal inν (J3 ) is obtained by setting a12 , p3 and p123 to zero in all 21 quadrics
in Example 3.3. The resulting ideal is generated by binomials and is prime. Hence, inν (J3 )
is a toric ideal. In the language of [20], the cone indexed by {a12 , p3 , p123 } is a prime cone.
The vector ν defines a degeneration of the Lagrangian Grassmannian LGr(3, 6) = V (J3 )
to the toric variety V (inν (J3 )). Both are 6-dimensional and have degree 16. The corresponding lattice polytope is the Newton–Okounkov body. It has dimension 6 and volume 16. It
is the join of the triangle {a12 , p3 , p123 } with the 3-dimensional polytope shown in Figure 3.
This polytope has 6 vertices, 11 edges and 7 facets. Five additional points lie on edges. The
toric ideal for this configuration of 11 = 6 + 5 lattice points in 3-space is equal to inν (J3 ). ♦
The positive part of the tropical Grassmannian plays an important role in the theory
of cluster algebras [6, 32]. Note that trop+ (Gr(3, 6)) was worked out in [32, § 6]: it is the
boundary of a 4-polytope known as the D4 -associahedron. In what follows we determine the
analogue for the Lagrangian Grassmannian, that is, the space of positive valuated gaussoids
trop+ (LGr(3, 6)) = trop+ (Gr(3, 6)) ∩ trop(LGr(3, 6)).
26

(20)

A

B
a

a
p

B

B
a

A

A

Figure 4: The 3-polytope that represents all positive valuated matroids for n = 3. Its boundary, a simplicial 2-sphere, is the positive tropical Lagrangian Grassmannian trop+ (LGr(3, 6)).
Corollary 7.3. The intersection (20) corresponds to a triangulated 2-sphere with 10 vertices,
24 edges and 16 facets. It is the boundary of the simplicial 3-polytope shown in Figure 4.
Proof and Explanation. We examined all 153 maximal cones in Theorem 7.1. A cone lies in
(20) if and only if its initial ideal inν (J3 ) is generated by pure difference binomials m1 − m2 .
This happens for the following 16 cones. For each of them, we list a representative vector ν:
apB/EEEG

22250084000000
25220084000000


22002580000400


25002280000400


00222580000004
00252280000004


aAB/EEFG

aAA/EEFFb


00666940000004
00696640000004


66006940000400


66690044000000


69006640000400
69660044000000




44226900000000
44692200000000
69442200000000

AAA/FFFGG



77556600000000

For instance, the vector ν = (22250084000000), indexed as in (18), is a positive valuated
gaussoid. It lies in a cone of type apB, and hence in a cone of type EEEG in trop+ (Gr(3, 6)).
Each positive valuated gaussoid ν records the ǫ-orders of the principal and almost-principal
minors of a covariance matrix that defines a Gaussian MTP2 distribution over R{{ǫ}}.
For example, ν = (77556600000000) is realized in this sense by the covariance matrix


1 −ǫ7 −ǫ5
Σ = the inverse of −ǫ7 1 −ǫ6  .
−ǫ5 −ǫ6 1
Figure 4 is a combinatorial classification of all Gaussian MTP2 distributions over R{{ǫ}}.
27

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

+ + + + + + + + + + + + + + + + + + + + + + ++
+ + + + + + + + + + + + − − − − − − − − − − −−
+ + + + + + + + + + + + + − + − − − + − − − −−
+ + + + + + + + + + + + + + + + + + + + + + +−
+ + + + + + + + + + − + + − + + − − − − + + ++
+ + + + + + + + + + − − + − + − − − − + + + ++
+ + + + + + + + + + + + + + + − + − + − + − +−
+ + + + + + + + + + + + + + + + + − + + + − −−
+ + + + + + + + + + + + + + + − + − + − − − −−
+ + + + + + + + + + + + + + + + + − + + + − +−
+ + + + + + + + + + − + + − + + + − − − + + ++
+ + + + + + + + + + + + + + + − − − + − − − −−
+ + + + + + + + + + − − + − − − + + + + + + ++
+ + + + + + + + + + − − + − + − − − − − + + ++
+ + + + + + + + + + + − + − − − + + + + + − ++
+ + + + + + + + + + − − + + − − + + + + + + ++
+ + + + + + + + + + + + + − + − + − + − + − −−
+ + + + + + + + + + + + + − + − + − + − + − +−
+ + + + + + + + + + + + + + + − − − − − − − −−
+ + + + + + + + + + − + + − + − + − − − + + ++
+ + + + + + + + + + + + + + + + + − + − − − −−
+ + + + + + + + + + + − + − − − + + + + + + ++
+ + + + + + + + + + + + + + + + + − + + − − −−
+ + + + + + + + + + − + + − + − + − − − + + +−
+ + + + + + + + + + + − + − + − + + + + + − ++
+ + + + + + + + + + + + + + + + + − + − + − +−
+ + + + + + + + + + − − + − + − + + − + + + ++
+ + + + + + + + + + + − + + + − + + + + + + ++
+ + + + + + + + + + + + + + + + + + + + + − −−
+ + + + + + + + + + − + − − + − − − − − + + +−
+ + + + + + + + + + + + + + + + + + + + − − −−
+ + + + + + + + + + + + + + − − − − − − − − −−
+ + + + + + + + + + − − + − + − + − − − + + ++
+ + + + + + + + + − − − + − − − + + + + + + ++
+ + + + + + + + + + + + + − + − + − + − − − −−
+ + + + + + + + + + + + + + − − + − + − + − +−
+ + + + + + + + + + + + + − − − − − − − − − −−
+ + + + + + + + + + + + + + + + + − + − + − −−
+ + + + + + + − + + − + + − + + + − − − + + ++
+ + + + + + + + + + − − + − − − + − + + + + ++
+ + + + + + + + + + + − + + − − + + + + + + ++
+ + + + + + + + + + + + + + + + + + + + + + −−
+ + + + + + + + + + − − + − + − + − − + + + ++
+ + + + + + + + + + + + + + + − + − + − + − −−
+ + + + + + + + + + − + + − + − − − − − + + ++
+ + + + + + + + + + − + + − + − − − − − + + +−

(1/8, 1/16, 1/4, 1/4, 1/16, 1/8)
(1/8, 1/16, 1/4, −1/2, −1/4, −1/16)
(1/4, 1/2, 1/16, 1/32, −1/128, −1/2)
1/100 · (44, 50, 51, 50, 51, 30)
(1/4, 1/8, 1/512, 1/128, −1/4, 1/8)
(1/4, 1/2, 1/128, 1/64, −1/32, 1/4)
1/100 · (57, 57, 76, 39, 12, 12)
1/100 · (64, 55, 60, 76, 32, 6)
(1/16, 1/32, 1/2, 1/64, 1/128, −1/2)
1/100 · (45, 57, 66, 57, 26, 19)
1/100 · (75, 69, 45, 45, 7, 75)
(1/16, 1/8, 1/2, 1/32, −1/512, −1/2)
(1/16, 1/2, 1/8, 1/512, 1/64, 1/2)
(1/8, 1/2, 1/16, 1/64, −1/64, 1/4)
1/100 · (53, 76, 46, 8, 71, 27)
(1/64, 1/8, 1/128, 1/128, 1/8, 1/8)
(1/2, 1/8, 1/8, 1/64, 1/32, 1/4096)
(1/16, 1/2, 1/2, 1/64, 1/128, 1/8)
(1/2, 1/256, 1/64, 1/256, −1/128, −1/4)
1/100 · (85, 67, 37, 39, 6, 64)
(1/4, 1/16, 1/2, 1/16, 1/32, −1/16)
1/100 · (59, 59, 48, 13, 59, 59)
(1/2, 1/2, 1/8, 1/2, 1/256, −1/8)
1/100 · (81, 84, 39, 43, 2, 49)
1/100 · (60, 85, 39, 21, 55, 27)
(1/8, 1/16, 1/8, 1/16, 1/128, 1/512)
(1/4, 1/2, 1/1024, 1/128, 1/1024, 1/4)
1/100 · (58, 58, 41, 41, 58, 58)
(1/16, 1/8, 1/8, 1/4, 1/4, 1/256)
(1/16, 1/8, 1/16384, −1/8192, −1/4, 1/512)
(1/16, 1/4, 1/8, 1/8, 1/8, −1/32)
(1/8, 1/32, 1/2, 1/32, −1/8, −1/2)
1/100 · (63, 70, 32, 33, 4, 63)
(1/4, 1/32, 1/256, 1/256, 1/2, 1/2)
(1/2, 1/4, 1/4, 1/16, 1/32, −1/4)
bi-quadratic final polynomial
(1/2, 1/2, 1/32, 1/128, −1/2, −1/16)
(1/4, 1/4, 1/16, 1/2, 1/256, 1/1024)
1/100 · (83, 46, 33, 33, 5, 83)
(1/4, 1/2, 1/32, 1/32768, 1/2048, 1/4)
1/100 · (46, 46, 43, 30, 74, 74)
(1/8, 1/256, 1/8, 1/64, 1/2, 1/256)
(1/4, 1/32, 1/512, 1/512, 1/4096, 1/2)
1/100 · (73, 59, 71, 49, 25, 6)
(1/4, 1/2, 1/64, 1/128, −1/4, 1/8)
(1/2, 1/2, 1/1024, 1/256, −1/2, 1/8)

Table 2: The 46 symmetry classes of uniform oriented gaussoids for n = 4.

8

Realizability

In this section we study the realizability problem for gaussoids and oriented gaussoids. There
is a substantial literature on the realizability of matroids and oriented matroids. We point
to [12] and the references therein. It is our aim to extend this to the setting developed in
this paper. Our first result concerns the realizability of uniform oriented gaussoids for n = 4.
Theorem 8.1. There are 46 symmetry classes of uniform oriented gaussoids for n = 4,
listed in Table 2. All but one of them are realizable. The unique non-realizable class admits
a bi-quadratic final polynomial in the sense of Bokowski and Richter [4].
Proof and Explanation. The 46 classes were derived from the list of 5376 uniform oriented
gaussoids in Theorem 5.3. The lists of 24 signs in Table 2 is with respect to the ordering
a12 , a12|3 , a12|4 , a12|34 , a13 , a13|2 , a13|4 , a13|24 , a14 , a14|2 , a14|3 , a14|23 ,
a23 , a23|1 , a23|4 , a23|14 , a24 , a24|1 , a24|3 , a24|13 , a34 , a34|1 , a34|2 , a34|12 .
In each realizable case, we list the entries (σ12 , σ13 , σ14 , σ23 , σ24 , σ34 ) of a positive definite
symmetric 4 × 4-matrix Σ with σ11 = σ22 = σ33 = σ44 = 1 for that oriented gaussoid. The
28

realization space of an oriented gaussoid is a semi-algebraic set. We used random search
with values 2−k for small k and the optimization software SCIP [25] to find realizations.
The oriented gaussoid #36 is of special interest since it has a bi-quadratic final polynomial.
We review this concept from [4]. The edge trinomials can be written as x1 x2 +x3 x4 −x5 x6 = 0,
where each xi is a positive unknown, equal to either some pI or some aij|K multiplied by
its sign. The equation hence implies the inequalities x1 x2 < x5 x6 and x3 x4 < x5 x6 . After
replacing each xi by its logarithm, yi = log(xi ), we get y1 + y2 < y5 + y6 and y3 + y4 < y5 + y6 .
Using Linear Programming (LP), we can easily decide whether the resulting system of linear
inequalities has a solution. If not, then the oriented gaussoid is non-realizable. A solution
to the dual LP yields a non-realizability certificate known as bi-quadratic final polynomial.
Here is how it works for type #36. Among the edge trinomials we find the following:
(−a23|4 )(p134 ) + (a13|4 )(a12|34 ) − (−a23|14 )(p34 ) , (a12|3 )(p134 ) + (a14|3 )(−a24|13 ) − (a12|34 )(p13 )
(a23|1 )(p134 ) + (−a23|14 )(p13 ) − (−a34|1 )(−a24|13 ) , (a34 )(p134 ) + (−a34|1 )(p34 ) − (a13|4 )(a14|3 ).
These are elements of J4 , written in such a way that each parenthesis is positive for #36.
From these four equations we infer the following inequalities among positive quantities:
a13|4 a12|34 <
(−a23|14 )p34
(−a23|14 )p13 < (−a34|1 )(−a24|13 )

a14|3 (−a24|13 ) < a12|34 p13
(−a34|1 )p34 < a13|4 a14|3

The product of the left hand sides equals the product of the right hand sides.
We now briefly discuss the case n = 5. A complex realization of a gaussoid G on [n] is a
symmetric n × n-matrix Σ with entries in C whose principal minors are nonzero and whose
vanishing almost-principal minors are indexed by G. The following example can be viewed
as a gaussoid analog to the Vámos matroid, which is the smallest non-realizable matroid.
Example 8.2. Let n = 5. The following collection of ten 2-faces of the 5-cube is a gaussoid:

G = a12 , a13|4 , a14|5 , a15|23 , a23|5 , a24|135 , a25|34 , a34|12 , a35|1 , a45|2 .

To see that G is not realizable over C, consider the ideal in Q[σ12 , σ13 , . . . , σ45 ] generated by
these 10 almost-principal minors, for a symmetric 5×5-matrix with ones on the diagonal and
2
unknowns σij off the diagonal. Saturation with respect to p24 = 1 − σ24
yields the maximal
ideal hσ12 , σ13 , . . . , σ45 i. So, there is no complex matrix with G = 0 and σ13 p24 6= 0.
♦
With Example 8.2 it is now easy to define a non-realizable valuated gaussoid.
Example 8.3. Fix G as in Example 8.2. Let ν be the map from A ∪ P to R that takes
G to 1 and (A\G) ∪ P to 0. By examining all the edge and square trinomials in (J5 )2 , we
can verify that ν is a valuated gaussoid. However, it is not realizable. There is no point in
V (J5 ) over the Puiseux series field C{{ǫ}} whose coordinates have valuation ν. Such a point
would come from a symmetric matrix Σ whose entries are in C{{ǫ}} and have valuations ≥ 0.
Setting ǫ = 0 in that matrix gives a complex realization of G. But this does not exist.
♦
We close the paper with some directions for future research on the realizability of gaussoids. We begin by conjecturing that the non-realizable valuated gaussoid above is minimal.
29

Conjecture 8.4. All tropical gaussoids for n = 4 are realizable, i.e. they lie in trop(V (J4 )).
Realization problems can be formulated as feasibility problems of (semi-)algebraic sets.
The following refers to Theorem 4.1. It is a challenge as far as computation goes, but it is
also an excellent opportunity for gaining statistical insights on Gaussian random variables.
Challenge 8.5. Classify the 16981 (Z/2Z)n ⋊ Sn -orbits of gaussoids for n = 5 according to
their realizability over C. Classify all 254826 Z/2Z ⋊ Sn -orbits according to realizability.
The Universality Theorem due to Mnëv [3, §8.6] states, roughly speaking, that any variety
arises as the realization space of a matroid, and any semialgebraic set arises as the realization
space of an oriented matroid. We wonder whether the same is true for gaussoids.
Problem 8.6. Does universality hold for gaussoids? Can arbitrary varieties and arbitrary
semialgebraic sets be the realization spaces of gaussoids and oriented gaussoids respectively?

Acknowledgements. We thank Moritz Firsching, Paul Görlach, Jon Hauenstein, Yue Ren, Caroline Uhler and Charles Wang for help with this project. Bernd Sturmfels was partially supported
by the Einstein Foundation Berlin and the US National Science Foundation (DMS-1419018, DMS1440140). Tobias Boege and Thomas Kahle were partially supported by the Deutsche Forschungsgemeinschaft (314838170, GRK 2297, “MathCoRe”).

References
[1] F. Ardila, F. Rincón and L. Williams: Positively oriented matroids are realizable,
J. Eur. Math. Soc. (JEMS) 19 (2017) 815–833.
[2] M. Baker and N. Bowler: Matroids over partial hyperstructures, arXiv:1709.09707.
[3] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler: Oriented Matroids,
Cambridge University Press, 1993.
[4] J. Bokowski and J. Richter: On the finding of final polynomials, European J. Combinatorics 11 (1990) 21–34.
[5] A. Borovik, I.M. Gelfand and N. White: Coxeter Matroids, Progress in Mathematics
216, Birkhäuser, Boston, MA, 2003.
[6] S. Brodsky, C. Ceballos and J-P. Labbé: Cluster algebras of type D4, tropical planes,
and the positive tropical Grassmannian, Beitr. Algebra Geom. 58 (2017) 25–46.
[7] A. Dress and W. Wenzel: Valuated matroids: a new look at the greedy algorithm,
Appl. Math. Letters 3 (1990) 33–35.
[8] A. Dress and W. Wenzel: Grassmann–Plücker relations and matroids with coefficients,
Adv. Math. 86 (1991) 68–110.
[9] M. Drton, B. Sturmfels and S. Sullivant: Lectures on Algebraic Statistics, Oberwolfach
Seminars, 39, Birkhäuser Verlag, Basel, 2009.
30

[10] M. Drton and H. Xiao: Smoothness of Gaussian conditional independence models, Algebraic methods in statistics and probability II, 155–177, Contemporary Mathematics,
516, Amer. Math. Soc., Providence, RI, 2010.
[11] S. Fallat, S. Lauritzen, K. Sadeghi, C. Uhler, N. Wermuth and P. Zwiernik: Total
positivity in Markov structures, Annals of Statistics 45 (2017) 1152–1184.
[12] K. Fukuda, H. Miyata and S. Moriyama: Complete enumeration of small realizable
oriented matroids, Discrete Comput. Geom. 49 (2013) 359–381.
[13] W. Fulton and J. Harris: Representation Theory, Graduate Texts in Mathematics 129,
Springer, New York, 1991.
[14] D. Grayson and M. Stillman: Macaulay2, a software system for research in algebraic
geometry, available at www.math.uiuc.edu/Macaulay2/.
[15] H. Hiller: Combinatorics and intersection of Schubert varieties, Comment. Math.
Helv. 57 (1982) 41–59.
[16] O. Holtz and B. Sturmfels: Hyperdeterminantal relations among symmetric principal
minors, Journal of Algebra 316 (2007) 634–648.
[17] A. Iliev and K. Ranestad: Geometry of the Lagrangian Grassmannian LG(3, 6) with
applications to Brill–Noether loci, Michigan Math. J. 53(2) (2005) 383–417.
[18] H. Joe: Generating random correlation matrices based on partial correlations, J. Multivariate Analysis 97 (2006) 2177–2189.
[19] S. Karlin and Y. Rinott: M-matrices as covariance matrices of multinormal distributions, Linear Algebra Appl. 52 (1983) 419–438.
[20] K. Kaveh and C. Manon: Khovanskii bases, higher rank valuations and tropical geometry, arXiv:1610.00298.
[21] R. Kenyon and R. Pemantle: Principal minors and rhombus tilings, J. Phys. A 47
(2014) 474010, 17 pp.
[22] S. Lauritzen, C. Uhler and P. Zwiernik: Maximum likelihood estimation in Gaussian
models under total positivity, arXiv:1702.04031.
[23] R. Lněnička and F. Matúš: On Gaussian conditional independence structures, Kybernetika 43 (2007) 327–342.
[24] D. Maclagan and B. Sturmfels: Introduction to Tropical Geometry, Graduate Studies
in Mathematics 161, American Mathematical Society, Providence, RI, 2015.
[25] S. J. Maher et al.: The SCIP Optimization Suite 4.0, Zuse Institute, Berlin.
[26] F. Mohammadi, C. Uhler, C. Wang and J. Yu: Generalized permutohedra from probabilistic graphical models, arXiv:1606.01814.
[27] L. Oeding: G-Varieties and the Principal Minors of Symmetric Matrices, PhD Dissertation, Texas A&M University, ProQuest LLC, Ann Arbor, MI, 2009.
[28] L. Oeding: Set-theoretic defining equations of the variety of principal minors of symmetric matrices, Algebra and Number Theory 5 (2011) 75–109.
[29] K. Sadeghi: Faithfulness of probability distributions and graphs, arXiv:1701.08366.
[30] SageMath, the Sage Mathematics Software System (Version 8.0), The Sage Developers,
2017, http://www.sagemath.org.
31

[31] P. Šimeček: Gaussian representation of independence models over four random variables
In: Proc. COMPSTAT 2006, World Conference on Computational Statistics 17 (A. Rizzi
and M. Vichi, eds.), Rome 2006, pp. 1405–1412.
[32] D. Speyer and L. Williams: The tropical totally positive Grassmannian, J. Algebraic
Combinatorics 22 (2005) 189–210.
[33] M. Studeny: Probabilistic Conditional Independence Structures, Information Science
and Statistics, Springer, London, 2005.
[34] B. Sturmfels: Open problems in algebraic statistics, Emerging Applications of Algebraic
Geometry, edited by M. Putinar and S. Sullivant, Springer, New York (2009), 351–363.
[35] B. Sturmfels, E. Tsukerman and L. Williams: Symmetric matrices, Catalan paths, and
correlations, J. Combinatorial Theory, Ser. A 144 (2016) 496–510.
[36] S. Sullivant: Gaussian conditional independence relations have no finite complete characterization, Journal of Pure and Applied Algebra 213 (2009) 1502–1506.
[37] M. Thurley: sharpSAT - Counting models with advanced component caching and implicit
BCP, Proc. 9th Int. Conf. Theory and Applications of Satisfiability Testing (SAT 2006),
(2006) pp. 424–429.
[38] T. Toda and S. Takehide: Implementing efficient all solutions SAT solvers, J. Experimental Algorithmics 21.1 (2016) 1–12.
[39] P. Vámos: The missing axiom of matroid theory is lost forever, Journal of the London
Mathematical Society 18 (1978) 403–408.

Authors’ addresses:
Tobias Boege, OvGU Magdeburg, Germany, tboege@st.ovgu.de
Alessio D’Alı̀, Max-Planck Institute for Math in the Sciences, Leipzig, Germany, alessio.dali@mis.mpg.de
Thomas Kahle, OvGU Magdeburg, Germany, thomas.kahle@ovgu.de
Bernd Sturmfels, MPI-MiS Leipzig, bernd@mis.mpg.de and UC Berkeley, bernd@berkeley.edu

32

