\magnification=\magstep1
\baselineskip=15pt
\leftline{\sevenrm July 24, 2001}
\vskip .2cm
\centerline{\bf A Gr\"obner basis for graphical models}
\vskip .3cm
\noindent
We shall describe a certain ideal generated by binomials
(= monomial differences) in a
polynomial ring $k[x_{i_1 i_2 \ldots i_n}]$, where
$k$ is any field and the indices of the variables satisfy
$$ 0 \leq i_1 \leq m_1, \, 0 \leq i_2 \leq m_2, \, \ldots \,
,\, 0 \leq i_n \leq m_n .$$
Hence the number of variables in $k[x_{i_1 i_2 \ldots i_n}]$
is $\,(m_1+1) (m_2+1) \cdots (m_n+1) $. All our examples concern the
{\it binary case} when $\, m_1 = m_2 = \cdots = m_n = 1$.
We order the variables in $k[x_{i_1 i_2 \ldots i_n}]$ in the
natural lexicographic order; for instance,
in the binary case for $n=3$:
$$
x_{000} >
x_{001} >
x_{010} >
x_{011} >
x_{100} >
x_{101} >
x_{110} >
x_{111} . \eqno (1) $$
We next introduce a second polynomial ring $k[y_{rst}]$.
The indices of its variables satisfy
$$ 1 \leq r \leq n- 1, \,\,\, 0 \leq s \leq m_r, \,\,
0 \leq t \leq m_{r+1}. $$
Hence the number of variables in $k[y_{rst}]$ is equal to
$$\,
(m_1+1) (m_2+1) \, + \,
(m_2+1) (m_3+1) \, + \, \cdots \, + \,
(m_{n-1}+1) (m_n+1) .$$
We define the following homomorphism from the first
polynomial ring to the second:
$$ \phi \, : \, k[x_{i_1 i_2 \ldots i_n}]\, \rightarrow \, k[y_{rst}] \, ,
\,\,\,
x_{i_1 i_2 \ldots i_n} \,\mapsto\,
y_{1 i_1 i_2}
y_{2 i_2 i_3}
y_{3 i_3 i_4}
\cdots
y_{n-1, i_{n-1} i_n}. $$
Our object of interest is the kernel of $\phi$.
This is an ideal in $k[x_{i_1 i_2 \ldots i_n}]$,
denoted $I = {\rm ker}(\phi)$.
\proclaim Example. \rm
In the binary case for $n=3$, our ideal $I$ is generated by
$$ \underline{x_{001} x_{100}} - x_{000} x_{101} \quad {\rm and} \quad
\underline{x_{011} x_{110}} - x_{010} x_{111} .
\eqno (2) $$
These two binomials form a Gr\"obner basis for $I$, with the
underlined leading terms.
\proclaim Theorem 1. The reduced Gr\"obner basis of $I$
with respect to the reverse lexicographic term order
consists of quadratic binomials
$\, x_{\dots} x_{\dots} - x_{\dots} x_{\dots} \,$
with both terms square-free.
The following strategy will be used to prove this theorem.
We shall exhibit a
suitable set ${\cal G}$ of quadratic binomials in
the ideal $I$. We shall consider the monomial ideal
$M$ generated by the leading terms in ${\cal G}$,
noting that none of the trailing terms from ${\cal G}$ lie in $M$.
Clearly, $M$ is a subideal of the initial ideal $in(I)$.
What we must prove is that $M$ is actually equal to $in(I)$.
This will be accomplished by showing that every monomial of
$k[y_{rst}]$ which lies in the image of $\phi$
has at most one preimage under $\phi$ that is not in $M$.
Before we begin, however, let us introduce a new notation
for monomials in $k[x_{i_1 i_2 \ldots i_n}]$. A monomial
of degree $d$ will be written as a matrix $T = (T_{ij})$ of size
$d \times n$, where the rows are sorted
lexicographically and the entries of the $j$-th column
are integers between $0$ and $m_j$. Borrowing terminology from
classical invariant theory, we call $T$ a {\it tableau}.
Such a tableau $T$ represents the monomial
$\,
x_{T_{11}T_{12}\dots T_{1n}}
x_{T_{21}T_{22}\dots T_{2n}} \cdots
x_{T_{d1}T_{d2}\dots T_{dn}}\,$ in $k[x_{i_1 i_2 \ldots i_n}]$.
Conversely, every monomial can be written uniquely as a tableau.
For example, for $n=3$:
$$
{\rm monomial} \,\, \,
x_{000} x_{001} x_{010} x_{011} x_{110}^2 \,\quad
\longleftrightarrow \quad
{\rm tableau} \,\,\,
\left[ \matrix{
0 & 0 & 0 \cr
0 & 0 & 1 \cr
0 & 1 & 0 \cr
0 & 1 & 1 \cr
1 & 1 & 0 \cr
1 & 1 & 0 \cr}
\right]. \eqno (3)
$$
%%% Changed 07/26
Note that in the definition of tableau we require
the rows are always sorted lexicographically. In particular,
the first column of a tableau must always be weakly increasing.
According to this convention,
$\, \left[ \matrix{
0 & 1 & 0 \cr
0 & 0 & 1 \cr} \right] \,$
is not a tableau but
$\, \left[ \matrix{
0 & 0 & 1 \cr
0 & 1 & 0 \cr} \right] \,$ is
a tableau.
We say that a tableau $T$ has a {\it violation}
in rows $i,j$ and column $k$ if the following holds:
$$ T_{i,k} \, = T_{jk} \quad
{\rm and } \quad
T_{i,{k+1}} \, > T_{j,{k+1}}. $$
For instance, the tableau in (3) has a violation
in rows $4,6$ and column $2$. A tableau
$T$ is said to be {\it standard} if it has no violation at all.
The following tableau is standard:
$$
\hbox{ standard tableau} \,\,
\left[ \matrix{
0 & 0 & 0 \cr
0 & 0 & 1 \cr
0 & 1 & 0 \cr
0 & 1 & 0 \cr
1 & 1 & 0 \cr
1 & 1 & 1 \cr}
\right]
\,\,\, \longrightarrow \,\,\,
\hbox{image under} \, \phi \, : \,\,
y_{100}^2
y_{101}^2
y_{111}^2
y_{200}
y_{201}
y_{210}^3
y_{211}.
\eqno (4)
$$
Note that the tableaux in (3) and (4) have the same image under $\phi$.
In other words, the tableau in (4) is congruent to
the tableau in (3) modulo our ideal $I$.
Consider a tableau $T$ which is not standard with a violation
in rows $i,j$ and column $k$. Let $l$ be the smallest index
such that $l > k$ and $\, T_{i,{l}} \, = T_{j,{l}}$.
If there is no such index then we set $l = n+1$.
This happens in example (3) where
$i =4, j =6, k = 2$ and $l = 4$.
We define a new tableau $T'$ as follows:
$T'$ agrees with $T$ in all rows except row
$i$ and row $j$. In these two rows, $T'$ agrees with $T$
in all columns up to column $k$ and after column $l$.
Finally, the substring
$\,T_{i,k+1}, T_{i,k+2}, \ldots, T_{i,l-1}\,$
is switched with
$\,T_{j,k+1}, T_{j,k+2}, \ldots, T_{j,l-1}\,$
when passing from $T$ to $T'$. More formally,
$\,T'_{i,r} = T_{j,r} \,$ and $\,T'_{j,r} = T_{i,r} \,$
for $k < r < l$. For example, if $T$ is the tableau in
(3), with $i =4$ and $j =6$ then $T'$ is the tableau in (4).
\proclaim Lemma 2.
The binomial $\,T - T' \,$ lies in the ideal $I$.
\noindent {\sl Proof: }
What we are claiming is
that the quadratic monomials in $k[x_{i_1 i_2 \ldots i_n}]$
which are represented by rows $i$ and $j$ of the tableaux $T$ and $T'$
have the same image under the map $\phi$. This holds because
$\, T_{i,k} = T_{j,k} = T'_{i,k} = T'_{j,k} \,$ and
$\, T_{i,l} = T_{j,l} = T'_{i,l} = T'_{j,l} $. //
\proclaim Remark 3.
The binomial $\, T - T'\,$ corresponds to an
independence statement in the graphical probability model
where the underlying graph is a chain with $n$ nodes.
\proclaim Lemma 4.
The tableau $T'$ is smaller than $T$ in the
reverse lexicographic monomial order.
\noindent {\sl Proof: }
Consider the four variables represented by rows $i$ and $j$
of $T$ and $T'$ respectively. The lexicographically smallest
of these four variables is the one represented by row $j$ of $T'$.
Therefore $T > T'$ in the reverse lexicographic monomial order
on $k[x_{i_1 i_2 \ldots i_n}]$. //
Suppose that $T$ is a tableau which has {\sl two rows only}.
We can apply the transformation from $T$ to $T'$ iteratively, say,
$\, T \, \rightarrow \, T' \, \rightarrow \, T''
\, \rightarrow \, T''' \, \cdots$.
Here $i= 1$ and $j=2$ throughout while the
value of $k$ increases (and hence so does the value of $l$).
In view of Lemma 2, this process terminates with a
standard tableau which we denote $T^*$.
The standard tableau $T^*$ is reverse lexicographically
smaller than $T$, and, by Lemma 1, we have $\, T - T^* \, \in \, I $.
Let ${\cal G}$ denote the set of quadratic binomials
$T - T^*$, where $T$ runs over all non-standard tableau
with two rows. We can now make the assertion in Theorem 1
more precise.
\proclaim Theorem 1'.
The set ${\cal G}$ is the reduced Gr\"obner basis of $I$.
In the binary case, the cardinality of the
set ${\cal G}$ is given by the following table:
$$ \matrix{ n & & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots \cr
\# {\cal G} & & 2 & 20 & 132 & 728 &
3640 &
17136 &
77520 &
341088 &
1470944 &
6249152 & \cdots \cr}
$$
For $n = 3$, the set ${\cal G}$ consists of the two binomials
in (2). Note that the two underlined leading monomials are
non-standard while all other monomials of degree $2$ are
standard.
Following the strategy of proof outlined at the beginning,
we now define $M$ to be the monomial ideal generated by
the reverse lexicographically leading terms of the binomials in ${\cal G}$.
In other words, $M$ is generated by the non-standard monomials of degree $2$.
\proclaim Lemma 5.
A monomial lies in $M$
if and only if it corresponds to a non-standard tableau.
\noindent {\sl Proof: }
A tableau $T$ is non-standard if and only if has
a subtableau consisting of two rows which is non-standard.
This happens if and only if the monomial
of $k[x_{i_1 i_2 \ldots i_n}]$ represented by $T$
has a quadratic factor which lies in $M$. //
\vskip .1cm
The following lemma is crucial and will be proved later:
\proclaim Lemma 6.
Let $m$ be any monomial of $k[y_{rst}]$
which lies in the image of the ring homomorphism $\phi$. Then
there exists a unique standard tableau $T = \tau(m)$
with $\phi(T) = m$.
\vskip .2cm
\noindent {\sl Proof of Theorem 1' (and hence of Theorem 1): } \hfill \break
The set ${\cal G}$ is a subset of the ideal $I$, by Lemma 2.
Therefore the ideal $M$ generated by the leading terms of ${\cal G}$
is a subideal of the initial ideal of $I$. In symbols,
$\, M \, \subseteq \, in(I) $. What we must prove is
that the equality $\, M \, = \, in(I) \,$ holds.
Assuming this has been accomplished, then it easily follows
that the Gr\"obner basis ${\cal G}$ is a reduced Gr\"obner basis.
Indeed, ${\cal G}$ is a minimal Gr\"obner basis (i.e.,
none of its elements can be omitted), and none of the
trailing monomials of the elements in ${\cal G}$ lies in $M$.
%%% Changed 07/26
We shall derive the equation $\, M \, = \, in (I) \,$ from
Lemma 6. We proceed by contradiction. Suppose that
$M$ is properly contained in $\,in(I)$. This means there exists
a polynomial $f$ in the ideal $I$ such that its leading monomial
$in(f)$ does not lie in $M$. We may assume that the leading
coefficient of $f$ equals one, so
that $\,f \,=\, T \,+ \,$ {\sl a sum of terms which
are reverse lexicographically smaller than $T$}, where $T$ is a monomial
in $k[x_{i_1 i_2 \ldots i_n}]$. Since $f$ vanishes under the
homomorphism $\phi$ which replaces each variable in
$k[x_{i_1 i_2 \ldots i_n}]$ by a monomial in $k[y_{rst}]$,
we can conclude that there is some other non-leading monomial $\tilde T $
appearing with non-zero coefficient
in the expansion of $f$ which satisfies $\phi(T) = \phi(\tilde T)$.
We can assume that the monomial $\tilde T$ does not lie in the
initial ideal $in(I)$. Otherwise we apply the division algorithm
to $\tilde T$ with respect to the reduced Gr\"obner basis of $I$,
which consists of binomials, and we replace $\tilde T$ by
its normal form, which is a monomial. Since
$\tilde T$ does not lie in $in(I)$,
it does not lie in $M$ either. Hence $T$ and $\tilde T$ are two
distinct monomials which have the same image under $\phi$.
Neither of them lies in $M$. Hence, by Lemma 5, both
$T$ and $\tilde T$ correspond to standard tableau. This
is a contradiction to Lemma 6. //
\vskip .2cm
Before proving Lemma 6, let us describe the algorithm
which computes the promised standard tableau
$\tau (m) \in k[x_{i_1 i_2 \ldots i_n}]$
from the given monomial $\, m \,\in \,{\rm image}(\phi) \,
\subset \, k[y_{rst}]$. The algorithm is recursive.
If $n$ equals $2$, the smallest possible value,
then the map $\phi$ is injective, and we get
$\tau(m)$ from $m$ by replacing each occurrence
of $y_{1rs}$ by $x_{rs}$.
If $n > 2$ then let $Y$ denote the largest factor of $m$
whose variables all have the form $\, y_{n-1,*,*}$.
We recursively compute $\, \tilde T \, = \, \tau(m/Y)$.
Using the monomial $Y$ we now construct our tableau
$T = \tau(m)$ by adding one column to the
tableau $\tilde T$ as follows.
For each index
$\,i \in \{0,1,\ldots,m_{n-1}\}$, let $Y_i$
denote the largest factor of $Y$ whose variables all
have the form $\, y_{n-1,i,*}$. Let $\delta$ be the degree of
$Y_i$. Then we can write
$$ Y_{i} \quad = \quad
y_{n-1,i,\nu_1}
y_{n-1,i,\nu_2}
y_{n-1,i,\nu_3} \cdots
y_{n-1,i,\nu_\delta} \qquad \hbox{where} \quad
\nu_1 \leq
\nu_2 \leq
\nu_3 \leq
\cdots \leq
\nu_\delta . \eqno (5)
$$
Since $m$ was assumed
to lie in the image of $\phi$,
there are exactly $\delta$ rows of
$\tilde T$ which have the entry $i$ in the last column.
We augment these $\delta$ rows, from top to bottom, by adding
the entries $\,\nu_1, \nu_2 , \nu_3 ,\ldots, \nu_\delta$
at the end.
Hence in the resulting tableau $T$ the entries
$\,\nu_1, \nu_2 , \nu_3 ,\ldots, \nu_\delta\,$ appear
in this order in the $(n-1)$-st column, adjacent to
the occurrences of the entry $i$ in the $(n-2)$-nd column.
Note that if we had added the $\nu$'s in any other order
then the resulting tableau would still map to $m$ under $\phi$
but it would not be standard.
Here is a small example, for $n=5$ in the binary case. The monomial
$$ m \,\,\, = \, \,\,
y_{100}^2
y_{101}\,
y_{110}^3
y_{111} \,\,
y_{200}
y_{201}^4\,
y_{210}
y_{211}\,\,
y_{301}^2\,
y_{310}^3
y_{311}^2\,\,
y_{400}^2
y_{401}\,
y_{410}^2
y_{411}^2 $$
is transformed by our recursive algorithm to the standard tableau
$$
\tau(m) \, = \,
\left[ \matrix{
0 & 0 & 0 & 1 & 0 \cr
0 & 0 & 1 & 0 & 0 \cr
0 & 1 & 0 & 1 & 0 \cr
1 & 0 & 1 & 0 & 0 \cr
1 & 0 & 1 & 0 & 1 \cr
1 & 0 & 1 & 1 & 1 \cr
1 & 1 & 1 & 1 & 1 \cr
}
\right]
$$
Lemma 6 states that there is no other standard tableau
which maps to $m$ under $\phi$.
\vskip .2cm
\noindent {\sl Proof of Lemma 6: }
We can modify the above algorithm to produce
the set of all tableau $T$ with $\phi(T) = m$.
All we need to do is to delete the assumption
that the indices
$\, \nu_1 , \nu_2 ,\nu_3 ,\ldots , \nu_\delta \,$
be sorted in (5). If we branch over all possible
orderings of these indices, then our algorithm
produces the set of all tableau $T$ with $\phi(T) = m$.
The correctness of this is easily seen by inducion on $n$,
with $\phi$ being injective in the base case $n=2$.
Any tableau $T$ produced by this modified algorithm,
other than the tableau $\tau(m)$, will have to violate the condition
$\, \nu_1 \leq \nu_2 \leq \nu_3 \leq \ldots \leq \nu_\delta \,$
somewhere along the way. This translates into a violation
somewhere in the resulting tableau $T$, and therefore
$T$ is not standard. This completes the proof
of Lemma 6 and hence of Theorems 1 and 1'. //
\vskip .2cm
\proclaim Corollary 7.
The set of independence statements $\,T - T' \,$
generates the ideal $I$.
\noindent {\sl Proof: }
The elements $T- T^*$ of the Gr\"obner basis ${\cal G}$
are integer linear combinations of the binomials
$\,T - T' $ in Remark 3. Since ${\cal G}$ is a
Gr\"obner basis (Theorem 1') of $I$, it also
generates the ideal $I$. //
\bye