线性代数 Cheat Sheet 2-5：矩阵因式分解
矩阵 $A$ 的因式分解是把 $A$ 表示为两个或更多个矩阵的乘积。矩阵乘法是数据的综合，矩阵因式分解是数据的分解，分解后的结构可能更有用，或更便于计算。
Contents
1. LU 分解
设 $A$ 是 $m \times n$ 矩阵，它可以行化简为阶梯形而不必进行行对换，则 $A$ 可写成形式 $A = LU$，$L$ 是 $m \times m$ 下三角矩阵，主对角线元素全是 $1$，$U$ 是 $A$ 的一个 $m \times n$ 阶梯形矩阵。
\begin{equation}
A = LU = \begin{bmatrix}
1 & 0 & 0 & 0 \\
* & 1 & 0 & 0 \\
* & * & 1 & 0 \\
* & * & * & 1
\end{bmatrix}
\begin{bmatrix}
\blacksquare & * & * & * & * \\
0 & \blacksquare & * & * & * \\
0 & 0 & 0 & \blacksquare & * \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}
\end{equation}
其中矩阵 $L$ 是可逆的，称为单位下三角矩阵。
当 $A = LU$ 时，方程 $A \boldsymbol x = \boldsymbol b$ 可以写成 $L(U \boldsymbol x) = \boldsymbol b$，把 $U \boldsymbol x$ 写成 $\boldsymbol y$，则可以由解下面一对方程来求解 $\boldsymbol x$：
\begin{equation}
L \boldsymbol y = \boldsymbol b \\
U \boldsymbol x = \boldsymbol y
\end{equation}
首先解 $L \boldsymbol y = \boldsymbol b$ 求得 $\boldsymbol y$，然后解 $U \boldsymbol x = \boldsymbol y$ 求得 $\boldsymbol x$。由于 $L$ 和 $U$ 都是三角矩阵，这两个方程都比较容易解。
2. LU 分解算法
设 $A$ 可以化为阶梯形 $U$，化简过程中仅使用行倍加变换，此时存在单位下三角矩阵 $E_1, \cdots, E_p$，使
\begin{equation}
E_p \cdots E_1 A = U \tag{1}
\end{equation}
于是
\begin{equation}
A = (E_p \cdots E_1)^{-1}U = LU
\end{equation}
其中
\begin{equation}
L = (E_p \cdots E_1)^{-1} \tag{2}
\end{equation}
可以证明，单位下三角矩阵的乘积和逆也是单位下三角矩阵，于是 $L$ 是单位下三角矩阵。
由 $(2)$ 式有
\begin{equation}
E_p \cdots E_1 L = I
\end{equation}
可见 $(1)$ 中的行变换 $E_p \cdots E_1$ 把 $A$ 化为 $U$，也把 $L$ 化为 $I$。
LU 分解的算法
1. 如果可能的话，用一系列的行倍加变换把 $A$ 化为阶梯形 $U$。
2. 填充 $L$ 的元素使相同的行变换把 $L$ 变为 $I$。
注意上面的第 1 步并不总是可能的，如果可能，则 LU 分解存在。