30、矩阵运算与高斯消元法的应用

矩阵运算与高斯消元法的应用

1. 高斯消元算法输出与操作

在算法结束时，除了输出矩阵 $B$ 外，还会输出矩阵 $M$。这是因为我们对矩阵 $B$ 执行的初等行变换，也会同样应用到矩阵 $M$ 上。该算法是正确的，并且在域 $F$ 中使用 $O(mn(m + n))$ 次运算。

以示例 15.4 为例，继续示例 15.3 的操作，扩展高斯消元算法会将矩阵 $M$ 初始化为单位矩阵，然后按以下步骤进行变换：
[
\begin{pmatrix}
[1] & [0] & [0] \
[0] & [1] & [0] \
[0] & [0] & [1]
\end{pmatrix}
\xrightarrow{M(1)\leftrightarrow M(2)}
\begin{pmatrix}
[0] & [1] & [0] \
[1] & [0] & [0] \
[0] & [0] & [1]
\end{pmatrix}
\xrightarrow{M(1)\leftarrow [2]M(1)}
\begin{pmatrix}
[0] & [2] & [0] \
[1] & [0] & [0] \
[0] & [0] & [1]
\end{pmatrix}
]
[
\xrightarrow{M(3)\leftarrow M(3) - [2]M(1)}
\be