On the Gröbner complexity of matrices

Abstract

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal \Ideal_A coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. We conclude that for the matrices A_{3\times 3} and A_{3\times 4}, defining the 3\times 3 and 3\times 4 transportation problems, we have u(A_{3\times 3})=g(A_{3\times 3})=9 and u(A_{3\times 4})=g(A_{3\times 4})\geq 27. Moreover, we prove u(A_{a,b})=g(A_{a,b})=2(a+b)/\gcd(a,b) for positive integers a,b and A_{a,b}=(\begin{smallmatrix} 1 & 1 & 1 & 1 0 & a & b & a+b \end{smallmatrix}).

9 pages