第四讲： $A$ 的 $L U$ 分解

$A B$ 的逆矩阵：

\begin{aligned} A \cdot A^{- 1} = I & = A^{- 1} \cdot A \\ (A B) \cdot (B^{- 1} A^{- 1}) & = I \\ 则 A B 的逆矩阵为 & B^{- 1} A^{- 1} \end{aligned}

$A^{T}$ 的逆矩阵：

\begin{aligned} (A \cdot A^{- 1})^{T} & = I^{T} \\ (A^{- 1})^{T} \cdot A^{T} & = I \\ 则 A^{T} 的逆矩阵为 & (A^{- 1})^{T} \end{aligned}

将一个 $n$ 阶方阵 $A$ 变换为 $L U$ 需要的计算量估计：

第一步，将 $a_{11}$ 作为主元，需要的运算量约为 $n^{2}$

[\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] \underset{\to}{消 元} [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ 0 & a_{22} & \dots & a_{2 n} \\ 0 & ⋮ & ⋱ & ⋮ \\ 0 & a_{n 2} & \dots & a_{n n} \end{matrix}]

以此类推，接下来每一步计算量约为 $(n - 1)^{2} 、 (n - 2)^{2} 、 \dots 、 2^{2} 、 1^{2}$ 。
则将 $A$ 变换为 $L U$ 的总运算量应为 $O (n^{2} + (n - 1)^{2} + \dots + 2^{2} + 1^{2})$ ，即 $O (\frac{n^{3}}{3})$ 。

置换矩阵(Permutation Matrix)：

3阶方阵的置换矩阵有6个：

[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}] [\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}] [\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}] [\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}]

$n$ 阶方阵的置换矩阵有 $(\binom{n}{1}) = n!$ 个。