### Ideals generated by 2-minors with applications to algebraic statistic

J ¨urgen Herzog Universit ¨at Duisburg-Essen

Ellwangen, March 2011

### Outline

Contingency tables

Random Walks

Primary Decompositions

Ideals generated by 2-minors

### Outline

Contingency tables

Random Walks

Primary Decompositions

Ideals generated by 2-minors

### Outline

Contingency tables

Random Walks

Primary Decompositions

Ideals generated by 2-minors

### Outline

Contingency tables

Random Walks

Primary Decompositions

Ideals generated by 2-minors

### Contingency tables

In statistics, acontingency tableis used to record and analyze the relation between two or more categorical variables. It displays the (multivariate) frequency distribution of the variables in a matrix format.

### Contingency tables

In statistics, acontingency tableis used to record and analyze the relation between two or more categorical variables. It displays the (multivariate) frequency distribution of the variables in a matrix format.

The following displays an example of a contingency table

Blue Green Brown

Blonde Red Black Totals

Totals EYE COLORS

HAIR COLORS

16 12 5

14 18 8

3 4 20

33 34 33

33 40 27

100

Blue Green Brown

Blonde Red Black Totals

Totals EYE COLORS

HAIR COLORS

16 12 5

14 18 8

3 4 20

33 34 33

33 40 27

100

The sequence of row and column sums is called themarginal distributionof the contingency table.

We have to decide for somestatistical model(which is our null hypothesis) and to test to what extend the given table fits this model.

We have to decide for somestatistical model(which is our null hypothesis) and to test to what extend the given table fits this model.

In general a (2-dimensional) contingency table is an

*m*×*n-matrix whose entries are called the*cell frequencies.

We have to decide for somestatistical model(which is our null hypothesis) and to test to what extend the given table fits this model.

In general a (2-dimensional) contingency table is an

*m*×*n-matrix whose entries are called the*cell frequencies.

*Say our contingency table has cell frequencies a** _{ij}*, while our

*statistical model gives the expected cell frequencies e*

*. Then theχ*

_{ij}^{2}-statistic of the contingency table is computed by the formula

χ^{2}=X

*i,j*

(a*ij* −*e** _{ij}*)

^{2}

*e*

*.*

_{ij}Under the hypothesis ofindependenceone has
*e** _{ij}* =

*r*

_{i}*c*

*/N*

_{j}where*r** _{i}* =P

*j**a*_{ij}*is the ith row sum,c** _{j}* =P

*i**a*_{ij}*is the jth*
column sum and*N* =P

*i**r** _{i}* =P

*j**c** _{j}* is the total number of
samples.

Under the hypothesis ofindependenceone has
*e** _{ij}* =

*r*

_{i}*c*

*/N*

_{j}where*r** _{i}* =P

*j**a*_{ij}*is the ith row sum,c** _{j}* =P

*i**a*_{ij}*is the jth*
column sum and*N* =P

*i**r** _{i}* =P

*j**c** _{j}* is the total number of
samples.

In our example we obtainχ^{2}=29.001.

Under the hypothesis ofindependenceone has
*e** _{ij}* =

*r*

_{i}*c*

*/N*

_{j}where*r** _{i}* =P

*j**a*_{ij}*is the ith row sum,c** _{j}* =P

*i**a*_{ij}*is the jth*
column sum and*N* =P

*i**r** _{i}* =P

*j**c** _{j}* is the total number of
samples.

In our example we obtainχ^{2}=29.001.

Does the value ofχ^{2}fit well our hypothesis of independence???

One strategy to answering this question is tocompare the
χ^{2}-statisticof the given table with a large number ofrandomly
selected contingency tableswith the same marginal distribution.

One strategy to answering this question is tocompare the
χ^{2}-statisticof the given table with a large number ofrandomly
selected contingency tableswith the same marginal distribution.

If only a rather low percentage (which is commonly fixed to be
5 %) of those randomly selected contingency tables has a
greaterχ^{2}than that of the given table, the null hypothesis is
rejected.

One strategy to answering this question is tocompare the
χ^{2}-statisticof the given table with a large number ofrandomly
selected contingency tableswith the same marginal distribution.

If only a rather low percentage (which is commonly fixed to be
5 %) of those randomly selected contingency tables has a
greaterχ^{2}than that of the given table, the null hypothesis is
rejected.

But how to produce random contingency tables with the same marginal distribution?

### Random Walks

*We start at the given table A and take*random movesthat do
not change the marginal distribution. Each single move is given
as follows: choose a pair of rows and a pair of columns at
*random, and modify A at the four entries where the selected*
rows and columns intersect by adding or subtracting 1
according to the following pattern of signs

+ −

− + or − +

+ −

with probability 1/2 each. In this way we obtain a random walk on the set of contingency tables with fixed marginal distribution.

If the move produces negative entries, discard it and continue by choosing a new pair of rows and columns.

If the move produces negative entries, discard it and continue by choosing a new pair of rows and columns.

*If A is a contingency table of shape m*×*n, then the number of*
possible moves is ^{m}_{2} _{n}

2

, which is a rather big number. In practice one obtains a pretty good selection of randomly

selected contingency tables with the same marginal distribution
*as that of A which allows to test the significance of A, if we*
restrict the setS of possible moves.

If the move produces negative entries, discard it and continue by choosing a new pair of rows and columns.

*If A is a contingency table of shape m*×*n, then the number of*
possible moves is ^{m}_{2} _{n}

2

, which is a rather big number. In practice one obtains a pretty good selection of randomly

selected contingency tables with the same marginal distribution
*as that of A which allows to test the significance of A, if we*
restrict the setS of possible moves.

*We say that two contingency tables A and B are*connectedvia
S*, if B can be obtained from A by a finite number of moves from*
S.

*If A is a contingency table of shape m*×*n, then the number of*
possible moves is ^{m}_{2} _{n}

2

, which is a rather big number. In practice one obtains a pretty good selection of randomly

selected contingency tables with the same marginal distribution
*as that of A which allows to test the significance of A, if we*
restrict the setS of possible moves.

*We say that two contingency tables A and B are*connectedvia
S*, if B can be obtained from A by a finite number of moves from*
S.

The question arises how to decide whether two contingency tables are connected.

*By composing the rows of a contingency table of shape m*×*n*
to a vector, we may view it as an element in the setN* ^{m×n}*of
nonnegative integer vectors.

*By composing the rows of a contingency table of shape m*×*n*
to a vector, we may view it as an element in the setN* ^{m×n}*of
nonnegative integer vectors.

Then the connectedness problem can be rephrased and
generalized as follows: letBbe a subset of vectors ofZ* ^{n}*. One
defines the graph

*G*

_{B}whose vertex set is the setN

*of*

^{n}nonnegative integer vectors.

*By composing the rows of a contingency table of shape m*×*n*
to a vector, we may view it as an element in the setN* ^{m×n}*of
nonnegative integer vectors.

Then the connectedness problem can be rephrased and
generalized as follows: letBbe a subset of vectors ofZ* ^{n}*. One
defines the graph

*G*

_{B}whose vertex set is the setN

*of*

^{n}nonnegative integer vectors.

**Two vectors a and c in**N* ^{n}*are

*connected by an edge of G*

_{B}if

**a**−

**c**∈ ±B.

*By composing the rows of a contingency table of shape m*×*n*
to a vector, we may view it as an element in the setN* ^{m×n}*of
nonnegative integer vectors.

Then the connectedness problem can be rephrased and
generalized as follows: letBbe a subset of vectors ofZ* ^{n}*. One
defines the graph

*G*

_{B}whose vertex set is the setN

*of*

^{n}nonnegative integer vectors.

**Two vectors a and c in**N* ^{n}*are

*connected by an edge of G*

_{B}if

**a**−

**c**∈ ±B.

We say that**a**and**c**areconnected viaB, if they belong to the
same connected component of*G*_{B}.

*We fix a field K and define the binomial ideal*

*I*_{B} = (x^{b}^{+} −**x**^{b}^{−}: **b**∈ B)⊂*K*[x_{1}, . . . ,*x**n*],
**where for a vector a**∈Z^{n}**, the vectors a**^{+},**a**^{−}∈N* ^{n}*are the

**unique vectors with a**=

**a**

^{+}−

**a**

^{−}and supp(a

^{+})∩supp(a

^{−}) =∅.

*We fix a field K and define the binomial ideal*

*I*_{B} = (x^{b}^{+} −**x**^{b}^{−}: **b**∈ B)⊂*K*[x_{1}, . . . ,*x**n*],
**where for a vector a**∈Z^{n}**, the vectors a**^{+},**a**^{−}∈N* ^{n}*are the

**unique vectors with a**=

**a**

^{+}−

**a**

^{−}and supp(a

^{+})∩supp(a

^{−}) =∅.

**Theorem. The non-negative integer vectorsa**and

**c**are

connected viaBif and only if**x**** ^{a}**−

**x**

**∈**

^{c}*I*

_{B}.

*We fix a field K and define the binomial ideal*

*I*_{B} = (x^{b}^{+} −**x**^{b}^{−}: **b**∈ B)⊂*K*[x_{1}, . . . ,*x**n*],
**where for a vector a**∈Z^{n}**, the vectors a**^{+},**a**^{−}∈N* ^{n}*are the

**unique vectors with a**=

**a**

^{+}−

**a**

^{−}and supp(a

^{+})∩supp(a

^{−}) =∅.

**Theorem. The non-negative integer vectorsa**and

**c**are

connected viaBif and only if**x**** ^{a}**−

**x**

**∈**

^{c}*I*

_{B}.

Howto decide whether a binomial belongs to a binomial ideal?

### Primary Decompositions

*Given a binomial ideal I and a binomial f , can we find feasible*
*conditions in terms of the exponents appearing in f that*
*guarantee that f* ∈*I?*

### Primary Decompositions

*Given a binomial ideal I and a binomial f , can we find feasible*
*conditions in terms of the exponents appearing in f that*
*guarantee that f* ∈*I?*

The following strategy may be successful in some cases. Write
*the given binomial ideal I as an intersection* *I*=T*r*

*k=1**J** _{k}* of
ideals

*J*

*. Then*

_{k}*f*∈

*I*if and only if

*f*∈

*J*

_{k}*for all k .*

### Primary Decompositions

*Given a binomial ideal I and a binomial f , can we find feasible*
*conditions in terms of the exponents appearing in f that*
*guarantee that f* ∈*I?*

The following strategy may be successful in some cases. Write
*the given binomial ideal I as an intersection* *I*=T*r*

*k=1**J** _{k}* of
ideals

*J*

*. Then*

_{k}*f*∈

*I*if and only if

*f*∈

*J*

_{k}*for all k .*

*This strategy is useful only if each of the ideals J** _{k}* has a simple
structure, so that it is possible to describe the conditions that

*guarantee that f belongs to J*

*.*

_{k}### Primary Decompositions

*Given a binomial ideal I and a binomial f , can we find feasible*
*conditions in terms of the exponents appearing in f that*
*guarantee that f* ∈*I?*

The following strategy may be successful in some cases. Write
*the given binomial ideal I as an intersection* *I*=T*r*

*k=1**J** _{k}* of
ideals

*J*

*. Then*

_{k}*f*∈

*I*if and only if

*f*∈

*J*

_{k}*for all k .*

*This strategy is useful only if each of the ideals J** _{k}* has a simple
structure, so that it is possible to describe the conditions that

*guarantee that f belongs to J*

*.*

_{k}A natural choice for such an intersection is a primary
*decomposition of I. In the case that I is a radical ideal the*
*natural choice for the ideals J*_{k}*are the minimal prime ideals of I.*

*We apply the above strategy to contingency tables A of shape*
2×*n.*

*We apply the above strategy to contingency tables A of shape*
2×*n.*

A single move is given by choosing a pair of columns, and
*modify A at the four entries where the selected columns*
intersect the two rows by adding or subtracting 1 according to
the following pattern of signs

+ −

− + or − +

+ −

*We apply the above strategy to contingency tables A of shape*
2×*n.*

A single move is given by choosing a pair of columns, and
*modify A at the four entries where the selected columns*
intersect the two rows by adding or subtracting 1 according to
the following pattern of signs

+ −

− + or − +

+ −

Given a set of moves. We want to decide when two
*contingency tables A and B are connected.*

In algebraic terms: given a matrix

*x*_{1} *x*_{2} . . . *x**n*

*y*_{1} *y*_{2} . . . *y*_{n}

.

*We let S be the set of 2-minors corresponding to the given set*
of moves.

In algebraic terms: given a matrix

*x*_{1} *x*_{2} . . . *x**n*

*y*_{1} *y*_{2} . . . *y*_{n}

.

*We let S be the set of 2-minors corresponding to the given set*
of moves.

*This set of minors is indexed by the edges of a graph G:*

*x*_{i}*y** _{j}* −

*x*

_{j}*y*

*, {*

_{i}*i,j*} ∈

*E(G).*

In algebraic terms: given a matrix

*x*_{1} *x*_{2} . . . *x**n*

*y*_{1} *y*_{2} . . . *y*_{n}

.

*We let S be the set of 2-minors corresponding to the given set*
of moves.

*This set of minors is indexed by the edges of a graph G:*

*x*_{i}*y** _{j}* −

*x*

_{j}*y*

*, {*

_{i}*i,j*} ∈

*E(G).*

We call

*J** _{G}* = (x

_{i}*y*

*−*

_{j}*x*

_{j}*y*

*: {*

_{i}*i,j*} ∈

*E*(G)) theedge ideal

*of G.*

* Theorem Let G be a finite graph on the vertex set*[n]

*and J*

*its*

_{G}*edge ideal. Then J*

*has a squarefree initial ideal with respect to the lexicographic order induced by*

_{G}*x*_{1}>*x*_{2}>· · ·>*x**n* >*y*_{1}>*y*_{2}>· · ·>*y**n*.

* Theorem Let G be a finite graph on the vertex set*[n]

*and J*

*its*

_{G}*edge ideal. Then J*

*has a squarefree initial ideal with respect to the lexicographic order induced by*

_{G}*x*_{1}>*x*_{2}>· · ·>*x**n* >*y*_{1}>*y*_{2}>· · ·>*y**n*.

**Corollary J**_{G}*is a radical ideal. In particular, J** _{G}* is the
intersection of its minimal prime ideals.

* Theorem Let G be a finite graph on the vertex set*[n]

*and J*

*its*

_{G}*edge ideal. Then J*

*has a squarefree initial ideal with respect to the lexicographic order induced by*

_{G}*x*_{1}>*x*_{2}>· · ·>*x**n* >*y*_{1}>*y*_{2}>· · ·>*y**n*.

**Corollary J**_{G}*is a radical ideal. In particular, J** _{G}* is the
intersection of its minimal prime ideals.

*Which are the minimal prime ideals of J** _{G}*??

*Let G be a simple graph on*[n]. For each subset*S*⊂[n]we
define a prime ideal*P** _{S}*(G)⊂

*K*[x1,· · ·,

*x*

*,*

_{n}*y*

_{1},· · · ,

*y*

*].*

_{n}*Let G be a simple graph on*[n]. For each subset*S*⊂[n]we
define a prime ideal*P** _{S}*(G)⊂

*K*[x1,· · ·,

*x*

*,*

_{n}*y*

_{1},· · · ,

*y*

*].*

_{n}*Let T* = [n]\*S, and let G*_{1}, . . . ,*G** _{c(S)}*be the connected

*component of G*

_{T}*. Here G*

_{T}*is the induced subgraph of G*whose edges are exactly those edges{

*i*,

*j*}

*of G for which*

*i*,

*j*∈

*T . For each G*

*we denote by*

_{i}*G*˜

*the complete graph on*

_{i}*the vertex set V*(G

*). We set*

_{i}*P** _{S}*(G) = ([

*i∈S*

{*x** _{i}*,

*y*

*},*

_{i}*J*

_{G}_{˜}

1, . . . ,*J*_{G}_{˜}

*c(S)*).

*P** _{S}*(G)

*is a prime ideal containing J*

*.*

_{G}*Let G be a simple graph on*[n]. For each subset*S*⊂[n]we
define a prime ideal*P** _{S}*(G)⊂

*K*[x1,· · ·,

*x*

*,*

_{n}*y*

_{1},· · · ,

*y*

*].*

_{n}*Let T* = [n]\*S, and let G*_{1}, . . . ,*G** _{c(S)}*be the connected

*component of G*

_{T}*. Here G*

_{T}*is the induced subgraph of G*whose edges are exactly those edges{

*i*,

*j*}

*of G for which*

*i*,

*j*∈

*T . For each G*

*we denote by*

_{i}*G*˜

*the complete graph on*

_{i}*the vertex set V*(G

*). We set*

_{i}*P** _{S}*(G) = ([

*i∈S*

{*x** _{i}*,

*y*

*},*

_{i}*J*

_{G}_{˜}

1, . . . ,*J*_{G}_{˜}

*c(S)*).

*P** _{S}*(G)

*is a prime ideal containing J*

*.*

_{G}**Theorem**

*J*

*=T*

_{G}*S⊂[n]**P** _{S}*(G)

* Theorem Let G be a connected simple graph on the vertex set*
[n], and S⊂[n]. Then P

*(G)*

_{S}*is a minimal prime ideal of J*

*if*

_{G}*and only if S*=∅

*, or S*6=∅

*and each i*∈

*S is a*cut pointof

*G*([n]\S)∪{i}, i.e., one has

*c(S*\ {

*i*})<

*c(S).*

* Theorem Let G be a connected simple graph on the vertex set*
[n], and S⊂[n]. Then P

*(G)*

_{S}*is a minimal prime ideal of J*

*if*

_{G}*and only if S*=∅

*, or S*6=∅

*and each i*∈

*S is a*cut pointof

*G*([n]\S)∪{i}, i.e., one has

*c(S*\ {

*i*})<

*c(S).*

*Consider for example the path graph G of length 4.*

• • • •

1 2 3 4

*Then the only subsets S*⊂[4], besides the empty set, for which
*each i* ∈*S is a cut-point of the graph G*([4]\S)∪{i}, are the sets
*S* ={2}*and S*={3}. Thus

*J** _{G}* =

*I*

_{2}(X)∩(x2,

*x*

_{2},

*x*

_{3}

*y*

_{4}−

*x*

_{4}

*y*

_{3})∩(x3,

*y*

_{3},

*x*

_{1}

*y*

_{2}−

*x*

_{2}

*y*

_{1}), where

*X* =

*x*_{1} *x*_{2} *x*_{3} *x*_{4}
*y*_{1} *y*_{2} *y*_{3} *y*_{4}

.

Let*A*= (a*ij*)and*B*= (b*ij*)be two contingency tables of shape
2×4. LetS be the set of adjacent moves

±

1 −1 0 0

−1 1 0 0

,

±

0 1 −1 0 0 −1 1 0

,

±

0 0 1 −1 0 0 −1 1

.

Let*A*= (a*ij*)and*B*= (b*ij*)be two contingency tables of shape
2×4. LetS be the set of adjacent moves

±

1 −1 0 0

−1 1 0 0

,

±

0 1 −1 0 0 −1 1 0

,

±

0 0 1 −1 0 0 −1 1

.

*Then A and B are connected via*S if and only if the following
conditions are satisfied:

(a) P4

*j=1**a** _{ij}* =P4

*j=1**b*_{ij}*for i* =1,2;

(b) *a** _{1j}* +

*a*

*=*

_{2j}*b*

*+*

_{1j}*b*

_{2j}*for j*=1,2,3,4;

(c) *either a*_{12}+*a*_{22} ≥*1 and b*_{12}+*b*_{22}≥*1, or a** _{ij}* =

*b*

*for*

_{ij}*i,j*≤

*2, and a*

_{13}+

*a*

_{14}=

*b*

_{13}+

*b*

_{14}and

*a*_{23}+*a*_{24}=*b*_{23}+*b*_{24};

(d) *either a*_{13}+*a*_{23} ≥*1 and b*_{13}+*b*_{23}≥*1, or a** _{ij}* =

*b*

*for*

_{ij}*i,j*≥

*3, and a*

_{11}+

*a*

_{12}=

*b*

_{11}+

*b*

_{12}and

*a*_{21}+*a*_{22}=*b*_{21}+*b*_{22}.

### Ideals generated by 2-minors

We have seen thatanyideal generated by a set of 2-minors of
an 2×*n-matrix of indeterminates is a radical ideal.*

### Ideals generated by 2-minors

We have seen thatanyideal generated by a set of 2-minors of
an 2×*n-matrix of indeterminates is a radical ideal.*

What about ideal generated by a set of 2-minors of an
*m*×*n-matrix of indeterminates?*

### Ideals generated by 2-minors

We have seen thatanyideal generated by a set of 2-minors of
an 2×*n-matrix of indeterminates is a radical ideal.*

What about ideal generated by a set of 2-minors of an
*m*×*n-matrix of indeterminates?*

*Consider the ideal I generated by the 2-minors*
*ae*−*bd*,*bf* −*ce,dh*−*eg*,*ei*−*fh*
of the matrix

*a* *b* *c*
*d* *e* *f*
*g* *h* *i*

.

### Ideals generated by 2-minors

*n-matrix of indeterminates is a radical ideal.*

What about ideal generated by a set of 2-minors of an
*m*×*n-matrix of indeterminates?*

*Consider the ideal I generated by the 2-minors*
*ae*−*bd*,*bf* −*ce,dh*−*eg*,*ei*−*fh*
of the matrix

*a* *b* *c*
*d* *e* *f*
*g* *h* *i*

.

Then*cdh*−*aei*∈√

*I*\*I. So I is*nota radical ideal.

Let*X* = (x* _{ij}*)

*i=1,...,m*

*j=1,...,n*

*be a matrix of indeterminates, and let S be*
*the polynomial ring over a field K in the variables x** _{ij}*.

Let*X* = (x* _{ij}*)

*i=1,...,m*

*j=1,...,n*

*be a matrix of indeterminates, and let S be*
*the polynomial ring over a field K in the variables x** _{ij}*.

The 2-minorδ = [a_{1},*a*_{2}|*b*_{1},*b*_{2}]is calledadjacent*if a*_{2}=*a*_{1}+1
*and b*_{2}=*b*_{1}+1.

Let*X* = (x* _{ij}*)

*i=1,...,m*

*j=1,...,n*

*be a matrix of indeterminates, and let S be*
*the polynomial ring over a field K in the variables x** _{ij}*.

The 2-minorδ = [a_{1},*a*_{2}|*b*_{1},*b*_{2}]is calledadjacent*if a*_{2}=*a*_{1}+1
*and b*_{2}=*b*_{1}+1.

LetCbe any set of adjacent 2-minors. We call such a set a
configurationof adjacent 2-minors. A configuration of adjacent
2-minors may be identified with apolyomino. We denote by*I(*C)
the ideal generated by the elements ofC.

Let*X* = (x* _{ij}*)

*i=1,...,m*

*j=1,...,n*

*be a matrix of indeterminates, and let S be*
*the polynomial ring over a field K in the variables x** _{ij}*.

The 2-minorδ = [a_{1},*a*_{2}|*b*_{1},*b*_{2}]is calledadjacent*if a*_{2}=*a*_{1}+1
*and b*_{2}=*b*_{1}+1.

LetCbe any set of adjacent 2-minors. We call such a set a
configurationof adjacent 2-minors. A configuration of adjacent
2-minors may be identified with apolyomino. We denote by*I(*C)
the ideal generated by the elements ofC.

The set of vertices ofC*, denoted V*(C), is the union of the
vertices of its adjacent 2-minors. Two distinct minors inδ, γ ∈ C
are calledconnectedif there existδ1. . . , δ*r* ∈ Csuch that
δ =δ1,γ =δ*r*, andδ* _{i}* andδ

*have a common edge.*

_{i+1}A Configuration of adjacent 2-minors

A Configuration of adjacent 2-minors

A Chess board configuration

**Theorem Let**Cbe a configuration of adjacent 2-minors. Then
the following conditions are equivalent:

(a) *I(*C)is a prime ideal.

(b) Cis a chessboard configuration withno cycle of length 4.

**Theorem Let**Cbe a configuration of adjacent 2-minors. Then
the following conditions are equivalent:

(a) *I(*C)is a prime ideal.

(b) Cis a chessboard configuration withno cycle of length 4.

Here is another case of primality of ideals of 2-minors discovered by my student Qureshi.

**Theorem Let**Cbe a configuration of adjacent 2-minors. Then
the following conditions are equivalent:

(a) *I(*C)is a prime ideal.

(b) Cis a chessboard configuration withno cycle of length 4.

Here is another case of primality of ideals of 2-minors discovered by my student Qureshi.

LetCbe a configuration of 2-minors. A minor[a1,*a*_{2}|*b*_{1},*b*_{2}]is
called aninner minorofC, if all adjacent 2-minors

[a,*a*+1|*b,b*+1]*with a*_{1}≤*a*<*a*_{2}*and b*_{1}≤*b*<*b*_{2}belong toC.

An inner minor

An inner minor

Not an inner minor

A configurationCis calledrectangular, if each minor

[a1,*a*_{2}|*b*_{1},*b*_{2}]with(a1,*b*_{1}),(a1,*b*_{2}),(a2,*b*_{1}),(a2,*b*_{2})∈*V*(C)is
an inner minor ofC. In the language of polyminoes, a

rectangular configuration is aconvex polyomino.

A configurationCis calledrectangular, if each minor

[a1,*a*_{2}|*b*_{1},*b*_{2}]with(a1,*b*_{1}),(a1,*b*_{2}),(a2,*b*_{1}),(a2,*b*_{2})∈*V*(C)is
an inner minor ofC. In the language of polyminoes, a

rectangular configuration is aconvex polyomino.

A rectangular configuration

A configurationCis calledrectangular, if each minor

[a1,*a*_{2}|*b*_{1},*b*_{2}]with(a1,*b*_{1}),(a1,*b*_{2}),(a2,*b*_{1}),(a2,*b*_{2})∈*V*(C)is
an inner minor ofC. In the language of polyminoes, a

rectangular configuration is aconvex polyomino.

A rectangular configuration

Not rectangular

**Theorem (Quereshi) Let**Cbe a rectangular configuration.

Then the ideal generated by all inner 2-minors is a prime ideal.

P. Diaconis, D. Eisenbud, B. Sturmfels. Lattice walks and primary decomposition, Mathematical Essays in Honor of Gian-Carlo Rota, Birkh ¨auser, Boston, 1998, pp. 173–193.

J Herzog, V. Ene. An Introduction to Gr ¨obner bases, book in preparation.

J. Herzog, T. Hibi, F. Hreinsdottir, T. Kahle, J. Rauh.

Binomial edge ideals and conditional independence
**statements, Adv. Appl. Math. 45 (2010), 317–333.**

J. Herzog, T. Hibi. Ideals generated by adjacent 2-minors, preprint 2011.

S. Hos¸ten, J. Shapiro. Primary decomposition of lattice
**basis ideals. J.Symbolic Computation, 29 (2000), 625–639.**

S. Hos¸ten, S. Sullivant, Ideals of adjacent minors, J.

**Algebra 277 (2004), 615–642.**

M. Ohtani, Graphs and Ideals generated by some 2-minors, Comm. Algebra, in press.

A. Qureshi, Ideals generated be 2-minors, preprint 2010.