L2-矩阵消元

（高斯）消元法 Gaussian elimination 是很多软件用于求解方程组的方法，结合回代替换 backward substitution，最终可以求出方程组各个未知数的值。

参考

Unit I: Ax = b and the Four Subspaces - Elimination with Matrices | pdf
课本章节：Section 2.2, and 2.3 in the 4^th or 5^th edition
练习题：L2-矩阵消元-习题集

使用矩阵「语言」来描述消元的过程，其核心步骤是矩阵变换 matrix operation 和矩阵乘法 matrix multiple

对于方程组

\left\{\begin{matrix} x+2y+z = {\color{Blue}2 } \\ 3x+8y+z = {\color{Blue}12 } \\ 4y+z = {\color{Blue}2 } \end{matrix}\right.

以矩阵 $Ax=b$ 形式来表示，其中系数矩阵 $A=\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$ ，结果向量 ${\color{Blue}\bold{b} =\begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix}}$ ，变量向量是 $\begin{bmatrix} x \\ y \\ z \end{bmatrix}$

其对应的增广矩阵是

(A|{\color{Blue}B }) = \begin{bmatrix} 1 & 2 & 1 & {\color{Blue} 2} \\ 3 & 8 & 1 & {\color{Blue} 12} \\ 0 & 4 & 1 & {\color{Blue} 2} \end{bmatrix}

消元步骤分解演示

首先如果要将矩阵中坐标为 $(1, 1)$ （即第一行第一列）的元素作为第一个主元 pivot，就要对矩阵进行变换以消除 $(2, 1)$ 元素和 $(3, 1)$ 元素（该元素已经是 $0$ 了，因此这一步可以省略），需要执行以下步骤
1. 增广矩阵第一行乘一个系数 $-3$ （即相当于方程组第一个等式两边乘以一个系数 $-3$ ）
2. 增广矩阵第二行加上第一行（即相当于方程组第二个等式和第一个等式相加，获得一个新等式），获得的结果作为第二行，实现 $(2, 1)$ 元素的消除
然后重复以上两步，直到将系数矩阵从 $A$ 变换为上三角矩阵 $U$
说明
这节课先假设求解的方程组的系数矩阵 $A$ 是可逆的，即可以通过矩阵的初等变换或/和置换成功得到 $U$
最后就可以通过回代替换的方法求解所有未知数

以上步骤 1 和 2 就是初等矩阵/消元矩阵 $E$ 的作用：初等矩阵与增广矩阵相乘（从行向量与矩阵相乘的角度考虑）实现增广矩阵行的基本变换（加减）

提示

在变换过程中，可能会遇到矩阵上方的某些行的元素先被消除，则需要使用置换矩阵 $P$ 进行行替换/交换

置换矩阵与增广矩阵相乘（从行向量与矩阵相乘的角度考虑）实现行交换，以便最终得到上三角矩阵

矩阵描述消元步骤

首先消除增广矩阵的 $(2, 1)$ 元素

E_{21}(A|B) = \begin{bmatrix} 1 & 0 & 0 \\ {\color{Red} -3} & {\color{Red} 1} & {\color{Red} 0} \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 & {\color{Blue}2 } \\ 3 & 8 & 1 & {\color{Blue}12 } \\ 0 & 4 & 1 & {\color{Blue}2 } \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 & {\color{Blue}2 } \\ {\color{Red} 0} & 2 & -2 & {\color{Blue}6 } \\ 0 & 4 & 1 & {\color{Blue}2 } \end{bmatrix} = A^{'}

说明

初等矩阵记作 $E_{21}$ 其下标的数字表示它的作用是消除增广矩阵的 $(2, 1)$ 元素（从行向量x矩阵的角度考虑），其核心是中间一行：

\begin{bmatrix} {\color{Red} -3} & {\color{Red} 1} & {\color{Red} 0} \\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 & {\color{Blue}2 } \\ 3 & 8 & 1 & {\color{Blue}12 } \\ 0 & 4 & 1 & {\color{Blue}2 } \end{bmatrix} = \begin{bmatrix} {\color{Red} 0} & 2 & -2 & {\color{Blue}6 } \end{bmatrix}

然后由于 $(3, 1)$ 元素已经是 $0$ ，因此 $E_{31}$ 是单位矩阵（可以省略这一步）

最后是消除 $(3, 2)$ 元素

E_{32}A^{'} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ {\color{Red} 0} & {\color{Red} -2} & {\color{Red} 1} \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 & {\color{Blue}2 } \\ 0 & 2 & -2 & {\color{Blue}6 } \\ 0 & 4 & 1 & {\color{Blue}2 } \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 & {\color{Blue}2 } \\ 0 & 2 & -2 & {\color{Blue}6 } \\ 0 & {\color{Red} 0} & 5 & {\color{Blue}-10 } \end{bmatrix} = A^{''}

最后实现将系数矩阵 $A$ 变换为上三角矩阵 $U$

U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2& -2 \\ 0 & 0 & 5 \end{bmatrix}

提示

三角矩阵的行列式是矩阵主元 pivot 的乘积，因此上述示例中的上三角矩阵的行列式是 $10$

根据 $A^{''}$ 可以得到

\left\{\begin{matrix} x+2y+z = {\color{Blue}2 } \\ 2y-2z = {\color{Blue}6 } \\ 5z = -{\color{Blue}10 } \end{matrix}\right.

因此方程组的解为

\left\{\begin{matrix} x = 2\\ y = 1\\ z = -2 \end{matrix}\right.

矩阵消元的核心是将系数矩阵 $A$ 变换为上三角矩阵 $U$ ，对于示例矩阵这个过程可以表示为 $E_{32}(E_{31}(E_{21}A)) = U$ ，其中 $E_{31} = I$ 为单位矩阵。

可以将多次初等变换整合到一步（利用矩阵乘法结合律，将初等矩阵先相乘起来），整合为一个矩阵，即 $EA=U$

不可逆矩阵

消元也可能会失败，这样的系数矩阵称为不可逆矩阵。

由于方程组中可能存在部分等式并不「独立」，因此在消元过程中出现一个消元步骤同时消去多个元的情况，相应地系数矩阵无法变换为上三角矩阵，无法得到应有数量的主元。

再从主元 pivot 的角度考虑，如果出现上述的情况，为了保证主元不能为 $0$ ；否则需要进行行置换（即如果该行的主元为 $0$ 时，而同时下方某行的相应列的元素存在非零，可以使用置换矩阵实现行置换）；如果该行以下的各行的相应列的元素都为 $0$ （无法进行置换），则原系数矩阵 $A$ 就不可逆的，相应的方程组 $Ax=b$ 也无法求得唯一解。

提示

类似地，对于方程组 $Ax=0$ 而言也是一样，如果 $A$ 是不可逆矩阵，则该方程组也是无法求得唯一解（即会有多个解）；如果 $A$ 是可逆矩阵时，则方程组只有一个唯一解，为零向量（即矩阵 $A$ 的零空间中只有零向量）

因为对于方程组 $Ax=0$ 从矩阵与列向量相乘的角度来考虑，列向量 $x$ 是使矩阵 $A$ 各列进行线性组合的系数，当矩阵是可逆的则表示矩阵的各列都是独立，为了使得线性组合得到零向量，只能 $x$ 本身就是 $0$ ；而如果 $A$ 是不可逆矩阵，则可能存在非零的系数，使得矩阵 $A$ 各列的线性组合为零向量

逆矩阵

在例子中，初等矩阵 $E_{21}$ 的作用是将系数矩阵 $A$ 的第二行减去第一行的三倍，结果作为新的第二行，因此消去 $(2,1)$ 元素， $E_{21}A$ 相乘得到的新矩阵为 $A{'}$

E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

将 「作用相反」的初等矩阵 记为 $E_{21}^{-1}$ ，即它的作用是将矩阵 $A^{'}$ 的第二行与第一行的三倍相加，结果作为新的第二行， $E_{21}^{-1}A'$ 相乘可以 「恢复」得到 A

E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

即 $E_{21}^{-1}(E_{21}A)=A$ ，根据矩阵的乘法分配律得 $E_{21}^{-1}E_{21}=I$ ，因此矩阵与逆矩阵的乘积为单位矩阵 $I$