L22-对角化和A的幂

参考

Unit II: Least Squares, Determinants and Eigenvalues - Diagonalization and Powers of A | pdf
课本章节：Read Section 6.2 in the 4^th or 5^th edition.
练习题：L22-对角化和A的幂-习题集

矩阵对角化

对于 $n \times n$ 矩阵 $A$ 如果具有 $n$ 个线性独立的特征向量，则可以通过以下公式将矩阵「变成」对角矩阵，该过程称为矩阵的对角化 diagonalization

S^{-1}AS=\Lambda

以上公式中矩阵 $S$ 是由 $n$ 个线性独立的特征向量作为列向量所构成的，矩阵 $\Lambda$ 是 $n$ 个特征值作为对角线上的元素的方阵（其他元素为 $0$ ）

注意

矩阵的对角化需要满足一个前提：矩阵 $A$ 具有 $n$ 个线性独立的特征向量

这样由 $n$ 个线性独立的特征向量作为列向量所构成的矩阵 $S$ 才是可逆矩阵，才存在矩阵 $S^{-1}$ ，以上公式才成立

证明

如果矩阵 $A$ 具有 $n$ 个线性独立的特征向量，它们分别为（列向量） $x_{1}, x_{2}, \dots x_{n}$ ，将它们构成矩阵 $S$ ，称作特征向量矩阵 eigenvector matrix

那么对于两个矩阵相乘 $AS$ 可以得到

AS=A \begin{bmatrix} x_{1} & x_{2} & \dots & x_{n} \end{bmatrix}

根据特征向量的定义，特征向量满足等式 $Ax=\lambda x$

所以以上等式（以矩阵与列向量相乘的角度考虑）可以进行以下转换

\begin{aligned} AS&=A \begin{bmatrix} x_{1} & x_{2} & \dots & x_{n} \end{bmatrix} \\ &= \begin{bmatrix} \lambda_{1} x_{1} & \lambda_{2} x_{2} & \dots & \lambda_{n} x_{n} \end{bmatrix} \end{aligned}

再将以上的结果矩阵进行分解，（通过对角矩阵）提取出各向量前面的系数

\begin{aligned} AS&=A \begin{bmatrix} x_{1} & x_{2} & \dots & x_{n} \end{bmatrix} \\ &= \begin{bmatrix} \lambda_{1} x_{1} & \lambda_{2} x_{2} & \dots & \lambda_{n} x_{n} \end{bmatrix} \\ &= \begin{bmatrix} x_{1} & x_{2} & \dots & x_{n} \end{bmatrix} \begin{bmatrix} \lambda_{1} & 0 & \dots & 0 \\ 0 & \lambda_{2} & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \dots & \lambda_{n} \end{bmatrix} \\ &= S \Lambda \end{aligned}

将由一系列的特征值 $\lambda$ 所构成的对角矩阵记作 $\Lambda$ （采用符号 $\Lambda$ 因为它是 $\lambda$ 的大写形式），称作特征值矩阵 eigenvalue matrix

然后在以上等式 $AS=S\Lambda$ 两边同时乘上逆矩阵 $S^{-1}$ ，即可证得

S^{-1}AS=S^{-1}S\Lambda=\Lambda

以上公式也可以写成矩阵分解的形式 $A=S \Lambda S^{-1}$

其他类型的分解

在前面的章节里，也有对矩阵 $A$ 进行不同类型的分解：

使用消元算法，将矩阵 $A$ 分解为 $A=LU$ ，其中 $L$ 和 $U$ 都是对角矩阵
使用正交算法，将矩阵 $A$ 分解为 $A=QR$ 其中 $Q$ 是正交矩阵（由一系列的标准正交（列）向量 $q_{i}$ 所构成的矩阵）， $R$ 是上三角矩阵

当矩阵 $A$ 的特征值 $\lambda_{i}$ 互不相同时（即没有重复的特征值），则矩阵 $A$ 必有 $n$ 个相互线性独立的特征向量（该矩阵 $A$ 可以对角化 diagonalizable）

提示

对于以上定理课堂上并没有证明，可以查阅书籍上的相关章节

大部分矩阵都满足有 $n$ 个相互线性独立的特征向量，所以在以下章节里都是假定了矩阵满足这个前提条件

而对于矩阵存在重复特征值时，则矩阵 $A$ 不一定存在 $n$ 个线性独立的特征向量，需要计算出具体的特征向量才可以判断

例如对于单位矩阵 $I$ （它也是一个对角矩阵，其特征值就是对角线上的元素；也可以通过求解特征方程 $det(I-\lambda I)=0$ 可以得到矩阵的所有特征值），具有的特征值 $n$ 个相同的特征值 $\lambda_{1}=\lambda_{2}=1$
将特征值 $\lambda_{1}=1$ 代入到方程 $(I - \lambda I)x=0$ 求出特征向量
由于（不可逆矩阵） $n \times n$ 的零矩阵的自由变量有 $n$ 个，所以可以得到 $n$ 个特解（列向量），而且它们是线性独立的
即对于单位矩阵 $I$ 有 $n$ 个线性独立的特征向量，所以单位矩阵 $I$ 可以进行对角化
而对于以下 $2 \times 2$ 对角矩阵，具有两个相同的特征值 $\lambda_{1}=\lambda_{2}=2$ $A= \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}$
（也可以通过求解特征方程 $det(A-\lambda I)=0$ 可以得到矩阵的所有特征值）
将特征值 $\lambda_{1}=2$ 代入到方程 $(A - \lambda I)x=0$ 求出特征向量 $(A-2I)x= \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}x =0$
其中一个特解是 $x=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$
由于（不可逆矩阵） $A-2I$ 的自由变量只有 $1$ 个，所以只需要 $1$ 个特解就可以张成方程组的通解，所以对于特征值 $\lambda=2$ 的特征向量是 $x=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$
对于 $\lambda_{2}=1$ 也是得到同样的特解
即对于以上例子没有足够的（需要 $2$ 个）线性独立的特征向量，所以矩阵 $A$ 无法进行对角化

矩阵对角化的应用

矩阵的幂

已知特征向量满足 $Ax=\lambda x$ 求矩阵 $A^{2}$ 的特征值和特征向量

说明前提

这里假定了矩阵 $A$ 具有 $n$ 个相互线性独立的特征向量

根据矩阵 $A$ 特征向量所满足的等式，可以得到

\begin{aligned} A^{2}x&=A(Ax) \\ &=A(\lambda x) \\ \end{aligned}

由于 ${\color{Red}\lambda }$ 是矩阵 $A$ 的特征值（常量），可以提到等式的最前面，以上等式可进一步变换

\begin{aligned} A^{2}x&=A(Ax) \\ &=A({\color{Red}\lambda } x) \\ &={\color{Red}\lambda } (Ax) \\ &=\lambda (\lambda x) \\ &=\lambda^{2} x \end{aligned}

观察以上等式的形式 $A^{2}x=\lambda^{2}x$ ，将 $A^{2}$ 看作一个整体（矩阵），满足特征向量的等式，则其中 $\lambda^{2}$ 就是矩阵 $A^{2}$ 的特征值，特征向量是 $x$

由于等式 $A^{2}x=\lambda^{2}x$ 是由等式 $Ax=\lambda x$ 导出的，所以其中的特征向量 $x$ 满足这两个等式，即矩阵 $A^{2}$ 和 $A$ 的特征向量相同

已知 $Ax=\lambda x$ 可得 $A^{2}x=\lambda^{2}x$ ，即矩阵 $A$ 的特征值是 $\lambda$ , 特征向量是 $x$ ；而矩阵 $A^{2}$ 的特征值进行相应的变换，变成 $\lambda^{2}$ ，而特征向量不变，也是 $x$

从矩阵分解（对角化）的角度来考虑，也会得到类似的结论：根据矩阵根据对角化公式，可以将矩阵 $A$ 分解为 $A=S \Lambda S^{-1}$

那么对于 $A^{2}$ 可以得到

\begin{aligned} A^{2}&=(S \Lambda S^{-1})(S \Lambda S^{-1}) \\ &=S \Lambda {\color{Red}S^{-1}S } \Lambda S^{-1} \\ &=S \Lambda {\color{Red}I } \Lambda S^{-1} \\ &=S \Lambda^{2} S^{-1} \end{aligned}

对比 $A=S \Lambda S^{-1}$ 和 $A=S \Lambda^{2} S^{-1}$ ，可知在分解结果中由特征向量构成的矩阵 $S$ 在两个等式中都不变；而由特征值构成的对角矩阵 $\Lambda$ ，在矩阵 $A$ 的分解结果中是 $\Lambda$ ，而在矩阵 $A^{2}$ 的分解结果中变成了 $\Lambda^{2}$

具体到矩阵 $\Lambda$ 里的每个元素而言，它们实际上也是变成平方

\begin{bmatrix} \lambda_{1} & 0 & \dots & 0 \\ 0 & \lambda_{2} & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \dots & \lambda_{n} \end{bmatrix} \Rightarrow \begin{bmatrix} \lambda_{1}^{2} & 0 & \dots & 0 \\ 0 & \lambda_{2}^{2} & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \dots & \lambda_{n}^{2} \end{bmatrix}

以上的结论/规律其实可以拓展到更高阶，即已知矩阵 $A$ 分解为 $A=S \Lambda S^{-1}$ ，则对于矩阵 $A^{k}$ 可以分解为 $A^{k}=S \Lambda^{k} S^{-1}$ ，其中 $S$ 不变， $\Lambda$ 变成 $k$ 次方

使用以上等式 $A^{k}=S \Lambda^{k} S^{-1}$ 可以对理解/计算/分析矩阵的幂有更好的方法

例如当高阶矩阵 $A^{k}$ 随着 $k$ 增大，趋同于零矩阵，可以知道原矩阵 $A$ 的特征值 $\lambda$ 满足的条件

根据矩阵的幂的分解公式 $A^{k}=S \Lambda^{k} S$ 可知 $S$ 并不随 $k$ 变化，所以造成 $A^{k}$ 随 $k$ 变化的是矩阵 $\Lambda$ ，它也是随着 $k$ 增大趋同于零矩阵

由于特征值矩阵 $\Lambda$ 是由一系列的特征值 $\lambda_{i}$ 作为对角元素（其他元素为 $0$ ）所构成的，那么可得 $\Lambda^{k}$ 的形式如下

\begin{bmatrix} \lambda_{1}^{k} & 0 & \dots & 0 \\ 0 & \lambda_{2}^{k} & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \dots & \lambda_{n}^{k} \end{bmatrix}

需要让 $\Lambda^{k}$ 随着 $k$ 增大趋同于零矩阵，实际上就是要让矩阵对角线上的每个元素 $\lambda_{i}^{k}$ 随着 $k$ 增大趋同于 $0$

即当 $k \to \infty$ 时，要让 $\lambda_{i}^{k} \to 0$ 成立，则 $\lambda_{i}$ 满足的条件是 $\left | \lambda_{i} \right | < 1$

等比递推关系式

差分方程

Recurrence relation 递推关系式（也称作 Difference equation 差分方程）是一种递推地定义一个序列的方程式，即序列的每一项目被定义为前若干项的函数

其中一阶差分方程是指递推式中，只包含前后的两项关系，例如 $x_{n}=kx_{n}$ ；而二阶差分方程是指递推式中，包含前后共计三项的关系，例如斐波那契数是由递推关系 $x_{n+2}=x_{n+1}+x_{n}$ 所定义的

使用矩阵的幂的分解公式，可以一阶对等比递推公式进行「拆解」简化，以求出通项公式

向量 $u_{k}$ 满足差分方程 $u_{k+1}=Au_{k}$ ，且已知首项是向量 $u_{0}$ ，可以用矩阵 $A$ 的特征值和特征向量表达向量 $u_{k}$ 的通项公式

说明

这里假定了一个前提是矩阵 $A$ 具有 $n$ 个相互线性独立的特征向量

由差分方程 $u_{k+1}=Au_{k}$ 可知向量 $u_{k}$ 和矩阵 $A$ 是可以相乘的，那么向量 $u_{k}$ 的维度（元素数量）和矩阵 $A$ 的列数是相同的

另外一个未提及的隐藏前提是，在涉及行列式的课程和问题中，都默认所研究的矩阵为方阵

所以可以简单地称作向量 $u_{k}$ 和矩阵 $A$ （列和行）的「维度」是相同的

由于矩阵 $A$ 具有 $n$ 个相互线性独立的特征向量 $x_{1}, x_{2} \dots x_{n}$ ，所以它们可以张成（矩阵 $A$ 所在的） $n \times n$ 向量空间，即通过它们的线性组合可以得到该空间中的任何一个向量

（假如在计算矩阵 $A$ 的特征向量时，都采用单位向量作为特解）那么 $n$ 维的向量 $u_{0}$ （它在 $n \times n$ 向量空间中）可以「分解」这 $n$ 个单位向量（特征向量）的线性组合

u_{0}=c_{1}x_{1}+c_{2}x_{2}+\dots+c_{n}x_{n}

其中 $c_{1}, c_{2}, \dots c_{n}$ 是向量线性组合时的相应系数

先考察 $Au_{0}$ 的分解情况

\begin{aligned} Au_{0}&=A(c_{1}x_{1}+c_{2}x_{2}+\dots+c_{n}x_{n}) \\ &=c_{1}Ax_{1}+c_{2}Ax_{2}+\dots+c_{n}Ax_{n} \end{aligned}

根据特征向量所满足的等式 $Ax=\lambda x$ ，所以上式可以进一步变换

\begin{aligned} Au_{0}&=c_{1}{\color{Red}Ax_{1} }+c_{2}{\color{Red}Ax_{2} }+\dots+c_{n}{\color{Red}Ax_{n} } \\ &=c_{1}{\color{Red}(\lambda_{1}x_{1}) }+c_{2}{\color{Red}(\lambda_{2}x_{2}) }+\dots+c_{n}{\color{Red}(\lambda_{n}x_{n}) } \end{aligned}

再进一步考察 $A^{2}u_{0}$ 的分解情况

由于 $A^{2}u_{0}=A(Au_{0})$ ，所以可以将以上 $Au_{0}$ 的分解结果代入得到

\begin{aligned} A^{2}u_{0}&=A(Au_{0}) \\ &=A(c_{1}\lambda_{1}x_{1}+c_{2}\lambda_{2}x_{2}+\dots+c_{n}\lambda_{n}x_{n}) \\ &=c_{1}\lambda_{1}Ax_{1}+c_{2}\lambda_{2}Ax_{2}+\dots+c_{n}\lambda_{n}Ax_{n} \end{aligned}

同样根据特征向量所满足的等式 $Ax=\lambda x$ 进一步变换

\begin{aligned} A^{2}u_{0}&=c_{1}\lambda_{1}{\color{Red}Ax_{1} }+c_{2}\lambda_{2}{\color{Red}Ax_{2} }+\dots+c_{n}\lambda_{n}{\color{Red}Ax_{n} } \\ &=c_{1}\lambda_{1}{\color{Red}(\lambda_{1}x_{1}) }+c_{2}\lambda_{2}{\color{Red}(\lambda_{2}x_{2}) }+\dots+c_{n}\lambda_{n}{\color{Red}(\lambda_{n}x_{n}) } \\ &=c_{1}\lambda_{1}^{{\color{Red}2}}x_{1}+c_{2}\lambda_{2}^{{\color{Red}2}}x_{2}+\dots+c_{n}\lambda_{n}^{{\color{Red}2}}x_{n} \end{aligned}

依次类推……

可得 $A^{k}u_{0}$ 的分解结果

\begin{aligned} A^{k}u_{0}&=A(A^{k-1}u_{0}) \\ &=A(A(A^{k-2}u_{0})) \\ &=A(A(\dots({\color{Violet}Au_{0} }))) \\ &=A(A(\dots({\color{Violet}c_{1}\lambda_{1}x_{1}+c_{2}\lambda_{2}x_{2}+\dots+c_{n}\lambda_{n}x_{n} }))) \\ &=c_{1}\lambda_{1}^{{\color{Red}k }}x_{1}+c_{2}\lambda_{2}^{{\color{Red}k }}x_{2}+\dots+c_{n}\lambda_{n}^{{\color{Red}k }}x_{n} \end{aligned}

根据递推公式 $u_{k+1}=Au_{k}$ 以及首项 $u_{0}$ 可知 ${\color{Red}u_{k}=A^{k}u_{0} }$

所以 $u_{k}$ 的通项公式为

\begin{aligned} u_{k}&=A^{k}u_{0} \\ &=A^{k}(c_{1}x_{1}+c_{2}x_{2}+\dots+c_{n}x_{n}) \\ &=c_{1}\lambda_{1}^{k}x_{1}+c_{2}\lambda_{2}^{k}x_{2}+\dots+c_{n}\lambda_{n}^{k}x_{n} \end{aligned}

提示

还可以利用对角矩阵，将以上长串的等式写成简短的形式

\begin{aligned} u_{k}&=A^{k}u_{0} \\ &=c_{1}\lambda_{1}^{k}x_{1}+c_{2}\lambda_{2}^{k}x_{2}+\dots+c_{n}\lambda_{n}^{k}x_{n} \\ &=\Lambda^{k}SC \end{aligned}

其中各矩阵的构成是

特征值矩阵 $\Lambda$ ：以特征值 $\lambda_{i}$ 作为对角线上的元素（其他元素都是 $0$ ）构成
特征向量矩阵 $S$ ：将特征向量 $x_{i}$ 作为列向量构成
系数矩阵 $C$ ：将系数 $c_{i}$ 作为对角线上的元素（其他元素都是 $0$ ）构成

斐波那契数列

斐波那契数列是 $0, 1, 1, 2, 3, 5, 8, 13, \dots$ 所满足的递推公式是 $F_{k+2}=F_{k+1}+F_{k}$ 求出通项公式

由于递推公式是 $F_{k+2}=F_{k+1}+F_{k}$ 是二阶差分方程，（为了可以使用矩阵的幂的分解公式进行求解）需要转变矩阵形式而且是一阶的差分方程，所以构建以下等式组

\begin{aligned} \left\{\begin{matrix} F_{k+2}=F_{k+1}+F_{k} \\ F_{k+1}=F_{k+1} \end{matrix}\right. \end{aligned}

以上等式组可以写成矩阵的形式

\begin{bmatrix} F_{k+2} \\ F_{k} \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}

令 $u_{k}=\begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}$ ，则以上等式可以写成

u_{k+1}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} u_{k}

通过以上的变换将二阶差分方程转换为一阶差分方程，然后就可以使用前一小节的结论先求出 $u_{k}$ 通项公式，再求得 $F_{k}$ 的通项公式

首先确保（以上变换得到的一阶差分方程中的矩阵） $A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ 满足矩阵分解的前提
说明
由于它具有两个不同的特征值 $\lambda_{1}=1$ 和 $\lambda_{2}=0$ ，所以该矩阵具有两个不同的特征向量，可以用它们的线性组合来表示数列的第一项 $u_{0}=c_{1}x_{1}+c_{2}x_{2}$

那么接下来的关键就是求出首项的分解等式中的各个特征向量（以及相应的系数）
可以通过求解特征方程 $det(A-\lambda I)=0$ 得到矩阵的所有特征值 $\begin{aligned} det(A-\lambda I) &= \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix} \\ &=\lambda^{2}-\lambda-1 \\ &=0 \end{aligned}$
解得 $\lambda_{1}=\cfrac{1}{2}(1+\sqrt{5})\approx 1.618$ 或 $\lambda_{2}=\cfrac{1}{2}(1-\sqrt{5})\approx -0.618$
再将上一步所求出的特征值分别带入方程 $(A-\lambda I)x=0$ 求出特解（特征向量）
这里通过直接观察方程的结构特点 $(A-\lambda I)x= \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix}x$
可以推导出方程的解的结构为 $x=\begin{bmatrix} \lambda \\ 1 \end{bmatrix}$
将上一步所求出的 $\lambda_{1}$ 和 $\lambda_{2}$ 分别代入，可得对应的特解（特征向量）为 $x_{1}=\begin{bmatrix} \lambda_{1} \\ 1 \end{bmatrix}$ 和 $x_{2}=\begin{bmatrix} \lambda_{2} \\ 1 \end{bmatrix}$
然后再将以上求得的特征向量 $x_{1}$ 和 $x_{2}$ 代入首项的分解等式中 $u_{0}=c_{1}x_{1}+c_{2}x_{2}$ 求出相应的系数 $u_{0}= \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix}= \begin{bmatrix} 1 \\ 0 \end{bmatrix}= c_{1}x_{1}+c_{2}x_{2}= c_{1} \begin{bmatrix} \lambda_{1} \\ 1 \end{bmatrix}+ c_{2} \begin{bmatrix} \lambda_{2} \\ 1 \end{bmatrix}$
将以上等式从矩阵转换为方程组形式 $\left\{\begin{matrix} 1=c_{1}\lambda_{1}+c_{2}\lambda_{2} \\ 0=c_{1}+c_{2} \end{matrix}\right.$
解得 $\left\{\begin{matrix} c_{1}=\cfrac{1}{\sqrt{5}} \\ c_{2}=-\cfrac{1}{\sqrt{5}} \end{matrix}\right.$
根据等比数列的递推式 $u_{k+1}=Au_{k}$ 以及首项 $u_{0}$ 可得 $u_{k}=A^{k}u_{0}$ ，并根据上一小节的结论，可得 $u_{k}$ 的分解形式（通项公式） $u_{k}=c_{1}\lambda_{1}^{k}x_{1}+c_{2}\lambda_{2}^{k}x_{2}$
再根据 $u_{k}$ 与 $F_{k}$ 的关系 $u_{k}= \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}$
所以 $F_{k}$ 的通项公式为 $F_{k}=\cfrac{1}{\sqrt{5}}(\cfrac{1+\sqrt{5}}{2})^{k}-\cfrac{1}{\sqrt{5}}(\cfrac{1-\sqrt{5}}{2})^{k}$

数列的增长速率

在斐波那契数列的通项公式 $F_{k}$ 中有两个 $k$ 次项，其中前一项 $\cfrac{1+\sqrt{5}}{2}$ 的值大于 $1$ （约为 $1.618$ ），而后一项 $\cfrac{1-\sqrt{5}}{2}$ 的绝对值是小于 $1$ 的（约为 $-0.618$ ）

所以随着 $k$ 的增大，后一项项会趋于 $0$ ，那么 $F_{k}$ 的增长速率只与前一项相关

结合所构造的矩阵 $A=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ 而言，斐波那契数列数列的增长速率只与该矩阵的特征值 $\lambda_{1}=\cfrac{1+\sqrt{5}}{2}$ 相关

该规律可以拓展至一般的等比数列，根据（通过矩阵的分解形式）所求出数列的通项公式可知，等比数列的增长率由所构造的矩阵的特征值决定