Frobenius 标准型算法

· · 个人记录

因为本人比较菜，所以就不复读了，就放一个代码。

代码

云剪贴板。

如果只需要计算特征多项式，可以发现只要提取算法里面计算 P 的部分就行了，不需要后续的调整（当然常数好像有点大）。

假设给出矩阵 A，我们可以求出它的 Frobenius 标准型 F_A 以及顺带的特征多项式 p_A(x)，实际上 F_A 是分块友矩阵，我们只是存了所有的友矩阵的特征多项式在代码的数组 P 中，以及也求出了转移阵 T 和 T^{-1} 使得 F_A=T^{-1}AT 成立。矩阵快速幂可以考虑直接计算分块友矩阵的幂，其中每一列都是 x^k\bmod{P} 的形式，这个在 常系数齐次线性递推 - OI Wiki 里面介绍了。

2024-11-1 更新：求矩阵 f\left(F_A\right)，其中 f 为多项式。可以用于求 \operatorname{adj} A，具体的在特征多项式中我们有 p_A(x)=x^n+p_{n-1}x^{n-1}+\cdots+\left(-1\right)^n\det A 其中 A\operatorname{adj} A=\left(\operatorname{adj}A\right)A=\left(\det A\right)I。

参考文献

  1. Elegia. A (Somehow) Simple (Randomized) Algorithm for Frobenius Form of a Matrix.
  2. Arne Storjohann. Algorithms for Matrix Canonical Forms.