Week 2 Notes

Linear system 指的是一个包含了多个相同变量的等式的方程组。以矩阵的方式来看，Linear system 可以写作 $Ax=b$ 的形式：

为了使 linear system 更加直观，上述的形式还可以通过省略变量做进一步的精简：



这种类型的矩阵被称为 Augmented matrix。

Gaussian Elimination（高斯消元法）是一种通过抵消 linear system 中等式系数的方式来达到求行列式（矩阵）解的方法。其最终目的是将某个（通常是最下方的）方程组中的变量减少到一个，再将该结果带入到其他方程组中，从而求出最后的结果。表现上，高斯消元法会将 $A$ 变换为一个上三角矩阵。比如上面的例子：


此时最后一行即为 $-2x_3 = 2$，将以次带入之前的等式即可求出结果。

• 高斯消元法会从左到右，从上到下依次消除第一行以下对应位置的变量
• 每一次消除都会使用之前的等式作为抵消
• 选择的等式与被消除变量的位置有关

还是以之前的例子为例，首先需要消除两个 $x_1$，也就是 $a_{12}$ 与 $a_{13}$。设行为 $L$，消除的参考等式是 $L_1$，消除的方式是对矩阵中每个对应的元素进行乘法和加法的运算。本例中的运算过程为：

• $L_1\times 2 + L2$
• $L_1+L_3$

得到的结果是： $$ \begin{pmatrix} -3 & 2 & -1&-1 \\ 6& -6& 7& -7\\ 3& -4& 4&-6 \end{pmatrix} \Rightarrow \begin{pmatrix} -3 & 2 & -1&-1 \\ 0& -2& 5& -9\\ 0& -2& 3&-7 \end{pmatrix} $$ $x_1$ 处理完毕之后，为了得到目标中的上三角矩阵，我们需要继续消除 $L_3$ 中的 $x_2$，也就是 $a_{32}$。该变量的系数可以通过：

• $L_2 \times (-1)+L_3$

的运算得到。进过这一轮的消元，我们已经得到了带上三角矩阵的形式了：

$$ \begin{pmatrix} -3 & 2 & -1&-1 \\ 0& -2& 5& -9\\ 0& -2& 3&-7 \end{pmatrix} \Rightarrow \begin{pmatrix} -3 & 2 & -1&-1 \\ 0& -2& 5& -9\\ 0& 0& -2&2 \end{pmatrix} $$

得到上面的形式后，我们将其转化为带变量的 linear system形式：

\[ \begin{align} -3x_1+2x_2-x_3&=-1 \\-2x_2+5x_3&=-9 \\-2x_3&=2 \end{align} \]
将最后一行的等式依次往上带入，即可得到最后的结果。因为这种带入的方式是自底向上的，因此被称为 back substitution。

Reduced Row Echelon Form（简化列阶梯形矩阵）指满足下面两个条件的矩阵：

• 每一行的第一个非零元素（Pivot），也就是首项系数，必须为 $1$
• 该 Pivot 是所在的列中唯一非零元素，除了该 Pivot，其他元素需要为 $0$

• 与高斯消元法不同，该矩阵需要同时对 pivot 上方和下方的元素进行消元
• 该矩阵形式记作 $rref(A)$
• 该矩阵存在 pivot 不存在的情况。如果某一列存在 pivot，那么该列被称为 pivot column。

由逆矩阵的定义可知，$AA^{-1}=I$。而 $AA^{-1}$ 可以被视作一个 linear system，即 $A$ 与 $A^{-1}$ 中对应的列进行相乘，得到 $I$ 中的对应列的，多个等式组成的系统：

也就是说，在这个系统（方程组）里，我们知道了未知数的系数，也知道了每一个方程的结果，那么整个求逆矩阵的过程实际上就转化为了解方程组的过程。因此，我们可以将 $A$ 视作已知矩阵，将 $I$ 视作结果组成一个 Augmented martix，并使用高斯消元来计算出 $A^{-1}$。

按照上述的思路，如果使用 RREF，上述的过程会变得更加简单。对于可逆矩阵 $A$，其 RREF 必然是一个单位矩阵。因此由 $AI$ 组成 Augmented martix，当 $A$ 变为 $I$ 时：$$AI \to IA^{-1}$$ 那么整个过程则是对整个 Augmented martix 进行 RREF 的变形；当 $A$ 转变为 $rref$ 形式时，Augmented matrix 右边的部分即为 $A^{-1}$：