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