大家好，欢迎来到IT知识分享网。

零化多项式/特征多项式/最小多项式/常系数线性齐次递推

约定:

\(I_n\)是\(n\)阶单位矩阵，即主对角线是\(1\)的\(n\)阶矩阵

一个矩阵\(A\)的\(|A|\)是\(A\)的行列式

默认\(A\)是一个\(n\times n\)的矩阵

定义

零化多项式:

对于一个矩阵\(A\)，它的一个零化多项式\(f(\lambda)\)是满足\(f(A)=0\)的多项式，定义域包含矩阵

最小多项式:次数最低的零化多项式

特征多项式

对于一个\(n\)阶的矩阵\(A\)，它的特征多项式

\(p(\lambda)=|\lambda I_n-A|\)

\(\lambda\)定义域不止是\(\R\)，还可以是矩阵

\(p(\lambda)\)是关于\(\lambda\)的一个不超过\(n+1\)次的多项式

即\(p(\lambda )=\sum_0^{n}a_ix^i\)

Cayley-Hamilton定理:矩阵的特征多项式也是它的零化多项式

求解特征多项式

带入\(n\)个数，求出得\(|x I_n-A|\),得到\(n\)个矩阵，通过高斯消元可以\(O(n^3)\)地求出行列式

然后可\(O(n^2)\)拉格朗日插值求出原来的多项式，总复杂度受限于高斯消元，为\(O(n^4)\)

求解最小多项式

构造矩阵序列\(a_i=A^i\)

求出它的一个线性递推\(r_i\)，即

\(\begin{aligned} \sum_{j=0}^{m} r_j a_{i-j}=\sum_{j=0}^{m} r_j A^{i-j}=(\sum_{j=0}^m r_{m-j}A^j)\cdot A^{i-m}=0\end{aligned}\)

\(\begin{aligned} \therefore \sum_{j=0}^m r_{m-j}A^j=0\end{aligned}\)

所以可以由\(r_i\)翻转得到\(f(\lambda)\)

求解\(a_i\)前\(n\)项的复杂度受限于矩阵乘法为\(O(n^4)\)，求解递推式的复杂度为\(O(n^3)\)

考虑到实际求解递推式时，随机生成了两个向量\(u,v\)

实际是计算标量序列\(\{uA^iv\}\)的递推式，所以实际每次求出\(uA^i\)复杂度应为\(O(n^2)\)

求这个递推式需要用到\(a_i\)前\(2n\)项，求解复杂度为\(O(n^3)\)

因此总复杂度为\(O(n^3)\)

(但是如果只是求出来并没有什么用，因为求解方法是随机的，甚至连检查一次保证正确都需要\(O(n^2(n+e))\)的时间(\(e\)为矩阵非0位置个数))

求解稀疏方程组

设方程系数用矩阵\(A\)表示，右侧每个方程的常数用向量\(b\)表示，答案用向量\(x\)表示，则满足关系式

\(Ax=b\)，即\(x=A^{-1}b\)

求出\(\{A^ib\}\)线性递推式，反推出\(A^{-1}b\)即可

反推方法:

带入线性递推的\(m\)项，则\(\sum_{i=0}^{m} A^{m-i}b\cdot r_i=0\)

两边同乘\(A^{-1}\)，得到\(A^{-1}b\cdot r_m +\sum_{i=0}^{m-1}A^{m-i}br_i=0\)

求解矩阵\(k\)次幂

我们要求解\(A^k\)，常规做法是直接用快速幂

设矩阵\(A\)的一个零化多项式是\(f(\lambda)\)

显然，\(A^k\)可以用一个多项式表示\(A^k=\sum_0^k w_i A^i\)

\(\{w_i\}\)构成了一个\(k+1\)次多项式\(F_k(x)\)

存在一种合法的表示是\(F_k(x)=x^k\)

\(\because f(A)=0 \therefore \forall i, f(A)A^i=0\)

也就是相当于我们要求出\(x^k\)对于\(f(x)\)这个\(n+1\)多项式取模

显然可以通过类似快速幂的方式倍增求解这个多项式，每次对\(f(x)\)取模复杂度是\(O(n\log n)\)

就能在\(O(n\log m\log n)\)时间得求出\(F(x)\)

最后得到的\(F(x)\)是一个\(n\)次多项式

那么带入就可以快速求出\(A_k\)

可以认为这个复杂度是受限于求解\(A^0,A^1,\cdots,A^{n-1}\)的\(O(n^4)\)

对于元矩阵\(A\)为稀疏矩阵的情况，设其包含\(e\)个非零位置

那么求解\(B\cdot A\)的过程是\(O(n\cdot e)\)的，求解\(A_0,A^1,\cdots,A^{n-1}\)的过程，是\(O(n^2e)\)的

求解零化多项式的复杂度也是\(O(n^2(n+e))\)的，因此总复杂度为\(O(n^2(n+e))\)

而一般的矩阵快速幂是\(O(n^3\log k)\)的，这种方法适用情况非常特殊

另外，对于并不需要知道整个矩阵的答案，并且\(A^0,A^1,\cdots,A^{n-1}\)特殊的具体问题，这个方法也十分有效

求解常系数线性齐次递推

问题是要求数列\(f_i=\sum _{j=1}^{n}a_j\cdot f_{i-j}\)

给出\(f_0,f_1,\cdots,f_{n-1}\)，求第\(k\)项的值

线性递推显然可以用 初始向量列 与 转移矩阵的幂次 的乘积表示，即\(f_i=(S \cdot A^i)_n\)，其中\(A\)为转移矩阵，\(S\)为初始向量列，我们求的是第\(n\)项

对于\(n=4\)的情况，我们的转移矩阵\(A\)是

鉴于它的特殊性，我们可以直接求出它的特征多项式表达式

由\(\lambda I_n-A=\)

带入行列式最暴力的求法

枚举一个排列\(p_i\)，设排列\(p\)的逆序对为\(f(p)\)，\(|A|=\sum (-1)^{f(p)} \Pi A_{i,p_i}\)

实际上合法的排列只有\(n\)个，就是

枚举\(p_i=n\)

那么\(p_j=\left\{\begin{aligned} j && j<i \\ n && j=i \\ j-1 && j> i\end{aligned}\right.\)

当\(i=n\)时，\((-1)^{f(p)} \Pi A_{i,p_i}=\lambda ^n-a_1\lambda ^{n-1}\)

当\(i>1\)时，

\(f(p)=n-i\)

\(\Pi A_{i,p_i}=(-1)^{n-i+1}\lambda^i\cdot a_{n-i+1}\)

\((-1)^{f(p)} \Pi A_{i,p_i}=-\lambda^i a_{n-i+1}\)

综上,转移矩阵\(A\)的特征多项式有简单的表达

\(p(\lambda) = |\lambda I_n-A|=\lambda^n-a_1\lambda^{n-1} -a_2\lambda^{n-2} -\cdots -a^n\)

假设有\(f_0\)这一项(不需要知道是多少)，那么认为初始向量列为\(S=(f_{-(n-1)},f_{-(n-2)},\cdots ,f_{0})\)

这个问题，我们要求的是\(S\cdot A^k\)的第\(n\)项，不需要知道整个矩阵

类似求出\(A^k\)的过程，求出\(F_k(x)\mod p(\lambda)\)

我们要求解\((S\cdot A^k)_n=\sum_1^{n}[x^i]{F(x)}(S\cdot A^i)_n\)

而\((S\cdot A^i)_n=f_i\)已知，求出\(F(x)\)后直接带入即可

需要用到多项式取模，求解这个表达式是\(O(n\log n\log k)\)的，求完直接带入即可

用最朴素的\(\text{NTT}\)，完全不卡常，甚至过不掉模板题