【线性代数】特征值、特征多项式与对角化

Bonely_Muffin · 2025-07-22 10:24:01 · 算法·理论

前言

学习时被 OI-wiki 比较抽象的定义和一些神秘博客折磨到了，遂有本文。

下文可能混淆“左乘矩阵 A”和“进行 A 矩阵对应的线性变换”两种表述，希望读者谅解。

本文中只研究方阵，即行数、列数相等的矩阵。

前置知识：线代基础（向量与矩阵，行列式，以及对线代的一些直观理解）。

十分推荐观看 3b1b 的线代合集。

特征值、特征向量

我们发现，有时在进行线性变换时，一些向量的方向并没有改变，只是在同一直线上伸缩了。显然，这些向量会更加容易研究。

如果对于方阵 A，存在非零向量 X 和常量 \lambda 满足

AX=\lambda X

则称 X 是矩阵 A 的一个特征向量，称 \lambda 是 X 对应的特征值。

将 X 压缩为零向量也认为是共线向量，因此特征值可以为 0，但规定特征向量不能是零向量。

一个特征值可以对应很多特征向量，比如与 X 共线的所有非零向量都是 \lambda 对应的特征向量。

为了研究特征值、特征向量需要满足什么条件，我们对上面的式子进行变换：

AX = \lambda I_n X

(\lambda I_n - A)X=0

由于 X 是非零向量，所以必须有 \det(\lambda I_n - A) = 0。接下来我们尝试用这个式子求解矩阵的特征值。

特征多项式

定义方阵 A 的特征多项式为

p_A(x) = \det(x I_n - A)

直观感受一下，它是这个方阵的行列式：

\begin{bmatrix} x-a_{11} & -a_{12} & -a_{13} & & -a_{1n}\\ -a_{21} & x-a_{22} & -a_{23} & \cdots & -a_{2n}\\ -a_{31} & -a_{32} & x-a_{33} & & -a_{3n}\\ & \vdots & & \ddots & \vdots\\ -a_{n1} & -a_{n2} & -a_{n3} & \cdots & x-a_{nn} \end{bmatrix}

很显然，p_A(x) 是一个 n 次多项式，最高次项的系数为 1。那么，p_A(x) 的 n 个根就是 A 的所有特征值。

（当然可能有重根，根的出现次数称为这个特征值的代数重数）

什么？你问怎么求这个矩阵的行列式？一般地，我们可以带入 x=0,1,2,\cdots,n 分别计算行列式，再进行插值，时间复杂度 O(n^4)；但是这个行列式也可以 O(n^3) 算出来。我们需要的工具名叫“相似变换”。

引理： P 为可逆方阵，则 \det(x I_n - A) = \det(x I_n - PAP^{-1}) .

证明是显然的：
=|x PI_nP^{-1} - PAP^{-1}|\\ =|P(x I_n-A)P^{-1}|\\ =|P|\cdot|P^{-1}|\cdot|xI_n -A|\\ =|xI_n-A|$. 把 $A$ 变换为 $PAP^{-1}$ 就称为相似变换，这两个矩阵称为相似矩阵。所以引理也可以表述为：**相似矩阵的特征多项式相同，特征值相同**。

那接下来我们的计划大概是这样的：对 A 进行相似变换，变成某种容易计算的方阵，再计算 \det(xI_n-A')。

我们对 A 使用魔改版高斯消元：在进行每种初等变换时，同时对矩阵进行对偶的变换（也就是左乘 P 的同时要右乘 P^{-1}）。把每种初等变换写成矩阵，再找一找它的逆，你就得到如下的变换法则：

把第 j 行减上第 i 行的 k 倍，再把第 i 列加上第 j 列的 k 倍。
把第 i 行和第 j 行互换，再把第 i 列和第 j 列互换。
然而并不需要 3。

只有上述的初等变换是合法的。那么有一个问题：我们高消的时候没法保证消成上三角矩阵，因为如果用第 i 行对第 j(j>i) 行消元，那么尚未消元的第 j 列会乘一个 k 倍加到第 i 列，从而“污染”掉消成 0 的元素。

虽然不能消成上三角，但是可以消成上海森堡矩阵，它长这样：

A' = \begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1(n-1)} & a_{1n} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2(n-1)} & a_{2n} \\ 0 & a_{32} & a_{33} & \cdots & a_{3(n-1)} & a_{3n} \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & a_{(n-1)(n-2)} & a_{(n-1)(n-1)} & a_{(n-1)n} \\ 0 & 0 & \cdots & 0 & a_{n(n-1)} & a_{nn} \end{bmatrix}

相比上三角，多了主对角线下方的一条次对角线也可以有值。

具体地，我们每次用 a_{i+1,i} ，消掉每个 j>i+1 行的第 i 个元素。这样的话，只会使第 j 列的内容加到第 i+1 列，从而保证我们的消元不被“污染”。时间复杂度 O(n^3)。

然后就可以求 \det(xI_n-A') 了，记 f_i(x) 是前 i 行 i 列子矩阵的行列式，且 f_0(x)=1。那么可以推出

f_i(x) = (x-a_{i,i})f_{i-1}(x) - \sum_{j=1}^{i-1} a_{j,i}(\prod_{k=j}^{i-1}a_{j+1,j})f_{j-1}(x)

很好写。加上多项式计算，时间复杂度也是 O(n^3)。

P7776 【模板】特征多项式

int a[N][N];
void Hess(){
    for(int i=1;i<n;i++){
        int p=-1;
        for(int j=i+1;j<=n;j++){
            if(a[j][i]) {p=j; break;}
        }
        if(p==-1) continue;
        if(p!=i+1){
            swap(a[p],a[i+1]);
            for(int k=1;k<=n;k++) swap(a[k][p],a[k][i+1]);
        }
        for(int j=i+2;j<=n;j++){
            ll rate=a[j][i]*qpow(a[i+1][i],mod-2)%mod;
            if(!rate) continue;
            for(int k=1;k<=n;k++) addt(a[j][k],mod-a[i+1][k]*rate%mod);
            for(int k=1;k<=n;k++) addt(a[k][i+1],a[k][j]*rate%mod);
        }
    }
}
int f[N][N];
int main(){
    n=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=read();
    Hess();
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int k=i-1;k>=0;k--){
            addt(f[i][k+1],f[i-1][k]);
            addt(f[i][k],ll(mod-a[i][i])*f[i-1][k]%mod);
        }
        ll mul=mod-1;
        for(int j=i-1;j>=1;j--){
            mul=a[j+1][j]*mul%mod;
            ll x=mul*a[j][i]%mod;
            for(int k=j-1;k>=0;k--){
                addt(f[i][k],x*f[j-1][k]%mod);
            }
        }
    }
    for(int i=0;i<=n;i++) printf("%d ",f[n][i]);
    puts("");

    return 0;
}

所以对于一般矩阵，求特征值是困难的，但求特征多项式是可做的。

那么特征多项式有什么用？

其实应用不多。首先，它可以 O(n^3) 算形如 (A+xB) 这个矩阵的行列式。

思路是把 \det(A+xB) 转化为求形如 \det(A'+xI_n) 的式子，然后就可做了。

我们有一个朴素的想法：如果 B 有逆，则

|A+xB| = \frac{|AB^{-1}+xI_n|}{|B^{-1}|}=|AB^{-1}+xI_n|\cdot|B|

两部分就都可做了。不幸的是， B 不一定存在逆。然而，我们可以尝试把 B 尝试化成对角阵。

注意到求行列式的时候，高消的自由度很高：每一步不管按行消元还是按列消元，行列式都不变。 本质上这是由 \det(AB)=\det(A)\det(B) 决定的，不管左乘、右乘倍加 (交换) 矩阵，都把行列式乘了 1(-1)。那么我们可以这样消元：

每步都要对 A 和 B 矩阵同步做同样的操作，来保证行列式不变。对于每一列，在 B 中尝试寻找主元。如果找到不为 0 的 b_{j,i}(j\geq i)，就把它提到 b_{i,i} 处；接下来，按行和按列消掉所有满足 j>i 的 b_{i,j} 和 b_{j,i}。

为什么这么消元？这是为找不到不为 0 的 b_{j,i} 铺垫：如果找不到，那么必然有第 i 列全为 0。这时并不代表行列式就是 0 ，因为还有 A 的存在。

那么我们可以把第 i 列整体乘以 x ，也就是把 A 的第 i 列移到 B 中，来强行让 B 的第 i 列存在主元，行列式也会乘以 x。当然，这样可能还是不存在主元。我们可以每次找不到主元都把 A 的内容移到 B 中，直到一共已经做了 n 次移动，也就是行列式的值乘了 n 次 x，这时就说明行列式只能为 0。

最后把 B 消成对角阵，就只用算 \det(A'+xI_n)，就可做了。时间复杂度 O(n^3)。

模版是qoj59。

学完可以做一下 [ABC323G] Inversion of Tree

还可以做 P6624 [省选联考 2020 A 卷] 作业题，加深对行列式的理解（这个好像和上文没什么关系……）

另外还有一个 Cayley–Hamilton 定理，内容是：任何一个矩阵的特征多项式都是它的零化多项式。也就是说，如果方阵 A 的特征多项式是 p_A(\lambda) = \lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_1\lambda+c_0，那么有

p_A(A)=A^n+c_{n-1}A^{n-1}+c_{n-2}A^{n-2}+\cdots+c_1A+c_0I_n = O_{n\times n}

其中 O_{n\times n} 为零矩阵。C-H 定理表明，任何一个矩阵都存在零化多项式，且零化多项式的次数不超过 n。

证明不会，感兴趣可以查一查。

基变换

即使是同样的向量或者矩阵，在不同的基底下表示也不同。那么自然地，我们就会考虑向量和矩阵如何在不同的基之间转换。

设一组新的基

P=\begin{bmatrix}p_1 & p_2 & p_3 & \cdots & p_n\end{bmatrix}

其中 p_1 到 p_n 都是列向量，p_i 表示 P 第 i 个基向量用原来的基底（通常为单位阵 I_n）的表示。

现在把用 P 表示的向量 v_p，变成我们的表示法 v。设 v_p = \begin{bmatrix}\lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \cdots \\ \lambda_n\end{bmatrix}，则

v_p = \lambda_1p_1 + \lambda_2p_2 + \lambda_3p_3 + \cdots + \lambda_np_n

显然地，

v=Pv_p

那么把我们表示法下的向量转化成 P 下的表示法，也是容易的，只需要

v_p=P^{-1}v

就行了。

再考虑一个问题：有一个线性变换 T（这里先不把它当矩阵，只把它当做一个符号就行……），它在 I_n 下表示为方阵 A。现在我们选另一组基 P ，这时这个变换表示为方阵 W。我们如何在基 P 下表示出变换 A？

可以这样思考：考虑任意一个向量 v，进行线性变换 T 后，得到的向量是 Av；我们也可以先把 v 给“翻译”成 P 下的向量，然后进行 W 变换，最后再把得到的向量给“翻译”回正常的向量，这三步后得到的向量就是 PWP^{-1}v。也就是说

A=PWP^{-1} \iff W=P^{-1}AP

这一段很绕，可以看 3b1b 的视频辅助理解。

对角化

刚刚讲基变换是为对角化做铺垫的。

注意到，假如 n 阶方阵 A 有 n 个不同的特征值，就可以找出 n 个线性无关的特征向量。如果我们选取这一组特征向量作为基底，那么每次进行变换 A 的时候，这一组基底都没有改变方向，只是伸缩了，伸缩倍数就是特征值！

也就是说，设这 n 个特征向量组成的基是 P 矩阵。那么，P^{-1}AP 就是一个对角阵。记 \Lambda=P^{-1}AP，那么有

\begin{bmatrix} \lambda_1 \\ & \lambda_2 \\ & & \lambda_3 \\ & & & \ddots \\ & & & & \lambda_n \end{bmatrix}

对角线上分别是 A 的 n 个特征值。

所以我们有对角化的两个式子，就是

A=P\Lambda P^{-1} \iff \Lambda=P^{-1}AP

这时候，如果我们需要大量进行 A 变换，正常的矩阵快速幂是 O(n^3 \log k) 的，但是对角阵的高次幂是好求的，是 O(n \log k) 的。所以我们可以先把基底变成 P，然后求对角阵 \Lambda=P^{-1}AP 的 k 次幂，最后再把基底变回来就行了。也就是

A^k = P \Lambda^k P^{-1}

（或者还有一种理解方法：由 A=P\Lambda P^{-1}，得 A^2=P\Lambda P^{-1}P\Lambda P^{-1} = P\Lambda^2P^{-1}，更高次幂同理。）

~~所以你就成功把矩阵快速幂从 O(n^3\log n) 优化到了 O(n^3)，还要求得能找到 n 个特征值和特征向量。~~

所以除非矩阵很特殊，要不然对角化就比较困难且 useless。

因此需要对角化的 OI 题也比较难出。感兴趣可以做一下 CF923E。

后记

题目比较少，如果找到会加进文章的。

笔者数学很烂，因此文中一些解释难免不够准确，还望读者海涵，也欢迎指正。

本文是蒟蒻的第一篇学习笔记，也算是一种赛博笔记本，供之后自己复习。同时如果你在读这篇文章，也希望它能帮助到你。

感觉线性代数算 oi 数学中比较简单的部分，因为结论偏多思维偏少，像线性基、矩阵树定理、LGV 引理、还有上文提到的特征多项式，都是把式子看懂，理解原理然后打一打板子就好了，没有特别的考验思维的地方。虽然如此，这两天学习线代也走了不少弯路。我们需要的是追根溯源，理解本质，理解结论“怎么来”“怎么用”。

到此完结撒花~