高斯消元随便记录

今天在群里问怎么求算 $\det\left(A+xB\right)$ 其中 $A,B\in\mathbb{F}^{n\times n}$，因为我们知道 $\deg \det\left(A+xB\right) \leq n$，所以还是能求的，问题是如何在 $O\left(n^3\right)$ 的时间进行求算，这个技巧应该很多人都会，但是我好像还不会，于是进行一个提的问。

如果 $B$ 可逆，那么求算 $\det\left(AB^{-1}+xI\right)\det B$ 就可以了。

钱哥告诉我最后我们几乎总是可以转换成特征多项式的求算，考虑高斯消元，我们只对 $x$ 的系数进行消元，要消完了之后用刚刚选的主元把上下的都消完。最后对于 $x$ 的系数而言一定是一个上三角矩阵并且对于选取了主元的一列都只有一个非零项了。这时候已经尽可能消元了，所以可能会产生没有主元的行，对于这些行，其 $x$ 的系数可能都是零，那么此时将这一行乘以 $x$，最后需要将结果除以 $x$，而因为上面的 $\deg\det\left(A+xB\right)$ 有约束，所以在若干次尝试之后仍然有没有找到主元的行，就说明行列式为零了。

这一算法看起来可以由 Elegia 的评论扩展到任意的多项式矩阵，只需要用上面类似的方法将多项式首项系数变成单位矩阵就可以了，注意度数的限制也要随之变化。

代码大概在这里。