On the Gröbner complexity of matrices

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_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. In fact, if the universal Gröbner basis of I_A 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 A_{3 × 3} and A_{3 × 4}, defining the 3×3 and 3×4 transportation problems, we have u (A_{3 × 3}) = g (A_{3 × 3}) = 9 and u (A_{3 × 4}) = g (A_{3 × 4}) ≥ 27. Moreover, we prove that u (A_{a, b}) = g (A_{a, b}) = 2 (a + b) / gcd (a, b) for positive integers a, b and A_{a, b} = ((1, 1, 1, 1; 0, a, b, a + b)).