arXiv:1302.4461v2 [] 25 Feb 2013

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS
ALDO CONCA, EMANUELA DE NEGRI, AND ELISA GORLA

Abstract. Bernstein, Sturmfels and Zelevinsky proved in 1993 that the maximal minors of a matrix of variables form a universal Gröbner basis. We present
a very short proof of this result, along with broad generalization to matrices
with multi homogeneous structures. Our main tool is a rigidity statement for
radical Borel fixed ideals in multigraded polynomial rings.

Introduction
A set G of polynomials in a polynomial ring S over a field is said to be a
universal Gröbner basis if G is a Gröbner basis with respect to every term order
on S. Twenty years ago Bernstein, Sturmfels and Zelevinsky proved in [3, 12] that
the set of the maximal minors of an m × n matrix of variables X is a universal
Gröbner basis. Indeed, in [12] the assertion is proved for certain values of m, n and
the general problem is reduced to a combinatorial statement that it is then proved
in [3]. Kalinin gave in [10] a different proof of this result. Boocher proved in [4] that
any initial ideal of the ideal Im (X) of maximal minors of X has a linear resolution
(or, equivalently in this case, defines a Cohen-Macaulay ring).
The goal of this paper is twofold. First, we give a quick proof of the results
mentioned above. Our proof is based on a specialization argument, see Section 1.
Second, we show that similar statements hold in a more general setting, for matrices
of linear forms satisfying certain homogeneity conditions. More precisely, in Section
3 we show that the set of the maximal minors of an m × n matrix L = (Lij ) of
linear forms is a universal Gröbner basis, provided that L is column-graded. By
this we mean that the entries Lij belong to a polynomial ring with a standard Zn graded structure, and that deg Lij = ej ∈ Zn . Under the same assumption we show
that every initial ideal of Im (L) has a linear resolution. Furthermore the projective
dimension of Im (L) and of its initial ideals is n−m, unless Im (L) = 0 or a column of
L is identically 0 (notice that, under these assumptions, the codimension of Im (L)
can be smaller than n − m + 1).
If instead L is row-graded, i.e. deg Lij = ei ∈ Zm , then we prove in Section 4
that Im (L) has a universal Gröbner basis of elements of degree m and that every
initial ideal of Im (L) has a linear resolution, provided that Im (L) has the expected
codimension. Notice that in the row-graded case the maximal minors do not form
Date: February 26, 2013.
2010 Mathematics Subject Classification. Primary 13C40, 14M12 Secondary 13P10, 05B35.
Key words and phrases. Determinantal ideals, Gröbner bases, matroids.
The first two authors were partially supported by the Italian Ministry of Education, University and Research through the PRIN 2010-11 “Geometria delle Varietà Algebriche”. The
third author was partially supported by the Swiss National Science Foundation under grant no.
PP00P2 123393.
1

2

A. CONCA, E. DE NEGRI, AND E. GORLA

a universal Gröbner basis in general (since every maximal minor might have the
same initial term).
The proofs of the statements in Sections 3 and 4 are based on a rigidity property
of radical Borel fixed ideals in a multigraded setting. This property has been
observed by Cartwright and Sturmfels in [5] and by Aholt, Thomas, and Sturmfels
in [1], in special cases. In a polynomial ring with a standard Zm -grading, one
can take generic initial ideals with respect to the the product of general linear
groups preserving the grading. Such generic initial ideals are Borel fixed. The
main theorem of Section 2 asserts that if two Borel fixed ideals I, J have the same
Hilbert series and I is radical, then I = J. This is the rigidity property that we
referred to, and which has very strong consequences. For instance if I is CohenMacaulay, radical and Borel fixed, then all the multihomogeneous ideals with the
same multigraded Hilbert series are Cohen-Macaulay and radical as well.
Extensive computations performed with CoCoA [6] led to the discovery of the
results and examples presented in this paper. We thank Christian Krattenthaler
for suggesting the elegant proof of formula (4.2.9). This work was done while the
authors were at MSRI for the 2012-13 special year in commutative algebra. We
thank the organizers and the MSRI staff members for the invitation and for the
warm hospitality.
1. A simple proof of the universal GB theorem
Let K be a field, S = K[xij : 1 ≤ i ≤ m, 1 ≤ j ≤ n]. Let X = (xij ) be an m × n
matrix of indeterminates, and let Im (X) be the ideal generated by the maximal
minors of X. The goal of this section is giving a quick proof of the following result
of Bernstein, Sturmfels, Zelevinsky [3, 12], and Boocher [4]:
Theorem 1.1. The set of maximal minors of X is a universal Gröbner basis of
Im (X), i.e., a Gröbner basis of Im (X) with respect to all the term orders. Furthermore every initial ideal of Im (X) has the same Betti numbers as Im (X).
We need the following “Hilfssatz”:
Lemma 1.2. Let R be a standard graded K-algebra, let M, N, T be finitely generated graded modules R-modules, and J = (y1 , . . . , ys ) ⊂ R be a homogeneous ideal.
Suppose that:
(1)
(2)
(3)
(4)

there exists a surjective graded R-homorphism f : T → N .
M and N have the same Hilbert series,
M/JM and T /JT have the same Hilbert series,
y1 , . . . , ys is M -regular sequence.

Then f is an isomorphism and y1 , . . . , ys is a T -regular sequence.
Proof. We denote by HS(M, x) ∈ Q[|x|][x−1 ] the Hilbert series of a finitely generated graded R-module M . For i = 1, . . . , s set Ji = (y1 , . . . , yi ), Ti = T /Ji T ,
Qi
di = deg(yi ) and gi (x) = j=1 (1 − xdj ) ∈ Q[x]. Furthermore set T0 = T and for
i = 0, . . . , s − 1 denote by Ki+1 the submodule {m ∈ Ti : yi+1 m = 0} of Ti shifted
by −di+1 . Finally set K0 = Ker f . For i ≥ 0 we have an exact complex:
0 → Ki+1 → Ti (−di+1 ) → Ti → Ti+1 → 0

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS

3

where the middle map is multiplication by yi+1 . Additivity of dimensions on exact
sequences of vector spaces yields:
HS(Ti+1 , x) = (1 − xdi+1 ) HS(Ti , x) + HS(Ki+1 , x)
and hence
HS(Ti+1 , x) = gi+1 (x) HS(T, x) +

i+1
X

gi+1−j (x) HS(Kj , x).

j=1

Since
HS(T, x) = HS(N, x) + HS(K0 , x)
we may write
HS(Ti+1 , x) = gi+1 (x) HS(N, x) +

i+1
X

gi+1−j (x) HS(Kj , x)

s
X

gs−j (x) HS(Kj , x).

j=0

and in particular, for i + 1 = s,
HS(T /JT, x) = gs (x) HS(N, x) +

j=0

Since HS(N, x) = HS(M, x) and y1 , . . . , ys is an M -regular sequence we obtain
HS(T /JT, x) = HS(M/JM, x) +

s
X

gs−j (x) HS(Kj , x).

j=0

Hence, by assumption (3), we have
0=

s
X

gs−j (x) HS(Kj , x).

j=0

Since HS(Kj , x) are powers series with non-negative terms and gi (x) are polynomials with least degree term coefficient equal to 1, we conclude that HS(Kj , x) = 0
for j = 0, . . . , s. Hence Kj = 0 for j = 0, . . . , s.

Proof of Theorem 1.1. We may assume without loss of generality that K is infinite.
Let A = (aij ) be an m × n matrix with entries in K ∗ , such that all its m-minors
are non-zero. It exists because K is infinite. Consider the K-algebra map
Φ : S = K[xij : 1 ≤ i ≤ m, 1 ≤ j ≤ n] → K[y1 , . . . , yn ]
induced by Φ(xij ) = aij yj for every i, j. By construction the kernel of Φ is generated
by n(m − 1) linear forms. Let Y = Φ(X) = (aij yj ). Denote by [c1 , . . . , cm ]W the
minor with column indices c1 , . . . , cm of an m × n matrix W . By construction
Φ([c1 , . . . , cm ]X ) = [c1 , . . . , cm ]A yc1 · · · ycm .
Hence, by our assumption on A, we have that
Φ(Im (X)) = Im (Y ) = (yc1 · · · ycm : 1 ≤ c1 < · · · < cm ≤ n)
i.e., Im (Y ) is generated by all the square-free monomials in y1 , . . . , yn of total degree
m. In particular it has codimension n − m + 1. It follows that Im (Y ) is resolved
by the Eagon-Northcott complex, hence Ker Φ is generated by a regular sequence
on S/Im (X). Now let ≺ be any term order on S and let D be the ideal generated

4

A. CONCA, E. DE NEGRI, AND E. GORLA

by the leading terms of the maximal minors of X with respect to ≺. We have
D ⊆ in≺ (Im (X)) and
Φ(in≺ ([c1 , . . . , cm ]X )) = Φ(xσ1 c1 · · · xσm cm ) = aσ1 c1 · · · aσm cm yc1 · · · ycm
for some σ ∈ Sm . Hence
Φ(D) = Im (Y ).
We apply Lemma 1.2 to the following data:
M = S/Im (X),

T = S/D,

N = S/ in≺ (Im (X)) and J = Ker Φ

to conclude that D = in≺ (Im (X)), and the Betti numbers of Im (X) equals those
of D.

Can one generalize Theorem 1.1 to ideals of maximal minors of matrices of linear
forms? In Sections 3 and 4 we will give positive answers to the question by assuming
the matrix is multigraded, either by rows or by columns. In general however one
cannot expect too much, as the following remark shows.
Remark 1.3. One can consider various properties related to the existence of
Gröbner bases and various families of matrices of linear forms. For instance we
can look at the following properties for the ideal Im (L) of m-minors of an m × n
matrix L of linear forms in a polynomial ring S:
(a) Im (L) has a Gröbner basis of elements of degree m with respect to some
term order and possibly after a change of coordinates.
(b) Im (L) has a Gröbner basis of elements of degree m with respect to some
term order and in the given coordinates.
(c) Property (b) holds and the associated initial ideal has a linear resolution.
(d) Im (L) has a universal Gröbner basis of elements of degree m.
We consider the following families of matrices of linear forms:
(1) No further assumption on L is made.
(2) Im (L) has codimension n − m + 1.
(3) The entries of L are linearly independent over the base field (i.e., L arises
from a matrix of variables by a change of coordinates).
What we know (and do not know) is summarized in the following table:
(a) (b)
(1) no no
(2) yes no
(3) yes ?

(c) (d)
no no
no no
?
no

There are ideals of 2-minors of 2 × 4 matrices of linear forms that define nonKoszul ring (see [7, Remark 3.6]). Hence those ideals cannot have a single Gröbner
bases of quadrics (not even after a change of coordinates). This explains the four
“no” in the first row of the table.
Every initial ideal of the ideal of 2-minors of


x1 + x2 x3 x3
0
x1 x2
has a generator in degree 3 if the characteristic of the base field is 6= 2. The
codimension of I2 (L) is 2. This example explains the three “no” in the second

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS

5

row of the table. The “yes” in the second row follows because the generic initial
ideal with respect to the reverse lexicographic order is generated in degree m under
assumption (2).
Finally, the matrix


x1
x4
x3
x5 x1 + x6 x2
belongs to the family (3) and the initial ideal with respect to any term order satisfying x1 > x2 > · · · > x6 has a generator in degree 3. This explains the “no” in
the third row. The “yes” is there because (3) is contained in (2).
It remains open whether the ideal of maximal minors of a matrix in the family
(3) has at least a Gröbner basis of elements of degree m in the given coordinates,
and whether the associated initial ideal has a linear resolution.
2. Radical and Borel fixed ideals
The goal of the section is to prove Theorem 2.5, a rigidity result for multigraded
Hilbert series associated to radical multigraded Borel fixed ideals. Special cases of
it appeared already in [5] and [1]. We will introduce the geometric multidegree,
a generalization of the notion of multidegree of Miller and Sturmfels [11, Chap.8],
that allows us to deal with minimal components of various codimensions in the case
of Borel fixed ideals.
Given m ∈ N and (n1 , . . . , nm ) ∈ Nm let S be the polynomial ring in the set
of variables xij with 1 ≤ i ≤ m and 1 ≤ j ≤ ni over an infinite field K, with
grading induced by deg(xij ) = ei ∈ Zm . Let M be a finitely generated, Zm -graded
S-module. The multigraded Hilbert series of M is:
X
−1
HS(M, y) = HS(M, y1 , . . . , ym ) =
(dim Ma )y a ∈ Q[|y1 , . . . , ym |][y1−1 , . . . , ym
|].
a∈Zm

The K-polynomial of M is:
K(M, y) = K(M, y1 , . . . , ym ) =

m
Y

(1 − yi )ni HS(M, y).

i=1

Indeed,
−1
K(M, y) ∈ Z[y1 , . . . , ym ][y1−1 , . . . , ym
].

The group G = GLn1 (K) × · · · × GLnm (K) acts on S as the group of Zm -graded
K-algebras automorphisms. Let B = Bn1 (K)×· · ·×Bnm (K) be the Borel subgroup
of G consisting of the upper triangular matrices with arbitrary non-zero diagonal
entries. An ideal I is said to be Borel fixed if g(I) = I for every g ∈ B. Borel
fixed ideals are monomial ideals that can be characterized in a combinatorial way
by means of exchange properties as it is explained in [8, Thm. 15.23]. Indeed in [8,
Thm. 15.23] details are given in the standard graded setting but, as observed in
[2, Sect.1], the same characterization holds also in the multigraded setting. Given
a term order ≺ such that xik ≺ xij for j > k, one can associate a (multigraded)
generic initial ideal gin≺ (I) to any Zm -graded ideal of I of S. gin≺ (I) is Borel
fixed.
The prime Borel fixed ideals are easy to describe. Set
U = {(b1 , . . . , bm ) ∈ Nm : bi ≤ ni for every i = 1, . . . , m}.
The following assertion follows immediately from the definition.

6

A. CONCA, E. DE NEGRI, AND E. GORLA

Lemma 2.1. For every vector b ∈ U the ideal
Pb = (xij : i = 1, . . . , m and 1 ≤ j ≤ bi )
is prime and Borel fixed, and every prime Borel fixed ideal is of this form.
Lemma 2.2. The associated prime ideals of a Borel fixed ideal I are Borel fixed.
Proof. Let P be an associated prime to S/I. Clearly P is monomial (i.e., generated
by variables) because I is monomial. We have to prove that if xij ∈ P then also
xik ∈ P for all k < j. We may write P = I : f for some monomial f . Let α be
the exponent of xij in f . Consider g ∈ B such that g(xij ) = xij + xik and fixes all
α
the other variables. Then g(xij f ) ∈ I because xij f ∈ I. The monomial xα+1
ik f /xij
α+1
α+1
α
appears with nonzero coefficient in g(xij f ). Hence xik f /xij ∈ I and xik f ∈ I.
In other words, xα+1
∈ I : f = P and hence xik ∈ P .

ik
Lemma 2.3. Let I be a radical and Borel fixed ideal. Then every minimal generator
of I has multidegree bounded above by (1, 1, . . . , 1) ∈ Zm .
Proof. Consider a generator f of I of degree (a1 , . . . , am ). We may write f = ug
with u a monomial of degree a1 e1 . Since I is Borel fixed we have xa1j1 g ∈ I, where
j = min{k : x1k |u}. Since I is radical we have x1j g ∈ I, and x1j g is a proper divisor
of f unless a1 = 1.

Lemma 2.4. Let I be a radical Borel fixed ideal and let {Pb1 , . . . , Pbc }, with
b1 , . . . , bc ∈ U , be the minimal primes of I. Then I is the Alexander dual of the
polarization of
Y b
J =(
xjij : i = 1, . . . , c) ⊂ K[x1 , . . . , xm ].
bij >0

In particular, if all the generators of I have the same multidegree, then I has a
linear resolution.
Proof. The first assertion follows immediately from the definition of polarization
and Alexander duality, see [11, Chap.5]. For the second, one observes that if all the
generators of I have degree, say, e1 + e2 + · · · + eu ∈ Zm , then I is the Alexander
dual of the polarization of an ideal J ⊂ K[x1 , . . . , xm ] involving only variables xi
with i ≤ u and whose radical is (x1 , . . . , xu ). Hence J defines a Cohen-Macaulay
ring, and so does its polarization. Finally one applies the Eagon-Reiner Theorem
[9, Thm. 8.1.9].

The goal of this section is to prove the following:
Theorem 2.5. Let I, J ⊂ S be Borel fixed ideals such that HS(I, y) = HS(J, y). If
I is radical then I = J.
The most important consequence of Theorem 2.5 is the following rigidity result:
Corollary 2.6. Let I be a radical Borel fixed ideal. For every multigraded ideal J
with HS(J, y) = HS(I, y) one has:
(a) gin≺ (J) = I for every term order ≺.
(b) J is radical.
(c) J has a linear resolution whenever I has a linear resolution.
(d) S/J is Cohen-Macaulay whenever S/I is Cohen-Macaulay.

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS

7

(e) βi,a (S/J) ≤ βi,a (S/I) for every i ∈ N and a ∈ Zm and βi,a (S/J) = 0 if
a 6≤ (1, 1, . . . , 1) ∈ Zm .
Proof. The ideal gin≺ (J) is a Borel fixed ideal and HS(J, y) = HS(gin≺ (J), y).
Since, by assumption, HS(J, y) = HS(I, y), we may conclude, by virtue of Theorem 2.5 that gin≺ (J) = I. This proves (a). Statements (b),(c) and (d) are standard
applications of well-known principles. Finally (e) follows from Lemma 2.3 and from
the bounds derived form the Taylor complex, see [11, Chap.6]

In order to prove Theorem 2.5 we need the following definition.
Definition 2.7. For every finitely generated Zm -graded S-module M we set
C(M, y) = K(M, 1 − y1 , . . . , 1 − ym ) ∈ Z[|y1 , . . . , ym |]
and we define the G-multidegree (geometric multidegree) of M as
X
ca y a ∈ Z[y1 , . . . , ym ]
G(M, y) =

where the sum is over the a ∈ Zm which are minimal in the support of C(M, y) and
ca is the coefficient of y a in C(M, y).
The following result follows immediately from the definition above.

Proposition 2.8.
(1) Let P be a prime ideal generated by variables and let
a(P ) be the vector whose i-th coordinate is #(P ∩ {xi1 , . . . , xini }). Then
G(S/P, y) = y a(P )
(2) One has a(Pb ) = b for every b ∈ U and for b1 , b2 ∈ U one has Pb1 ⊆ Pb2 if
and only if y b1 |y b2 .
The key observation is the following:
Proposition 2.9. Let I be a Borel fixed ideal. One has
c
X
length((S/I)Pbi )y bi
G(S/I, y) =
i=1

where Min(I) = {Pb1 , . . . , Pbc } for some bi ∈ U .
Proof. In order to compute the K-polynomial of M = S/I, consider a filtration of
Zm -graded modules
0 = M0 ⊂ M1 ⊂ · · · ⊂ Mh = M
such that Mi /Mi−1 ≃ S/Pi (−vi ). Here Pi is a Zm -graded monomial prime ideal
and vi = (vi1 , . . . , vim ) ∈ Zm . Existence of such a filtration follows from basic
commutative algebra facts, see [8, Prop.3.7]. Furthermore
Min(I) ⊆ Ass(S/I) ⊆ {P1 , . . . , Ph }.
Hence we have
K(S/I, y) =

h
X

K(S/Pi (−vi ), y) =

C(S/I, y) =

y vi K(S/Pi , y).

i=1

i=1

It follows that

h
X

h Y
m
X

i=1 j=1

(1 − yj )vij C(S/Pi , y).

8

A. CONCA, E. DE NEGRI, AND E. GORLA

Qm
Then the support of the polynomial j=1 (1 − yj )vij C(S/Pi , y) contains exactly
one minimal element, namely y a(Pi ) , which appears in the polynomial with coefficient 1. It follows that G(S/I, y) is obtained as the sum of the terms which are
minimal in the support of the polynomial
(2.9.1)

h
X

y a(Pi )

i=1

Now the elements that are minimal support in the support of (2.9.1) are exactly
the y bi corresponding to the minimal primes Pbi . This follows from Proposition 2.8,
′
since if P ⊆ P ′ , then y a(P ) |y a(P ) . Finally, by standard localization arguments we
have that each minimal prime Pbi appears in the multiset {P1 , . . . , Ph } as many
times as length((S/I)Pbi ).

We are finally ready to prove Theorem 2.5.
Proof of Theorem 2.5. Since I and J have the same Hilbert series we have that
C(S/I, y) = C(S/J, y) and hence
G(S/I, y) = G(S/J, y).
It follows by Proposition 2.9 that Min(I) = Min(J). Since I is radical, the coefficients in G(S/I, y) are all 1. Hence the primary decomposition of J is of the form
I ∩ Q, where Q is the intersection of the components associated to the embedded
prime ideals of J, if any. We deduce that J ⊆ I and the Hilbert series forces the
equality I = J.

3. Column-graded ideals of maximal minors
Consider S = K[xij : 1 ≤ i ≤ m, 1 ≤ j ≤ n] graded by deg(xij ) = ej ∈ Zn .
Let L = (Lij ) be a m × n matrix of linear forms which is column-graded, that is,
whose entries Lij satisfy deg(Lij ) = ej . In other words,
Lij =

m
X

λijk xkj

k=1

where λijk ∈ K. As a first direct application of Corollary 2.6 we have:
Theorem 3.1. Let L = (Lij ) be a m×n matrix which is column-graded and assume
that the codimension of Im (L) is n − m + 1. Then Im (L) is radical and the maximal
minors of L form a universal Gröbner basis of it. Furthermore every initial ideal
of Im (L) is radical, has a linear resolution, and its Betti numbers equals those of
Im (L).
Proof. We may assume without loss of generality that K is infinite. Let I =
(x1j1 x1j2 · · · x1jm : 1 ≤ j1 < j2 < · · · < jm ≤ n). Then I is generated by the
maximal minors of a column-graded matrix whose (i, j)-th entry is aij x1j with
randomly chosen scalars aij . Since the codimension of I is n − m + 1, by the
Eagon-Northcott complex it follows that I and Im (L) have the same multigraded
Hilbert series. Since I is radical and Borel fixed, we may apply Corollary 2.6 with
J = Im (L) or J equal any initial ideal of Im (L) to conclude.

We want now to generalize Theorem 3.1 and get rid of the assumption on the
codimension of Im (L).

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS

9

Theorem 3.2. Let L = (Lij ) be an m × n matrix which is column-graded. Then:
(a) The maximal minors of L form a universal Gröbner basis of Im (L).
(b) Im (L) is radical and it has a linear resolution.
(c) Any initial ideal J of Im (L) is radical and has a linear resolution. In
particular, βi,j (Im (L)) = βi,j (J) for all i, j.
(d) Assume that Im (L) 6= 0 and that no column of Im (L) is identically 0. Then
the projective dimension of Im (L) (and hence of all its initial ideals) is
n − m.
Proof. Again we may assume that K is infinite. Fix a term order ≺. It is not
restrictive to assume that x1j ≻ xij for all i 6= 1 and j; set for simplicity xj = x1j .
Let
I = (xj1 · · · xjm | [j1 , . . . , jm ]L 6= 0).
We claim that I = gin≺ (Im (L)). First we note that I ⊆ gin≺ (Im (L)). This is
because if [j1 , . . . , jm ]L 6= 0, then Im (L) contains a non-zero element of degree
ej1 + · · · + ejm and its initial term in generic coordinates is xj1 · · · xjm .
Next note that I is the Stanley-Reisner ideal of the Alexander dual of the matroid
dual ML∗ of the matroid ML associated to L. As such, I has a linear resolution
by the Eagon-Reiner Theorem [9, Thm.8.1.9], since ML∗ is Cohen-Macaulay. By
Buchberger’s Algorithm, in order to prove that I = gin≺ (Im (L)) it suffices to show
that any S-pair associated to a linear syzygy among the generators of I reduces to
0. Any such linear syzygy involves at most m + 1 column indices in total. After
renaming the column indices, we may assume that the syzygy in question involves
the column indices {1, 2, . . . , m + 1}. Set
d = e1 + e2 + · · · + em+1 .
To prove that the S-polynomial reduces to 0 we may as well prove that dim Im (L)d ≤
dim Id . Let
W = {u : 1 ≤ u ≤ m + 1 and [{1, . . . , m + 1} \ {u}]L 6= 0}.
Renaming if needed, we may assume that
W = {1, 2, . . . , s}
By definition Id is generated by the set of monomials


x1 x2 · · · xm+1
xij : j = 1, . . . s and i = 1, . . . m
xj
whose cardinality is easily seen to be sm − s + 1. Hence it remains to prove that
dim Im (L)d ≤ sm − s + 1.
Denote by Ω the first syzygy module of {[{1, . . . , m + 1} \ {u}]L : u = 1, . . . , s}.
Since
dim Im (L)d = sm − dim Ωd
it suffices to show that
dim Ωd ≥ s − 1.
Let L1 be the submatrix of L consisting of the first s columns of L. Since the
rows of L1 are elements of Ωd , it is enough to show that that L1 has at least
s − 1 linearly independent rows over K. By contradiction, if this is not the case, by
applying invertible K-linear operations to the rows of L we may assume that the last

10

A. CONCA, E. DE NEGRI, AND E. GORLA

m−s+2 rows of L1 are identically zero. In particular the minor [2, . . . , m+1]L = 0,
contradicting our assumptions.
Since I is Borel fixed and radical with HS(I, y) = HS(Im (L), y), we may apply
Corollary 2.6 and deduce (a), (b) and (c). For (d) one observes that, under the
assumption that no column of L is 0 and Im (L) 6= 0, the ideal I is non-zero and each
of the variables x1 , . . . , xn is involved in some generator. Then ML∗ has dimension
n − m and has no cone-points. This implies that the Stanley-Reisner ring of ML∗
has regularity n − m, as it is 2-Cohen-Macaulay (see [13, pg.94] for details). By
[9, Prop.8.1.10] the projective dimension of I (that is the Alexander dual of ML∗ ) is
n − m.

4. Row-graded ideals of maximal minors
In this section we treat ideals of maximal minors of row-graded matrices. Consider S = K[xij : i = 1, . . . , m and j = 1, . . . , n] graded by deg(xij ) = ei ∈ Zm .
Let L = (Lij ) be a m × n matrix of linear forms which is row-graded, i.e., whose
entries Lij satisfy deg(Lij ) = ei . In other words,
Lij =

m
X

λijk xik

k=1

where λijk ∈ K. Observe that in the row-graded case we cannot expect that the
maximal minors of X form a Gröbner basis simply because every maximal minor
might have the same leading term. Nevertheless we can prove the following:
Theorem 4.1. Let L = (Lij ) be an m × n matrix which is row-graded and assume
that the codimension of Im (L) is n − m + 1. Then Im (L) is radical and every initial
ideal is generated by elements of total degree m (equivalently, there is a universal
Gröbner basis of elements of degree m). Furthermore every initial ideal of Im (L)
is radical, has a linear resolution, and its Betti numbers equals those of Im (L).
Set
I = (x1j1 · · · xmjm : j1 + · · · + jm ≤ n).
Theorem 4.1 follows immediately from Corollary 2.6 and from the following proposition, by observing that I is radical and Borel fixed. Notice that Corollary 2.6 also
implies that I = gin≺ (Im (L)) for every term order ≺.
Proposition 4.2. Under the assumptions of Theorem 4.1, the Zm -graded Hilbert
series of Im (L) equals that of I.
Proof. The Hilbert series of Im (L) equals that of Im (X) with X = (xij ), because
both ideals are resolved by the multigraded version of the Eagon-Northcott complex.
Hence we may assume without loss of generality that L = X. We will show that
S/Im (X) and S/I have the same K-polynomial.
Let Km,n (y) be the K-polynomial of S/Im (X). By looking at the diagonal initial
ideal of Im (X) one obtains the recursion:
Km,n (y) = (1 − ym )Km,n−1 (y1 , . . . , ym ) + ym Km−1,n−1 (y1 , . . . , ym−1 ).
Solving the recursion or, alternatively, by looking directly at the multigraded version
of the Eagon-Northcott complex, one obtains:


n−m
m
X
Y
n
k
hk (y1 , . . . , ym )
(−1)
(4.2.1)
Km,n (y) = 1 − ( yi )
m+k
i=1
k=0

UNIVERSAL GRÖBNER BASES FOR MAXIMAL MINORS

11

where hk (y1 , . . . , ym ) is the complete symmetric polynomial of degree k, i.e., the
sum of all the monomials of degree k in the variables y1 , . . . , ym .
We now compute the K-polynomial of S/I. For b ∈ [n]m set xb = x1b1 x2b2 · · · xmbm
so that
I = (xb : b ∈ Nm
>0 and |b| ≤ n).
Extend the natural partial order, i.e. xb ≤ xc if b ≤ c coefficientwise, to a total
order < (no matter how). For every b ∈ [n]m we have:
(4.2.2)

(xc : xc < xb ) : xb = (xij : i = 1, . . . , m and 1 ≤ j < bi ).

Filtering I according to < and using (4.2.2) one obtains:
(4.2.3)

K(S/I, y) = 1 − y1 . . . ym

m
XY

(1 − yi )bi −1

i=1

b

P
where the sum b is over all the b ∈ Nm
>0 and |b| ≤ n. Setting c = b − (1, . . . , 1)
and replacing b with c in (4.2.3) we obtain:
(4.2.4)

K(S/I, y) = 1 − y1 . . . ym

m
XY
c

m

where the sum
expression as:

P

(4.2.5)

K(S/I, y) = 1 − y1 . . . ym

c

is over all the c ∈ N

(1 − yi )ci

i=1

and |c| ≤ n − m. We may rewrite the last

n−m
X

hk (1 − y1 , . . . , 1 − ym ).

k=0

Taking into consideration (4.2.1) and (4.2.5), it remains to prove that:


n−m
n−m
X
X
n
k
hk (y1 , . . . , ym )
(4.2.6)
hk (1 − y1 , . . . , 1 − ym ) =
(−1)
m+k
k=0

k=0

or equivalently, by replacing yi with −yi in (4.2.6), it is left to show that:
n−m
n−m
X
X n 
(4.2.7)
hk (1 + y1 , . . . , 1 + ym ) =
hk (y1 , . . . , ym ).
m+k
k=0

k=0

Setting t = n − m, (4.2.7) is equivalent to the assertion that the equality:

t
t 
X
X
m+t
(4.2.8)
hk (1 + y1 , . . . , 1 + ym ) =
hk (y1 , . . . , ym )
m+k
k=0

k=0

holds for every m and t. The formula (4.2.8) can be derived from the more precise:

t 
X
m+t−1
(4.2.9)
ht (1 + y1 , . . . , 1 + ym ) =
hk (y1 , . . . , ym ).
m+k−1
k=0

Equation (4.2.9) can be proved by (long and tedious) induction on m. The
following simple argument using generating functions was suggested by Christian
Krattenthaler. First notice that:
m
Y
X
1
.
(4.2.10)
ht (y1 , . . . , ym )z t =
1
−
yi z
i=1
t≥0

12

A. CONCA, E. DE NEGRI, AND E. GORLA

Replacing in (4.2.10) yi with yi + 1 and observing that
m
m
Y
Y
1
1
1
=
z
m
1 − (yi + 1)z
(1 − z) i=1 1 − yi (1−z)
i=1
we have:
(4.2.11)

X
t≥0

ht (1 + y1 , . . . , 1 + ym )z t =

X

ht (y1 , . . . , ym )

t≥0

Expanding the right-hand side of (4.2.11) one obtains (4.2.9).

zt
.
(1 − z)t+m


References
[1] C. Aholt, R. Thomas, B. Sturmfels, A Hilbert scheme in computer vision. arXiv:1107.2875,
to appear in the Canadian Journal of Mathematics.
[2] A. Aramova, K. Crona, E. De Negri, Bigeneric initial ideals, diagonal subalgebras and bigraded Hilbert functions. J. Pure Appl. Algebra 150 (2000), no. 3, 215–235.
[3] D. Bernstein, A. Zelevinsky, Combinatorics of maximal minors. J. Algebraic Combin. 2
(1993), no. 2, 111–121.
[4] A. Boocher, Free resolution and sparse determinantal ideals. Math. Res. Lett. 19 (2012),
805–821.
[5] D. Cartwright, B. Sturmfels, The Hilbert scheme of the diagonal in a product of projective
spaces. Int. Math. Res. Not. IMRN 2010, no. 9, 1741–1771.
[6] CoCoA Team, CoCoA: a system for doing Computations in Commutative Algebra, Available
at http://cocoa.dima.unige.it
[7] A. Conca, Linear spaces, transversal polymatroids and ASL domains. J. Algebraic Combin.
25 (2007), no. 1, 25–41.
[8] D. Eisenbud, Commutative algebra. With a view toward algebraic geometry. Graduate Texts
in Mathematics, 150. Springer-Verlag, New York, 1995.
[9] J. Herzog, T. Hibi, Monomial ideals. Graduate Texts in Mathematics, 260. Springer-Verlag
London, Ltd., London, 2011.
[10] M. Y. Kalinin, Universal and comprehensive Gröbner bases of the classical determinantal ideal. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 373 (2009),
Teoriya Predstavlenii, Dinamicheskie Sistemy, Kombinatornye Metody. XVII, 134–143, 348;
translation in J. Math. Sci. (N. Y.) 168 (2010), no. 3, 385–389.
[11] E. Miller, B. Sturmfels, Combinatorial commutative algebra. Graduate Texts in Mathematics,
227. Springer-Verlag, 2005.
[12] B. Sturmfels, A. Zelevinsky, Maximal minors and their leading terms. Adv. Math. 98 (1993),
no. 1, 65-112.
[13] R. Stanley, Combinatorics and commutative algebra. Second edition. Progress in Mathematics, 41, 1996
Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, I-16146 Genova, Italy
E-mail address: conca@dima.unige.it
Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, I-16146 Genova, Italy
E-mail address: denegri@dima.unige.it
Institut de Mathématiques, Université de Neuchâtel, Rue Emile-Argand 11, CH-2000
Neuchâtel, Switzerland
E-mail address: elisa.gorla@unine.ch

