矩阵的特征多项式$M$可以写成

$\chi_M(z) = z^n + \textrm{trace(M)}z^{n-1}+\ldots + \det(M)$.

因为你提前知道所有的条目$M$是理性的，你可以放心$\det(M)$是理性的；说$\det(M) = p/q$. 现在，有理根定理向您保证，如果$\chi_M$有理根$\lambda = k/l$， 然后$k$划分$p$和$l$划分$q$. 但是，您提前（不知何故）知道$M$是理性的。

您可以计算的行列式$M$通过计算 LU 分解，比完整特征多项式快得多$M$. 由于所有的条目都是有理的，所以三角因子的条目也是有理的；您当然必须确保以符号方式进行分解，以便也可以准确计算行列式。

尝试所有有理数$k/l$这样$k | p$和$l | q$也非常昂贵。但是，您可以使用传统的特征求解器来获得一组近似特征值$\hat{\lambda}_1,\ldots,\hat{\lambda}_n$，然后在每个近似值附近寻找具有所需可除性属性的精确、有理特征值。

粗略的谷歌搜索没有找到任何关于有理矩阵的确切特征分解的信息，所以我怀疑以前是否有人编写过这样的程序。但是，您可能会对sympy的线性代数特性感到幸运。

有一种“简单”的方法，在某种意义上说我们只需要几行程序就很简单（这里我使用 Maple，但 Mathematica 也可以使用 PSLQ 来完成）。第 1 步：Maple 用（例如）200 位计算特征多项式的根。第 2 步：Maple 使用 Lenstra 的 LLL 方法给出根的最小多项式（如果我们以足够的精度知道根）。这里最小多项式有度$1$但是，为了安全起见，我们要求一个多项式$2$. （如果你得到一个多项式$2$，提高准确性）。在以下随机实例中，计算时间为 0"12。

roll := rand(-10^10 .. 10^10): 
Digits:= 200:
f := 1:
 for i to 10 do f := f*(x-roll()*(1/roll())) end do;
 f; 
f := numer(expand(f));
t := time():
 res := fsolve(f):
with(PolynomialTools):

for i to 10 do 
print(MinimalPolynomial(res[i], 2)) end do;
time()-t;