04-高斯消元法与矩阵对角化

本文最后更新于128 天前，其中的信息可能已经过时，如有错误请留言

高斯消元法 Gaussian Elimination 是求解线性方程组的一种高效算法，该方法基于以下定理：

定理 1（高斯消元法基本定理）：对线性方程组进行以下运算，不会改变其解集合：
（1）交换两个方程的位置；
（2）将某个方程（等号两边同时）乘以一个非零常数；
（3）将一个方程替换为该方程与另一个方程的若干倍之和

三个基本初等行变换对应的矩阵

上述三种运算（交换方程位置、数乘方程（或称为缩放）、方程组合）被称为初等行变换。

注 1：请注意这些运算的限制条件：将方程乘以 0 是不被允许的，因为这会改变方程组的解集合。同样，将一个方程的若干倍加到该方程自身也是不允许的，因为若将该方程的−1倍加到自身，实际上相当于将该方程乘以 0。

主变量 leading variable：在方程组的每一行中，第一个系数非零的变量被称为该行的
自由变量：行阶梯形线性方程组中的非主变量
行阶梯形方程组：除第一行的主变量外，其余每一行的主变量都位于上一行主变量的右侧；同时，所有系数全为零的行（若存在）都位于方程组的最下方

Gauss-Jordan reduction 高斯若当消元法解方程组
Row Echelon Form 行阶梯型 Reduced Row Echelon Forms 行最简型

行阶梯形：每个方程的 “第一个非零系数”（主变量）都比上一行的主变量靠右
简化行阶梯形：不仅是行阶梯形，每个主变量还必须是 1，而且主变量所在的列里，只有主变量是 1，其他都是 0。

使用高斯 – 若尔当消元法求解方程组，虽然会增加一些额外的计算量，但优点是可以直接从简化行阶梯形方程组中读出解的形式。
无论是简化行阶梯形方程组还是普通的行阶梯形方程组，判断解的情况的规则都是一致的：若出现矛盾方程，则方程组无解；若未出现矛盾方程且每个变量都是主变量，则方程组有唯一解；若未出现矛盾方程但存在至少一个自由变量，则方程组有无穷多解。

方程组的解有 3 种情况

无解：出现 “0 = 非零数” 的行（比如 [0 0 | 5]），这显然矛盾，说明没有能满足所有方程的解
唯一解：没有矛盾行，且每个未知数都是 “主变量”（没有 “自由变量”），比如 3 个未知数对应 3 个主变量，能算出唯一的 x、y、z
无穷多解：没有矛盾行，但有 “自由变量”（不是主变量的未知数，比如 3 个未知数只有 2 个主变量，剩下 1 个可以随便取）

无穷多解：没有矛盾行，但有 “自由变量”（不是主变量的未知数，比如 3 个未知数只有 2 个主变量，剩下 1 个可以随便取）

矩阵的秩

用高斯消元还能算出矩阵的 “秩”，相当于矩阵的 “有效信息量”：

行秩：矩阵中 “线性无关的行” 的数量（比如两行成倍数关系，比如 [1 2] 和 [2 4]，就不是线性无关，有效信息只有 1 行）
列秩：矩阵中 “线性无关的列” 的数量

行秩 = 列秩，所以统称 “秩”

秩还能判断方程组的解：对于 n 个未知数的方程组，系数矩阵的秩是 r：

无解：增广矩阵的秩 > r（出现矛盾行）。
唯一解：r = n（没有自由变量）。
无穷多解：r < n（有 n-r 个自由变量）。

A and B are row equivalent 矩阵行等价

若两个矩阵可通过一系列初等行变换相互转化，则称这两个矩阵是行等价的。

引理 1：若矩阵A与矩阵B行等价，则Row(A)=Row(B)（即矩阵A的行空间与矩阵B的行空间相等）。
因为当一个矩阵通过初等行变换转化为另一个矩阵时，第二个矩阵的每一行都是第一个矩阵各行的线性组合。

对称矩阵：一个 n 阶方阵 A 满足 $A^T = A$（转置等于自身）
补充：正交矩阵（Orthogonal Matrix）$A^{-1} = A^T$（逆矩阵等于自身的转置），每一列都是单位向量

设A∈Mm×n(R)（即A是m×n实矩阵），矩阵A的行秩定义为其行空间Row(A)的维数，列秩定义为其列空间Col(A)的维数。
定理 2：对任意矩阵而言，其行秩等于列秩。
定义 8：矩阵A的秩（记为rank(A)）定义为其行秩或列秩（由于行秩等于列秩，因此无需区分）。