【线性代数】若尔当标准型的基础应用
ducati
·
·
科技·工程
Update on 2024.4.2：修改了最后一个 Theorem 的表述。
Application #1
令 v_0 \in \mathbb{R}^n 为列向量，A \in \mathbb{R}^{n \times n} 为线性变换矩阵。若 \forall i \in \mathrm{N}^{+} \ \text{s.t.} \ v_i = A v_{i - 1}，则有
v_n = A^n v_0
将 A 化为 Jordan 标准型
A = P^{-1} JP
则
v_n = P^{-1} J^n Pv_0
考虑 J 的每个 Jordan Block J_i，其主对角线元素均为 \lambda_i，阶为 c_i，则
J_{ixy}^n = {n \choose y - x} \lambda_i^{n-(y-x)}
显然存在多项式 f_{xy}(n) 满足 \deg(f_{xy}(n)) < c_i 且在 n \ge y-x 时有 \boldsymbol{\lambda^n f_{xy}(n) = J_{ixy}^n}。
代回 v_n = P^{-1} J^n Pv_0。同理，存在多项式 g_{ij}(n) 满足 \deg(g_{ij}(n)) < c_j 且
\boldsymbol{\sum_j \lambda_j^n f_{ij}(n) = v_{ni}}
可应用于齐次线性递推或 dp。
在绝大多数情况中，A 无重根，特征向量是 \mathbb{R}^n 的基底。
设 v_0 = \sum_{i = 1} ^ n t_i v_i，其中 t_i \in \mathbb{R}，v_i 为 A 的特征向量，那么
v_n = \sum_{i = 1} ^n t_i \lambda_i^n v_i
更进一步的，考虑以下三个逐步减弱的条件：
不难发现：上式不仅适用于最强的条件，也可推广至最弱的条件。
Application #2
定义谱半径（spectral radius）为所有特征根的最大模长，记作 \rho。
令 n 阶方阵 A 满足 A \in \mathbb{C}^{n \times n}。
Lemma：\rho(A) < 1 \implies \lim_{n \to +\infty} A^n = 0
Proof：设 J 为与 A 相似的 Jordan 标准型，令 J = P^{-1}AP，则
\begin{aligned} \lim_{n \to +\infty} A^n = 0 &\iff \lim_{n \to +\infty} P^{-1}J^nP = 0 \\ &\iff \lim_{n \to +\infty} J^n = 0 \end{aligned}
由于 P 可逆，最后一步等价变换成立。
考虑 J 的每个 Jordan Block J_i，其主对角线元素均为 \lambda_i，阶为 c_i，则
\begin{aligned} J_{ixy}^n &= {n \choose y - x} \lambda_i^{n-(y-x)} \\ &\le n^{y - x} \lambda_i^{n-(y-x)} \end{aligned}
令 p = y - x，则
\begin{aligned} (\lambda_i \neq 0) \lim_{n \to +\infty} n^p \lambda_i^{n - p} &= \frac {1} {\lambda_i^p} \lim_{n \to +\infty} n^p \lambda_i^n \\ &= 0 \end{aligned}
若 \lambda_i = 0，极限值仍为 0。
即 \lim_{n \to +\infty} J^n = 0。
Theorem：\lim_{n \to +\infty} A^n = 0 当且仅当 \rho(A) < 1。
Exercise：令矩阵 A 所有特征根构成的集合为 S，且特征根 \lambda 的几何重数、代数重数分别为 g(\lambda), a(\lambda)，请使用 S, g(\lambda), a(\lambda), \rho(\lambda) 写出 \lim_{n \to +\infty} A^n 存在的充要条件。