对角化不只是矩阵的分类;它把重复的或连续的线性演化化为标量问题。若 , 为对角矩阵,则每个幂 以及由 构成的任何表达式,都可由 的对角元算出。本单元把这个想法应用于三种标准情形:离散动力系统 与马尔可夫(Markov)链、线性递推关系,以及线性微分方程组 。它用到特征值与特征向量(5.1)、对角化与相似(5.2)以及 5.3 的对角化判别。
可对角化矩阵的幂
定理 5.5.1
(沿特征向量基计算幂)
设 ,其中 , 的列是特征向量 ,满足 。则对每个整数 ,
若 ,则以 为初始向量的 的解为
证明
(相邻因子相消)
在乘积 中,每个相邻的 都相消,剩下 。第二个结论:对 归纳得 ,再由线性即得公式。
系数 是 在特征向量基下的坐标,即 的解。
马尔可夫链
定义 5.5.2
(列随机矩阵)
若方阵 的所有元素非负且每列之和为 ,称 为列随机矩阵。若 是描述时刻 各状态分布的概率向量(元素非负且和为 ),而 是一步内由状态 转到状态 的概率,则 。
定理 5.5.3
(列随机矩阵的特征值)
设 为 的列随机矩阵。则 是 的特征值,并且 的每个特征值 (实或复)都满足 。此外 ( 为全 向量),故 :总概率守恒。
证明
(转置矩阵特征向量的最大分量)
各列和为 即 ,所以 是 的特征值。由 , 与 有相同的特征值。设 ,(可为复向量),取 使 最大。 的第 行的元素非负且和为 ,故
所以 。
证明透视
非负性与“和为一”用在何处
证明有两个关键步骤。第一, 与 有相同的特征值,所以只需研究 ;它的每一行(而非每一列)之和为 ,这把列条件转化为关于平均值的陈述。第二,取使 最大的下标 。 的第 行是一组非负且和为 的权,所以 是 各分量的加权平均,其模不会超过最大的模,由此得 ,而 才允许约去。非负性用在 这一步。若没有非负性,结论不成立: 的两列之和都是 ,特征值却是 与 。
定义 5.5.4
(平稳分布)
若概率向量 (元素非负且和为 )满足 ,就称 为列随机矩阵 的平稳分布。
定理 5.5.5
(收敛到平稳分布)
设 为列随机矩阵,在 上可对角化,特征值 的重数为一,其余特征值都满足 。则存在满足 且元素之和为 的向量 ,并且对每个初始向量 ,
证明
(特征向量基展开与总概率守恒)
令 ,展开 。则 ,因为 。由守恒,对所有 有 ,取极限得 。取 可知 ,故 的元素之和为 ,且 。
反例模式
若其他特征值的模不严格小于一,迭代未必收敛
断言:若 为列随机矩阵,在 上可对角化,且 是单特征值,则对每个概率向量 , 都收敛。当另有特征值的模为 时,这是错的。取对换矩阵 :它的各列之和为 ,特征值为 (特征向量 )与 (特征向量 ),所以可对角化,且 是单特征值。取 ,则 、,依此类推:序列来回振荡,没有极限。在展开式 中,项 并不趋于 。补救办法是要求其余每个特征值 都满足 。
线性递推与微分方程组
递推关系 可化为 的一阶方程组:
特征值是 的根;当两根相异时,由幂的公式得 的闭式。
对微分方程组 ,,设 ,令 。则 ,解耦为标量方程 ,解为 。
定理 5.5.6
(沿特征向量基解线性方程组)
若 有特征向量基 ,且 ,则 , 的唯一解为
证明
(直接求导与唯一性)
求导得 ,且 。唯一性:任一解 给出 ,满足 ,而 ,故解由 决定。
以上关于幂、收敛与微分方程组的结论都假设存在完整的特征向量基。若特征值有重复,应先用 5.3 与 5.4 的对角化判别。
例题
例题 5.5.7
(马尔可夫链的闭式轨道)
设 (每列之和为 )。迹为 ,行列式为 ,故 给出 与 。: 给出 ,故 。: 给出 。由 出发,解 :、 给出 、。因此
验算 :公式给出 ,直接计算 。平稳分布为 。
例题 5.5.8
(由特征向量基得出斐波那契(Fibonacci)数)
设 ,,。令 ,则 ,。特征值为 与 ( 的根),特征向量为 与 。写 :、 给出 。 的第二个分量为
验算 :,故 。
例题 5.5.9
(解耦的微分方程组)
设 ,。特征值为 ()与 ()。因 ,由特征向量基的解公式,
验算:,而 。
常见错误与细节
常见错误
(行随机的约定会使特征向量反转)
若转移矩阵是每一行(而非每一列)之和为 ,概率行向量的演化为 ,平稳向量是左特征向量。以 (第一个例题的矩阵转置)为例, 的右特征向量是 ,它并不是分布;平稳行向量是 :确实 。
常见错误
(特征向量还不是分布)
第一个例题中,消元得到 的 ,但它的元素之和是 而不是 。任何非零倍数都是特征向量,所以平稳分布是元素之和为 的那个倍数,即 。
常见错误
(离散的幂与连续的指数)
对 ,特征值 贡献 ,衰减需要 ;对 ,它贡献 ,衰减需要 。例如 给出 ,永不衰减,但 ; 在离散系统中给出 ,在连续系统中 却增长。
练习
快速检查
(求列随机矩阵 的平稳分布及另一个特征值。)
解答 · 引导解答
迹为 ,行列式为 ,故 ,特征值为 与 。: 给出 ;除以和 归一化,得平稳分布 。验算:。
快速检查
(解 ,,。)
解答 · 引导解答
特征方程为 ,根为 与 ,故 。条件 、 给出 ,。因此 。验算:,而 。
快速检查
(对 ,解 ,。)
解答 · 引导解答
为下三角矩阵,特征值为 与 。: 给出 。: 给出 。解 :,。故 。验算:,。
快速检查
(证明列随机矩阵 的特征值为 与 ,并说明当 时,何时对每个 都有 收敛。)
解答 · 引导解答
各列和为 ,故 是特征值;迹为 ,所以另一个特征值为 。当 时 ,且 当且仅当 。此时矩阵有两个相异特征值,可对角化,由收敛定理,对每个 都收敛。当 时矩阵是 , 平凡地收敛,但极限依赖于 ,不存在唯一的平稳分布。当 时矩阵是对换矩阵 ,除非 的两个分量相等,否则 振荡。因此对每个 都有 收敛当且仅当 ;而收敛到 乘以唯一的平稳分布当且仅当 。
快速检查
(设 ,求 的公式。)
解答 · 引导解答
特征值 的特征向量为 与 ,故 ,。于是