零化多项式/特征多项式/最小多项式/常系数线性齐次递推
零化多项式/特征多项式/最小多项式/常系数线性齐次递推
约定:
$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\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)$的，求完直接带入即可