论文标题
在整数矩阵的特征值差距上
On Eigenvalue Gaps of Integer Matrices
论文作者
论文摘要
给定一个$ n \ times n $矩阵，其中包含整数条目$ [ - h，h] $，其两个不同的特征值有多近？ 最好的以前已知的示例的最小差距为$ h^{ - o（n）} $。在这里，我们给出了矩阵的明确构造，其中包含$ [0，h] $的条目，其中两个特征值最多由$ h^{ - n^2/16+o（n^2）} $分开。最多达到指数中的常数，这与已知的下限$ω（（（2 \ sqrt {n}）^{ - n^2} h^{ - n^2}）$ \ cite {mahler1964inequality}。最小差距上的界限与对角线化和计算整数矩阵的规范形式的最坏情况分析有关。 除了明确的结构外，我们还显示许多矩阵的矩阵大约$ h^{ - n^2/32} $。我们还构建了0-1矩阵，这些矩阵具有两个特征值，最多$ 2^{ - n^2/64+o（n^2）} $。
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 $Ω((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)}$.
