Day 2 Ax=b
Published:
$\mathbf A \vec x = \vec 0$
给定一个矩阵 $\mathbf A$，求出其 null space $N(\mathbf A)$，即 $\mathbf A \vec x = \vec 0$ 的所有解。
例：求出
\[N\left(\begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 4 & 8 \\ 3 & 7 & 8 & 10 \\ \end{bmatrix}\right)\]
直接盯着 $\mathbf A$ 看你是什么都看不出来的。但是，如果我们能够把 $\mathbf A$ 变一变形式，同时又不改变 null space 呢？
什么变换能保证 null space 不变？
我们学习过了矩阵乘法，我们尝试把 $\mathbf A$ 左边乘上某个矩阵 $\mathbf B$。若 null space 不变，则 $\mathbf A \vec x = \vec 0 \iff \mathbf B \mathbf A \vec x = \vec 0$。左推右是显然的，右推左时我们需要保证 $\mathbf B$ 可逆。
总之，若我们把 $\mathbf A$ 左乘上一个可逆矩阵，则 null space 不变。
什么形式能方便我们看出 null space？
从一个性质最好的情况入手，即我们的矩阵是 non-singular 的方阵。
根据小学时的经验，若我们最后的方程长成这个样子，就可以着手开始解了（以三元为例）：
\[\begin{cases} a_{1,1} x &+& a_{1,2} y &+& a_{1,3} z = b_1 \\ && a_{2,2} y &+& a_{2,3} z = b_2 \\ && && a_{3,3} z = b_3 \\ \end{cases}\]我们只要从最底下倒推，先搞出 $z$，然后搞 $y$，最后搞 $x$。
也就是说，若我们最后的方阵能变成这个格式就好了：
\[\begin{bmatrix} ? & ? & \cdots & ? \\ & ? & \cdots & ? \\ & & \ddots & \vdots \\ & & & ? \\ \end{bmatrix}\]即对角线左边全是 $0$ 的矩阵，这被称为上三角矩阵。上三角矩阵特别适合解线性方程组。
但是对角线上也不一定都不是 $0$。有的未知数可能消着消着没有自己的独立方程了，所以最后或许会长这样：
\[\begin{bmatrix} \boxed{?} & ? & ? & ? & ? & ? & ? \\ & & \boxed{?} & ? & ? & ? & ? \\ & & & & & \boxed{?} & ? \\ \\ \end{bmatrix}\]类似这样的阶梯型。这被称为 row echelon form。
框框标出的列是有自己独立约束的未知数（$1,3,6$ 位置），称为主元 (pivot variable)；剩下死了的未知数称为自由元 (free variable)（$2,4,5,7$ 位置）。
主元的个数代表了这个矩阵的有效约束数量，这被称为这个矩阵的秩 (rank)，记作 $\text{rank}(\mathbf A)$（在 Mathematica 中可以使用 MatrixRank 函数）。
当我们调整所有自由元时，我们可以根据这些自由元解出唯一的主元。
可以用什么操作构造 REF？
根据小学知识，方程之间是可以加减消元的。我们尝试玩一下题目给的矩阵，探究一下加减消元过程中涉及的操作。
\[\begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 4 & 8 \\ 3 & 7 & 8 & 10 \\ \end{bmatrix}\]第一列 $x_1$ 肯定是主元，我们可以把第二行减掉第一行 $2$ 倍，把第三行减掉第一行 $3$ 倍，以保证其他行不出现 $x_1$：
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & 0 & 0 & 4 \\ & 1 & 2 & 4 \\ \end{bmatrix}\]然后我们试图选取 $x_2$ 作为主元，但是失败了，因为系数是 $0$。
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & \textcolor{red}{0} & 0 & 4 \\ & 1 & 2 & 4 \\ \end{bmatrix}\]但是其实是可以的，只要我们把第三行换上来：
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & \boxed{1} & 2 & 4 \\ & & 0 & 4 \\ \end{bmatrix}\]然后我们试图选取 $x_3$ 作为主元，但是失败了，而且这次是真不行：
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & \boxed{1} & 2 & 4 \\ & & \textcolor{red}{0} & 4 \\ \end{bmatrix}\]只能选 $x_4$ 为主元：
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & \boxed{1} & 2 & 4 \\ & & & \boxed{4} \\ \end{bmatrix}\]此时就得到了 REF。
总之，我们可知我们要支持以下操作（称为初等行操作）：
- 将一行乘一个倍数；
- 将一行减去若干倍的另一行；
- 交换两行。
其实它们都可以用可逆矩阵描述（这些操作的矩阵称为初等矩阵），以下会说明。因此确实可以保证 null space 不变。
这套算法称为 Gauss 消元法 (Gauss Elimination)：
- 看当前行的应该称为主元的位置是不是 $0$：
- 若不是，则令它为主元；
- 若是，则尝试从后面的行中换一行上来：
- 若后面行中这一列都是 $0$，则失败，跳过这个未知数；
- 否则随便换一个非 $0$ 的就行，然后令它为主元。
- 对后面的行，减掉合适倍数的当前行进行加减消元，以保证主元系数被清成 $0$。
- 回到第一步。
初等矩阵
刚才的那些对于 $\mathbf A$ 的行的操作，真的都可以用可逆矩阵描述吗？
行操作我们不会，但是我们会列操作啊。怎么把行变成列？转置。
假设我希望对 $\mathbf A$ 左乘一个初等矩阵 $\mathbf E$ 表示经过一次行操作。我们其实可以研究：
\[(\mathbf E \mathbf A)^T = \mathbf A^T \mathbf E^T\]$\mathbf E^T$ 的构造就显而易见了：
- 把 $\mathbf A^T$第 $i$ 列乘 $k$ 倍：单位矩阵，把 $(i,i)$ 的位置从 $1$ 改成 $k$。
- 交换 $\mathbf A^T$ 的 $i,j$ 两列：单位矩阵，把 $(i,i), (j,j)$ 改成 $0$，把 $(i,j), (j,i)$ 改成 $1$。
- 把 $\mathbf A^T$ 第 $i$ 列加上第 $j$ 列的 $k$ 倍：单位矩阵，把 $(j,i)$ 从 $0$ 改成 $k$。
- 从 $\mathbf E^T$ 翻回到 $\mathbf E$ 就是改 $(i,j)$。
它们的逆矩阵都很好求，倒着操作就行了。
这样我们就证明了初等行操作都可以用可逆矩阵描述，这保证了 Gauss 消元法的正确性。
与此同时，任意矩阵都可以被 Gauss 消元，这意味着任意可逆矩阵都可以被表示为若干初等矩阵的乘积。因为 $\mathbf E \mathbf A = \mathbf I$，即 $\mathbf A = \mathbf E^{-1}$。
怎么根据 REF 求 null space？
还是刚才的矩阵，我们设自由元 $x_3$ 为参数 $c_1$，我们可以用自由元表示所有主元（计算省略）：
\[\begin{cases} x_1 = 2 c_1 \\ x_2 = -2 c_1 \\ x_4 = 0 c_1 \\ \end{cases}\]因此这个矩阵的 null space 为：
\[\boxed{ c_1 \begin{bmatrix} 2 \\ -2 \\ 1 \\ 0 \end{bmatrix}, c_1 \in \mathbb R }\]即
\[\boxed{ \text{span}\left( \begin{bmatrix} 2 \\ -2 \\ 1 \\ 0 \end{bmatrix} \right) }\]若有更多的自由元，在开头设更多参数（$c_1, c_2, \cdots$），后续加入更多的基向量即可。
RREF
设完一堆 $c$ 之后还要回代，太复杂了！主播主播，你的 REF 确实很强，但还是太吃操作了，有没有更加简单又强势的角色推荐一下呢？
有的兄弟，有的。在 REF 的基础上，只要我们保证所有主元都只出现在一个方程里，那就轻轻松松了。如果能保证主元系数都是 $1$ 就更方便了。
以刚才的 REF 为例：
\[\begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ & \boxed{1} & 2 & 4 \\ & & & \boxed{4} \\ \end{bmatrix}\]把第一行减掉第二行 $2$ 倍：
\[\begin{bmatrix} \boxed{1} & & -2 & -6 \\ & \boxed{1} & 2 & 4 \\ & & & \boxed{4} \\ \end{bmatrix}\]把第三行除以 $4$：
\[\begin{bmatrix} \boxed{1} & & -2 & -6 \\ & \boxed{1} & 2 & 4 \\ & & & \boxed{1} \\ \end{bmatrix}\]把第一行减掉第三行 $-6$ 倍，把第二行减掉第三行 $4$ 倍：
\[\begin{bmatrix} \boxed{1} & & -2 & \\ & \boxed{1} & 2 & \\ & & & \boxed{1} \\ \end{bmatrix}\]完成啦！这种特别的 REF 被称为 row reduced echelon form，简称 RREF。（在 Mathematica 中可以用 RowReduce 函数计算 RREF）这种消元方法被称为 Gauss-Jordan 消元法 (Gauss-Jordan Elimination)。
一个矩阵可以有很多种不一样的 REF，但是 RREF 是唯一的。
RREF 功能上相较于 REF 似乎没什么优越性，但是它用起来绝对比 REF 方便。
$\mathbf A \vec x = \vec b$
$\mathbf A \vec x = \vec 0$ 会解了，我们尝试解一下 $\mathbf A \vec x = \vec b$。
分析解的结构
不妨设我们有方程的两个解 $\vec x_1, \vec x_2$：
\[\begin{cases} \mathbf A \vec x_1 = \vec b \\ \mathbf A \vec x_2 = \vec b \\ \end{cases}\]减一下可知
\[\mathbf A (\vec x_1 - \vec x_2) = \vec 0\]即
\[(\vec x_1 - \vec x_2) \in N(\mathbf A)\]这有一个等价的表述：若我们已知一个特解 $\vec x^*$，则任何一个解 $\vec x$ 都满足
\[(\vec x - \vec x^*) \in N(\mathbf A)\]也即我们可以用 $\vec x^*$ 加上 $N(\mathbf A)$ 中的任何一个向量来生成所有解，以下是解集：
\[\{\vec x^* + \vec x_n \mid \vec x_n \in N(\mathbf A)\}\]也就是说，现在我们的目标是：
- 找到 $N(\mathbf A)$，这我们已经会了；
- 找到任何一个特解 $\vec x^*$。
怎么找特解？
假设我们现在对 $\mathbf A$ 左乘了一堆初等矩阵 $\mathbf E = \mathbf E_n \mathbf E_{n-1} \cdots \mathbf E_1$ 让它变成了 REF。
\[\mathbf E \mathbf A \vec x = \mathbf E \vec b\]此时 $\mathbf E \mathbf A$ 是 REF，我可以知道哪些是主元哪些是自由元。我只要把所有自由元设为 $0$，必定可以解出主元。这样就得到了特解。
Example
解关于 $\vec x$ 的方程：
\[\begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 4 & 8 \\ 3 & 7 & 8 & 10 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} =\begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}\]
省略 Gauss 消元的过程，可知：
\[\begin{bmatrix} \boxed{1} & & -2 & \\ & \boxed{1} & 2 & \\ & & & \boxed{1} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}=\begin{bmatrix} 4 b_1 + \frac 3 2 b_2 - 2 b_3 \\ - b_1 - b_2 + b_3 \\ - \frac 1 2 b_1 + \frac 1 4 b_2 \\ \end{bmatrix}\]令自由元 $x_3 = 0$，解出特解：
\[\vec x^* = \begin{bmatrix} 4 b_1 + \frac 3 2 b_2 - 2 b_3 \\ - b_1 - b_2 + b_3 \\ 0 \\ - \frac 1 2 b_1 + \frac 1 4 b_2 \\ \end{bmatrix}\]我们又知道
\[N(\mathbf A) = \{c \begin{bmatrix} 2 \\ -2 \\ 1 \\ 0 \end{bmatrix} \mid c \in \mathbb R\}\]因此所有解为
\[\boxed{ \vec x = \begin{bmatrix} 4 b_1 + \frac 3 2 b_2 - 2 b_3 \\ - b_1 - b_2 + b_3 \\ 0 \\ - \frac 1 2 b_1 + \frac 1 4 b_2 \\ \end{bmatrix} + c \begin{bmatrix} 2 \\ -2 \\ 1 \\ 0 \end{bmatrix}, c \in \mathbb R }\]这个题目性质比较好，没有无解的情况。若 RREF 最后有空行，则这会给 $b$ 带来限制。
秩与解集的关系
以下说明中，$\mathbf A$ 是 $m \times n$ 的矩阵。
列满秩
\[\text{rank}(\mathbf A) = n\]主元数等于列数，说明每个未知数都是主元。
此时 RREF 是这样的格式：
\[\begin{bmatrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \\ 0 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 0 \\ \end{bmatrix}\]上面是单位矩阵，底下全 $0$。
行满秩
（这个是例题的情况）
\[\text{rank}(\mathbf A) = m\]主元数等于行数，说明没有没用的方程，每个方程都贡献了一个主元。
由于最后没有空行，对于任意 $\vec b$ 都有解。
行列同时不满秩
性质最烂。对于每一个 $\vec b$，能解出的 $\vec x$ 要么无解，要么无穷解。
方阵行列同时满秩
此时性质超级好！
首先此时 RREF 是一个单位矩阵。其次，对于每一个 $\vec b$，都有且仅有唯一的 $\vec x$ 是方程的解。
秩—零化度定理
对于任意 $m \times n$ 矩阵 $\mathbf A$：
\[\boxed{ \text{rank}(\mathbf A) + \dim N(\mathbf A) = n }\]这是显然的：$\text{rank}(\mathbf A)$ 是主元个数，$\dim N(\mathbf A)$ 是自由元个数。
行秩与列秩
\[\boxed{ \text{rank}(\mathbf A) = \text{rank}(\mathbf A^T) }\]证明：
【引理 1】初等行变换不改变行之间的线性关系，因此 RREF 中有几行不空，就意味着这些行之间的最大线性无关个数：
\[\text{rank}(\mathbf A) = \dim C(\mathbf A^T)\]【引理 2】在 RREF 中，主元列显然线性无关，而非主元列可以用主元列表示。因此
\[\dim C(\mathbf A) = \text{rank}(\mathbf A)\]由【引理 1】和【引理 2】：
\[\text{rank}(\mathbf A) = \dim C(\mathbf A^T) = \text{rank}(\mathbf A^T)\]三角矩阵与 LU 分解
【定义】下三角矩阵是对于 $i<j$ 的位置 $(i,j)$ 都是 $0$ 的方阵。
\[(\mathbf A \mathbf B)_{i,j} = \sum_k \mathbf A_{i,k} \mathbf B_{k,j}\]对于下三角矩阵 $\mathbf A, \mathbf B$，其乘积 $\mathbf A \mathbf B$ 依然是下三角矩阵。
即下三角矩阵对乘法的封闭性。这个性质对上三角矩阵也成立。
当 $i<j$ 时，$i<k$ 和 $k<j$ 不可能同时不成立，因此 $\mathbf A_{i,k} = 0$ 或 $\mathbf B_{k,j} = 0$，求和起来还是 $0$。证完了。
回忆 Gauss 消元的过程，对于方阵 $\mathbf A$，我们把 $\mathbf A$ 左乘了一个可逆矩阵 $\mathbf E$ 得到了一个上三角矩阵 $\mathbf U$：
\[\begin{aligned} \mathbf E \mathbf A &= \mathbf U \\ \mathbf A &= \mathbf E^{-1} \mathbf U \\ \mathbf A &= (\mathbf E_1^{-1} \cdots \mathbf E_n^{-1}) \mathbf U \end{aligned}\]若没有“行交换”矩阵，则这里每一个矩阵都是下三角矩阵，乘起来还是下三角矩阵。
即当没有“行交换”操作时，$\mathbf A$ 可以被分解为下三角矩阵 $\mathbf L$ 和上三角矩阵 $\mathbf U$：
\[\boxed{ \mathbf A = \mathbf L \mathbf U }\]显然满秩方阵必然有 LU 分解。
秩 1 矩阵
$\text{rank}$ 为 $1$ 的矩阵，必然可以分解为以下形式：
\[\begin{bmatrix} 1 & 4 & 5 \\ 2 & 8 & 10 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 4 & 5 \end{bmatrix}\]即
\[\mathbf A = \vec u \vec v^T\]