特征多项式与常系数齐次线性递推

定义

对于 n$n$ 阶矩阵，若存在非零列向量 x$x$ 和数 λ$\lambda$ 满足 Ax=λx$Ax=\lambda x$，则称 λ$\lambda$ 和 x$x$ 为一组对应的特征值和特征向量。

在确定了特征值之后，可以得到对应的无穷多个解。

$$$$

求解特征值和特征向量

求解特征值和特征向量：

容易发现，λ$\lambda$ 是一个特征值，只需要满足 Ax=λx$Ax=\lambda x$ 有解，以 x$x$ 为元容易列出方程，其常数项为均 0$0$，系数矩阵为。

⎡⎣⎢⎢⎢⎢⎢⎢⎢λ−A1,1−A2,1−A3,1⋮−An,1−A1,2λ−A2,2−A3,2⋮−An,2−A1,3−A2,3λ−A3,3⋮−An,3⋯⋯⋯⋮⋯−A1,n−A2,n−A3,n⋮λ−An,n⎤⎦⎥⎥⎥⎥⎥⎥⎥=λI−A$$\left[\begin{array}{c}\begin{array}{ccccc}\lambda -A_{1,1}& -A_{1,2}& -A_{1,3}& \cdots & -A_{1,n}\\ -A_{2,1}& \lambda -A_{2,2}& -A_{2,3}& \cdots & -A_{2,n}\\ -A_{3,1}& -A_{3,2}& \lambda -A_{3,3}& \cdots & -A_{3,n}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ -A_{n,1}& -A_{n,2}& -A_{n,3}& \cdots & \lambda -A_{n,n}\end{array}\end{array}\right]=\lambda I-A$$

其中I$I$是单位矩阵。

这个方程有非零解的充要条件是：det(λI−A)=0$det(\lambda I-A)=0$ （因为如果不为 0$0$，则矩阵满秩，所有向量线性无关，无法得到0向量）

而 det(λI−A)$det(\lambda I-A)$ 是一个 n$n$ 次多项式 p(λ)$p(\lambda )$，称为特征多项式，所有的特征值 λ$\lambda$ 就是 p(λ)$p(\lambda )$ 的根。

$$$$

应用

加速矩阵乘法：

由 Ax=λx$Ax=\lambda x$，迭代该式可以得到 Anx=λnx$A^{n}x={\lambda }^{n}x$ 。

特殊矩阵的特征值

上三角矩阵

λI−A=⎡⎣⎢⎢⎢⎢⎢⎢⎢λ−A1,100⋮0−A1,2λ−A2,20⋮0−A1,3−A2,3λ−A3,3⋮0⋯⋯⋯⋮⋯−A1,n−A2,n−A3,n⋮λ−An,n⎤⎦⎥⎥⎥⎥⎥⎥⎥$$\lambda I-A=\left[\begin{array}{c}\begin{array}{ccccc}\lambda -A_{1,1}& -A_{1,2}& -A_{1,3}& \cdots & -A_{1,n}\\ 0& \lambda -A_{2,2}& -A_{2,3}& \cdots & -A_{2,n}\\ 0& 0& \lambda -A_{3,3}& \cdots & -A_{3,n}\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ 0& 0& 0& \cdots & \lambda -A_{n,n}\end{array}\end{array}\right]$$

带入行列式即可知道 det(λI−A)=∏(λ−Ai,i)${\displaystyle det(\lambda I-A)=\prod (\lambda -A_{i,i})}$ 。

也就是说，主对角线上所有的 Ai,i$A_{i,i}$ 都是 det(λI−A)=0$det(\lambda I-A)=0$ 的根。

$$$$

零化多项式

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

最小多项式：次数最低的零化多项式。

Cayley-Hamilton$\text{Cayley-Hamilton}$ 定理

特征多项式：p(λ)=|λI−A|$p(\lambda )=|\lambda I-A|$，λ$\lambda$ 定义域不止是 R$\mathbb{R}$，还可以是矩阵。

Cayley-Hamilton$\text{Cayley-Hamilton}$ 定理指出：矩阵的特征多项式也是它的零化多项式。

即令：

φ(λ)=det(λI−A)=λn+a1λn−1+⋯+an−1λ+an$$\phi (\lambda )=det(\lambda I-A)={\lambda }^n+a_1{\lambda }^{n-1}+\cdots +a_{n-1}\lambda +a_n$$

则有：

φ(A)=An+a1An−1+⋯+an−1A+an=O$$\phi (A)=A^n+a_1{A}^{n-1}+\cdots +a_{n-1}A+a_n=O$$

证明：

将 φ(λ)$\phi (\lambda )$ 改写为：

φ(λ)=(λ−λ1)(λ−λ2)⋯(λ−λn)$$\phi (\lambda )=(\lambda -{\lambda }_1)(\lambda -{\lambda }_2)\cdots (\lambda -{\lambda }_n)$$

由定理：任意的 n$n$ 阶矩阵都能相似为上三角矩阵 可知，存在可逆矩阵 P$P$，使得：

PAP−1=⎡⎣⎢⎢⎢⎢⎢⎢λ1∗λ2⋯⋱⋱∗⋮∗λn⎤⎦⎥⎥⎥⎥⎥⎥$$PA{P}^{-1}=\left[\begin{array}{cccc}{\lambda }_1& \ast & \cdots & \ast \\ & {\lambda }_2& \ddots & ⋮\\ & & \ddots & \ast \\ & & & {\lambda }_n\end{array}\right]$$

将 PAP−1$PA{P}^{-1}$ 代入 φ(λ)$\phi (\lambda )$ 得到：

φ(PAP−1)=(PAP−1−λ1I)(PAP−1−λ2I)⋯(PAP−1−λnI)$$\phi (PA{P}^{-1})=(PA{P}^{-1}-{\lambda }_{1}I)(PA{P}^{-1}-{\lambda }_{2}I)\cdots (PA{P}^{-1}-{\lambda }_{n}I)$$

计算：

⎡⎣⎢⎢⎢⎢⎢⎢0∗λ2−λ1⋯⋱⋱∗⋮∗λn−λ1⎤⎦⎥⎥⎥⎥⎥⎥×⎡⎣⎢⎢⎢⎢⎢⎢λ1−λ2∗0⋯⋱⋱∗⋮∗λn−λ2⎤⎦⎥⎥⎥⎥⎥⎥×⋯×⎡⎣⎢⎢⎢⎢⎢⎢λ1−λn∗λ2−λn⋯⋱⋱∗⋮∗0⎤⎦⎥⎥⎥⎥⎥⎥=O$$\left[\begin{array}{cccc}0& \ast & \cdots & \ast \\ & {\lambda }_2-{\lambda }_1& \ddots & ⋮\\ & & \ddots & \ast \\ & & & {\lambda }_n-{\lambda }_1\end{array}\right]\times \left[\begin{array}{cccc}{\lambda }_1-{\lambda }_2& \ast & \cdots & \ast \\ & 0& \ddots & ⋮\\ & & \ddots & \ast \\ & & & {\lambda }_n-{\lambda }_2\end{array}\right]\times \cdots \times \left[\begin{array}{cccc}{\lambda }_1-{\lambda }_n& \ast & \cdots & \ast \\ & {\lambda }_2-{\lambda }_n& \ddots & ⋮\\ & & \ddots & \ast \\ & & & 0\end{array}\right]=O$$

即 φ(PAP−1)=Pφ(A)P−1=O$\phi (PA{P}^{-1})=P\phi (A)P^{-1}=O$，故有 φ(A)=O$\phi (A)=O$

$$$$

求解特征多项式

带入 n$n$ 个数，求出得 det(xIn−A)$det(x{I}_n-A)$，得到 n$n$ 个矩阵，通过高斯消元可以 O(n3)$O(n^3)$ 地求出行列式。

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

$$$$

求解最小多项式

构造矩阵序列 ai=Ai$a_i=A^i$。

求出它的一个线性递推 ri$r_i$，即：

∑j=0mrjai−j=∑j=0mrjAi−j=(∑j=0mrm−jAj)⋅Ai−m=0∴∑j=0mrm−jAj=0$$\begin{gathered} {\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} \\ {\displaystyle \therefore \sum _{j=0}^m{r}_{m-j}{A}^j=0} \end{gathered}$$

所以可以由 ri$r_i$ 翻转得到 f(λ)$f(\lambda )$ 。

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

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

实际是计算标量序列 {uAiv}$\{u{A}^{i}v\}$ 的递推式，所以实际每次求出 uAi$u{A}^i$ 复杂度应为 O(n2)$O(n^2)$ 。

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

因此总复杂度为 O(n3)$O(n^3)$ 。

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

$$$$

求解稀疏方程组

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

Ax=b$Ax=b$，即 x=A−1b$x=A^{-1}b$ 。

求出 {Aib}$\{A^{i}b\}$ 线性递推式，反推出 A−1b$A^{-1}b$ 即可。

反推方法：

带入线性递推的 m$m$ 项，则 ∑i=0mAm−ib⋅ri=0$\sum _{i=0}^m{A}^{m-i}b\cdot r_i=0$

两边同乘 A−1$A^{-1}$，得到 A−1b⋅rm+∑i=0m−1Am−ibri=0$A^{-1}b\cdot r_m+\sum _{i=0}^{m-1}{A}^{m-i}b{r}_i=0$

求解矩阵 k 次幂

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

设矩阵 A$A$ 的一个零化多项式是 f(λ)$f(\lambda )$ ，显然，Ak$A^k$ 可以用一个多项式表示 Ak=∑k0wiAi$A^k=\sum _0^k{w}_i{A}^i$。

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

存在一种合法的表示是 Fk(x)=xk$F_k(x)=x^k$。

∵f(A)=0∴∀i,f(A)Ai=0$$\begin{gathered} \because f(A)=0 \\ \therefore \mathrm{\forall }i,f(A)A^i=0 \end{gathered}$$

所以对于任意实数 T$T$，Gk(x)=xk−Tf(x)$G_k(x)=x^k-Tf(x)$ 也合法，也就是相当于我们要求出 xk$x^k$ 对于 f(x)$f(x)$ 这个 n+1$n+1$ 多项式取模。

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

最后得到的 F(x)$F(x)$ 是一个 n$n$ 次多项式，带入就可以快速求出 Ak$A_k$，可以认为这个复杂度是受限于求解 A0,A1,⋯,An−1$A^0,A^1,\cdots ,A^{n-1}$ 的 O(n4)$O(n^4)$ 。

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

那么求解 B⋅A$B\cdot A$ 的过程是 O(n⋅e)$O(n\cdot e)$ 的，求解 A0,A1,⋯,An−1$A_0,A^1,\cdots ,A^{n-1}$ 的过程，是 O(n2e)$O(n^{2}e)$ 的。

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

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

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

求解常系数线性齐次递推

问题是要求数列 fi=∑nj=1aj⋅fi−j$f_i=\sum _{j=1}^n{a}_j\cdot f_{i-j}$ 。

给出 f0,f1,⋯,fn−1$f_0,f_1,\cdots ,f_{n-1}$，求第 k$k$ 项的值。

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

对于n=4$n=4$的情况，我们的转移矩阵。

A=⎛⎝⎜⎜⎜111a4a3a2a1⎞⎠⎟⎟⎟$$A=\left(\begin{array}{cccc}& & & a_4\\ 1& & & a_3\\ & 1& & a_2\\ & & 1& a_1\end{array}\right)$$

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

由

λIn−A=⎛⎝⎜⎜⎜λ−1λ−1λ−1−a4−a3−a2λ−a1⎞⎠⎟⎟⎟$$\lambda I_n-A=\left(\begin{array}{cccc}\lambda & & & -a_4\\ -1& \lambda & & -a_3\\ & -1& \lambda & -a_2\\ & & -1& \lambda -a_1\end{array}\right)$$

带入行列式最暴力的求法

枚举一个排列pi$p_i$，设排列p$p$的逆序对为f(p)$f(p)$，|A|=∑(−1)f(p)ΠAi,pi$|A|=\sum (-1{)}^{f(p)}\mathrm{\Pi }{A}_{i,p_i}$

实际上合法的排列只有n$n$个，就是

枚举pi=n$p_i=n$

那么

pj=⎧⎩⎨jnj−1j<ij=ij>i$$p_j=\{\begin{array}{rlr}j& & j<i\\ n& & j=i\\ j-1& & j>i\end{array}$$

当 i=n$i=n$ 时，(−1)f(p)ΠAi,pi=λn−a1λn−1$(-1{)}^{f(p)}\mathrm{\Pi }{A}_{i,p_i}={\lambda }^n-a_1{\lambda }^{n-1}$

当 i=1$i=1$ 时，f(p)=n−i$f(p)=n-i$

ΠAi,pi=(−1)n−i+1λi⋅an−i+1$\mathrm{\Pi }{A}_{i,p_i}=(-1{)}^{n-i+1}{\lambda }^i\cdot a_{n-i+1}$

(−1)f(p)ΠAi,pi=−λian−i+1$(-1{)}^{f(p)}\mathrm{\Pi }{A}_{i,p_i}=-{\lambda }^i{a}_{n-i+1}$

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

p(λ)=|λIn−A|=λn−a1λn−1−a2λn−2−⋯−an$p(\lambda )=|\lambda I_n-A|={\lambda }^n-a_1{\lambda }^{n-1}-a_2{\lambda }^{n-2}-\cdots -a^n$

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

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

类似求出 Ak$A^k$ 的过程，求出 Fk(x)modp(λ)$F_k(x)\mathrm{mod}p(\lambda )$

我们要求解 (S⋅Ak)n=∑n1[xi]F(x)(S⋅Ai)n$(S\cdot A^k{)}_n=\sum _1^n[x^i]F(x)(S\cdot A^i{)}_n$

而 (S⋅Ai)n=fi$(S\cdot A^i{)}_n=f_i$ 已知，求出 F(x)$F(x)$ 后直接带入即可

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