On eigenvalue gaps of integer matrices
- 12 September 2024
- journal article
- research article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 94 (352) , 853-862
Abstract
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)} .Keywords
All Related Versions
Funding Information
- National Science Foundation (2009011)
This publication has 14 references indexed in Scilit:
- Upper Hessenberg and Toeplitz BohemiansLinear Algebra and its Applications, 2020
- Minimal Height Companion Matrices for Euclid PolynomialsMathematics in Computer Science, 2018
- Discriminant and Root Separation of Integral PolynomialsJournal of Mathematical Sciences, 2016
- Integral polynomials with small discriminants and resultantsAdvances in Mathematics, 2016
- Root separation for irreducible integer polynomialsBulletin of the London Mathematical Society, 2011
- The distribution of close conjugate algebraic numbersCompositio Mathematica, 2010
- ON THE DISTANCE BETWEEN ROOTS OF INTEGER POLYNOMIALSProceedings of the Edinburgh Mathematical Society, 2004
- The Minimum Root Separation of a PolynomialMathematics of Computation, 1974
- An inequality for the discriminant of a polynomial.The Michigan Mathematical Journal, 1964
- Matrices of rational integersBulletin of the American Mathematical Society, 1960