ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS
SETH SULLIVANT
Abstract. Conditional independence models in the Gaussian case are algebraic varieties in the
cone of positive definite covariance matrices. We study these varieties in the case of Bayesian
networks, with a view towards generalizing the recursive factorization theorem to situations with
hidden variables. In the case when the underlying graph is a tree, we show that the vanishing
ideal of the model is generated by the conditional independence statements implied by graph.
We also show that the ideal of any Bayesian network is homogeneous with respect to a multi-
grading induced by a collection of upstream random variables. This has a number of important
consequences for hidden variable models. Finally, we relate the ideals of Bayesian networks to
a number of classical constructions in algebraic geometry including toric degenerations of the
Grassmannian, matrix Schubert varieties, and secant varieties.
1. Introduction
A Bayesian network or directed graphical model is a statistical model that uses a directed
acyclic graph (DAG) to represent the conditional independence structures between collections
of random variables. The word Bayesian is used to describe these models because the nodes
in the graph can be used to represent random variables that correspond to parameters or hy-
perparameters, though the basic models themselves are not a priori Bayesian. These models
are used throughout computational statistics to model complex interactions between collections
of random variables. For instance, tree models are used in computational biology for sequence
alignment [4] and in phylogenetics [5, 15]. Special cases of Bayesian networks include familiar
models from statistics like factor analysis [3] and the hidden Markov model [4].
The DAG that specifies the Bayesian network specifies the model in two ways. The first is
through a recursive factorization of the parametrization, via restricted conditional distributions.
The second method is via the conditional independence statements implied by the graph. The
recursive factorization theorem [13, Thm 3.27] says that these two methods for specifying a
Bayesian network yield the same family of probability density functions.
When the underlying random variables are Gaussian or discrete, conditional independence
statements can be interpreted as algebraic constraints on the parameter space of the global
model. In the Gaussian case, this means that conditional independence corresponds to algebraic
constraints on the cone of positive definite matrices. One of our main goals in this paper is to
explore the recursive factorization theorem using algebraic techniques in the case of Gaussian
random variables, with a view towards the case of hidden random variables. In this sense, the
current paper is a generalization of the work began in [3] which concerned the special case of
factor analysis. Some past work has been done on the algebraic geometry of Bayesian networks
in the discrete case in [6, 7], but there are many open questions that remain in both the Gaussian
and the discrete case.
2 SETH SULLIVANT
In the next section, we describe a combinatorial parametrization of a Bayesian network in
the Gaussian case. In statistics, this parametrization in known as the trek rule [17]. We also
describe the algebraic interpretation of conditional independence in the Gaussian case which
leads us to our main problem: comparing the vanishing ideal of the model IG to the conditional
independence ideal CG. Section 3 describes the results of computations regarding the ideals
of Bayesian networks, and some algebraic conjectures that these computations suggest. In
particular, we conjecture that the coordinate ring of a Bayesian network is always normal and
Cohen-Macaulay.
As a first application of our algebraic perspective on Gaussian Bayesian networks, we provide a
new and greatly simplified proof of the tetrad representation theorem [17, Thm 6.10] in Section
4. Then in Section 5 we provide an extensive study of trees in the fully observed case. In
particular, we prove that for any tree T , the ideal IT is a toric ideal generated by linear forms
and quadrics that correspond to conditional independence statements implied by T . Techniques
from polyhedral geometry are used to show that C[Σ]/IT is always normal and Cohen-Macaulay.
Sections 6 and 7 are concerned with the study of hidden variable models. In Section 6 we
prove the Upstream Variables Theorem (Theorem 6.4) which shows that IG is homogeneous
with respect to a two dimensional multigrading induced by upstream random variables. As
a corollary, we deduce that hidden tree models are generated by tetrad constraints. Finally
in Section 7 we show that models with hidden variables include, as special cases, a number
of classical constructions from algebraic geometry. These include toric degenerations of the
Grassmannian, matrix Schubert varieties, and secant varieties.
Acknowledgments. I would like to thank Mathias Drton, Thomas Richardson, Mike Stillman,
and Bernd Sturmfels for helpful comments and discussions about the results in this paper. The
IMA provided funding and computer equipment while I worked on parts of this project.
2. Parametrization and Conditional Independence
Let G be a directed acyclic graph (DAG) with vertex set V (G) and edge set E(G). Often,
we will assume that V (G) = [n] := {1, 2, . . . , n}. To guarantee the acyclic assumption, we
assume that the vertices are numerically ordered ; that is, i → j ∈ E(G) only if i < j. The
Bayesian network associated to this graph can be specified by either a recursive factorization
formula or by conditional independence statements. We focus first on the recursive factorization
representation, and use it to derive an algebraic description of the parametrization. Then we
introduce the conditional independence constraints that vanish on the model and the ideal that
these constraints generate.
Let X = (X1, . . . , Xn) be a random vector, and let f(x) denote the probability density
function of this random vector. Bayes’ theorem says that this joint density can be factorized as
a product
f(x) =
fi(xi|x1, . . . , xi−1),
where fi(xi|x1, . . . , xi−1) denotes the conditional density of Xi given X1 = x1, . . . , Xi−1 = xi−1.
The recursive factorization property of the graphical model is that each of the conditional
densities fi(xi|x1, . . . , xi−1) only depends on the parents pa(i) = {j ∈ [n] | j → i ∈ E(G)}. We
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 3
can rewrite this representation as
fi(xi|x1, . . . , xi−1) = fi(xi|xpa(i)).
Thus, a density function f belongs to the Bayesian network if it factorizes as
f(x) =
fi(xi|xpa(i)).
To explore the consequences of this parametrization in the Gaussian case, we first need to
recall some basic facts about Gaussian random variables. Each n-dimensional Gaussian random
variable X is completely specified by its mean vector µ and its positive definite covariance matrix
Σ. Given these data, the joint density function of X is given by
f(x) =
(2π)n/2|Σ|1/2
exp(−
(x− µ)T Σ−1(x− µ)),
where |Σ| is the determinant of Σ. Rather than writing out the density every time, the short-
hand X ∼ N (µ,Σ) is used to indicate that X is a Gaussian random variable with mean µ
and covariance matrix Σ. The multivariate Gaussian generalizes the familiar “bell curve” of
a univariate Gaussian and is an important distribution in probability theory and multivariate
statistics because of the central limit theorem [1].
Given an n-dimensional random variable X and A ⊆ [n], let XA = (Xa)a∈A. Similarly, if
x is a vector, then xA is the subvector indexed by A. For a matrix Σ, ΣA,B is the submatrix
of Σ with row index set A and column index set B. Among the nice properties of Gaussian
random variables are the fact that marginalization and conditioning both preserve the Gaussian
property; see [1].
Lemma 2.1. Suppose that X ∼ N (µ,Σ) and let A,B ⊆ [n] be disjoint. Then
(1) XA ∼ N (µA,ΣA,A) and
(2) XA|XB = xB ∼ N (µA + ΣA,BΣ−1B,B(xB − µB),ΣA,A − ΣA,BΣ
B,BΣB,A).
To build the Gaussian Bayesian network associated to the DAG G, we allow any Gaussian con-
ditional distribution for the distribution f(xi|xpa(i)). This conditional distribution is recovered
by saying that
i∈pa(j)
λijXi +Wj
where Wj ∼ N (νj , ψ2j ) and is independent of the Xi with i < j, and the λij are the regression
parameters. Linear transformations of Gaussian random variables are Gaussian, and thus X is
also a Gaussian random variable. Since X is completely specified by its mean µ and covariance
matrix Σ, we must calculate these from the conditional distribution. The recursive expression
for the distribution of Xj given the variables preceding it yields a straightforward and recursive
expression for the mean and covariance. Namely
µj = E(Xj) = E(
i∈pa(j)
λijXi +Wj) =
i∈pa(j)
λijµi + νj
4 SETH SULLIVANT
and if k < j the covariance is:
σkj = E ((Xk − µk)(Xj − µj))
(Xk − µk)
i∈pa(j)
λij(Xi − µi) +Wj − νj
i∈pa(j)
λijE ((Xk − µk)(Xi − µi)) + E ((Xk − µk)(Wj − νj))
i∈pa(j)
λijσik
and the variance satisfies:
σjj = E
(Xj − µj)2
i∈pa(j)
λij(Xi − µi) +Wj − νj
i∈pa(j)
k∈pa(j)
λijλkjσik + ψ
If there are no constraints on the vector ν, there will be no constraints on µ either. Thus, we
will focus attention on the constraints on the covariance matrix Σ. If we further assume that the
ψ2j are completely unconstrained, this will imply that we can replace the messy expression for
the covariance σjj by a simple new parameter aj . This leads us to the algebraic representation
of our model, called the trek rule [17].
For each edge i → j ∈ E(G) let λij be an indeterminate and for each vertex i ∈ V (G) let ai
be an indeterminate. Assume that the vertices are numerically ordered, that is i → j ∈ E(G)
only if i < j. A collider is a pair of edges i → k, j → k with the same head. For each pair of
vertices i, j, let T (i, j) be the collection of simple paths P in G from i to j such that there is no
collider in P . Such a colliderless path is called a trek. The name trek come from the fact that
every colliderless path from i to j consists of a path from i up to some topmost element top(P )
and then from top(P ) back down to j. We think of each trek as a sequence of edges k → l. If
i = j, T (i, i) consists of a single empty trek from i to itself.
Let φG be the ring homomorphism
φG : C[σij | 1 ≤ i ≤ j ≤ n]→ C[ai, λij | i, j ∈ [n]i→ j ∈ E(G)]
σij 7→
P∈T (i,j)
atop(P ) ·
k→l∈P
When i = j, we get σii = ai. If there is no trek in T (i, j), then φG(σij) = 0. Let IG = kerφG.
Since IG is the kernel of a ring homomorphism, it is a prime ideal.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 5
Example 2.2. Let G be the directed graph on four vertices with edges 1 → 2, 1 → 3, 2 → 4,
and 3→ 4. The ring homomorphism φG is given by
σ11 7→ a1 σ12 7→ a1λ12 σ13 7→ a1λ13 σ14 7→ a1λ12λ24 + a1λ13λ34
σ22 7→ a2 σ23 7→ a1λ12λ13 σ24 7→ a2λ24 + a1λ12λ13λ34
σ33 7→ a3 σ34 7→ a3λ34 + a1λ13λ12λ24
σ44 7→ a4
The ideal IG is the complete intersection of a quadric and a cubic:
σ11σ23 − σ13σ21, σ12σ23σ34 + σ13σ24σ23 + σ14σ22σ33 − σ13σ24σ33 − σ13σ22σ34 − σ14σ223
Dual to the ring homomorphism is the rational parametrization
φ∗G : R
E(G)+V (G) → R(
φ∗G(a, λ) = (
P∈T (i,j)
atop(P ) ·
k→l∈P
λkl)i,j .
We will often write σij(a, λ) to denote the coordinate polynomial that represents this function.
Let Ω ⊂ RE(G)+V (G) be the subset of parameter space satisfying the constraints:
j∈pa(i)
k∈pa(i)
λjiλkiσjk(a, λ)
for all i, where in the case that pa(i) = ∅ the sum is zero.
Proposition 2.3. [Trek Rule] The set of covariance matrices in the Gaussian Bayesian network
associated to G is the image φ∗G(Ω). In particular, IG is the vanishing ideal of the model.
The proof of the trek rule parametrization can also be found in [17].
Proof. The proof goes by induction. First, we make the substitution
i∈pa(j)
k∈pa(j)
λijλkjσik + ψ
which is valid because, given the λij ’s, ψ2j can be recovered from aj and vice versa. Clearly
σ11 = a1. By induction, suppose that the desired formula holds for all σij with i, j < n. We
want to show that σin has the same formula. Now from above, we have
σin =
k∈pa(n)
λknσik
k∈pa(n)
P∈T (i,k)
atop(P ) ·
r→s∈P
This last expression is a factorization of φ(σkn) since every trek from i to n is the union of a
trek P ∈ T (i, k) and an edge k → n where k is some parent of n. �
The parameters used in the trek rule parametrization are a little unusual because they involve
a mix of the natural parameters (regression coefficients λij) and coordinates on the image space
(variance parameters ai). While this mix might seem unusual from a statistical standpoint,
we find that this parametrization is rather useful for exploring the algebraic structure of the
covariance matrices that come from the model. For instance:
6 SETH SULLIVANT
Corollary 2.4. If T is a tree, then IT is a toric ideal.
Proof. For any pair of vertices i, j in T , there is at most one trek between i and j. Thus φ(σij)
is a monomial and IT is a toric ideal. �
In fact, as we will show in Section 5, when T is a tree, IT is generated by linear forms and
quadratic binomials that correspond to conditional independence statements implied by the
graph. Before getting to properties of conditional independence, we first note that these models
are identifiable. That is, it is possible to recover the λij and ai parameters directly from Σ. This
also allows us to determine the most basic invariant of IG, namely its dimension.
Proposition 2.5. The parametrization φ∗G is birational. In other words, the model parameters
λij and ai are identifiable and dim IG = #V (G) + #E(G).
Proof. It suffices to prove that the parameters are identifiable via rational functions of the entries
of Σ, as all the other statements follow from this. We have ai = σii so the ai parameters are
identifiable. We also know that for i < j
σij =
k∈pa(j)
σikλkj .
Thus, we have the matrix equation
Σpa(j),j = Σpa(j),pa(j)λpa(j),j
where λpa(j),j is the vector (λij)
i∈pa(j). Since Σpa(j),pa(j) is invertible in the positive definite
cone, we have the rational formula
λpa(j),j = Σ
pa(j),pa(j)
Σpa(j),j
and the λij parameters are identifiable. �
One of the problems we want to explore is the connection between the prime ideal defining the
graphical model (and thus the image of the parametrization) and the relationship to the ideal
determined by the independence statements induced by the model. To explain this connection,
we need to recall some information about the algebraic nature of conditional independence.
Recall the definition of conditional independence.
Definition 2.6. Let A, B, and C be disjoint subsets of [n], indexing subsets of the random
vector X. The conditional independence statement A⊥⊥B|C (“A is independent of B given C)
holds if and only if
f(xA, xB|xC) = f(xA|xC)f(xB|xC)
for all xC such that f(xC) 6= 0.
We refer to [13] for a more extensive introduction to conditional independence. In the Gauss-
ian case, a conditional independence statement is equivalent to an algebraic restriction on the
covariance matrix.
Proposition 2.7. Let A,B,C be disjoint subsets of [n]. Then X ∼ N (µ,Σ) satisfies the con-
ditional independence constraint A⊥⊥B|C if and only if the submatrix ΣA∪C,B∪C has rank less
than or equal to #C.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 7
Proof. If X ∼ N (µ, σ), then
XA∪B|XC = xC ∼ N
µA∪B + ΣA∪B,CΣ
C,C(xC − µC),ΣA∪B,A∪B − ΣA∪B,CΣ
C,CΣC,A∪B
The CI statement A⊥⊥B|C holds if and only if (ΣA∪B,A∪B − ΣA∪B,CΣ−1C,CΣC,A∪B)A,B = 0. The
A,B submatrix of ΣA∪B,A∪B − ΣA∪B,CΣ−1C,CΣC,A∪B is easily seen to be ΣA,B − ΣA,CΣ
C,CΣC,B
which is the Schur complement of the matrix
ΣA∪C,B∪C =
ΣA,B ΣA,C
ΣC,B ΣC,C
Since ΣC,C is always invertible (it is positive definite), the Schur complement is zero if and only
if the matrix ΣA∪C,B∪C has rank less than or equal to #C. �
Given a DAG G, a collection of conditional independence statements are forced on the joint
distribution by the nature of the graph. These independence statements are usually described
via the notion of d-separation (the d stands for “directed”).
Definition 2.8. Let A, B, and C be disjoint subsets of [n]. The set C d-separates A and B if
every path in G connecting a vertex i ∈ A and B ∈ j contains a vertex k that is either
(1) a non-collider that belongs to C or
(2) a collider that does not belong to C and has no descendants that belong to C.
Note that C might be empty in the definition of d-separation.
Proposition 2.9 ([13]). The conditional independence statement A⊥⊥B|C holds for the Bayesian
network associated to G if and only if C d-separates A from B in G.
A joint probability distribution that satisfies all the conditional independence statements
implied by the graph G is said to satisfy the global Markov property of G. The following theorem
is a staple of the literature of graphical models, that holds with respect to any σ-algebra.
Theorem 2.10 (Recursive Factorization Theorem). [13, Thm 3.27] A probability density has
the recursive factorization property with respect to G if and only if it satisfies the global Markov
property.
Definition 2.11. Let CG ⊆ C[Σ] be the ideal generated by the minors of Σ corresponding to
the conditional independence statements implied by G; that is,
CG = 〈(#C + 1) minors of ΣA∪C,B∪C | C d-separates A from B in G〉 .
The ideal CG is called the conditional independence ideal of G.
A direct geometric consequence of the recursive factorization theorem is the following
Corollary 2.12. For any DAG G,
V (IG) ∩ PDn = V (CG) ∩ PDn.
In the corollary PDn ⊂ R(
2 ) is the cone of n × n positive definite symmetric matrices. It
seems natural to ask whether or not IG = CG for all DAGs G. For instance, this was true for
the DAG in Example 2.2. The Verma graph provides a natural counterexample.
8 SETH SULLIVANT
2 3 4 5
Example 2.13. Let G be the DAG on five vertices with edges 1 → 3, 1 → 5, 2 → 3, 2 → 4,
3→ 4, and 4→ 5. This graph is often called the Verma graph.
The conditional independence statements implied by the model are all implied by the three
statements 1⊥⊥2, 1⊥⊥4|{2, 3}, and {2, 3}⊥⊥5|{1, 4}. Thus, the conditional independence ideal
CG is generated by one linear form and five determinantal cubics. In this case, we find that
IG = CG + 〈f〉 where f is the degree four polynomial:
f = σ23σ24σ25σ34 − σ22σ25σ234 − σ23σ
24σ35 + σ22σ24σ34σ35
−σ223σ25σ44 + σ22σ25σ33σ44 + σ
23σ24σ45 − σ22σ24σ33σ45.
We found that the primary decomposition of CG is
CG = IG ∩ 〈σ11, σ12, σ13, σ14〉
so that f is not even in the radical of CG. Thus, the zero set of CG inside the positive semidefinite
cone contains singular covariance matrices that are not limits of distributions that belong to the
model. Note that since none of the indices of the σij appearing in f contain 1, f vanishes on
the marginal distribution for the random vector (X2, X3, X4, X5). This is the Gaussian version
of what is often called the Verma constraint. Note that this computation shows that the Verma
constraint is still needed as a generator of the unmarginalized Verma model. �
The rest of this paper is concerned with studying the ideals IG and investigating the circum-
stances that guarantee that CG = IG. We report on results of a computational study in the
next section. Towards the end of the paper, we study the ideals IG,O that arise when some of
the random variables are hidden.
3. Computational Study
Whenever approaching a new family of ideals, our first instinct is to compute as many exam-
ples as possible to gain some intuition about the structure of the ideals. This section summarizes
the results of our computational explorations.
We used Macaulay2 [9] to compute the generating sets of all ideals IG for all DAGs G on n ≤ 6
vertices. Our computational results concerning the problem of when CG = IG are summarized
in the following proposition.
Proposition 3.1. All DAGs on n ≤ 4 vertices satisfy CG = IG. Of the 302 DAGs on n = 5
vertices, exactly 293 satisfy CG = IG. Of the 5984 DAGs on n = 6 vertices exactly 4993 satisfy
CG = IG.
On n = 5 vertices, there were precisely nine graphs that fail to satisfy CG = IG. These
nine exceptional graphs are listed below. The numberings of the DAGs come from the Atlas of
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 9
Graphs [14]. Note that the Verma graph from Example 2.13 appears as A218 after relabeling
vertices.
(1) A139: 1→ 4, 1→ 5, 2→ 4, 3→ 4, 4→ 5.
(2) A146: 1→ 3, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(3) A197: 1→ 2, 1→ 3, 1→ 5, 2→ 4, 3→ 4, 4→ 5.
(4) A216: 1→ 2, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(5) A217: 1→ 3, 1→ 4, 2→ 4, 2→ 5, 3→ 4, 4→ 5.
(6) A218: 1→ 3, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(7) A275: 1→ 2, 1→ 4, 1→ 5, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(8) A277: 1→ 2, 1→ 3, 1→ 5, 2→ 4, 3→ 4, 3→ 5, 4→ 5.
(9) A292: 1→ 2, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 3→ 5, 4→ 5.
The table below displays the numbers of minimal generators of different degrees for each of the
ideals IG where G is one of the nine graphs on five vertices such that CG 6= IG. The coincidences
among rows in this table arise because sometimes two different graphs yield the same family of
probability distributions. This phenomenon is known as Markov equivalence [13, 17].
Network 1 2 3 4 5
A139 3 1 2 0 0
A146 1 3 7 0 0
A197 0 1 5 0 1
A216 0 1 5 0 1
A217 2 1 2 0 0
A218 1 0 5 1 0
A275 0 1 1 1 3
A277 0 1 1 1 3
A292 0 1 1 1 3
It is worth noting the methods that we used to perform our computations, in particular,
how we computed generators for the ideals IG. Rather than using the trek rule directly, and
computing the vanishing ideal of the parametrization, we exploited the recursive nature of the
parametrization to determine IG. This is summarized by the following proposition.
Proposition 3.2. Let G be a DAG and G \ n the DAG with vertex n removed. Then
IG\n +
σin −
j∈pa(n)
λjnσij | i ∈ [n− 1]
〉⋂C[σij | i, j ∈ [n]]
where the ideal IG\n is considered as a graph on n− 1 vertices.
Proof. This is a direct consequence of the trek rule: every trek that goes to n passes through a
parent of n and cannot go below n. �
Based on our (limited) computations up to n = 6 we propose some optimistic conjectures
about the structures of the ideals IG.
10 SETH SULLIVANT
Conjecture 3.3.
IG = CG :
A⊂[n]
(|ΣA,A|)∞
Conjecture 3.3 says that all the uninteresting components of CG (that is, the components that
do not correspond to probability density functions) lie on the boundary of the positive definite
cone. Conjecture 3.3 was verified for all DAGs on n ≤ 5 vertices. Our computational evidence
also suggests that all the ideals IG are Cohen-Macaulay and normal, even for graphs with loops
and other complicated graphical structures.
Conjecture 3.4. The quotient ring C[Σ]/IG is normal and Cohen-Macaulay for all G.
Conjecture 3.4 was verified computationally for all graphs on n ≤ 5 vertices and graphs with
n = 6 vertices and less than 8 edges. We prove Conjecture 3.4 when the underlying graph is a
tree in Section 5. A more negative conjecture concerns the graphs such that IG = CG.
Conjecture 3.5. The proportion of DAGs on n vertices such that IG = CG tends to zero as
To close the section, we provide a few useful propositions for reducing the computation of the
generating set of the ideal IG to the ideals for smaller graphs.
Proposition 3.6. Suppose that G is a disjoint union of two subgraph G = G1 ∪G2. Then
IG = IG1 + IG2 + 〈σij | i ∈ V (G1), j ∈ V (G2)〉 .
Proof. In the parametrization φG, we have φG(σij) = 0 if i ∈ V (G1) and j ∈ V (G2), because
there is no trek from i to j. Furthermore, φG(σij) = φG1(σij) if i, j ∈ V (G1) and φG(σkl) =
φG2(σkl) if k, l ∈ V (G2) and these polynomials are in disjoint sets of variables. Thus, there can
be no nontrivial relations involving both σij and σkl. �
Proposition 3.7. Let G be a DAG with a vertex m with no children and a decomposition into
two induced subgraphs G = G1 ∪G2 such that V (G1) ∩ V (G2) = {m}. Then
IG = IG1 + IG2 + 〈σij | i ∈ V (G1) \ {m}, j ∈ V (G2) \ {m}〉 .
Proof. In the paremtrization φG, we have φG(σij) = 0 if i ∈ V (G1) \ {m} and j ∈ V (G2) \ {m},
because there is no trek from i to j. Furthermore φG(σij) = φG1(σij) if i, j ∈ V (G1) and
φG(σkl) = φG2(σkl) if k, l ∈ V (G2) and these polynomials are in disjoint sets of variables unless
i = j = k = l = m. However, in this final case, φG(σmm) = am and this is the only occurrence
of am in any of the expressions φG(σij). This is a consequence of the fact that vertex m has no
children. Thus, we have a partition of the σij into three sets in which φG(σij) appear in disjoint
sets of variables and there can be no nontrivial relations involving two or more of these sets of
variables. �
Proposition 3.8. Suppose that for all i ∈ [n − 1], the edge i → n ∈ E(G). Let G \ n be the
DAG obtained from G by removing the vertex n. Then
IG = IG\n · C[σij : i, j ∈ [n]].
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 11
Proof. Every vertex in G \ n is connected to n and is a parent of n. This implies that n cannot
appear in any conditional independence statement implied by G. Furthermore, if C d-separates
A from B in G\n, it will d-separate A from B in G, because n is below every vertex in G\n. This
implies that the CI statements that hold for G are precisely the same independence statements
that hold for G \ n. Thus
V (CG) ∩ PDn = V (CG\n · C[σij | i, j ∈ [n]]) ∩ PDn.
Since IG = I(V (CG) ∩ PDn), this implies the desired equality. �
4. Tetrad Representation Theorem
An important step towards understanding the ideals IG is to derive interpretations of the
polynomials in IG. We have an interpretation for a large part of IG, namely, the subideal
CG ⊆ IG. Conversely, we can ask when polynomials of a given form belong to the ideals IG.
Clearly, any linear polynomial in IG is a linear combination of polynomials of the form σij with
i 6= j, all of which must also belong to IG. Each linear polynomial σij corresponds to the
independence statement Xi⊥⊥Xj . Combinatorially, the linear from σij is in IG if and only if
there is no trek from i to j in G.
A stronger result of this form is the tetrad representation theorem, first proven in [17], which
gives a combinatorial characterization of when a tetrad difference
σijσkl − σilσjk
belongs to the ideal IG. The constraints do not necessarily correspond to conditional indepen-
dence statements, and need not belong to the ideal CG. This will be illustrated in Example
The original proof of the tetrad representation theorem in [17] is quite long and technical. Our
goal in this section is to show how our algebraic perspective can be used to greatly simplify the
proof. We also include this result here because we will need the tetrad representation theorem
in Section 5.
Definition 4.1. A vertex c ∈ V (G) is a choke point between sets I and J if every trek from a
point in I to a point in J contains c and either
(1) c is on the I-side of every trek from I to J , or
(2) c is on the J-side of every trek from I to J .
The set of all choke points in G between I and J is denoted C(I, J).
Example 4.2. In the graph c is a choke point between {1, 4} and {2, 3}, but is not a choke
point between {1, 2} and {3, 4}.
1 2 3 4
12 SETH SULLIVANT
Theorem 4.3 (Tetrad Representation Theorem [17]). The tetrad constraint σijσkl−σilσjk = 0
holds for all covariance matrices in the Bayesian network associated to G if and only if there is
a choke point in G between {i, k} and {j, l}.
Our proof of the tetrad representation theorem will follow after a few lemmas that lead to
the irreducible factorization of the polynomials σij(a, λ).
Lemma 4.4. In a fixed DAG G, every trek from I to J is incident to every choke point in
C(I, J) and they must be reached always in the same order.
Proof. If two choke points are on, say, the I side of every trek from I to J and there are two
treks which reach these choke points in different orders, there will be a directed cycle in G. If
the choke points c1 and c2 were on the I side and J side, respectively, and there were two treks
from I to J that reached them in a different order, this would contradict the property of being
a choke point. �
Lemma 4.5. Let i = c0, c1, . . . , ck = j be the ordered choke points in C({i}, {j}). Then the
irreducible factorization of σij(a, λ) is
σij(a, λ) =
f tij(a, λ)
where f tij(a, λ) only depends on λpq such that p and q are between choke points ct−1 and ct.
Proof. First of all, we will show that σij(a, λ) has a factorization as indicated. Then we will
show that the factors are irreducible. Define
f tij(a, λ) =
P∈T (i,j;ct−1,ct)
atop(P )
k→l∈P
where T (i, j; ct−1, ct) consists of all paths from ct−1 to ct that are partial treks from i to j (that
is, that can be completed to a trek from i to j) and atop(P ) = 1 if the top of the partial trek
P is not the top. When deciding whether or not the top is included in the partial trek, note
that almost all choke points are associated with either the {i} side or the {j} side. So there is
a natural way to decide if atop(P ) is included or not. In the exceptional case that c is a choke
point on both the {i} and the {j} side, we repeat this choke point in the list. This is because c
must be the top of every trek from i to j, and we will get a factor f tij(a, λ) = ac.
Since each ct is a choke point between i and j, the product of the monomials, one from each
f tij , is the monomial corresponding to a trek from i to j. Conversely, every monomial arises as
such a product in a unique way. This proves that the desired factorization holds.
Now we will show that each of the f tij(a, λ) cannot factorize further. Note that every monomial
in f tij(a, λ) is squarefree in all the a and λ indeterminates. This means that every monomial
appearing in f tij(a, λ) is a vertex of the Newton polytope of f
ij(a, λ). This, in turn, implies
that in any factorization f tij(a, λ) = fg there is no cancellation since in any factorization of any
polynomial, the vertices of the Newton polytope is the product of two vertices of the constituent
Newton polytopes. This means that in any factorization f tij(a, λ) = fg, f and g can be chosen
to be the sums of squarefree monomials all with coefficient 1.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 13
Now let f tij(a, λ) = fg be any factorization and let m be a monomial appearing in f
ij(a, λ).
If the factorization is nontrivial m = mfmg where mf and mg are monomials in f and g
respectively. Since the factorization is nontrivial and m corresponds to a partial trek P in
T (i, j; ct−1, ct), there must exist a c on P such that, without loss of generality such that λpc
appears in mf and λcq appears in mg. Since every monomial in the expansion of fg corresponds
to a partial trek from ct−1 to ct it must be the case that every monomial in f contains an
indeterminate λsc from some s and similarly, every monomial appearing in g contains a λcs for
some s. But this implies that every partial trek from ct−1 to ct passes through c, with the same
directionality, that is, it is a choke point between i and j. However, this contradicts the fact the
C({i}, {j}) = {c0, . . . , ct}. �
Proof of Thm 4.3. Suppose that the vanishing tetrad condition holds, that is,
σijσkl = σilσkj
for all covariance matrices in the model. This factorization must thus also hold when we sub-
stitute the polynomial expressions in the parametrization:
σij(a, λ)σkl(a, λ) = σil(a, λ)σkj(a, λ).
Assuming that none of these polynomials are zero (in which case the choke condition is satisfied
for trivial reasons), this means that each factor f tij(a, λ) must appear on both the left and the
right-hand sides of this expression. This is a consequence of the fact that polynomial rings
over fields are unique factorization domains. The first factor f1ij(a, λ) could only be a factor of
σil(a, λ). There exists a unique t ≥ 1 such that f1ij · · · f
ij divides σil but f
ij · · · f
ij does not
divide σil. This implies that f
ij divides σkj . However, this implies that ct is a choke point
between i and j, between i and l, between k and j. Furthermore, this will imply that ct is a
choke point between k and l as well, which implies that ct is a choke point between {i, k} and
{j, l}.
Conversely, suppose that there is a choke point c between {i, k} and {j, l}. Our unique
factorization of the σij implies that we can write
σij = f1g1, σkl = f2g2, σil = f1g2, σkj = f2g1
where f1 and f2 corresponds to partial treks from i to c and k to c, respectively, and g1 and g2
correspond to partial treks from c to j and l, respectively. Then we have
σijσkl = f1g1f2g2 = σilσkj ,
so that Σ satisfies the tetrad constraint. �
At first glance, it is tempting to suggest that the tetrad representation theorem says that
a tetrad vanishes for every covariance matrix in the model if and only if an associated condi-
tional independence statement holds. Unfortunately, this is not true, as the following example
illustrates.
Example 4.6. Let A139 be the graph with edges 1→ 4, 1→ 5, 2→ 4, 3→ 4 and 4→ 5. Then
4 is a choke point between {2, 3} and {4, 5} and the tetrad σ24σ35 − σ25σ34 belongs to IA139 .
However, it is not implied by the conditional independence statements implied by the graph
(that is, σ24σ35 − σ25σ34 /∈ CA139). It is precisely this extra tetrad constraint that forces A139
onto the list of graphs that satisfy CG 6= IG from Section 3.
14 SETH SULLIVANT
In particular, a choke point between two sets need not be a d-separator of those sets. In the
case that G is a tree, it is true that tetrad constraints are conditional independence constraints.
Proposition 4.7. Let T be a tree and suppose that c is a choke point between I and J in T .
Then either c d-separates I \ {c} and J \ {c} or ∅ d-separates I \ {c} and J \ {c}.
Proof. Since T is a tree, there is a unique path from an element in I \ c to an element in J \ c.
If this path is not a trek, we have ∅ d-separates I \ {c} from J \ {c}. On the other hand, if this
path is always a trek we see that {c} d-separates I \ {c} from J \ {c}. �
The tetrad representation theorem gives a simple combinatorial rule for determining when a
2 × 2 minor of Σ is in IG. More generally, we believe that there should exist a graph theoretic
rule that determines when a general determinant |ΣA,B| ∈ IG in terms of structural features of
the DAG G. The technique we have used above, which relies on giving a factorization of the
polynomials σ(a, λ), does not seem like it will extend to higher order minors. One approach
at a generalization of the tetrad representation theorem would be to find a cancellation free
expression for the determinant |ΣA,B| in terms of the parameters ai and λij , along the lines of
the Gessel-Viennot theorem [8]. From such a result, one could deduce a combinatorial rule for
when |ΣA,B| is zero. This suggests the following problem.
Problem 4.8. Develop a Gessel-Viennot theorem for treks; that is, determine a combinatorial
formula for the expansion of |ΣA,B| in terms of the treks in G.
5. Fully Observed Trees
In this section we study the Bayesian networks of trees in the situation where all random
variables are observed. We show that the toric ideal IT is generated by linear forms σij and
quadratic tetrad constraints. The Tetrad Representation Theorem and Proposition 4.7 then
imply that IT = CT . We also investigate further algebraic properties of the ideals IT using the
fact that IT is a toric ideal and some techniques from polyhedral geometry.
For the rest of this section, we assume that T is a tree, where by a tree we mean a DAG
whose underlying undirected graph is a tree. These graphs are sometimes called polytrees in
the graphical models literature. A directed tree is a tree all of whose edges are directed away
from a given source vertex.
Since IT is a toric ideal, it can be analyzed using techniques from polyhedral geometry. In
particular, for each i, j such that T (i, j) is nonempty, let aij denote the exponent vector of the
monomial σij = atop(P )
k→l∈P λkl. Let AT denote the set of all these exponent vectors. The
geometry of the toric variety V (IT ) is determined by the discrete geometry of the polytope
PT = conv(AT ).
The polytope PT is naturally embedded in R2n−1, where n of the coordinates on R2n−1
correspond to the vertices of T and n − 1 of the coordinates correspond to the edges of T .
Denote the first set of coordinates by xi and the second by yij where i→ j is an edge in T . Our
first results is a description of the facet structure of the polytope PT .
Theorem 5.1. The polytope PT is the solution to the following set of equations and inequalities:
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 15
xi ≥ 0 for all i ∈ V (T )
yij ≥ 0 for all i→ j ∈ E(T )∑
i∈V (T ) xi = 1
i: i→j∈E(T ) yij − yjk ≥ 0 for all j → k ∈ E(T )
2xj +
i: i→j∈E(T ) yij −
k: j→k∈E(T ) yjk ≥ 0 for all j ∈ V (T ).
Proof. Let QT denote the polyhedron defined as the solution space to the given constraints.
First of all, QT is bounded. To see this, first note that because of the positive constraints and
the equation
i∈V (T ) xi = 1, we have that xi ≤ 1 is implied by the given constraints. Then,
starting from the sources of the tree and working our way down the edges repeatedly using the
inequalities xj +
i: i→j∈E(T ) yij − yjk ≥ 0, we see that the yij are also bounded.
Now, we have PT ⊆ QT , since every trek will satisfy any of the indicated constraints. Thus,
we must show that QT ⊆ PT . To do this, it suffices to show that for any vector (x0, y0) ∈ QT ,
there exists λ > 0, (x1, y1) and (x2, y2) such that
(x0, y0) = λ(x1, y1) + (1− λ)(x2, y2)
where (x1, y1) is one of the 0/1 vectors aij and (x2, y2) ∈ QT . Because QT is bounded, this
will imply that the extreme points of QT are a subset of the extreme points of PT , and hence
QT ⊆ PT . Without loss of generality we may suppose that all of the coordinates y0ij are positive,
otherwise the problem reduces to a smaller tree or forest because the resulting inequalities that
arise when yij = 0 are precisely those that are necessary for the smaller tree. Note that for
a forest F , the polytope PF is the direct join of polytopes PT as T ranges over the connected
components of F , by Proposition 3.6.
For any fixed j, there cannot exist distinct values k1, k2, and k3 such that all of
x0j +
i: i→j∈E(T )
y0ij − y
x0j +
i: i→j∈E(T )
y0ij − y
x0j +
i: i→j∈E(T )
y0ij − y
hold. If there were, we could add these three equations together to deduce that
3x0j + 3
i: i→j∈E(T )
y0ij − y
− y0jk2 − y
This in turn implies that
2x0j +
i: i→j∈E(T )
y0ij − y
− y0jk2 − y
with equality if and only if pa(j) = ∅ and x0j = 0. This in turn implies that, for instance,
y0jk1 = 0 contradicting our assumption that y
ij > 0 for all i and j. By a similar argument, if
exactly two of these facet defining inequalities hold sharply, we see that
2x0j + 2
i: i→j∈E(T )
y0ij − y
− y0jk2 = 0
16 SETH SULLIVANT
which implies that j has exactly two descendants and no parents.
Now mark each edge j → k in the tree T such that
x0j +
i: i→j∈E(T )
y0ij − y
jk = 0.
By the preceding paragraph, we can find a trek P from a sink in the tree to a source in the tree
and (possibly) back to a different sink that has the property that for no i in the trek there exists
k not in the path such that i → k is a marked edge. That is, the preceding paragraph shows
that there can be at most 2 marked edges incident to any given vertex.
Given P , let (x1, y1) denote the corresponding 0/1 vector. We claim that there is a λ > 0
such that
(1) (x0, y0) = λ(x1, y1) + (1− λ)(x2, y2)
holds with (x2, y2) ∈ QT . Take λ > 0 to be any very small number and define (x2, y2) by the
given equation. Note that by construction the inequalities x2i ≥ 0 and y
ij ≥ 0 will be satisfied
since for all the nonzero entries in (x1, y1), the corresponding inequality for (x0, y0) must have
been nonstrict and λ is small. Furthermore, the constraint
x2i = 1 is also automatically
satisfied. It is also easy to see that the last set of inequalities will also be satisfied since through
each vertex the path will either have no edges, an incoming edge and an outgoing edge, or two
outgoing edges and the top vertex, all of which do not change the value of the linear functional.
Finally to see that the inequalities of the form
i: i→j∈E(T )
yij − yjk ≥ 0
are still satisfied by (x2, y2), note that marked edges of T are either contained in the path
P or not incident to the path P . Thus, the strict inequalities remain strict (since they will
involve modifying by an incoming edge and an outgoing edge or an outgoing edge and the top
vertex), and the nonstrict inequalities remain nonstrict since λ is small. Thus, we conclude that
QT ⊆ PT , which completes the proof. �
Corollary 5.2. Let ≺ be any reverse lexicographic term order such that σii � σjk for all i and
j 6= k. Then in≺(IT ) is squarefree. In other words, the associated pulling triangulation of PT is
unimodular.
Proof. The proof is purely polyhedral, and relies on the geometric connections between trian-
gulations and initial ideals of toric ideals. See Chapter 8 in [19] for background on this material
including pulling triangulations. Let aij denote the vertex of PT corresponding to the monomial
φG(σij). For i 6= j, each of the vertices aij has lattice distance at most one from any of the
facets described by Theorem 5.1. This is seen by evaluating each of the linear functionals at the
0/1 vector corresponding to the trek between i and j.
If we pull from one of these vertices we get a unimodular triangulation provided that the
induced pulling triangulation on each of the facets of PT not containing aij is unimodular. This
is because the normalized volume of a simplex is the volume of the base times the lattice distance
from the base to the vertex not on the base.
The facet defining inequalities of any face of PT are obtained by taking an appropriate subset
of the facet defining inequalities of PT . Thus, as we continue the pulling triangulation, if the
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 17
current face contains a vertex aij with i 6= j, we will pull from this vertex first and get a
unimodular pulling triangulation provided the induced pulling triangulation of every face is
unimodular. Thus, by induction, it suffices to show that the faces of PT that are the convex
hull of vertices aii have unimodular pulling triangulations. However, these faces are always
unimodular simplices. �
Corollary 5.3. The ring C[Σ]/IT is normal and Cohen-Macaulay when T is a tree.
Proof. Since PT has a unimodular triangulation, it is a normal polytope and hence the semigroup
ring C[Σ]/IT is normal. Hochster’s theorem [10] then implies that C[Σ]/IT is Cohen-Macaulay.
While we know that C[Σ]/IT is always Cohen-Macaulay, it remains to determine how the
Cohen-Macaulay type of IT depends on the underlying tree T . Here is a concrete conjecture
concerning the special case of Gorenstein trees.
Conjecture 5.4. Suppose that T is a directed tree. Then C[Σ]/IT is Gorenstein if and only if
the degree of every vertex in T is less than or equal to three.
A downward directed tree is a tree all of whose edges point to the unique sink in the tree. A
leaf of such a downward directed tree is then a source of the tree. With a little more refined
information about which inequalities defining PT are facet defining, we can deduce results about
the degrees of the ideals IT in some cases.
Corollary 5.5. Let T be a downward directed tree and let i be any leaf of T , s the sink of T ,
and P the unique trek in T (i, s). Then
deg IT =
k→l∈P
deg IT\k→l
where T \ k → l denotes the forest obtained from T by removing the edge k → l.
Proof. First of all, note that in the case of a downward directed tree the inequalities of the form
2xj +
i: i→j∈E(T )
yij −
k: j→k∈E(T )
yjk ≥ 0
are redundant: since each vertex has at most one descendant, it is implied by the the other
constraints. Also, for any source t, the inequality xt ≥ 0 is redundant, because it is implied by
the inequalities xt − ytj ≥ 0 and ytj ≥ 0 where j is the unique child of t.
Now we will compute the normalized volume of the polytope PT (which is equal to the degree
of the toric ideal IT ) by computing the pulling triangulation from Corollary and relating the
volumes of the pieces to the associated subforests.
Since the pulling triangulation of PT with ais pulled first is unimodular, the volume of PT is
the sum of the volumes of the facets of PT that do not contain ais. Note that ais lies on all the
facets of the form
i: i→j∈E(T )
yij − yjk ≥ 0
since through every vertex besides the source and sink, the trek has either zero or two edges
incident to it. Thus, the only facets that ais does not lie on are of the form ykl ≥ 0 such that
18 SETH SULLIVANT
k → l is an edge in the trek P . However, the facet of PT obtained by setting ykl = 0 is precisely
the polytope PT\k→l, which follows from Theorem 5.1. �
Note that upon removing an edge in a tree we obtain a forest. Proposition 3.6 implies that
the degree of such a forest is the product of the degrees of the associated trees. Since the degree
of the tree consisting of a single point is one, the formula from Corollary 5.5 yields a recursive
expression for the degree of a downward directed forest.
Corollary 5.6. Let Tn be the directed chain with n vertices. Then deg ITn =
, the n−1st
Catalan number.
Proof. In Corollary 5.5 we take the unique path from 1 to n. The resulting forests obtained
by removing an edge are the disjoint unions of two paths. By the product formula implied by
Proposition 3.6 we deduce that the degree of ITn satisfies the recurrence:
deg ITn =
deg ITi · deg ITn−i
with initial condition deg IT1 = 1. This is precisely the recurrence and initial conditions for the
Catalan numbers [18]. �
Now we want to prove the main result of this section, that the determinantal conditional
independence statements actually generate the ideal IT when T is a tree. To do this, we will
exploit the underlying toric structure, introduce a tableau notation for working with monomials,
and introduce an appropriate ordering of the variables.
Each variable σij that is not zero can be identified with the unique trek in T from i to j.
We associate to σij the tableau which records the elements of T in this unique trek, which is
represented like this:
σij = [aBi|aCj]
where B and C are (possibly empty) strings. If, say, i were at the top of the path, we would
write the tableau as
σij = [i|iCj].
The tableau is in its standard form if aBi is lexicographically earlier than aCj. We introduce a
lexicographic total order on standard form tableau variables by declaring [aA|aB] ≺ [cC|cD] if
aA is lexicographically smaller that cC, or if aA = cC and aB is lexicographically smaller than
cD. Given a monomial, its tableau representation is the row-wise concatenation of the tableau
forms of each of the variables appearing in the monomial.
Example 5.7. Let T be the tree with edges 1 → 3, 1 → 4, 2 → 4, 3 → 5, 3 → 6, 4 → 7,
and 4→ 8. Then the monomial σ14σ18σ24σ234σ38σ57σ78 has the standard form lexicographically
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 19
ordered tableau: 

1 148
13 14
13 14
13 148
135 147
47 48

Note that if a variable appears to the d-th power in a monomial, the representation for this
variable is repeated as d rows in the tableau. �
When we write out general tableau, lower-case letters will always correspond to single char-
acters (possibly empty) and upper case letters will always correspond to strings of characters
(also, possibly empty).
Theorem 5.8. For any tree T , the conditional independence statements implied by T generate
IT . In particular, IT is generated by linear polynomials σij and quadratic tetrad constraints.
Proof. First of all, we can ignore the linear polynomials as they always correspond to indepen-
dence constraints and work modulo these linear constraints when working with the toric ideal
IT . In addition, every quadratic binomial of the form σijσkl − σilσkj that belongs to IT is im-
plied by a conditional independence statement. This follows from Proposition 4.7. Note that
this holds even if the set {i, j, k, l} does not have four elements. Thus, it suffices to show that
IT modulo the linear constraints is generated by quadratic binomials.
To show that IT is generated by quadratic binomials, it suffices to show that any binomial in
IT can be written as a polynomial linear combination of the quadratic binomials in IT . This, in
turn, will be achieved by showing that we can “move” from the tableau representation of one
of the monomials to the other by making local changes that correspond to quadratic binomials.
To show this last part, we will define a sort of distance between two monomials and show that
it is always possible to decrease this distance using these quadratic binomials/ moves. This is a
typical trick for dealing with toric ideals, illustrated, for instance, in [19].
To this end let f be a binomial in IT . Without loss of generality, we may suppose the terms
of f have no common factors, because if σa · f ∈ IT then f ∈ IT as well. We will write f as the
difference of two tableaux, which are in standard form with their rows lexicographically ordered.
The first row in the two tableaux are different and they have a left-most place where they
disagree. We will show that we can always move this position further to the right. Eventually
the top rows of the tableaux will agree and we can delete this row (corresponding to the same
variable) and arrive at a polynomial of smaller degree.
Since f ∈ IT , the treks associated to the top rows of the two tableaux must have the same
top. There are two cases to consider. Either the first disagreement is immediately after the top
or not. In the first case, this means that the binomial f must have the form:[
abB acC
abB adD
20 SETH SULLIVANT
Without loss of generality we may suppose that c < d. Since f ∈ IT the string ac must appear
somewhere on the right-hand monomial. Thus, f must have the form:
 abB acC
 abB adDaeE acC ′
If d 6= e, we can apply the quadratic binomial[
abB adD
aeE acC ′
abB acC ′
aeE adD
to the second monomial to arrive at a monomial which has fewer disagreements with the left-
hand tableau in the first row. On the other hand, if d = e, we cannot apply this move (its
application results in “variables” that do not belong to C[Σ]). Keeping track of all the ad
patterns that appear on the right-hand side, and the consequent ad patterns that appear on the
left-hand side, we see that our binomial f has the form
abB acC
ad∗ ∗
ad∗ ∗
−

abB adD
adD′ acC ′
ad∗ ∗
ad∗ ∗
 .
Since there are the same number of ad’s on both sides we see that there is at least one more a
on the right-hand side which has no d’s attached to it. Thus, omitting the excess ad’s on both
sides, our binomial f contains:
 abB acC
 abB adDadD′ acC ′
aeE agG
with d 6= e or g. We can also assume that c 6= e, g otherwise, we could apply a quadratic move
as above. Thus we apply the quadratic binomials[
adD′ acC ′
aeE agG
adD′ agG
aeE acC ′
and [
abB adD
aeE acC ′
abB acC ′
aeE adD
to reduce the number of disagreements in the first row. This concludes the proof of the first
case. Now suppose that the first disagreement does not occur immediately after the a. Thus we
may suppose that f has the form:[
aAxbB aC
aAxdD aE
Note that it does not matter whether or not this disagreement appears on the left-hand or
right-hand side of the tableaux. Since the string xd appears on right-hand monomial it must
also appear somewhere on the left-hand monomial as well. If x is not the top in this occurrence,
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 21
we can immediately apply a quadratic binomial to reduce the discrepancies in the first row. So
we may assume the f has the form:
 aAxbB aCxdD′ xgG
 aAxdD aE
If b 6= g we can apply the quadratic binomial[
aAxbB aC
xdD′ xgG
aAxdD′ aC
xbB xgG
to the left-hand monomial to reduce the discrepancies in the first row. So suppose that g = b.
Enumerating the xb pairs that can arise on the left and right hand monomials, we deduce, akin
to our argument in the first case above, that f has the form:
aAxbB aC
xdD′ xbG
xhH xkK
aAxdD aE
where h and k are not equal to b or d. Then we can apply the two quadratic binomials:[
xdD′ xbG
xhH xkK
xhH xbG
xdD′ xkK
and [
aAxbB aC
xdD′ xkK
aAxdD′ aC
xbB xkK
to the left-hand monomial to produce a monomial with fewer discrepancies in the first row. We
have shown that no matter what type of discrepancy that can occur in the first row, we can
always apply quadratic moves to produce fewer discrepancies. This implies that IT is generated
by quadrics. �
Among the results in this section were our proofs that IT has a squarefree initial ideal (and
hence C[Σ]/IT is normal and Cohen-Macaulay) and that IT is generated by linear forms and
quadrics. It seems natural to wonder if there is a term order that realizes these two features
simultaneously.
Conjecture 5.9. There exists a term order ≺ such that in≺(IT ) is generated by squarefree
monomials of degree one and two.
6. Hidden Trees
This section and the next concern Bayesian networks with hidden variables. A hidden or
latent random variable is one which we do not have direct access to. These hidden variables
might represent theoretical quantities that are directly unmeasurable (e.g. a random variable
representing intelligence), variables we cannot have access to (e.g. information about extinct
species), or variables that have been censored (e.g. for sensitive random variables in census
data). If we are given a model over all the observed and hidden random variables, the partially
22 SETH SULLIVANT
observed model is the one obtained by marginalizing over the hidden random variables. A
number of interesting varieties arise in this hidden variable setting.
For Gaussian random variables, the marginalization is again Gaussian, and the mean and
covariance matrix are obtained by extracting the subvector and submatrix of the mean and
covariance matrix corresponding to the observed random variables. This immediately yields the
following proposition.
Proposition 6.1. Let I ⊆ C[µ,Σ] be the vanishing ideal for a Gaussian model. Let H ∪O = [n]
be a partition of the random variables into hidden and observed variables H and O. Then
IO := I ∩ C[µi, σij | i, j ∈ O]
is the vanishing ideal for the partially observed model.
Proof. Marginalization in the Gaussian case corresponds to projection onto the subspace of pairs
(µO,ΣO,O) ⊆ R|O| × R(
|O|+1
2 ). Coordinate projection is equivalent to elimination [2]. �
In the case of a Gaussian Bayesian network, Proposition 6.1 has a number of useful corollaries,
of both a computational and theoretical nature. First of all, it allows for the computation of the
ideals defining a hidden variable model as an easy elimination step. Secondly, it can be used to
explain the phenomenon we observed in Example 2.13, that the constraints defining a hidden
variable model appeared as generators of the ideal of the fully observed model.
Definition 6.2. Let H ∪ O be a partition of the nodes of the DAG G. The hidden nodes H
are said to be upstream from the observed nodes O in G if there are no edges o→ h in G with
o ∈ O and h ∈ H.
If H∪O is an upstream partition of the nodes of G, we introduce a grading on the ring C[a, λ]
which will, in turn, induce a grading on C[Σ]. Let deg ah = (1, 0) for all h ∈ H, deg ao = (1, 2)
for all o ∈ O, deg λho = (0, 1) if h ∈ H and o ∈ O, and deg λij = (0, 0) otherwise.
Lemma 6.3. Suppose that H ∪O = [n] is an upstream partition of the vertices of G. Then each
of the polynomials φG(σij) is homogeneous with respect to the upstream grading and
deg(σij) =
(1, 0) if i ∈ H, j ∈ H
(1, 1) if i ∈ H, j ∈ O or i ∈ O, j ∈ H
(1, 2) if i ∈ O, j ∈ O.
Thus, IG is homogeneous with respect to the induced grading on C[Σ].
Proof. There are three cases to consider. If both i, j ∈ H, then every trek in T (i, j) has a top
element in H and no edges of the form h→ o. In this case, the degree of each path is the vector
(1, 0). If i ∈ H and j ∈ O, every trek from i to j has a top in H and exactly one edge of the
form h→ o. Thus, the degree of every monomial in φ(σij) is (1, 1). If both i, j ∈ O, then either
each trek P from i to j has a top in O, or has a top in H. In the first case there can be no
edges in P of the form h → o, and in the second case there must be exactly two edges in P of
the form h→ o. In either case, the degree of the monomial corresponding to P is (1, 2). �
Note that the two dimensional grading we have described can be extended to an n dimensional
grading on the ring C[Σ] by considering all collections of upstream variables in G simultaneously.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 23
Theorem 6.4 (Upstream Variables Theorem). Let H∪O be an upstream partition of the vertices
of G. Then every minimal generating set of IG that is homogeneous with respect to the upstream
grading contains a minimal generating set of IG,O.
Proof. The set of indeterminates σij corresponding to the observed variables are precisely the
variables whose degrees lie on the facet of the degree semigroup generated by the vector (1, 2).
This implies that the subring generated by these indeterminates is a facial subring. �
The upstream variables theorem is significant because any natural generating set of an ideal
I is homogeneous with respect to its largest homogeneous grading group. For instance, every
reduced Gröbner basis if IG will be homogeneous with respect to the upstream grading. For
trees, the upstream variables theorem immediately implies:
Corollary 6.5. Let T be a rooted directed tree and O consist of the leaves of T . Then IT,O is
generated by the quadratic tetrad constraints
σikσjl − σilσkj
such that i, j, k, l ∈ O, and there is a choke point c between {i, j} and {k, l}.
Corollary 6.5 says that the ideal of a hidden tree model is generated by the tetrad constraints
induced by the choke points in the tree. Sprites et al [17] use these tetrad constraints as a tool
for inferring DAG models with hidden variables. Given a sample covariance matrix, they test
whether a collection of tetrad constraints is equal to zero. From the given tetrad constraints
that are satisfied, together with the tetrad representation theorem, they construct a DAG that
is consistent with these vanishing tetrads. However, it is not clear from that work whether or
not it is enough to consider only these tetrad constraints. Indeed, as shown in [17], there are
pairs of graphs with hidden nodes that have precisely the same set of tetrad constraints that do
not yield the same family of covariance matrices. Theorem 6.5 can be seen as a mathematical
justification of the tetrad procedure of Spirtes, et al, in the case of hidden tree models, because
it shows that the tetrad constraints are enough to distinguish between the covariance matrices
coming from different trees.
7. Connections to Algebraic Geometry
In this section, we give families of examples to show how classical varieties from algebraic
geometry arise in the study of Gaussian Bayesian networks. In particular, we show how toric
degenerations of the Grassmannian, matrix Schubert varieties, and secant varieties all arise as
special cases of Gaussian Bayesian networks with hidden variables.
7.1. Toric Initial Ideals of the Grassmannian. Let Gr2,n be the Grassmannian of 2-planes
in Cn. The Grassmannian has the natural structure of an algebraic variety under the Plücker
embedding. The ideal of the Grassmannian is generated by the quadratic Plücker relations:
I2,n := I(Gr2,n) = 〈σijσkl − σikσjl + σilσjk | 1 ≤ i < j < k < l ≤ n〉 ⊂ C[Σ].
The binomial initial ideals of I2,n are in bijection with the unrooted trivalent trees with n
leaves. These binomial initial ideals are, in fact, toric ideals, and we will show that:
24 SETH SULLIVANT
Theorem 7.1. Let T be a rooted directed binary tree with [n] leaves and let O be the set of
leaves of T . Then there is a weight vector ω ∈ R(
2 ) and a sign vector τ ∈ {±1}(
2 ) such that
IT,O = τ · inω(I2,n).
The sign vector τ acts by multiplying coordinate σij by τij .
Proof. The proof idea is to show that the toric ideals IT,O have the same generators as the toric
initial ideals of the Grassmannian that have already been characterized in [16]. Without loss
of generality, we may suppose that the leaves of T are labeled by [n], that the tree is drawn
without edge crossings, and the leaves are labeled in increasing order from left to right. These
assumptions will allow us to ignore the sign vector τ in the proof. The sign vector results from
straightening the tree and permuting the columns in the Steifel coordinates. This results in sign
changes in the Plücker coordinates.
In Corollary 6.5, we saw that IT,O was generated by the quadratic relations
σikσjl − σilσkj
such that there is a choke point in T between {i, j} and {k, l}. This is the same as saying
that the induced subtree of T on {i, j, k, l} has the split {i, j}|{k, l}. These are precisely the
generators of the toric initial ideals of the Grassmannian G2,n identified in [16]. �
In the preceding Theorem, any weight vector ω that belongs to the relative interior of the cone
of the tropical Grassmannian corresponding to the tree T will serve as the desired partial term
order. We refer to [16] for background on the tropical Grassmannian and toric degenerations of
the Grassmannian. Since and ideal and its initial ideals have the same Hilbert function, we see
Catalan numbers emerging as degrees of Bayesian networks yet again.
Corollary 7.2. Let T be a rooted, directed, binary tree and O consist of the leaves of T . Then
deg IT,O = 1n−1
, the (n− 2)-nd Catalan number.
The fact that binary hidden tree models are toric degenerations of the Grassmannian has
potential use in phylogenetics. Namely, it suggests a family of new models, of the same di-
mension as the binary tree models, that could be used to interpolate between the various tree
models. That is, rather than choosing a weight vector in a full dimensional cone of the tropical
Grassmannian, we could choose a weight vector ω that sits inside of lower dimensional cone.
The varieties of the initial ideals V (inω(I2,n)) then correspond to models that sit somewhere
“between” models corresponding of the full dimensional trees of the maximal dimensional cones
containing ω. Phylogenetic recovery algorithms could reference these in-between models to indi-
cate some uncertainty about the relationships between a given collection of species or on a given
branch of the tree. These new models have the advantage that they have the same dimension
as the tree models and so there is no need for dimension penalization in model selection.
7.2. Matrix Schubert Varieties. In this section, we will describe how certain varieties called
matrix Schubert varieties arise as special cases of the varieties of hidden variable models for
Gaussian Bayesian networks. More precisely, the variety for the Gaussian Bayesian network will
be the cone over one of these matrix Schubert varieties. To do this, we first need to recall some
equivalent definitions of matrix Schubert varieties.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 25
Let w be a partial permutation matrix, which is an n × n 0/1 matrix with at most one 1 in
each row and column. The matrix w is in the affine space Cn×n. The Borel group B of upper
triangular matrices acts on Cn×n on the right by multiplication and on the left by multiplication
by the transpose.
Definition 7.3. The matrix Schubert variety Xw is the orbit closure of w by the action of B
on the right and left:
Xw = BTwB.
Let Iw be the vanishing ideal of Xw.
The matrix Schubert variety Xw ⊆ Cn×n, so we can identify its coordinate ring with a quotient
of C[σij | i ∈ [n], j ∈ [n′]]. Throughout this section [n′] = {1′, 2′, . . . , n′}, is a set of n symbols
that we use to distinguish from [n] = {1, 2, . . . , n}.
An equivalent definition of a matrix Schubert variety comes as follows. Let S(w) = {(i, j) | wij =
1} be the index set of the ones in w. For each (i, j) let Mij be the variety of rank one matrices:
Mij =
x ∈ Cn×n | rankx ≤ 1, xkl = 0 if k < i or l < j
(i,j)∈S(w)
where the sum denotes the pointwise Minkowski sum of the varieties. Since Mij are cones over
projective varieties, this is the same as taking the join, defined in the next section.
Example 7.4. Let w be the partial permutation matrix
1 0 00 1 0
0 0 0
Then Xw consists of all 3× 3 matrices of rank ≤ 2 and Iw =
|Σ[3],[3′]|
. More generally, if w is
a partial permutation matrix of the form
where Ed is a d×d identity matrix, then Iw is the ideal of (d+1) minors of a generic matrix. �
The particular Bayesian networks which yield the desired varieties come from taking certain
partitions of the variables. In particular, we assume that the observed variables come in two
types labeled by [n] = {1, 2, . . . , n} and [n′] = {1′, 2′, . . . , n′}. The hidden variables will be
labeled by the set S(w).
Define the graph G(w) with vertex set V = [n] ∪ [n′] ∪ S(w) and edge set consisting of edges
k → l for all k < l ∈ [n], k′ → l′ for all k′ < l′ ∈ [n′], (i, j) → k for all (i, j) ∈ S(w) and k ≥ i
and (i, j)→ k′ for all (i, j) ∈ S(w) and k′ ≥ j.
Theorem 7.5. The generators of the ideal Iw defining the matrix Schubert variety Xw are the
same as the generators of the ideal IG(w),[n]∪[n′] of the hidden variable Bayesian network for the
DAG G(w) with observed variables [n] ∪ [n′]. That is,
Iw · C[σij | i, j ∈ [n] ∪ [n′]] = IG(w),[n]∪[n′].
26 SETH SULLIVANT
Proof. The proof proceeds in a few steps. First, we give a parametrization of a cone over
the matrix Schubert variety, whose ideal is naturally seen to be Iw · C[σij | i, j ∈ [n] ∪ [n′]].
Then we describe a rational transformation φ on C[σij | i, j ∈ [n] ∪ [n′]] such that φ(Iw) =
IG(w),[n]∪[n′]. We then exploit that fact that this transformation is invertible and the elimination
ideal IG(w),[n]∪[n′] ∩ C[σij | i ∈ [n], j ∈ [n′]] is fixed to deduce the desired equality.
First of all, we give our parametrization of the ideal Iw. To do this, we need to carefully
identify all parameters involved in the representation. First of all, we split the indeterminates
in the ring C[σij | i, i ∈ [n]∪ [n′]] into three classes of indeterminates: those with i, j ∈ [n], those
with i, j ∈ [n′], and those with i ∈ [n] and j ∈ [n′]. Then we define a parametrization φw which
is determined as follows:
φw : C[τ, γ, a, λ]→ C[σij | i, j ∈ [n] ∪ [n′]
φw(σij) =
τij if i, j ∈ [n]
γij if i, j ∈ [n′]∑
(k,l)∈S(w):k≤i,l≤j a(k,l)λ(k,l),iλ(k,l),j if i ∈ [n], j ∈ [n
Let Jw = kerφw. Since the τ , γ, λ, and a parameters are all algebraically independent, we
deduce that in Jw, there will be no generators that involve combinations of the three types
of indeterminates in C[σij | i, j ∈ [n] ∪ [n′]]. Furthermore, restricting to the first two types of
indeterminates, there will not be any nontrivial relations involving these types of indeterminates.
Thus, to determine Jw, it suffices to restrict to the ideal among the indeterminates of the form
σij such that i ∈ [n] and j ∈ [n′]. However, considering the parametrization in this case, we see
that this is precisely the parametrization of the ideal Iw, given as the Minkowski sum of rank
one matrices. Thus, Jw = Iw.
Now we will define a map from φ : C[σij ] → C[σij ] which sends Jw to another ideal, closely
related to IG(w),[n]∪[n′]. To define this map, first, we use the fact that from the submatrix
Σ[n],[n] we can recover the λij and ai parameters associated to [n], when only considering the
complete subgraph associated to graph G(w)[n] (and ignoring the treks that involve the vertices
(k, l) ∈ S(w)). This follows because these parameters are identifiable by Proposition 2.5. A
similar fact holds when restricting to the subgraph G(w)[n′]. The ideal Jw we have defined thus
far can be considered as the vanishing ideal of a parametrization which gives the complete graph
parametrization for G(w)[n] and G(w)[n′] and a parameterization of the matrix Schubert variety
Xw on the σij with i ∈ [n] and j ∈ [n′]. So we can rationally recover the λ and a parameters
associated to the subgraphs G(w)[n] and G(w)[n′].
For each j < k pair in [n] or in [n′], define the partial trek polynomial
sjk(λ) =
j=l0<l1<...<lm=k
λli−1li .
We fit these into two upper triangular matrices S and S′ where Sjk = sjk if j < k with j, k ∈ [n],
Sjj = 1 and Sjk = 0 otherwise, with a similar definition for S′ with [n] replaced by [n′]. Now
we are ready to define our map. Let φ be the rational map φ : C[Σ] → C[Σ] which leaves σij
fixed if i, j ∈ [n] or i, j ∈ [n′], and maps σij with i ∈ [n] and j ∈ [n′] by sending
Σ[n],[n′] 7→ SΣ[n],[n′](S
′)T .
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 27
This is actually a rational map, because the λij that appear in the formula for sjk are expressed
as rational functions in terms of the σij by the rational parameter recovery formula of Proposition
2.5. Since this map transforms Σ[n],[n′] by multiplying on the left and right but lower and upper
triangular matrices, this leaves the ideal Jw ∩ C[σij | i ∈ [n], j ∈ [n′]] fixed. Thus Jw ⊆ φ(Jw).
On the other hand φ is invertible on Jw so Jw = φ(Jw).
If we think about the formulas for the image φ◦φw, we see that the formulas for σij with i ∈ [n]
and j ∈ [n′] in terms of parameters are the correct formulas which we would see coming from
the parametrization φG(w). On the other hand, the formulas for σij with i, j ∈ [n] or i, j ∈ [n′]
are the formulas for the restricted graph G[n] and G[n′], respectively. Since every trek contained
in G[n] or G[n′] is a trek in G(w), we see that the current parametrization of Jw is only “almost
correct”, in that it is only missing terms corresponding to treks that go outside of G(w)[n] or
G(w)[n′]. Denote this map by ψw, and let φG(w) be the actual parametrizing map of the model.
Thus, we have, for each σij with i, j ∈ [n] or i, j ∈ [n′], φG(w)(σij) = ψw(σij) + rw(σij), where
rw(σij) is a polynomial remainder term that does not contain any ai with i ∈ [n] ∪ [n′], when
i, j ∈ [n] or i, j ∈ [n′], and rw(σij) = 0 otherwise. On the other hand, every term of ψw(σij) will
involve exactly one ai with i ∈ [n] ∪ [n′], when i, j ∈ [n] or i, j ∈ [n′].
Now we define a weight ordering ≺ on the ring C[a, λ] that gives deg ai = 1 if i ∈ [n]∪ [n′] and
deg ai = 0 otherwise and deg λij = 0 for all i, j. Then, the largest degree term of φG(w)(σij) with
respect to this weight ordering is ψw(σ). Since highest weight terms must all cancel with each
other, we see that f ∈ IG(w),[n]∪[n′], implies that f ∈ Jw. Thus, we deduce that IG(w),[n]∪[n′] ⊆ Jw.
On the other hand,
IG(w),[n]∪[n]′ ∩ C[σij | i ∈ [n], j ∈ [n
′]] = Jw ∩ C[σij | i ∈ [n], j ∈ [n′]]
and since the generators of Jw ∩ C[σij | i ∈ [n], j ∈ [n′]] generate Jw, we deduce that Jw ⊆
IG(w),[n]∪[n′] which completes the proof. �
The significance of Theorem 7.5 comes from the work of Knutson and Miller [11]. They gave
a complete description of antidiagonal Gröbner bases for the ideals Iw. Indeed, these ideals
are generated by certain subdeterminants of the matrix Σ[n],[n′]. These determinants can be
interpretted combinatorially in terms of the graph G(w).
Theorem 7.6. [11] The ideal Iw defining the matrix Schubert variety is generated by the con-
ditional independence statements implied by the DAG G(w). In particular,
#C + 1 minors ofΣA,B | A ⊂ [n], B ⊂ [n′], C ⊂ S(w), and C d-separates A from B
7.3. Joins and Secant Varieties. In this section, we will show how joins and secant varieties
arise as special cases of Gaussian Bayesian networks in the hidden variable case. This, in turn,
implies that techniques that have been developed for studying defining equations of joins and
secant varieties (e.g. [12, 20]) might be useful for studying the equations defining these hidden
variable models.
Given two ideals I and J in a polynomial ring K[x] = K[x1, . . . , xm], their join is the new
ideal
I ∗ J := (I(y) + J(z) + 〈xi − yi − zi | i ∈ [m]〉)
28 SETH SULLIVANT
where I(y) is the ideal obtained from I by plugging in the variables y1, . . . , ym for x1, . . . , xm.
The secant ideal is the iterated join:
I{r} = I ∗ I ∗ · · · ∗ I
with r copies of I. If I and J are homogeneous radical ideals over an algebraically closed field,
the join ideal I ∗ J is the vanishing ideal of the join variety which is defined geometrically by
the rule
V (I ∗ J) = V (I) ∗ V (J) =
a∈V (I)
b∈V (J)
< a, b >
where < a, b > denotes the line spanned by a and b and the bar denotes the Zariski closure.
Suppose further that I and J are the vanishing ideals of parametrizations; that is there are
φ and ψ such that
φ : C[x]→ C[θ] and ψ : C[x]→ C[η]
and I = kerφ and J = kerψ. Then I ∗ J is the kernel of the map
φ+ ψ : C[x]→ C[θ, η]
xi 7→ φ(xi) + ψ(xi).
Given a DAG G and a subset K ⊂ V (G), GK denotes the induced subgraph on K.
Proposition 7.7. Let G be a DAG and suppose that the vertices of G are partitioned into
V (G) = O ∪H1 ∪H2 where both H1 and H2 are hidden sets of variables. Suppose further that
there are no edges of the form o1 → o2 such that o1, o2 ∈ O or edges of the form h1 → h2 or
h2 → h1 with h1 ∈ H1 and h2 ∈ H2. Then
IG,O = IGO∪H1 ,O ∗ IGO∪H2 ,O.
The proposition says that if the hidden variables are partitioned with no edges between the
two sets and there are no edges between the observed variables the ideal is a join.
Proof. The parametrization of the hidden variable model only involves the σij such that i, j ∈ O.
First, we restrict to the case where i 6= j. Since there are no edges between observed variables
and no edges between H1 and H2, every trek from i to j involves only edges in GO∪H1 or only
edges in GO∪H2 . This means that
φG(σij) = φGO∪H1 (σij) + φGO∪H2 (σij)
and these summands are in non-overlapping sets of indeterminates. Thus, by the comments
preceding the proposition, the ideal only in the σij with i 6= j ∈ O is clearly a join. However,
the structure of this hidden variable model implies that there are no nontrivial relations that
involve the diagonal elements σii with i ∈ O. This implies that IG,O is a join. �
Example 7.8. Let Kp,m be the directed complete bipartite graph with bipartition H = [p′]
and O = [m] such that i′ → j ∈ E(Kp,m) for all i′ ∈ [p′] and j ∈ [m]. Then Kp,m satisfies the
conditions of the theorem recursively up to p copies, and we see that:
IKp,m,O = I
K1,m,O
This particular hidden variable Gaussian Bayesian network is known as the factor analysis model.
This realization of the factor analysis model as a secant variety was studied extensively in [3].
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 29
Example 7.9. Consider the two “doubled trees” pictured in the figure.
1 2 3 4 5 6
1 2 3 4 5 6
Since in each case, the two subgraphs GO∪H1 and GO∪H2 are isomorphic, the ideals are secant
ideals of the hidden tree models IT,O for the appropriate underlying trees. In both cases, the
ideal I{2}T,O = IG,O is a principal ideal, generated by a single cubic. In the first case, the ideal
is the determinantal ideal J{2}T = 〈|Σ123,456|〉. In the second case, the ideal is generated by an
eight term cubic
IG,O = 〈σ13σ25σ46 − σ13σ26σ45 − σ14σ25σ36 + σ14σ26σ35
+σ15σ23σ46 − σ15σ24σ36 − σ16σ23σ45 + σ16σ24σ35〉 .
In both of the cubic cases in the previous example, the ideals under questions were secant
ideals of toric ideals that were initial ideals of the Grassmann-Plücker ideal, as we saw in Theorem
7.1. Note also that the secant ideals I{2}T,O are, in fact, the initial terms of the 6× 6 Pfaffian with
respect to appropriate weight vectors. We conjecture that this pattern holds in general.
Conjecture 7.10. Let T be a binary tree with n leaves and O the set of leaves of T . Let
I2,n be the Grassmann-Pluücker ideal, let ω be a weight vector and τ a sign vector so that
IT,O = τ · inω(I2,n) as in Theorem 7.1. Then for each r
T,O = τ · inω(I
2,n ).
References
[1] P. Bickel and K. Doksum. Mathematical Statistics. Vol 1. Prentice-Hall, London, 2001.
[2] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics.
Springer, New York, 1997.
[3] M. Drton, B. Sturmfels, and S. Sullivant. Algebraic factor analysis: tetrads, pentads, and beyond. To appear
in Probability Theory and Related Fields, 2006.
[4] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press,
Cambridge, 1999.
[5] J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Inc. Sunderland, MA, 2004.
[6] L. Garcia. Polynomial constraints of Bayesian networks with hidden variables. Preprint, 2006.
[7] L. Garcia, M. Stillman, and B. Sturmfels. Algebraic geometry of Bayesian networks. Journal of Symbolic
Computation 39 (2005) 331-355.
[8] I. Gessel and G. Viennot. Binomial determinants, paths, and hook length formulae. Adv. in Math. 58 (1985),
no. 3, 300–321.
30 SETH SULLIVANT
[9] D. Grayson and M. Stillman. Macaulay 2, a software system for research in algebraic geometry. Available at
http://www.math.uiuc.edu/Macaulay2/
[10] M. Hochster. Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes,
Annals of Mathematics 96 (1972) 318–337.
[11] A. Knutson and E. Miller. Gröbner geometry of Schubert polynomials. Ann. of Math. (2) 161 (2005), no. 3,
1245–1318.
[12] J. M. Landsberg, L. Manivel. On the ideals of secant varieties of Segre varieties. Found. Comput. Math. 4
(2004), no. 4, 397–422.
[13] S. Lauritzen. Graphical Models. Oxford Statistical Science Series 17 Clarendon Press, Oxford, 1996.
[14] R. Read and R. Wilson. An Atlas of Graphs. Oxford Scientific Publications. (1998)
[15] C. Semple and M. Steel. Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications 24 Oxford
University Press, Oxford, 2003.
[16] D. Speyer and B. Sturmfels. The tropical Grassmannian. Advances in Geometry 4 (2004) 389-411.
[17] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. The MIT Press, Cambridge,
MA, 2000.
[18] R. Stanley. Enumerative Combinatorics Vol. 2 Cambridge Studies in Advanced Mathematics 62, Cambridge
University Press, 1999.
[19] B. Sturmfels. Gröbner Bases and Convex Polytopes. University Lecture Series 8, American Mathematical
Society, Providence, RI, 1996.
[20] B. Sturmfels and S. Sullivant. Combinatorial secant varieties. Quarterly Journal of Pure and Applied Math-
ematics 2 (2006) 285-309.
Department of Mathematics and Society of Fellows, Harvard University, Cambridge, MA 02138
http://www.math.uiuc.edu/Macaulay2/
	1. Introduction
	Acknowledgments
	2. Parametrization and Conditional Independence
	3. Computational Study
	4. Tetrad Representation Theorem
	5. Fully Observed Trees
	6. Hidden Trees
	7. Connections to Algebraic Geometry
	7.1. Toric Initial Ideals of the Grassmannian
	7.2. Matrix Schubert Varieties
	7.3. Joins and Secant Varieties
	References

  Conditional independence models in the Gaussian case are algebraic varieties
in the cone of positive definite covariance matrices. We study these varieties
in the case of Bayesian networks, with a view towards generalizing the
recursive factorization theorem to situations with hidden variables. In the
case when the underlying graph is a tree, we show that the vanishing ideal of
the model is generated by the conditional independence statements implied by
graph. We also show that the ideal of any Bayesian network is homogeneous with
respect to a multigrading induced by a collection of upstream random variables.
This has a number of important consequences for hidden variable models.
Finally, we relate the ideals of Bayesian networks to a number of classical
constructions in algebraic geometry including toric degenerations of the
Grassmannian, matrix Schubert varieties, and secant varieties.

Introduction
A Bayesian network or directed graphical model is a statistical model that uses a directed
acyclic graph (DAG) to represent the conditional independence structures between collections
of random variables. The word Bayesian is used to describe these models because the nodes
in the graph can be used to represent random variables that correspond to parameters or hy-
perparameters, though the basic models themselves are not a priori Bayesian. These models
are used throughout computational statistics to model complex interactions between collections
of random variables. For instance, tree models are used in computational biology for sequence
alignment [4] and in phylogenetics [5, 15]. Special cases of Bayesian networks include familiar
models from statistics like factor analysis [3] and the hidden Markov model [4].
The DAG that specifies the Bayesian network specifies the model in two ways. The first is
through a recursive factorization of the parametrization, via restricted conditional distributions.
The second method is via the conditional independence statements implied by the graph. The
recursive factorization theorem [13, Thm 3.27] says that these two methods for specifying a
Bayesian network yield the same family of probability density functions.
When the underlying random variables are Gaussian or discrete, conditional independence
statements can be interpreted as algebraic constraints on the parameter space of the global
model. In the Gaussian case, this means that conditional independence corresponds to algebraic
constraints on the cone of positive definite matrices. One of our main goals in this paper is to
explore the recursive factorization theorem using algebraic techniques in the case of Gaussian
random variables, with a view towards the case of hidden random variables. In this sense, the
current paper is a generalization of the work began in [3] which concerned the special case of
factor analysis. Some past work has been done on the algebraic geometry of Bayesian networks
in the discrete case in [6, 7], but there are many open questions that remain in both the Gaussian
and the discrete case.
2 SETH SULLIVANT
In the next section, we describe a combinatorial parametrization of a Bayesian network in
the Gaussian case. In statistics, this parametrization in known as the trek rule [17]. We also
describe the algebraic interpretation of conditional independence in the Gaussian case which
leads us to our main problem: comparing the vanishing ideal of the model IG to the conditional
independence ideal CG. Section 3 describes the results of computations regarding the ideals
of Bayesian networks, and some algebraic conjectures that these computations suggest. In
particular, we conjecture that the coordinate ring of a Bayesian network is always normal and
Cohen-Macaulay.
As a first application of our algebraic perspective on Gaussian Bayesian networks, we provide a
new and greatly simplified proof of the tetrad representation theorem [17, Thm 6.10] in Section
4. Then in Section 5 we provide an extensive study of trees in the fully observed case. In
particular, we prove that for any tree T , the ideal IT is a toric ideal generated by linear forms
and quadrics that correspond to conditional independence statements implied by T . Techniques
from polyhedral geometry are used to show that C[Σ]/IT is always normal and Cohen-Macaulay.
Sections 6 and 7 are concerned with the study of hidden variable models. In Section 6 we
prove the Upstream Variables Theorem (Theorem 6.4) which shows that IG is homogeneous
with respect to a two dimensional multigrading induced by upstream random variables. As
a corollary, we deduce that hidden tree models are generated by tetrad constraints. Finally
in Section 7 we show that models with hidden variables include, as special cases, a number
of classical constructions from algebraic geometry. These include toric degenerations of the
Grassmannian, matrix Schubert varieties, and secant varieties.
Acknowledgments. I would like to thank Mathias Drton, Thomas Richardson, Mike Stillman,
and Bernd Sturmfels for helpful comments and discussions about the results in this paper. The
IMA provided funding and computer equipment while I worked on parts of this project.
2. Parametrization and Conditional Independence
Let G be a directed acyclic graph (DAG) with vertex set V (G) and edge set E(G). Often,
we will assume that V (G) = [n] := {1, 2, . . . , n}. To guarantee the acyclic assumption, we
assume that the vertices are numerically ordered ; that is, i → j ∈ E(G) only if i < j. The
Bayesian network associated to this graph can be specified by either a recursive factorization
formula or by conditional independence statements. We focus first on the recursive factorization
representation, and use it to derive an algebraic description of the parametrization. Then we
introduce the conditional independence constraints that vanish on the model and the ideal that
these constraints generate.
Let X = (X1, . . . , Xn) be a random vector, and let f(x) denote the probability density
function of this random vector. Bayes’ theorem says that this joint density can be factorized as
a product
f(x) =
fi(xi|x1, . . . , xi−1),
where fi(xi|x1, . . . , xi−1) denotes the conditional density of Xi given X1 = x1, . . . , Xi−1 = xi−1.
The recursive factorization property of the graphical model is that each of the conditional
densities fi(xi|x1, . . . , xi−1) only depends on the parents pa(i) = {j ∈ [n] | j → i ∈ E(G)}. We
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 3
can rewrite this representation as
fi(xi|x1, . . . , xi−1) = fi(xi|xpa(i)).
Thus, a density function f belongs to the Bayesian network if it factorizes as
f(x) =
fi(xi|xpa(i)).
To explore the consequences of this parametrization in the Gaussian case, we first need to
recall some basic facts about Gaussian random variables. Each n-dimensional Gaussian random
variable X is completely specified by its mean vector µ and its positive definite covariance matrix
Σ. Given these data, the joint density function of X is given by
f(x) =
(2π)n/2|Σ|1/2
exp(−
(x− µ)T Σ−1(x− µ)),
where |Σ| is the determinant of Σ. Rather than writing out the density every time, the short-
hand X ∼ N (µ,Σ) is used to indicate that X is a Gaussian random variable with mean µ
and covariance matrix Σ. The multivariate Gaussian generalizes the familiar “bell curve” of
a univariate Gaussian and is an important distribution in probability theory and multivariate
statistics because of the central limit theorem [1].
Given an n-dimensional random variable X and A ⊆ [n], let XA = (Xa)a∈A. Similarly, if
x is a vector, then xA is the subvector indexed by A. For a matrix Σ, ΣA,B is the submatrix
of Σ with row index set A and column index set B. Among the nice properties of Gaussian
random variables are the fact that marginalization and conditioning both preserve the Gaussian
property; see [1].
Lemma 2.1. Suppose that X ∼ N (µ,Σ) and let A,B ⊆ [n] be disjoint. Then
(1) XA ∼ N (µA,ΣA,A) and
(2) XA|XB = xB ∼ N (µA + ΣA,BΣ−1B,B(xB − µB),ΣA,A − ΣA,BΣ
B,BΣB,A).
To build the Gaussian Bayesian network associated to the DAG G, we allow any Gaussian con-
ditional distribution for the distribution f(xi|xpa(i)). This conditional distribution is recovered
by saying that
i∈pa(j)
λijXi +Wj
where Wj ∼ N (νj , ψ2j ) and is independent of the Xi with i < j, and the λij are the regression
parameters. Linear transformations of Gaussian random variables are Gaussian, and thus X is
also a Gaussian random variable. Since X is completely specified by its mean µ and covariance
matrix Σ, we must calculate these from the conditional distribution. The recursive expression
for the distribution of Xj given the variables preceding it yields a straightforward and recursive
expression for the mean and covariance. Namely
µj = E(Xj) = E(
i∈pa(j)
λijXi +Wj) =
i∈pa(j)
λijµi + νj
4 SETH SULLIVANT
and if k < j the covariance is:
σkj = E ((Xk − µk)(Xj − µj))
(Xk − µk)
i∈pa(j)
λij(Xi − µi) +Wj − νj
i∈pa(j)
λijE ((Xk − µk)(Xi − µi)) + E ((Xk − µk)(Wj − νj))
i∈pa(j)
λijσik
and the variance satisfies:
σjj = E
(Xj − µj)2
i∈pa(j)
λij(Xi − µi) +Wj − νj
i∈pa(j)
k∈pa(j)
λijλkjσik + ψ
If there are no constraints on the vector ν, there will be no constraints on µ either. Thus, we
will focus attention on the constraints on the covariance matrix Σ. If we further assume that the
ψ2j are completely unconstrained, this will imply that we can replace the messy expression for
the covariance σjj by a simple new parameter aj . This leads us to the algebraic representation
of our model, called the trek rule [17].
For each edge i → j ∈ E(G) let λij be an indeterminate and for each vertex i ∈ V (G) let ai
be an indeterminate. Assume that the vertices are numerically ordered, that is i → j ∈ E(G)
only if i < j. A collider is a pair of edges i → k, j → k with the same head. For each pair of
vertices i, j, let T (i, j) be the collection of simple paths P in G from i to j such that there is no
collider in P . Such a colliderless path is called a trek. The name trek come from the fact that
every colliderless path from i to j consists of a path from i up to some topmost element top(P )
and then from top(P ) back down to j. We think of each trek as a sequence of edges k → l. If
i = j, T (i, i) consists of a single empty trek from i to itself.
Let φG be the ring homomorphism
φG : C[σij | 1 ≤ i ≤ j ≤ n]→ C[ai, λij | i, j ∈ [n]i→ j ∈ E(G)]
σij 7→
P∈T (i,j)
atop(P ) ·
k→l∈P
When i = j, we get σii = ai. If there is no trek in T (i, j), then φG(σij) = 0. Let IG = kerφG.
Since IG is the kernel of a ring homomorphism, it is a prime ideal.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 5
Example 2.2. Let G be the directed graph on four vertices with edges 1 → 2, 1 → 3, 2 → 4,
and 3→ 4. The ring homomorphism φG is given by
σ11 7→ a1 σ12 7→ a1λ12 σ13 7→ a1λ13 σ14 7→ a1λ12λ24 + a1λ13λ34
σ22 7→ a2 σ23 7→ a1λ12λ13 σ24 7→ a2λ24 + a1λ12λ13λ34
σ33 7→ a3 σ34 7→ a3λ34 + a1λ13λ12λ24
σ44 7→ a4
The ideal IG is the complete intersection of a quadric and a cubic:
σ11σ23 − σ13σ21, σ12σ23σ34 + σ13σ24σ23 + σ14σ22σ33 − σ13σ24σ33 − σ13σ22σ34 − σ14σ223
Dual to the ring homomorphism is the rational parametrization
φ∗G : R
E(G)+V (G) → R(
φ∗G(a, λ) = (
P∈T (i,j)
atop(P ) ·
k→l∈P
λkl)i,j .
We will often write σij(a, λ) to denote the coordinate polynomial that represents this function.
Let Ω ⊂ RE(G)+V (G) be the subset of parameter space satisfying the constraints:
j∈pa(i)
k∈pa(i)
λjiλkiσjk(a, λ)
for all i, where in the case that pa(i) = ∅ the sum is zero.
Proposition 2.3. [Trek Rule] The set of covariance matrices in the Gaussian Bayesian network
associated to G is the image φ∗G(Ω). In particular, IG is the vanishing ideal of the model.
The proof of the trek rule parametrization can also be found in [17].
Proof. The proof goes by induction. First, we make the substitution
i∈pa(j)
k∈pa(j)
λijλkjσik + ψ
which is valid because, given the λij ’s, ψ2j can be recovered from aj and vice versa. Clearly
σ11 = a1. By induction, suppose that the desired formula holds for all σij with i, j < n. We
want to show that σin has the same formula. Now from above, we have
σin =
k∈pa(n)
λknσik
k∈pa(n)
P∈T (i,k)
atop(P ) ·
r→s∈P
This last expression is a factorization of φ(σkn) since every trek from i to n is the union of a
trek P ∈ T (i, k) and an edge k → n where k is some parent of n. �
The parameters used in the trek rule parametrization are a little unusual because they involve
a mix of the natural parameters (regression coefficients λij) and coordinates on the image space
(variance parameters ai). While this mix might seem unusual from a statistical standpoint,
we find that this parametrization is rather useful for exploring the algebraic structure of the
covariance matrices that come from the model. For instance:
6 SETH SULLIVANT
Corollary 2.4. If T is a tree, then IT is a toric ideal.
Proof. For any pair of vertices i, j in T , there is at most one trek between i and j. Thus φ(σij)
is a monomial and IT is a toric ideal. �
In fact, as we will show in Section 5, when T is a tree, IT is generated by linear forms and
quadratic binomials that correspond to conditional independence statements implied by the
graph. Before getting to properties of conditional independence, we first note that these models
are identifiable. That is, it is possible to recover the λij and ai parameters directly from Σ. This
also allows us to determine the most basic invariant of IG, namely its dimension.
Proposition 2.5. The parametrization φ∗G is birational. In other words, the model parameters
λij and ai are identifiable and dim IG = #V (G) + #E(G).
Proof. It suffices to prove that the parameters are identifiable via rational functions of the entries
of Σ, as all the other statements follow from this. We have ai = σii so the ai parameters are
identifiable. We also know that for i < j
σij =
k∈pa(j)
σikλkj .
Thus, we have the matrix equation
Σpa(j),j = Σpa(j),pa(j)λpa(j),j
where λpa(j),j is the vector (λij)
i∈pa(j). Since Σpa(j),pa(j) is invertible in the positive definite
cone, we have the rational formula
λpa(j),j = Σ
pa(j),pa(j)
Σpa(j),j
and the λij parameters are identifiable. �
One of the problems we want to explore is the connection between the prime ideal defining the
graphical model (and thus the image of the parametrization) and the relationship to the ideal
determined by the independence statements induced by the model. To explain this connection,
we need to recall some information about the algebraic nature of conditional independence.
Recall the definition of conditional independence.
Definition 2.6. Let A, B, and C be disjoint subsets of [n], indexing subsets of the random
vector X. The conditional independence statement A⊥⊥B|C (“A is independent of B given C)
holds if and only if
f(xA, xB|xC) = f(xA|xC)f(xB|xC)
for all xC such that f(xC) 6= 0.
We refer to [13] for a more extensive introduction to conditional independence. In the Gauss-
ian case, a conditional independence statement is equivalent to an algebraic restriction on the
covariance matrix.
Proposition 2.7. Let A,B,C be disjoint subsets of [n]. Then X ∼ N (µ,Σ) satisfies the con-
ditional independence constraint A⊥⊥B|C if and only if the submatrix ΣA∪C,B∪C has rank less
than or equal to #C.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 7
Proof. If X ∼ N (µ, σ), then
XA∪B|XC = xC ∼ N
µA∪B + ΣA∪B,CΣ
C,C(xC − µC),ΣA∪B,A∪B − ΣA∪B,CΣ
C,CΣC,A∪B
The CI statement A⊥⊥B|C holds if and only if (ΣA∪B,A∪B − ΣA∪B,CΣ−1C,CΣC,A∪B)A,B = 0. The
A,B submatrix of ΣA∪B,A∪B − ΣA∪B,CΣ−1C,CΣC,A∪B is easily seen to be ΣA,B − ΣA,CΣ
C,CΣC,B
which is the Schur complement of the matrix
ΣA∪C,B∪C =
ΣA,B ΣA,C
ΣC,B ΣC,C
Since ΣC,C is always invertible (it is positive definite), the Schur complement is zero if and only
if the matrix ΣA∪C,B∪C has rank less than or equal to #C. �
Given a DAG G, a collection of conditional independence statements are forced on the joint
distribution by the nature of the graph. These independence statements are usually described
via the notion of d-separation (the d stands for “directed”).
Definition 2.8. Let A, B, and C be disjoint subsets of [n]. The set C d-separates A and B if
every path in G connecting a vertex i ∈ A and B ∈ j contains a vertex k that is either
(1) a non-collider that belongs to C or
(2) a collider that does not belong to C and has no descendants that belong to C.
Note that C might be empty in the definition of d-separation.
Proposition 2.9 ([13]). The conditional independence statement A⊥⊥B|C holds for the Bayesian
network associated to G if and only if C d-separates A from B in G.
A joint probability distribution that satisfies all the conditional independence statements
implied by the graph G is said to satisfy the global Markov property of G. The following theorem
is a staple of the literature of graphical models, that holds with respect to any σ-algebra.
Theorem 2.10 (Recursive Factorization Theorem). [13, Thm 3.27] A probability density has
the recursive factorization property with respect to G if and only if it satisfies the global Markov
property.
Definition 2.11. Let CG ⊆ C[Σ] be the ideal generated by the minors of Σ corresponding to
the conditional independence statements implied by G; that is,
CG = 〈(#C + 1) minors of ΣA∪C,B∪C | C d-separates A from B in G〉 .
The ideal CG is called the conditional independence ideal of G.
A direct geometric consequence of the recursive factorization theorem is the following
Corollary 2.12. For any DAG G,
V (IG) ∩ PDn = V (CG) ∩ PDn.
In the corollary PDn ⊂ R(
2 ) is the cone of n × n positive definite symmetric matrices. It
seems natural to ask whether or not IG = CG for all DAGs G. For instance, this was true for
the DAG in Example 2.2. The Verma graph provides a natural counterexample.
8 SETH SULLIVANT
2 3 4 5
Example 2.13. Let G be the DAG on five vertices with edges 1 → 3, 1 → 5, 2 → 3, 2 → 4,
3→ 4, and 4→ 5. This graph is often called the Verma graph.
The conditional independence statements implied by the model are all implied by the three
statements 1⊥⊥2, 1⊥⊥4|{2, 3}, and {2, 3}⊥⊥5|{1, 4}. Thus, the conditional independence ideal
CG is generated by one linear form and five determinantal cubics. In this case, we find that
IG = CG + 〈f〉 where f is the degree four polynomial:
f = σ23σ24σ25σ34 − σ22σ25σ234 − σ23σ
24σ35 + σ22σ24σ34σ35
−σ223σ25σ44 + σ22σ25σ33σ44 + σ
23σ24σ45 − σ22σ24σ33σ45.
We found that the primary decomposition of CG is
CG = IG ∩ 〈σ11, σ12, σ13, σ14〉
so that f is not even in the radical of CG. Thus, the zero set of CG inside the positive semidefinite
cone contains singular covariance matrices that are not limits of distributions that belong to the
model. Note that since none of the indices of the σij appearing in f contain 1, f vanishes on
the marginal distribution for the random vector (X2, X3, X4, X5). This is the Gaussian version
of what is often called the Verma constraint. Note that this computation shows that the Verma
constraint is still needed as a generator of the unmarginalized Verma model. �
The rest of this paper is concerned with studying the ideals IG and investigating the circum-
stances that guarantee that CG = IG. We report on results of a computational study in the
next section. Towards the end of the paper, we study the ideals IG,O that arise when some of
the random variables are hidden.
3. Computational Study
Whenever approaching a new family of ideals, our first instinct is to compute as many exam-
ples as possible to gain some intuition about the structure of the ideals. This section summarizes
the results of our computational explorations.
We used Macaulay2 [9] to compute the generating sets of all ideals IG for all DAGs G on n ≤ 6
vertices. Our computational results concerning the problem of when CG = IG are summarized
in the following proposition.
Proposition 3.1. All DAGs on n ≤ 4 vertices satisfy CG = IG. Of the 302 DAGs on n = 5
vertices, exactly 293 satisfy CG = IG. Of the 5984 DAGs on n = 6 vertices exactly 4993 satisfy
CG = IG.
On n = 5 vertices, there were precisely nine graphs that fail to satisfy CG = IG. These
nine exceptional graphs are listed below. The numberings of the DAGs come from the Atlas of
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 9
Graphs [14]. Note that the Verma graph from Example 2.13 appears as A218 after relabeling
vertices.
(1) A139: 1→ 4, 1→ 5, 2→ 4, 3→ 4, 4→ 5.
(2) A146: 1→ 3, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(3) A197: 1→ 2, 1→ 3, 1→ 5, 2→ 4, 3→ 4, 4→ 5.
(4) A216: 1→ 2, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(5) A217: 1→ 3, 1→ 4, 2→ 4, 2→ 5, 3→ 4, 4→ 5.
(6) A218: 1→ 3, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(7) A275: 1→ 2, 1→ 4, 1→ 5, 2→ 3, 2→ 5, 3→ 4, 4→ 5.
(8) A277: 1→ 2, 1→ 3, 1→ 5, 2→ 4, 3→ 4, 3→ 5, 4→ 5.
(9) A292: 1→ 2, 1→ 4, 2→ 3, 2→ 5, 3→ 4, 3→ 5, 4→ 5.
The table below displays the numbers of minimal generators of different degrees for each of the
ideals IG where G is one of the nine graphs on five vertices such that CG 6= IG. The coincidences
among rows in this table arise because sometimes two different graphs yield the same family of
probability distributions. This phenomenon is known as Markov equivalence [13, 17].
Network 1 2 3 4 5
A139 3 1 2 0 0
A146 1 3 7 0 0
A197 0 1 5 0 1
A216 0 1 5 0 1
A217 2 1 2 0 0
A218 1 0 5 1 0
A275 0 1 1 1 3
A277 0 1 1 1 3
A292 0 1 1 1 3
It is worth noting the methods that we used to perform our computations, in particular,
how we computed generators for the ideals IG. Rather than using the trek rule directly, and
computing the vanishing ideal of the parametrization, we exploited the recursive nature of the
parametrization to determine IG. This is summarized by the following proposition.
Proposition 3.2. Let G be a DAG and G \ n the DAG with vertex n removed. Then
IG\n +
σin −
j∈pa(n)
λjnσij | i ∈ [n− 1]
〉⋂C[σij | i, j ∈ [n]]
where the ideal IG\n is considered as a graph on n− 1 vertices.
Proof. This is a direct consequence of the trek rule: every trek that goes to n passes through a
parent of n and cannot go below n. �
Based on our (limited) computations up to n = 6 we propose some optimistic conjectures
about the structures of the ideals IG.
10 SETH SULLIVANT
Conjecture 3.3.
IG = CG :
A⊂[n]
(|ΣA,A|)∞
Conjecture 3.3 says that all the uninteresting components of CG (that is, the components that
do not correspond to probability density functions) lie on the boundary of the positive definite
cone. Conjecture 3.3 was verified for all DAGs on n ≤ 5 vertices. Our computational evidence
also suggests that all the ideals IG are Cohen-Macaulay and normal, even for graphs with loops
and other complicated graphical structures.
Conjecture 3.4. The quotient ring C[Σ]/IG is normal and Cohen-Macaulay for all G.
Conjecture 3.4 was verified computationally for all graphs on n ≤ 5 vertices and graphs with
n = 6 vertices and less than 8 edges. We prove Conjecture 3.4 when the underlying graph is a
tree in Section 5. A more negative conjecture concerns the graphs such that IG = CG.
Conjecture 3.5. The proportion of DAGs on n vertices such that IG = CG tends to zero as
To close the section, we provide a few useful propositions for reducing the computation of the
generating set of the ideal IG to the ideals for smaller graphs.
Proposition 3.6. Suppose that G is a disjoint union of two subgraph G = G1 ∪G2. Then
IG = IG1 + IG2 + 〈σij | i ∈ V (G1), j ∈ V (G2)〉 .
Proof. In the parametrization φG, we have φG(σij) = 0 if i ∈ V (G1) and j ∈ V (G2), because
there is no trek from i to j. Furthermore, φG(σij) = φG1(σij) if i, j ∈ V (G1) and φG(σkl) =
φG2(σkl) if k, l ∈ V (G2) and these polynomials are in disjoint sets of variables. Thus, there can
be no nontrivial relations involving both σij and σkl. �
Proposition 3.7. Let G be a DAG with a vertex m with no children and a decomposition into
two induced subgraphs G = G1 ∪G2 such that V (G1) ∩ V (G2) = {m}. Then
IG = IG1 + IG2 + 〈σij | i ∈ V (G1) \ {m}, j ∈ V (G2) \ {m}〉 .
Proof. In the paremtrization φG, we have φG(σij) = 0 if i ∈ V (G1) \ {m} and j ∈ V (G2) \ {m},
because there is no trek from i to j. Furthermore φG(σij) = φG1(σij) if i, j ∈ V (G1) and
φG(σkl) = φG2(σkl) if k, l ∈ V (G2) and these polynomials are in disjoint sets of variables unless
i = j = k = l = m. However, in this final case, φG(σmm) = am and this is the only occurrence
of am in any of the expressions φG(σij). This is a consequence of the fact that vertex m has no
children. Thus, we have a partition of the σij into three sets in which φG(σij) appear in disjoint
sets of variables and there can be no nontrivial relations involving two or more of these sets of
variables. �
Proposition 3.8. Suppose that for all i ∈ [n − 1], the edge i → n ∈ E(G). Let G \ n be the
DAG obtained from G by removing the vertex n. Then
IG = IG\n · C[σij : i, j ∈ [n]].
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 11
Proof. Every vertex in G \ n is connected to n and is a parent of n. This implies that n cannot
appear in any conditional independence statement implied by G. Furthermore, if C d-separates
A from B in G\n, it will d-separate A from B in G, because n is below every vertex in G\n. This
implies that the CI statements that hold for G are precisely the same independence statements
that hold for G \ n. Thus
V (CG) ∩ PDn = V (CG\n · C[σij | i, j ∈ [n]]) ∩ PDn.
Since IG = I(V (CG) ∩ PDn), this implies the desired equality. �
4. Tetrad Representation Theorem
An important step towards understanding the ideals IG is to derive interpretations of the
polynomials in IG. We have an interpretation for a large part of IG, namely, the subideal
CG ⊆ IG. Conversely, we can ask when polynomials of a given form belong to the ideals IG.
Clearly, any linear polynomial in IG is a linear combination of polynomials of the form σij with
i 6= j, all of which must also belong to IG. Each linear polynomial σij corresponds to the
independence statement Xi⊥⊥Xj . Combinatorially, the linear from σij is in IG if and only if
there is no trek from i to j in G.
A stronger result of this form is the tetrad representation theorem, first proven in [17], which
gives a combinatorial characterization of when a tetrad difference
σijσkl − σilσjk
belongs to the ideal IG. The constraints do not necessarily correspond to conditional indepen-
dence statements, and need not belong to the ideal CG. This will be illustrated in Example
The original proof of the tetrad representation theorem in [17] is quite long and technical. Our
goal in this section is to show how our algebraic perspective can be used to greatly simplify the
proof. We also include this result here because we will need the tetrad representation theorem
in Section 5.
Definition 4.1. A vertex c ∈ V (G) is a choke point between sets I and J if every trek from a
point in I to a point in J contains c and either
(1) c is on the I-side of every trek from I to J , or
(2) c is on the J-side of every trek from I to J .
The set of all choke points in G between I and J is denoted C(I, J).
Example 4.2. In the graph c is a choke point between {1, 4} and {2, 3}, but is not a choke
point between {1, 2} and {3, 4}.
1 2 3 4
12 SETH SULLIVANT
Theorem 4.3 (Tetrad Representation Theorem [17]). The tetrad constraint σijσkl−σilσjk = 0
holds for all covariance matrices in the Bayesian network associated to G if and only if there is
a choke point in G between {i, k} and {j, l}.
Our proof of the tetrad representation theorem will follow after a few lemmas that lead to
the irreducible factorization of the polynomials σij(a, λ).
Lemma 4.4. In a fixed DAG G, every trek from I to J is incident to every choke point in
C(I, J) and they must be reached always in the same order.
Proof. If two choke points are on, say, the I side of every trek from I to J and there are two
treks which reach these choke points in different orders, there will be a directed cycle in G. If
the choke points c1 and c2 were on the I side and J side, respectively, and there were two treks
from I to J that reached them in a different order, this would contradict the property of being
a choke point. �
Lemma 4.5. Let i = c0, c1, . . . , ck = j be the ordered choke points in C({i}, {j}). Then the
irreducible factorization of σij(a, λ) is
σij(a, λ) =
f tij(a, λ)
where f tij(a, λ) only depends on λpq such that p and q are between choke points ct−1 and ct.
Proof. First of all, we will show that σij(a, λ) has a factorization as indicated. Then we will
show that the factors are irreducible. Define
f tij(a, λ) =
P∈T (i,j;ct−1,ct)
atop(P )
k→l∈P
where T (i, j; ct−1, ct) consists of all paths from ct−1 to ct that are partial treks from i to j (that
is, that can be completed to a trek from i to j) and atop(P ) = 1 if the top of the partial trek
P is not the top. When deciding whether or not the top is included in the partial trek, note
that almost all choke points are associated with either the {i} side or the {j} side. So there is
a natural way to decide if atop(P ) is included or not. In the exceptional case that c is a choke
point on both the {i} and the {j} side, we repeat this choke point in the list. This is because c
must be the top of every trek from i to j, and we will get a factor f tij(a, λ) = ac.
Since each ct is a choke point between i and j, the product of the monomials, one from each
f tij , is the monomial corresponding to a trek from i to j. Conversely, every monomial arises as
such a product in a unique way. This proves that the desired factorization holds.
Now we will show that each of the f tij(a, λ) cannot factorize further. Note that every monomial
in f tij(a, λ) is squarefree in all the a and λ indeterminates. This means that every monomial
appearing in f tij(a, λ) is a vertex of the Newton polytope of f
ij(a, λ). This, in turn, implies
that in any factorization f tij(a, λ) = fg there is no cancellation since in any factorization of any
polynomial, the vertices of the Newton polytope is the product of two vertices of the constituent
Newton polytopes. This means that in any factorization f tij(a, λ) = fg, f and g can be chosen
to be the sums of squarefree monomials all with coefficient 1.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 13
Now let f tij(a, λ) = fg be any factorization and let m be a monomial appearing in f
ij(a, λ).
If the factorization is nontrivial m = mfmg where mf and mg are monomials in f and g
respectively. Since the factorization is nontrivial and m corresponds to a partial trek P in
T (i, j; ct−1, ct), there must exist a c on P such that, without loss of generality such that λpc
appears in mf and λcq appears in mg. Since every monomial in the expansion of fg corresponds
to a partial trek from ct−1 to ct it must be the case that every monomial in f contains an
indeterminate λsc from some s and similarly, every monomial appearing in g contains a λcs for
some s. But this implies that every partial trek from ct−1 to ct passes through c, with the same
directionality, that is, it is a choke point between i and j. However, this contradicts the fact the
C({i}, {j}) = {c0, . . . , ct}. �
Proof of Thm 4.3. Suppose that the vanishing tetrad condition holds, that is,
σijσkl = σilσkj
for all covariance matrices in the model. This factorization must thus also hold when we sub-
stitute the polynomial expressions in the parametrization:
σij(a, λ)σkl(a, λ) = σil(a, λ)σkj(a, λ).
Assuming that none of these polynomials are zero (in which case the choke condition is satisfied
for trivial reasons), this means that each factor f tij(a, λ) must appear on both the left and the
right-hand sides of this expression. This is a consequence of the fact that polynomial rings
over fields are unique factorization domains. The first factor f1ij(a, λ) could only be a factor of
σil(a, λ). There exists a unique t ≥ 1 such that f1ij · · · f
ij divides σil but f
ij · · · f
ij does not
divide σil. This implies that f
ij divides σkj . However, this implies that ct is a choke point
between i and j, between i and l, between k and j. Furthermore, this will imply that ct is a
choke point between k and l as well, which implies that ct is a choke point between {i, k} and
{j, l}.
Conversely, suppose that there is a choke point c between {i, k} and {j, l}. Our unique
factorization of the σij implies that we can write
σij = f1g1, σkl = f2g2, σil = f1g2, σkj = f2g1
where f1 and f2 corresponds to partial treks from i to c and k to c, respectively, and g1 and g2
correspond to partial treks from c to j and l, respectively. Then we have
σijσkl = f1g1f2g2 = σilσkj ,
so that Σ satisfies the tetrad constraint. �
At first glance, it is tempting to suggest that the tetrad representation theorem says that
a tetrad vanishes for every covariance matrix in the model if and only if an associated condi-
tional independence statement holds. Unfortunately, this is not true, as the following example
illustrates.
Example 4.6. Let A139 be the graph with edges 1→ 4, 1→ 5, 2→ 4, 3→ 4 and 4→ 5. Then
4 is a choke point between {2, 3} and {4, 5} and the tetrad σ24σ35 − σ25σ34 belongs to IA139 .
However, it is not implied by the conditional independence statements implied by the graph
(that is, σ24σ35 − σ25σ34 /∈ CA139). It is precisely this extra tetrad constraint that forces A139
onto the list of graphs that satisfy CG 6= IG from Section 3.
14 SETH SULLIVANT
In particular, a choke point between two sets need not be a d-separator of those sets. In the
case that G is a tree, it is true that tetrad constraints are conditional independence constraints.
Proposition 4.7. Let T be a tree and suppose that c is a choke point between I and J in T .
Then either c d-separates I \ {c} and J \ {c} or ∅ d-separates I \ {c} and J \ {c}.
Proof. Since T is a tree, there is a unique path from an element in I \ c to an element in J \ c.
If this path is not a trek, we have ∅ d-separates I \ {c} from J \ {c}. On the other hand, if this
path is always a trek we see that {c} d-separates I \ {c} from J \ {c}. �
The tetrad representation theorem gives a simple combinatorial rule for determining when a
2 × 2 minor of Σ is in IG. More generally, we believe that there should exist a graph theoretic
rule that determines when a general determinant |ΣA,B| ∈ IG in terms of structural features of
the DAG G. The technique we have used above, which relies on giving a factorization of the
polynomials σ(a, λ), does not seem like it will extend to higher order minors. One approach
at a generalization of the tetrad representation theorem would be to find a cancellation free
expression for the determinant |ΣA,B| in terms of the parameters ai and λij , along the lines of
the Gessel-Viennot theorem [8]. From such a result, one could deduce a combinatorial rule for
when |ΣA,B| is zero. This suggests the following problem.
Problem 4.8. Develop a Gessel-Viennot theorem for treks; that is, determine a combinatorial
formula for the expansion of |ΣA,B| in terms of the treks in G.
5. Fully Observed Trees
In this section we study the Bayesian networks of trees in the situation where all random
variables are observed. We show that the toric ideal IT is generated by linear forms σij and
quadratic tetrad constraints. The Tetrad Representation Theorem and Proposition 4.7 then
imply that IT = CT . We also investigate further algebraic properties of the ideals IT using the
fact that IT is a toric ideal and some techniques from polyhedral geometry.
For the rest of this section, we assume that T is a tree, where by a tree we mean a DAG
whose underlying undirected graph is a tree. These graphs are sometimes called polytrees in
the graphical models literature. A directed tree is a tree all of whose edges are directed away
from a given source vertex.
Since IT is a toric ideal, it can be analyzed using techniques from polyhedral geometry. In
particular, for each i, j such that T (i, j) is nonempty, let aij denote the exponent vector of the
monomial σij = atop(P )
k→l∈P λkl. Let AT denote the set of all these exponent vectors. The
geometry of the toric variety V (IT ) is determined by the discrete geometry of the polytope
PT = conv(AT ).
The polytope PT is naturally embedded in R2n−1, where n of the coordinates on R2n−1
correspond to the vertices of T and n − 1 of the coordinates correspond to the edges of T .
Denote the first set of coordinates by xi and the second by yij where i→ j is an edge in T . Our
first results is a description of the facet structure of the polytope PT .
Theorem 5.1. The polytope PT is the solution to the following set of equations and inequalities:
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 15
xi ≥ 0 for all i ∈ V (T )
yij ≥ 0 for all i→ j ∈ E(T )∑
i∈V (T ) xi = 1
i: i→j∈E(T ) yij − yjk ≥ 0 for all j → k ∈ E(T )
2xj +
i: i→j∈E(T ) yij −
k: j→k∈E(T ) yjk ≥ 0 for all j ∈ V (T ).
Proof. Let QT denote the polyhedron defined as the solution space to the given constraints.
First of all, QT is bounded. To see this, first note that because of the positive constraints and
the equation
i∈V (T ) xi = 1, we have that xi ≤ 1 is implied by the given constraints. Then,
starting from the sources of the tree and working our way down the edges repeatedly using the
inequalities xj +
i: i→j∈E(T ) yij − yjk ≥ 0, we see that the yij are also bounded.
Now, we have PT ⊆ QT , since every trek will satisfy any of the indicated constraints. Thus,
we must show that QT ⊆ PT . To do this, it suffices to show that for any vector (x0, y0) ∈ QT ,
there exists λ > 0, (x1, y1) and (x2, y2) such that
(x0, y0) = λ(x1, y1) + (1− λ)(x2, y2)
where (x1, y1) is one of the 0/1 vectors aij and (x2, y2) ∈ QT . Because QT is bounded, this
will imply that the extreme points of QT are a subset of the extreme points of PT , and hence
QT ⊆ PT . Without loss of generality we may suppose that all of the coordinates y0ij are positive,
otherwise the problem reduces to a smaller tree or forest because the resulting inequalities that
arise when yij = 0 are precisely those that are necessary for the smaller tree. Note that for
a forest F , the polytope PF is the direct join of polytopes PT as T ranges over the connected
components of F , by Proposition 3.6.
For any fixed j, there cannot exist distinct values k1, k2, and k3 such that all of
x0j +
i: i→j∈E(T )
y0ij − y
x0j +
i: i→j∈E(T )
y0ij − y
x0j +
i: i→j∈E(T )
y0ij − y
hold. If there were, we could add these three equations together to deduce that
3x0j + 3
i: i→j∈E(T )
y0ij − y
− y0jk2 − y
This in turn implies that
2x0j +
i: i→j∈E(T )
y0ij − y
− y0jk2 − y
with equality if and only if pa(j) = ∅ and x0j = 0. This in turn implies that, for instance,
y0jk1 = 0 contradicting our assumption that y
ij > 0 for all i and j. By a similar argument, if
exactly two of these facet defining inequalities hold sharply, we see that
2x0j + 2
i: i→j∈E(T )
y0ij − y
− y0jk2 = 0
16 SETH SULLIVANT
which implies that j has exactly two descendants and no parents.
Now mark each edge j → k in the tree T such that
x0j +
i: i→j∈E(T )
y0ij − y
jk = 0.
By the preceding paragraph, we can find a trek P from a sink in the tree to a source in the tree
and (possibly) back to a different sink that has the property that for no i in the trek there exists
k not in the path such that i → k is a marked edge. That is, the preceding paragraph shows
that there can be at most 2 marked edges incident to any given vertex.
Given P , let (x1, y1) denote the corresponding 0/1 vector. We claim that there is a λ > 0
such that
(1) (x0, y0) = λ(x1, y1) + (1− λ)(x2, y2)
holds with (x2, y2) ∈ QT . Take λ > 0 to be any very small number and define (x2, y2) by the
given equation. Note that by construction the inequalities x2i ≥ 0 and y
ij ≥ 0 will be satisfied
since for all the nonzero entries in (x1, y1), the corresponding inequality for (x0, y0) must have
been nonstrict and λ is small. Furthermore, the constraint
x2i = 1 is also automatically
satisfied. It is also easy to see that the last set of inequalities will also be satisfied since through
each vertex the path will either have no edges, an incoming edge and an outgoing edge, or two
outgoing edges and the top vertex, all of which do not change the value of the linear functional.
Finally to see that the inequalities of the form
i: i→j∈E(T )
yij − yjk ≥ 0
are still satisfied by (x2, y2), note that marked edges of T are either contained in the path
P or not incident to the path P . Thus, the strict inequalities remain strict (since they will
involve modifying by an incoming edge and an outgoing edge or an outgoing edge and the top
vertex), and the nonstrict inequalities remain nonstrict since λ is small. Thus, we conclude that
QT ⊆ PT , which completes the proof. �
Corollary 5.2. Let ≺ be any reverse lexicographic term order such that σii � σjk for all i and
j 6= k. Then in≺(IT ) is squarefree. In other words, the associated pulling triangulation of PT is
unimodular.
Proof. The proof is purely polyhedral, and relies on the geometric connections between trian-
gulations and initial ideals of toric ideals. See Chapter 8 in [19] for background on this material
including pulling triangulations. Let aij denote the vertex of PT corresponding to the monomial
φG(σij). For i 6= j, each of the vertices aij has lattice distance at most one from any of the
facets described by Theorem 5.1. This is seen by evaluating each of the linear functionals at the
0/1 vector corresponding to the trek between i and j.
If we pull from one of these vertices we get a unimodular triangulation provided that the
induced pulling triangulation on each of the facets of PT not containing aij is unimodular. This
is because the normalized volume of a simplex is the volume of the base times the lattice distance
from the base to the vertex not on the base.
The facet defining inequalities of any face of PT are obtained by taking an appropriate subset
of the facet defining inequalities of PT . Thus, as we continue the pulling triangulation, if the
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 17
current face contains a vertex aij with i 6= j, we will pull from this vertex first and get a
unimodular pulling triangulation provided the induced pulling triangulation of every face is
unimodular. Thus, by induction, it suffices to show that the faces of PT that are the convex
hull of vertices aii have unimodular pulling triangulations. However, these faces are always
unimodular simplices. �
Corollary 5.3. The ring C[Σ]/IT is normal and Cohen-Macaulay when T is a tree.
Proof. Since PT has a unimodular triangulation, it is a normal polytope and hence the semigroup
ring C[Σ]/IT is normal. Hochster’s theorem [10] then implies that C[Σ]/IT is Cohen-Macaulay.
While we know that C[Σ]/IT is always Cohen-Macaulay, it remains to determine how the
Cohen-Macaulay type of IT depends on the underlying tree T . Here is a concrete conjecture
concerning the special case of Gorenstein trees.
Conjecture 5.4. Suppose that T is a directed tree. Then C[Σ]/IT is Gorenstein if and only if
the degree of every vertex in T is less than or equal to three.
A downward directed tree is a tree all of whose edges point to the unique sink in the tree. A
leaf of such a downward directed tree is then a source of the tree. With a little more refined
information about which inequalities defining PT are facet defining, we can deduce results about
the degrees of the ideals IT in some cases.
Corollary 5.5. Let T be a downward directed tree and let i be any leaf of T , s the sink of T ,
and P the unique trek in T (i, s). Then
deg IT =
k→l∈P
deg IT\k→l
where T \ k → l denotes the forest obtained from T by removing the edge k → l.
Proof. First of all, note that in the case of a downward directed tree the inequalities of the form
2xj +
i: i→j∈E(T )
yij −
k: j→k∈E(T )
yjk ≥ 0
are redundant: since each vertex has at most one descendant, it is implied by the the other
constraints. Also, for any source t, the inequality xt ≥ 0 is redundant, because it is implied by
the inequalities xt − ytj ≥ 0 and ytj ≥ 0 where j is the unique child of t.
Now we will compute the normalized volume of the polytope PT (which is equal to the degree
of the toric ideal IT ) by computing the pulling triangulation from Corollary and relating the
volumes of the pieces to the associated subforests.
Since the pulling triangulation of PT with ais pulled first is unimodular, the volume of PT is
the sum of the volumes of the facets of PT that do not contain ais. Note that ais lies on all the
facets of the form
i: i→j∈E(T )
yij − yjk ≥ 0
since through every vertex besides the source and sink, the trek has either zero or two edges
incident to it. Thus, the only facets that ais does not lie on are of the form ykl ≥ 0 such that
18 SETH SULLIVANT
k → l is an edge in the trek P . However, the facet of PT obtained by setting ykl = 0 is precisely
the polytope PT\k→l, which follows from Theorem 5.1. �
Note that upon removing an edge in a tree we obtain a forest. Proposition 3.6 implies that
the degree of such a forest is the product of the degrees of the associated trees. Since the degree
of the tree consisting of a single point is one, the formula from Corollary 5.5 yields a recursive
expression for the degree of a downward directed forest.
Corollary 5.6. Let Tn be the directed chain with n vertices. Then deg ITn =
, the n−1st
Catalan number.
Proof. In Corollary 5.5 we take the unique path from 1 to n. The resulting forests obtained
by removing an edge are the disjoint unions of two paths. By the product formula implied by
Proposition 3.6 we deduce that the degree of ITn satisfies the recurrence:
deg ITn =
deg ITi · deg ITn−i
with initial condition deg IT1 = 1. This is precisely the recurrence and initial conditions for the
Catalan numbers [18]. �
Now we want to prove the main result of this section, that the determinantal conditional
independence statements actually generate the ideal IT when T is a tree. To do this, we will
exploit the underlying toric structure, introduce a tableau notation for working with monomials,
and introduce an appropriate ordering of the variables.
Each variable σij that is not zero can be identified with the unique trek in T from i to j.
We associate to σij the tableau which records the elements of T in this unique trek, which is
represented like this:
σij = [aBi|aCj]
where B and C are (possibly empty) strings. If, say, i were at the top of the path, we would
write the tableau as
σij = [i|iCj].
The tableau is in its standard form if aBi is lexicographically earlier than aCj. We introduce a
lexicographic total order on standard form tableau variables by declaring [aA|aB] ≺ [cC|cD] if
aA is lexicographically smaller that cC, or if aA = cC and aB is lexicographically smaller than
cD. Given a monomial, its tableau representation is the row-wise concatenation of the tableau
forms of each of the variables appearing in the monomial.
Example 5.7. Let T be the tree with edges 1 → 3, 1 → 4, 2 → 4, 3 → 5, 3 → 6, 4 → 7,
and 4→ 8. Then the monomial σ14σ18σ24σ234σ38σ57σ78 has the standard form lexicographically
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 19
ordered tableau: 

1 148
13 14
13 14
13 148
135 147
47 48

Note that if a variable appears to the d-th power in a monomial, the representation for this
variable is repeated as d rows in the tableau. �
When we write out general tableau, lower-case letters will always correspond to single char-
acters (possibly empty) and upper case letters will always correspond to strings of characters
(also, possibly empty).
Theorem 5.8. For any tree T , the conditional independence statements implied by T generate
IT . In particular, IT is generated by linear polynomials σij and quadratic tetrad constraints.
Proof. First of all, we can ignore the linear polynomials as they always correspond to indepen-
dence constraints and work modulo these linear constraints when working with the toric ideal
IT . In addition, every quadratic binomial of the form σijσkl − σilσkj that belongs to IT is im-
plied by a conditional independence statement. This follows from Proposition 4.7. Note that
this holds even if the set {i, j, k, l} does not have four elements. Thus, it suffices to show that
IT modulo the linear constraints is generated by quadratic binomials.
To show that IT is generated by quadratic binomials, it suffices to show that any binomial in
IT can be written as a polynomial linear combination of the quadratic binomials in IT . This, in
turn, will be achieved by showing that we can “move” from the tableau representation of one
of the monomials to the other by making local changes that correspond to quadratic binomials.
To show this last part, we will define a sort of distance between two monomials and show that
it is always possible to decrease this distance using these quadratic binomials/ moves. This is a
typical trick for dealing with toric ideals, illustrated, for instance, in [19].
To this end let f be a binomial in IT . Without loss of generality, we may suppose the terms
of f have no common factors, because if σa · f ∈ IT then f ∈ IT as well. We will write f as the
difference of two tableaux, which are in standard form with their rows lexicographically ordered.
The first row in the two tableaux are different and they have a left-most place where they
disagree. We will show that we can always move this position further to the right. Eventually
the top rows of the tableaux will agree and we can delete this row (corresponding to the same
variable) and arrive at a polynomial of smaller degree.
Since f ∈ IT , the treks associated to the top rows of the two tableaux must have the same
top. There are two cases to consider. Either the first disagreement is immediately after the top
or not. In the first case, this means that the binomial f must have the form:[
abB acC
abB adD
20 SETH SULLIVANT
Without loss of generality we may suppose that c < d. Since f ∈ IT the string ac must appear
somewhere on the right-hand monomial. Thus, f must have the form:
 abB acC
 abB adDaeE acC ′
If d 6= e, we can apply the quadratic binomial[
abB adD
aeE acC ′
abB acC ′
aeE adD
to the second monomial to arrive at a monomial which has fewer disagreements with the left-
hand tableau in the first row. On the other hand, if d = e, we cannot apply this move (its
application results in “variables” that do not belong to C[Σ]). Keeping track of all the ad
patterns that appear on the right-hand side, and the consequent ad patterns that appear on the
left-hand side, we see that our binomial f has the form
abB acC
ad∗ ∗
ad∗ ∗
−

abB adD
adD′ acC ′
ad∗ ∗
ad∗ ∗
 .
Since there are the same number of ad’s on both sides we see that there is at least one more a
on the right-hand side which has no d’s attached to it. Thus, omitting the excess ad’s on both
sides, our binomial f contains:
 abB acC
 abB adDadD′ acC ′
aeE agG
with d 6= e or g. We can also assume that c 6= e, g otherwise, we could apply a quadratic move
as above. Thus we apply the quadratic binomials[
adD′ acC ′
aeE agG
adD′ agG
aeE acC ′
and [
abB adD
aeE acC ′
abB acC ′
aeE adD
to reduce the number of disagreements in the first row. This concludes the proof of the first
case. Now suppose that the first disagreement does not occur immediately after the a. Thus we
may suppose that f has the form:[
aAxbB aC
aAxdD aE
Note that it does not matter whether or not this disagreement appears on the left-hand or
right-hand side of the tableaux. Since the string xd appears on right-hand monomial it must
also appear somewhere on the left-hand monomial as well. If x is not the top in this occurrence,
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 21
we can immediately apply a quadratic binomial to reduce the discrepancies in the first row. So
we may assume the f has the form:
 aAxbB aCxdD′ xgG
 aAxdD aE
If b 6= g we can apply the quadratic binomial[
aAxbB aC
xdD′ xgG
aAxdD′ aC
xbB xgG
to the left-hand monomial to reduce the discrepancies in the first row. So suppose that g = b.
Enumerating the xb pairs that can arise on the left and right hand monomials, we deduce, akin
to our argument in the first case above, that f has the form:
aAxbB aC
xdD′ xbG
xhH xkK
aAxdD aE
where h and k are not equal to b or d. Then we can apply the two quadratic binomials:[
xdD′ xbG
xhH xkK
xhH xbG
xdD′ xkK
and [
aAxbB aC
xdD′ xkK
aAxdD′ aC
xbB xkK
to the left-hand monomial to produce a monomial with fewer discrepancies in the first row. We
have shown that no matter what type of discrepancy that can occur in the first row, we can
always apply quadratic moves to produce fewer discrepancies. This implies that IT is generated
by quadrics. �
Among the results in this section were our proofs that IT has a squarefree initial ideal (and
hence C[Σ]/IT is normal and Cohen-Macaulay) and that IT is generated by linear forms and
quadrics. It seems natural to wonder if there is a term order that realizes these two features
simultaneously.
Conjecture 5.9. There exists a term order ≺ such that in≺(IT ) is generated by squarefree
monomials of degree one and two.
6. Hidden Trees
This section and the next concern Bayesian networks with hidden variables. A hidden or
latent random variable is one which we do not have direct access to. These hidden variables
might represent theoretical quantities that are directly unmeasurable (e.g. a random variable
representing intelligence), variables we cannot have access to (e.g. information about extinct
species), or variables that have been censored (e.g. for sensitive random variables in census
data). If we are given a model over all the observed and hidden random variables, the partially
22 SETH SULLIVANT
observed model is the one obtained by marginalizing over the hidden random variables. A
number of interesting varieties arise in this hidden variable setting.
For Gaussian random variables, the marginalization is again Gaussian, and the mean and
covariance matrix are obtained by extracting the subvector and submatrix of the mean and
covariance matrix corresponding to the observed random variables. This immediately yields the
following proposition.
Proposition 6.1. Let I ⊆ C[µ,Σ] be the vanishing ideal for a Gaussian model. Let H ∪O = [n]
be a partition of the random variables into hidden and observed variables H and O. Then
IO := I ∩ C[µi, σij | i, j ∈ O]
is the vanishing ideal for the partially observed model.
Proof. Marginalization in the Gaussian case corresponds to projection onto the subspace of pairs
(µO,ΣO,O) ⊆ R|O| × R(
|O|+1
2 ). Coordinate projection is equivalent to elimination [2]. �
In the case of a Gaussian Bayesian network, Proposition 6.1 has a number of useful corollaries,
of both a computational and theoretical nature. First of all, it allows for the computation of the
ideals defining a hidden variable model as an easy elimination step. Secondly, it can be used to
explain the phenomenon we observed in Example 2.13, that the constraints defining a hidden
variable model appeared as generators of the ideal of the fully observed model.
Definition 6.2. Let H ∪ O be a partition of the nodes of the DAG G. The hidden nodes H
are said to be upstream from the observed nodes O in G if there are no edges o→ h in G with
o ∈ O and h ∈ H.
If H∪O is an upstream partition of the nodes of G, we introduce a grading on the ring C[a, λ]
which will, in turn, induce a grading on C[Σ]. Let deg ah = (1, 0) for all h ∈ H, deg ao = (1, 2)
for all o ∈ O, deg λho = (0, 1) if h ∈ H and o ∈ O, and deg λij = (0, 0) otherwise.
Lemma 6.3. Suppose that H ∪O = [n] is an upstream partition of the vertices of G. Then each
of the polynomials φG(σij) is homogeneous with respect to the upstream grading and
deg(σij) =
(1, 0) if i ∈ H, j ∈ H
(1, 1) if i ∈ H, j ∈ O or i ∈ O, j ∈ H
(1, 2) if i ∈ O, j ∈ O.
Thus, IG is homogeneous with respect to the induced grading on C[Σ].
Proof. There are three cases to consider. If both i, j ∈ H, then every trek in T (i, j) has a top
element in H and no edges of the form h→ o. In this case, the degree of each path is the vector
(1, 0). If i ∈ H and j ∈ O, every trek from i to j has a top in H and exactly one edge of the
form h→ o. Thus, the degree of every monomial in φ(σij) is (1, 1). If both i, j ∈ O, then either
each trek P from i to j has a top in O, or has a top in H. In the first case there can be no
edges in P of the form h → o, and in the second case there must be exactly two edges in P of
the form h→ o. In either case, the degree of the monomial corresponding to P is (1, 2). �
Note that the two dimensional grading we have described can be extended to an n dimensional
grading on the ring C[Σ] by considering all collections of upstream variables in G simultaneously.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 23
Theorem 6.4 (Upstream Variables Theorem). Let H∪O be an upstream partition of the vertices
of G. Then every minimal generating set of IG that is homogeneous with respect to the upstream
grading contains a minimal generating set of IG,O.
Proof. The set of indeterminates σij corresponding to the observed variables are precisely the
variables whose degrees lie on the facet of the degree semigroup generated by the vector (1, 2).
This implies that the subring generated by these indeterminates is a facial subring. �
The upstream variables theorem is significant because any natural generating set of an ideal
I is homogeneous with respect to its largest homogeneous grading group. For instance, every
reduced Gröbner basis if IG will be homogeneous with respect to the upstream grading. For
trees, the upstream variables theorem immediately implies:
Corollary 6.5. Let T be a rooted directed tree and O consist of the leaves of T . Then IT,O is
generated by the quadratic tetrad constraints
σikσjl − σilσkj
such that i, j, k, l ∈ O, and there is a choke point c between {i, j} and {k, l}.
Corollary 6.5 says that the ideal of a hidden tree model is generated by the tetrad constraints
induced by the choke points in the tree. Sprites et al [17] use these tetrad constraints as a tool
for inferring DAG models with hidden variables. Given a sample covariance matrix, they test
whether a collection of tetrad constraints is equal to zero. From the given tetrad constraints
that are satisfied, together with the tetrad representation theorem, they construct a DAG that
is consistent with these vanishing tetrads. However, it is not clear from that work whether or
not it is enough to consider only these tetrad constraints. Indeed, as shown in [17], there are
pairs of graphs with hidden nodes that have precisely the same set of tetrad constraints that do
not yield the same family of covariance matrices. Theorem 6.5 can be seen as a mathematical
justification of the tetrad procedure of Spirtes, et al, in the case of hidden tree models, because
it shows that the tetrad constraints are enough to distinguish between the covariance matrices
coming from different trees.
7. Connections to Algebraic Geometry
In this section, we give families of examples to show how classical varieties from algebraic
geometry arise in the study of Gaussian Bayesian networks. In particular, we show how toric
degenerations of the Grassmannian, matrix Schubert varieties, and secant varieties all arise as
special cases of Gaussian Bayesian networks with hidden variables.
7.1. Toric Initial Ideals of the Grassmannian. Let Gr2,n be the Grassmannian of 2-planes
in Cn. The Grassmannian has the natural structure of an algebraic variety under the Plücker
embedding. The ideal of the Grassmannian is generated by the quadratic Plücker relations:
I2,n := I(Gr2,n) = 〈σijσkl − σikσjl + σilσjk | 1 ≤ i < j < k < l ≤ n〉 ⊂ C[Σ].
The binomial initial ideals of I2,n are in bijection with the unrooted trivalent trees with n
leaves. These binomial initial ideals are, in fact, toric ideals, and we will show that:
24 SETH SULLIVANT
Theorem 7.1. Let T be a rooted directed binary tree with [n] leaves and let O be the set of
leaves of T . Then there is a weight vector ω ∈ R(
2 ) and a sign vector τ ∈ {±1}(
2 ) such that
IT,O = τ · inω(I2,n).
The sign vector τ acts by multiplying coordinate σij by τij .
Proof. The proof idea is to show that the toric ideals IT,O have the same generators as the toric
initial ideals of the Grassmannian that have already been characterized in [16]. Without loss
of generality, we may suppose that the leaves of T are labeled by [n], that the tree is drawn
without edge crossings, and the leaves are labeled in increasing order from left to right. These
assumptions will allow us to ignore the sign vector τ in the proof. The sign vector results from
straightening the tree and permuting the columns in the Steifel coordinates. This results in sign
changes in the Plücker coordinates.
In Corollary 6.5, we saw that IT,O was generated by the quadratic relations
σikσjl − σilσkj
such that there is a choke point in T between {i, j} and {k, l}. This is the same as saying
that the induced subtree of T on {i, j, k, l} has the split {i, j}|{k, l}. These are precisely the
generators of the toric initial ideals of the Grassmannian G2,n identified in [16]. �
In the preceding Theorem, any weight vector ω that belongs to the relative interior of the cone
of the tropical Grassmannian corresponding to the tree T will serve as the desired partial term
order. We refer to [16] for background on the tropical Grassmannian and toric degenerations of
the Grassmannian. Since and ideal and its initial ideals have the same Hilbert function, we see
Catalan numbers emerging as degrees of Bayesian networks yet again.
Corollary 7.2. Let T be a rooted, directed, binary tree and O consist of the leaves of T . Then
deg IT,O = 1n−1
, the (n− 2)-nd Catalan number.
The fact that binary hidden tree models are toric degenerations of the Grassmannian has
potential use in phylogenetics. Namely, it suggests a family of new models, of the same di-
mension as the binary tree models, that could be used to interpolate between the various tree
models. That is, rather than choosing a weight vector in a full dimensional cone of the tropical
Grassmannian, we could choose a weight vector ω that sits inside of lower dimensional cone.
The varieties of the initial ideals V (inω(I2,n)) then correspond to models that sit somewhere
“between” models corresponding of the full dimensional trees of the maximal dimensional cones
containing ω. Phylogenetic recovery algorithms could reference these in-between models to indi-
cate some uncertainty about the relationships between a given collection of species or on a given
branch of the tree. These new models have the advantage that they have the same dimension
as the tree models and so there is no need for dimension penalization in model selection.
7.2. Matrix Schubert Varieties. In this section, we will describe how certain varieties called
matrix Schubert varieties arise as special cases of the varieties of hidden variable models for
Gaussian Bayesian networks. More precisely, the variety for the Gaussian Bayesian network will
be the cone over one of these matrix Schubert varieties. To do this, we first need to recall some
equivalent definitions of matrix Schubert varieties.
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 25
Let w be a partial permutation matrix, which is an n × n 0/1 matrix with at most one 1 in
each row and column. The matrix w is in the affine space Cn×n. The Borel group B of upper
triangular matrices acts on Cn×n on the right by multiplication and on the left by multiplication
by the transpose.
Definition 7.3. The matrix Schubert variety Xw is the orbit closure of w by the action of B
on the right and left:
Xw = BTwB.
Let Iw be the vanishing ideal of Xw.
The matrix Schubert variety Xw ⊆ Cn×n, so we can identify its coordinate ring with a quotient
of C[σij | i ∈ [n], j ∈ [n′]]. Throughout this section [n′] = {1′, 2′, . . . , n′}, is a set of n symbols
that we use to distinguish from [n] = {1, 2, . . . , n}.
An equivalent definition of a matrix Schubert variety comes as follows. Let S(w) = {(i, j) | wij =
1} be the index set of the ones in w. For each (i, j) let Mij be the variety of rank one matrices:
Mij =
x ∈ Cn×n | rankx ≤ 1, xkl = 0 if k < i or l < j
(i,j)∈S(w)
where the sum denotes the pointwise Minkowski sum of the varieties. Since Mij are cones over
projective varieties, this is the same as taking the join, defined in the next section.
Example 7.4. Let w be the partial permutation matrix
1 0 00 1 0
0 0 0
Then Xw consists of all 3× 3 matrices of rank ≤ 2 and Iw =
|Σ[3],[3′]|
. More generally, if w is
a partial permutation matrix of the form
where Ed is a d×d identity matrix, then Iw is the ideal of (d+1) minors of a generic matrix. �
The particular Bayesian networks which yield the desired varieties come from taking certain
partitions of the variables. In particular, we assume that the observed variables come in two
types labeled by [n] = {1, 2, . . . , n} and [n′] = {1′, 2′, . . . , n′}. The hidden variables will be
labeled by the set S(w).
Define the graph G(w) with vertex set V = [n] ∪ [n′] ∪ S(w) and edge set consisting of edges
k → l for all k < l ∈ [n], k′ → l′ for all k′ < l′ ∈ [n′], (i, j) → k for all (i, j) ∈ S(w) and k ≥ i
and (i, j)→ k′ for all (i, j) ∈ S(w) and k′ ≥ j.
Theorem 7.5. The generators of the ideal Iw defining the matrix Schubert variety Xw are the
same as the generators of the ideal IG(w),[n]∪[n′] of the hidden variable Bayesian network for the
DAG G(w) with observed variables [n] ∪ [n′]. That is,
Iw · C[σij | i, j ∈ [n] ∪ [n′]] = IG(w),[n]∪[n′].
26 SETH SULLIVANT
Proof. The proof proceeds in a few steps. First, we give a parametrization of a cone over
the matrix Schubert variety, whose ideal is naturally seen to be Iw · C[σij | i, j ∈ [n] ∪ [n′]].
Then we describe a rational transformation φ on C[σij | i, j ∈ [n] ∪ [n′]] such that φ(Iw) =
IG(w),[n]∪[n′]. We then exploit that fact that this transformation is invertible and the elimination
ideal IG(w),[n]∪[n′] ∩ C[σij | i ∈ [n], j ∈ [n′]] is fixed to deduce the desired equality.
First of all, we give our parametrization of the ideal Iw. To do this, we need to carefully
identify all parameters involved in the representation. First of all, we split the indeterminates
in the ring C[σij | i, i ∈ [n]∪ [n′]] into three classes of indeterminates: those with i, j ∈ [n], those
with i, j ∈ [n′], and those with i ∈ [n] and j ∈ [n′]. Then we define a parametrization φw which
is determined as follows:
φw : C[τ, γ, a, λ]→ C[σij | i, j ∈ [n] ∪ [n′]
φw(σij) =
τij if i, j ∈ [n]
γij if i, j ∈ [n′]∑
(k,l)∈S(w):k≤i,l≤j a(k,l)λ(k,l),iλ(k,l),j if i ∈ [n], j ∈ [n
Let Jw = kerφw. Since the τ , γ, λ, and a parameters are all algebraically independent, we
deduce that in Jw, there will be no generators that involve combinations of the three types
of indeterminates in C[σij | i, j ∈ [n] ∪ [n′]]. Furthermore, restricting to the first two types of
indeterminates, there will not be any nontrivial relations involving these types of indeterminates.
Thus, to determine Jw, it suffices to restrict to the ideal among the indeterminates of the form
σij such that i ∈ [n] and j ∈ [n′]. However, considering the parametrization in this case, we see
that this is precisely the parametrization of the ideal Iw, given as the Minkowski sum of rank
one matrices. Thus, Jw = Iw.
Now we will define a map from φ : C[σij ] → C[σij ] which sends Jw to another ideal, closely
related to IG(w),[n]∪[n′]. To define this map, first, we use the fact that from the submatrix
Σ[n],[n] we can recover the λij and ai parameters associated to [n], when only considering the
complete subgraph associated to graph G(w)[n] (and ignoring the treks that involve the vertices
(k, l) ∈ S(w)). This follows because these parameters are identifiable by Proposition 2.5. A
similar fact holds when restricting to the subgraph G(w)[n′]. The ideal Jw we have defined thus
far can be considered as the vanishing ideal of a parametrization which gives the complete graph
parametrization for G(w)[n] and G(w)[n′] and a parameterization of the matrix Schubert variety
Xw on the σij with i ∈ [n] and j ∈ [n′]. So we can rationally recover the λ and a parameters
associated to the subgraphs G(w)[n] and G(w)[n′].
For each j < k pair in [n] or in [n′], define the partial trek polynomial
sjk(λ) =
j=l0<l1<...<lm=k
λli−1li .
We fit these into two upper triangular matrices S and S′ where Sjk = sjk if j < k with j, k ∈ [n],
Sjj = 1 and Sjk = 0 otherwise, with a similar definition for S′ with [n] replaced by [n′]. Now
we are ready to define our map. Let φ be the rational map φ : C[Σ] → C[Σ] which leaves σij
fixed if i, j ∈ [n] or i, j ∈ [n′], and maps σij with i ∈ [n] and j ∈ [n′] by sending
Σ[n],[n′] 7→ SΣ[n],[n′](S
′)T .
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 27
This is actually a rational map, because the λij that appear in the formula for sjk are expressed
as rational functions in terms of the σij by the rational parameter recovery formula of Proposition
2.5. Since this map transforms Σ[n],[n′] by multiplying on the left and right but lower and upper
triangular matrices, this leaves the ideal Jw ∩ C[σij | i ∈ [n], j ∈ [n′]] fixed. Thus Jw ⊆ φ(Jw).
On the other hand φ is invertible on Jw so Jw = φ(Jw).
If we think about the formulas for the image φ◦φw, we see that the formulas for σij with i ∈ [n]
and j ∈ [n′] in terms of parameters are the correct formulas which we would see coming from
the parametrization φG(w). On the other hand, the formulas for σij with i, j ∈ [n] or i, j ∈ [n′]
are the formulas for the restricted graph G[n] and G[n′], respectively. Since every trek contained
in G[n] or G[n′] is a trek in G(w), we see that the current parametrization of Jw is only “almost
correct”, in that it is only missing terms corresponding to treks that go outside of G(w)[n] or
G(w)[n′]. Denote this map by ψw, and let φG(w) be the actual parametrizing map of the model.
Thus, we have, for each σij with i, j ∈ [n] or i, j ∈ [n′], φG(w)(σij) = ψw(σij) + rw(σij), where
rw(σij) is a polynomial remainder term that does not contain any ai with i ∈ [n] ∪ [n′], when
i, j ∈ [n] or i, j ∈ [n′], and rw(σij) = 0 otherwise. On the other hand, every term of ψw(σij) will
involve exactly one ai with i ∈ [n] ∪ [n′], when i, j ∈ [n] or i, j ∈ [n′].
Now we define a weight ordering ≺ on the ring C[a, λ] that gives deg ai = 1 if i ∈ [n]∪ [n′] and
deg ai = 0 otherwise and deg λij = 0 for all i, j. Then, the largest degree term of φG(w)(σij) with
respect to this weight ordering is ψw(σ). Since highest weight terms must all cancel with each
other, we see that f ∈ IG(w),[n]∪[n′], implies that f ∈ Jw. Thus, we deduce that IG(w),[n]∪[n′] ⊆ Jw.
On the other hand,
IG(w),[n]∪[n]′ ∩ C[σij | i ∈ [n], j ∈ [n
′]] = Jw ∩ C[σij | i ∈ [n], j ∈ [n′]]
and since the generators of Jw ∩ C[σij | i ∈ [n], j ∈ [n′]] generate Jw, we deduce that Jw ⊆
IG(w),[n]∪[n′] which completes the proof. �
The significance of Theorem 7.5 comes from the work of Knutson and Miller [11]. They gave
a complete description of antidiagonal Gröbner bases for the ideals Iw. Indeed, these ideals
are generated by certain subdeterminants of the matrix Σ[n],[n′]. These determinants can be
interpretted combinatorially in terms of the graph G(w).
Theorem 7.6. [11] The ideal Iw defining the matrix Schubert variety is generated by the con-
ditional independence statements implied by the DAG G(w). In particular,
#C + 1 minors ofΣA,B | A ⊂ [n], B ⊂ [n′], C ⊂ S(w), and C d-separates A from B
7.3. Joins and Secant Varieties. In this section, we will show how joins and secant varieties
arise as special cases of Gaussian Bayesian networks in the hidden variable case. This, in turn,
implies that techniques that have been developed for studying defining equations of joins and
secant varieties (e.g. [12, 20]) might be useful for studying the equations defining these hidden
variable models.
Given two ideals I and J in a polynomial ring K[x] = K[x1, . . . , xm], their join is the new
ideal
I ∗ J := (I(y) + J(z) + 〈xi − yi − zi | i ∈ [m]〉)
28 SETH SULLIVANT
where I(y) is the ideal obtained from I by plugging in the variables y1, . . . , ym for x1, . . . , xm.
The secant ideal is the iterated join:
I{r} = I ∗ I ∗ · · · ∗ I
with r copies of I. If I and J are homogeneous radical ideals over an algebraically closed field,
the join ideal I ∗ J is the vanishing ideal of the join variety which is defined geometrically by
the rule
V (I ∗ J) = V (I) ∗ V (J) =
a∈V (I)
b∈V (J)
< a, b >
where < a, b > denotes the line spanned by a and b and the bar denotes the Zariski closure.
Suppose further that I and J are the vanishing ideals of parametrizations; that is there are
φ and ψ such that
φ : C[x]→ C[θ] and ψ : C[x]→ C[η]
and I = kerφ and J = kerψ. Then I ∗ J is the kernel of the map
φ+ ψ : C[x]→ C[θ, η]
xi 7→ φ(xi) + ψ(xi).
Given a DAG G and a subset K ⊂ V (G), GK denotes the induced subgraph on K.
Proposition 7.7. Let G be a DAG and suppose that the vertices of G are partitioned into
V (G) = O ∪H1 ∪H2 where both H1 and H2 are hidden sets of variables. Suppose further that
there are no edges of the form o1 → o2 such that o1, o2 ∈ O or edges of the form h1 → h2 or
h2 → h1 with h1 ∈ H1 and h2 ∈ H2. Then
IG,O = IGO∪H1 ,O ∗ IGO∪H2 ,O.
The proposition says that if the hidden variables are partitioned with no edges between the
two sets and there are no edges between the observed variables the ideal is a join.
Proof. The parametrization of the hidden variable model only involves the σij such that i, j ∈ O.
First, we restrict to the case where i 6= j. Since there are no edges between observed variables
and no edges between H1 and H2, every trek from i to j involves only edges in GO∪H1 or only
edges in GO∪H2 . This means that
φG(σij) = φGO∪H1 (σij) + φGO∪H2 (σij)
and these summands are in non-overlapping sets of indeterminates. Thus, by the comments
preceding the proposition, the ideal only in the σij with i 6= j ∈ O is clearly a join. However,
the structure of this hidden variable model implies that there are no nontrivial relations that
involve the diagonal elements σii with i ∈ O. This implies that IG,O is a join. �
Example 7.8. Let Kp,m be the directed complete bipartite graph with bipartition H = [p′]
and O = [m] such that i′ → j ∈ E(Kp,m) for all i′ ∈ [p′] and j ∈ [m]. Then Kp,m satisfies the
conditions of the theorem recursively up to p copies, and we see that:
IKp,m,O = I
K1,m,O
This particular hidden variable Gaussian Bayesian network is known as the factor analysis model.
This realization of the factor analysis model as a secant variety was studied extensively in [3].
ALGEBRAIC GEOMETRY OF GAUSSIAN BAYESIAN NETWORKS 29
Example 7.9. Consider the two “doubled trees” pictured in the figure.
1 2 3 4 5 6
1 2 3 4 5 6
Since in each case, the two subgraphs GO∪H1 and GO∪H2 are isomorphic, the ideals are secant
ideals of the hidden tree models IT,O for the appropriate underlying trees. In both cases, the
ideal I{2}T,O = IG,O is a principal ideal, generated by a single cubic. In the first case, the ideal
is the determinantal ideal J{2}T = 〈|Σ123,456|〉. In the second case, the ideal is generated by an
eight term cubic
IG,O = 〈σ13σ25σ46 − σ13σ26σ45 − σ14σ25σ36 + σ14σ26σ35
+σ15σ23σ46 − σ15σ24σ36 − σ16σ23σ45 + σ16σ24σ35〉 .
In both of the cubic cases in the previous example, the ideals under questions were secant
ideals of toric ideals that were initial ideals of the Grassmann-Plücker ideal, as we saw in Theorem
7.1. Note also that the secant ideals I{2}T,O are, in fact, the initial terms of the 6× 6 Pfaffian with
respect to appropriate weight vectors. We conjecture that this pattern holds in general.
Conjecture 7.10. Let T be a binary tree with n leaves and O the set of leaves of T . Let
I2,n be the Grassmann-Pluücker ideal, let ω be a weight vector and τ a sign vector so that
IT,O = τ · inω(I2,n) as in Theorem 7.1. Then for each r
T,O = τ · inω(I
2,n ).
References
[1] P. Bickel and K. Doksum. Mathematical Statistics. Vol 1. Prentice-Hall, London, 2001.
[2] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics.
Springer, New York, 1997.
[3] M. Drton, B. Sturmfels, and S. Sullivant. Algebraic factor analysis: tetrads, pentads, and beyond. To appear
in Probability Theory and Related Fields, 2006.
[4] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press,
Cambridge, 1999.
[5] J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Inc. Sunderland, MA, 2004.
[6] L. Garcia. Polynomial constraints of Bayesian networks with hidden variables. Preprint, 2006.
[7] L. Garcia, M. Stillman, and B. Sturmfels. Algebraic geometry of Bayesian networks. Journal of Symbolic
Computation 39 (2005) 331-355.
[8] I. Gessel and G. Viennot. Binomial determinants, paths, and hook length formulae. Adv. in Math. 58 (1985),
no. 3, 300–321.
30 SETH SULLIVANT
[9] D. Grayson and M. Stillman. Macaulay 2, a software system for research in algebraic geometry. Available at
http://www.math.uiuc.edu/Macaulay2/
[10] M. Hochster. Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes,
Annals of Mathematics 96 (1972) 318–337.
[11] A. Knutson and E. Miller. Gröbner geometry of Schubert polynomials. Ann. of Math. (2) 161 (2005), no. 3,
1245–1318.
[12] J. M. Landsberg, L. Manivel. On the ideals of secant varieties of Segre varieties. Found. Comput. Math. 4
(2004), no. 4, 397–422.
[13] S. Lauritzen. Graphical Models. Oxford Statistical Science Series 17 Clarendon Press, Oxford, 1996.
[14] R. Read and R. Wilson. An Atlas of Graphs. Oxford Scientific Publications. (1998)
[15] C. Semple and M. Steel. Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications 24 Oxford
University Press, Oxford, 2003.
[16] D. Speyer and B. Sturmfels. The tropical Grassmannian. Advances in Geometry 4 (2004) 389-411.
[17] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. The MIT Press, Cambridge,
MA, 2000.
[18] R. Stanley. Enumerative Combinatorics Vol. 2 Cambridge Studies in Advanced Mathematics 62, Cambridge
University Press, 1999.
[19] B. Sturmfels. Gröbner Bases and Convex Polytopes. University Lecture Series 8, American Mathematical
Society, Providence, RI, 1996.
[20] B. Sturmfels and S. Sullivant. Combinatorial secant varieties. Quarterly Journal of Pure and Applied Math-
ematics 2 (2006) 285-309.
Department of Mathematics and Society of Fellows, Harvard University, Cambridge, MA 02138
http://www.math.uiuc.edu/Macaulay2/
	1. Introduction
	Acknowledgments
	2. Parametrization and Conditional Independence
	3. Computational Study
	4. Tetrad Representation Theorem
	5. Fully Observed Trees
	6. Hidden Trees
	7. Connections to Algebraic Geometry
	7.1. Toric Initial Ideals of the Grassmannian
	7.2. Matrix Schubert Varieties
	7.3. Joins and Secant Varieties
	References
