On Eigenvalue Gaps of Integer Matrices
On Eigenvalue Gaps of Integer Matrices
复制标题
关于整数矩阵的特征值间隙
DOI：
10.48550/arxiv.2212.07032
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
N. Srivastava
中科院分区：
文献类型：
--
作者：
Aaron Abrams;Zeph Landau;James Pommersheim;N. Srivastava
给定一个$n\times n$矩阵，其整数元素在$[-h，h]$范围内，它的两个不同的特征值能有多接近？最好的已知的例子有一个最小的差距为$h^{-O（n）}$。这里我们给出了元素在$[0，h]$中且两个特征值至多相隔$h^{-n^2/16+o（n^2）}$的矩阵的显式构造。直到指数中的常数，这与已知的$\Omega（（2\sqrt{n}）^{-n^2}h^{-n^2}）$ \cite{mahler 1964 inequality}的下界一致。最小间隔的界与对角化算法的最坏情况分析和整数矩阵标准形的计算有关。除了我们的显式构造之外，我们还证明了有许多矩阵的间隙略大，大约为h^{-n^2/32}$。我们还构造了两个特征值至多相隔2 ^{-n^2/64+o（n^2）}$的0-1矩阵。
Given an $n\times n$ matrix with integer entries in the range $[-h,h]$, how close can two of its distinct eigenvalues be? The best previously known examples have a minimum gap of $h^{-O(n)}$. Here we give an explicit construction of matrices with entries in $[0,h]$ with two eigenvalues separated by at most $h^{-n^2/16+o(n^2)}$. Up to a constant in the exponent, this agrees with the known lower bound of $\Omega((2\sqrt{n})^{-n^2}h^{-n^2})$ \cite{mahler1964inequality}. Bounds on the minimum gap are relevant to the worst case analysis of algorithms for diagonalization and computing canonical forms of integer matrices. In addition to our explicit construction, we show there are many matrices with a slightly larger gap of roughly $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)}$.