On eigenvalue gaps of integer matrices

Given an n × n n× n matrix with integer entries in the range [ − h , h ] [-h,h] , how close can two of its distinct eigenvalues be? The best previously known examples (Lu [Minimum eigenvalue separation, ProQuest LLC, Ann Arbor, MI, 1992. Thesis (Ph.D.)–University of California, Berkeley; Wilkinson [The algebraic eigenvalue problem, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1988]) have a minimum gap of h − O ( n ) h-O(n) . Here we give an explicit construction of matrices with entries in [ 0 , h ] [0,h] with two eigenvalues separated by at most h − n 2 / 16 + o ( n 2 ) h-n^2/16+o(n^2) . Up to a constant in the exponent, this agrees with the known lower bound of Ω ( ( 2 n ) − n 2 h − n 2 ) Ω ((2√n)-n^2h-n^2) (Mahler [Michigan Math. J. 11 (1964), pp. 257–262]). Bounds on the minimum gap are relevant to the worst case analysis of algorithms for diagonalization and computing canonical forms of integer matrices (e.g. Dey et al. [Bit complexity of Jordan normal form and polynomial spectral factorization, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023, pp. Art. No. 42]). In addition to our explicit construction, we show there are many matrices with a slightly larger gap of roughly h − n 2 / 32 h-n^2/32 . We also construct 0-1 matrices which have two eigenvalues separated by at most 2 − n 2 / 64 + o ( n 2 ) 2-n^2/64+o(n^2) .