On the Gröbner complexity of matrices

AbstractIn this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal IA 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. In fact, if the universal Gröbner basis of IA coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A3×3 and A3×4, defining the 3×3 and 3×4 transportation problems, we have u(A3×3)=g(A3×3)=9 and u(A3×4)=g(A3×4)≥27. Moreover, we prove that u(Aa,b)=g(Aa,b)=2(a+b)/gcd(a,b) for positive integers a,b and Aa,b=(11110aba+b)