定义
设(A)是(n)阶方阵，如果存在数(lambda)和(n)阶非零列向量(x)满足
称(lambda)为此方阵的特征值 (x)为此方阵的特征向量
由于(x)不为0 所以(|lambda ext{I} - ext{A} |=0)
证明：
考虑(Mx = 0 Leftrightarrow |M| = 0 (x e 0))
显然(x = 0)是一个解，满秩对应唯一解，因为此时(x)是非0解，所以不止一个解，代表(M)不是满秩，即(|M|=0)
记 $ f(lambda) = |lambda ext{I} - ext{A}| $ 这是一个关于 $ lambda $ 的 $ n $ 次多项式（考虑行列式定义 会经过主对角线0~n次不等）称其为特征多项式 (f(lambda) = 0) 也就是它的特征方程 （ n次方程）
根据定义，特征方程的(n)个根就是原方阵的(n)个特征值
定理
Cayley-Hamilton定理
考虑特征多项式(P(x) = x^n + b_1 x^{n-1} + ... +b_n) 有(P(A) = A^n + b_1A^{n-1}+...+b_n = 0)
证明：考虑(|lambda ext{I} - ext{A}|=0) (P(lambda)=0 ightarrow P(lambda ext{I}) = 0 ightarrow P( ext{A}) =0)
（因为特征值带入进去是特征方程的根所以(P(lambda)=0)）
举例
常系数线性递推
考虑转移矩阵
(C = egin{bmatrix} b_1&b_2&dots&b_k \ 1& 0& dots &0 \ vdots&& ddots & vdots\ 0 &dots&1&0end{bmatrix})
按定义代入可解得多项式
(f(lambda) = |lambda ext{I} -C| = egin{bmatrix} lambda -b_1&-b_2&dots&-b_k \ -1& lambda& dots &0 \ vdots&& ddots & vdots\ 0 &dots&-1&lambdaend{bmatrix})
考虑从最后一行展开(f_k(lambda) = lambda f_{k-1}(lambda) - b_k)
（考虑最后一列选择什么 如果选择(lambda)则可以按照定义接着选下去，若是选择((-b_k))的话会有((-1)^{k-1} (-1)^{k-1})的贡献（前面是强制选的 后面是产生了(k-1)逆序对）
又因为(f_1(lambda)=lambda - b_1) 于是有 (f_k(lambda) = lambda^k - b_{1}lambda^{k-1} - dots - b_k)
我们用快速幂求递推式的时候瓶颈在于求 (C^n) 接下来考虑如何快速求这个玩意
根据Hamilton-Cayley定理（上面那个）有(f(C)=C^k - b_1C^{k-1} -b_2C^{k-2} -... -b_k ext{I} = 0)
因此 求(C^ n)就快了 因为有(f(C)=0) 所以我们考虑让(C^n)对(f(C))取模（这里指多项式取模）
这样 我们就只需要知道(I,C,...,C^{k-1})就可以了
但实际上 我们真的需要知道吗？
考虑我们求的(a_n) 只是列向量的第一项 把整个柿子写出来
(v_0)是我们的初始序列 由定义可以得到(v0)的第一项是(a_0)，(C^{k-1}v_0)的第一项是(a_{k-1})
（前提是这是前k项也满足这个递推关系 不然就需要预处理出前2k项）
所以预处理前(k)项就可以快速求了
现在就分为了两个子问题 1.求系数(c_i) 2.快速求前k项
-
其实就是(x^n mod f(x))
类似自然数快速幂，用NTT优化多项式取模就可以做到(O(k ext{log}k ext{log}n))
-
快速求(k/2k)项
如果没有给出前k项的话 考虑利用生成函数 原数列是(G) 转移序列是(A) 可以得到(G = GA +r) （r是常数项）
移项得到(G = frac{r}{1-A}) 在模(x^{k+1})意义下做
如果要求(2k)项的话是没有快速做法的 至少可以分治(NTT)做到(O(klg^2k))（至少我没找到 如果找到了的话请戳我/kel 超级感谢）
More Advanced——矩阵对角化
利用了HC定理 我们在已知特征多项式的前提下能快速求特殊矩阵高次幂了 那么我们是否能做到求任意的矩阵高次幂了呢？矩阵对角化就可以让我们来快速计算高次幂
Prob0.对角矩阵(diag(a_1,a_2,dots,a_k))的(n)次幂
考虑(diag(a_1,a_2,dots,a_k)^n = diag(a_1^n,a_2^n,dots,a_k^n))
所以这玩意超级好求
那么肯定不是所有矩阵都能做到快速求对角矩阵（暴力是(O(k^3))） 我们考虑怎么办
前缀知识——桥函数
先讲个简单的玩意，函数迭代。
考虑(f(x)=3x+4) 快速求(f^{(n)}(x))
考虑构造桥函数(phi(x)=x-2) 有(phi^{-1}(x)=x-2) 且(f(x)=3(x+2)-2) 记(g(x)=3x) 有(f(x) = phi(g(phi^{-1}(x)))=phi circ g circ phi^{-1}(x))
（(circ)是函数复合 有结合律 无交换律【应该显然】）
于是(f^{(2)}=fcirc f=phi^{-1} circ g circ phi circ phi^{-1} circ g circ phi^{-1}=phi^{-1} circ g^{(2)} circ phi^{-1})类似可以推出
(f^{(n)}=phi^{-1} circ g^{(n)} circ phi^{-1}) 对于(g)可以快速计算 此时(phi)函数起到的桥接作用 我们称(g)和(f)相似
既然函数可以这么做到 我们考虑矩阵能否这么做
类似的有记矩阵( ext{A})与矩阵( ext{B})相似为( ext{A} sim ext{B}) 若( ext{A} sim ext{B})用(Phi)桥接的话 则有( ext{A}^{n} = Phi^{-1} cdot ext{B}^{n} cdot Phi)
定理
(n)阶方阵可对角化的充要条件时( ext{A})有(n)个线性无关的特征向量
结论
(Phi = [v_1 v_2 cdots v_n])
((v_i)是第(i)个线性无关的列特征向量)
证明
（(lambda_i)是对应(v_i)的特征值 原因见全文第一句话）
于是有整个柿子(=diag(lambda_1,cdots,lambda_n))
你以为你学会了对角化你就能算所有高次幂辣？你还是(naddot{imath}ve)了
事实上对于大部分矩阵你根本求不出来特征值和特征向量！
如果需要例题的话可以看CF947E 综合了线代特征系统的一道好题 具体的我懒得写了 可以戳sundz的博客