零化多项式/特征多项式/最小多项式/常系数线性齐次递推
约定:
\(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\)是
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | \(a_4\) | |||
| 2 | 1 | \(a_3\) | ||
| 3 | 1 | \(a_2\) | ||
| 4 | 1 | \(a_1\) |
鉴于它的特殊性，我们可以直接求出它的特征多项式表达式
由\(\lambda I_n-A=\)
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | \(\lambda\) | \(-a_4\) | ||
| 2 | $-1 $ | \(\lambda\) | \(-a_3\) | |
| 3 | \(-1\) | \(\lambda\) | \(-a_2\) | |
| 4 | \(-1\) | \(\lambda -a_1\) |
带入行列式最暴力的求法
枚举一个排列\(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)\)的，求完直接带入即可