On eigenvalue gaps of integer matrices

Given an n × n n\times 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 ) \Omega ((2\sqrt {n})^{-n^2}h^{-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)} .