自动搬运

查看原文

来自洛谷，原作者为

	Gorenstein 人于天地中，似蝼蚁千万。

搬运于2025-08-24 22:33:00，当前版本为作者最后更新于2023-02-25 15:55:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

2023/5/15 upd：修改一处笔误。

这题现有的两篇题解中，SSerxhs 较为简略，而 Dementor 则稍混乱，对于一些关键处没有彻底解释到位。因此该题解期望能对特征多项式以及其能够通过本题的一类解法做一个较全面的介绍。

---

我们使用的大致思路是：

1. 利用相似矩阵特征多项式相同的性质将给定矩阵消成上海森堡矩阵。
2. 使用行列式展开定理递推计算它的特征多项式。

矩阵相似不变量

定义：设 $\bf A,B$ 皆为 $R$ 上 $n$ 级矩阵，若存在一个矩阵 $\bf P$ 使得 ${\bf P}^{-1}{\bf AP}={\bf B}$，则称矩阵 $\bf A,B$ 相似，记作 ${\bf A\sim B}$。

引理：相似矩阵的行列式相等。

$Proof.\quad$ 假设 ${\bf A\sim B}$，那么：

$$|{\bf B}|=\left|{\bf P}^{-1}\right||{\bf AP}|=\left|{\bf P}^{-1}\right||{\bf P|}|{\bf A}|=|{\bf A}| $$

此外，我们还可以证明矩阵的秩和迹在相似关系下也不变。它们称为矩阵的相似不变量；在本题中，我们只需利用行列式的不变性。

今将证明相似矩阵的特征多项式相等。

$Proof.\quad$ 假设 ${\bf A\sim B}$，那么：

$$|\lambda{\bf I}-{\bf A}|=\left|\lambda{\bf I}-{\bf P}^{-1}{\bf B}{\bf P}\right|=\left|{\bf P}^{-1}(\lambda{\bf I}-{\bf B}){\bf P}\right|=\left|{\bf P}^{-1}\right||\lambda{\bf I}-{\bf B}||{\bf P}|=|\lambda{\bf I}-{\bf B}| $$

所以我们可以利用左右乘初等矩阵及其逆来对矩阵进行消元，而保持特征多项式不变。

利用初等矩阵消元

令 ${\bf P}(j,i(k))$ 表示将 $\bf I$ 的第 $i$ 行的 $k$ 倍加到第 $j$ 行所得的矩阵，也即：

$${\bf P}(j,i(k))=\begin{pmatrix} 1&&&&&&\\ &\ddots&&&&&\\ &&1&&&&\\ &&\vdots&\ddots&&&\\ &&k&\cdots&1&&\\ &&&&&\ddots&\\ &&&&&&1 \end{pmatrix} $$

根据经典结论，设有 $n$ 级矩阵 ${\bf A}$，其行、列向量分别为 $\gamma_1,\cdots,\gamma_n$ 和 $\alpha_1,\cdots,\alpha_n$，那么：

$${\bf P}(j,i(k)){\bf A}=\begin{pmatrix} \gamma_1\\\vdots\\\gamma_i\\\vdots\\k\gamma_i+\gamma_j\\\vdots\\\gamma_n \end{pmatrix} $$$${\bf AP}(j,i(k))=(\alpha_1,\cdots,\alpha_i+k\alpha_j,\cdots,\alpha_j,\cdots,\alpha_n) $$

今将求其逆。根据矩阵求逆的初等变换法，其逆矩阵为：

$${\bf P}^{-1}(j,i(k))=\begin{pmatrix} 1&&&&&&\\ &\ddots&&&&&\\ &&1&&&&\\ &&\vdots&\ddots&&&\\ &&-k&\cdots&1&&\\ &&&&&\ddots&\\ &&&&&&1 \end{pmatrix}={\bf P}(j,i(-k)) $$

因此对于 ${\bf A}$ 和初等矩阵 ${\bf P}$，构造相似矩阵 ${\bf P}{\bf AP}^{-1}$ 对 $\bf A$ 进行消元。它是对 ${\bf A}$ 依次进行初等行变换和列变换的结果，其和高斯消元唯一的区别就是：在将第 $i$ 行的 $k$ 倍加至第 $j$ 行后，还需将第 $j$ 列的 $-k$ 倍加至第 $i$ 列。

其余几种初等行变换也需要进行类似修改。

而如果我们将矩阵消成上海森堡形式，则对于每一个 $i$，我们操作的行是 $i+1$，相应的列的改变也到 $i+1$ 列为止。从而乘上矩阵 ${\bf P}^{-1}$ 的过程不会污染已经完成消元的部分。

递推计算矩阵的特征多项式

循 OI-wiki 的记号。若我们已经消元得到矩阵 $\bf H$ 为：

$${\bf H}_n=\begin{pmatrix} \alpha_1&h_{12}&h_{13}&\cdots&h_{1n}\\ \beta_2&\alpha_2&h_{23}&\cdots&h_{2n}\\ &\ddots&\ddots&\ddots&\vdots\\ &&\ddots&\ddots&h_{n-1,n}\\ &&&\beta_n&\alpha_n \end{pmatrix} $$

那么就有：

$$f_n(\lambda)=|\lambda{\bf I}_{n\times n}-{\bf H}_n|=\begin{vmatrix} x-\alpha_1&-h_{12}&-h_{13}&\cdots&-h_{1n}\\ -\beta_2&x-\alpha_2&-h_{23}&\cdots&-h_{2n}\\ &\ddots&\ddots&\ddots&\vdots\\ &&\ddots&\ddots&-h_{n-1,n}\\ &&&-\beta_n&x-\alpha_n \end{vmatrix} $$

若将其按最后一行展开，便得到：

$$f_n(\lambda)=(x-\alpha_n)f_{n-1}(\lambda)+\beta_n\begin{vmatrix} x-\alpha_1&-h_{12}&\cdots&-h_{1,n-2}&-h_{1n}\\ -\beta_2&x-\alpha_2&\cdots&-h_{2,n-2}&-h_{2n}\\ &\ddots&\ddots&\vdots&\vdots\\ &&\ddots&x-\alpha_{n-2}&-h_{n-2,n}\\ &&&-\beta_{n-1}&-h_{n-1,n} \end{vmatrix} $$

把右边这个行列式按最后一列展开。我们发现对于一个 $-h_{n-i,n}$ 项，其余子式皆形如：

$$\begin{vmatrix} \\\\ &&\big[\lambda{\bf I}_{(n-i-1)\times(n-i-1)}-{\bf H}_{n-i-1}\big]\\ \\ \\ &&&\beta_{n-i+1}&\cdots\\ &&&&\ddots&\vdots&\vdots\\ &&&&&-\beta_{n-2}&\vdots\\ &&&&&&-\beta_{n-1} \end{vmatrix} $$

也即左上角是已经出现过的 $n-i-1$ 级 $f_{n-i-1}(\lambda)$ 代表的子矩阵，它的右下的主对角线上元素为 $\beta_{n-i},\cdots,\beta_{n-1}$，该主对角线以下部分的元素皆零。那么根据分块矩阵的行列式的性质，它等于：

$$f_{n-i-1}(\lambda)\prod_{j=n-i+1}^{n-1}\beta_j$$

从而最终结果为：

$$f_n(\lambda)=(x-\alpha_n)f_{n-1}(\lambda)-\sum_{i=1}^{n-1}f_{n-i-1}(\lambda)\left(\prod_{j=n-i+1}^{n}\beta_{j}\right)h_{n-i,n} $$

据此递推即可。