\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
