证明LU分解及单位下三角矩阵的性质。

单位下三角矩阵指对角线元素均为 1 的下三角矩阵，一个很好的例子就是 LU 分解得到的 L 矩阵。

证明LU分解

我们考虑对一个矩阵进行高斯消元（假设这里不考虑换行），消元的过程就是对原始矩阵左乘很多个初等矩阵。

举个例子，考虑下面的矩阵 \(\mathbf{A}\) \[ \left[ \begin{array}{c} 2 & 1 \\ 8 & 7 \\ \end{array} \right] \] 消元的过程等于左乘一个初等矩阵 \(\mathbf{E_{21}}\) \[ \left[ \begin{array}{c} 1 & 0 \\ -4 & 1 \\ \end{array} \right] \left[ \begin{array}{c} 2 & 1 \\ 8 & 7 \\ \end{array} \right] = \left[ \begin{array}{c} 2 & 1 \\ 0 & 3 \\ \end{array} \right] \] 这样就能一次性得到 \(\mathbf{U}\) 矩阵了。

但是如果我们要得到 \(\mathbf{A = LU}\) , 那么我们就需要 \(\mathbf{E_{21}}\) 求逆放在右手项中，在这个例子中， \(\mathbf{E_{21}}\) 的逆矩阵只需要将 -4 改为 4，即 \[ \left[ \begin{array}{c} 2 & 1 \\ 8 & 7 \\ \end{array} \right] = \left[ \begin{array}{c} 1 & 0 \\ 4 & 1 \\ \end{array} \right] \left[ \begin{array}{c} 2 & 1 \\ 0 & 3 \\ \end{array} \right] \] 这是最简单的 \(2 \times 2\) 的情况。

这里我们可以换一个格式来证明，使用高斯变换矩阵，高斯变换矩阵是只有某一列存在非零元素的单位下三角矩阵，即 \[ \mathbf{L}_i=\left[\begin{array}{cccccccc} 1 & & & \ldots & & & & 0 \\ 0 & \ddots & & & & & & \\ 0 & \ddots & 1 & & & & & \vdots \\ 0 & \ddots & 0 & 1 & & & & \vdots \\ & & 0 & l_{i+1, i} & 1 & & & \vdots \\ \vdots & & 0 & l_{i+2, i} & 0 & \ddots & & \\ & & \vdots & \vdots & \vdots & \ddots & 1 & \\ 0 & \ldots & 0 & l_{n, i} & 0 & \ldots & 0 & 1 \end{array}\right] \] 其可以写为 \[ \mathbf{L}_{i} = \mathbf{I} + \mathbf{l}_{i} \mathbf{e}_{i}^{T} \] 其中 \[ \mathbf{l}_{k} = (0\cdots0,l_{i+1,i},\cdots,l_{n,i})^{T} \] 其逆矩阵为 \(\mathbf{L}_{i}^{-1} = \mathbf{I} - \mathbf{l}_{i} \mathbf{e}_{i}^{T}\)， 因为 \((\mathbf{I} - \mathbf{l}_{i} \mathbf{e}_{i}^{T})(\mathbf{I} + \mathbf{l}_{i} \mathbf{e}_{i}^{T}) = \mathbf{I} - \mathbf{l}_{i} \mathbf{e}_{i}^{T}\mathbf{l}_{i} \mathbf{e}_{i}^{T} = \mathbf{I}\) 。

所以其逆矩阵仍为高斯变换矩阵，如下 \[ \mathbf{L}_i^{-1} =\left[\begin{array}{cccccccc} 1 & & & \ldots & & & & 0 \\ 0 & \ddots & & & & & & \\ 0 & \ddots & 1 & & & & & \vdots \\ 0 & \ddots & 0 & 1 & & & & \vdots \\ & & 0 & -l_{i+1, i} & 1 & & & \vdots \\ \vdots & & 0 & -l_{i+2, i} & 0 & \ddots & & \\ & & \vdots & \vdots & \vdots & \ddots & 1 & \\ 0 & \ldots & 0 & -l_{n, i} & 0 & \ldots & 0 & 1 \end{array}\right] \] 这一点很好理解，左乘 \(\mathbf{L}_{i}\) 的作用是对 \(i+1\) 到 \(n\) 行均加上了第 \(i\) 行的倍数，而左乘 \(\mathbf{L}_{i}^{-1}\) 的作用是对 \(i+1\) 到 \(n\) 行均减去了第 \(i\) 行的相应倍数，因此就还原了原来的矩阵，因此 \(\mathbf{L}_{i} \mathbf{L}_{i}^{-1} = \mathbf{I}\) 。

对于一个 \(n \times n\) 的矩阵 \(\mathbf{A}\) ，经过了消元之后（假设没有换行），则有 \[ \mathbf{L}_{n-1}^{-1} \cdots\mathbf{L}_{1}^{-1} \mathbf{A} = \mathbf{U} \] 因此我们有 \[ \begin{aligned} \mathbf{L} &= \mathbf{L}_{1}\mathbf{L}_{2} \cdots \mathbf{L}_{n-1} \\ &= (\mathbf{I} + \mathbf{l}_{1} \mathbf{e}_{1}^{T}) (\mathbf{I} + \mathbf{l}_{2} \mathbf{e}_{2}^{T}) \cdots (\mathbf{I} + \mathbf{l}_{n-1} \mathbf{e}_{n-1}^{T}) \\ \end{aligned} \] 这里我们可以证明，对于 \(i < j\) ，存在 \[ \mathbf{l}_{i} \mathbf{e}_{i}^{T} \mathbf{l}_{j} \mathbf{e}_{j}^{T} = \mathbf{l}_{i} (\mathbf{e}_{i}^{T} \mathbf{l}_{j}) \mathbf{e}_{j}^{T} = 0 \times \mathbf{l}_{i} \mathbf{e}_{j}^{T} = \mathbf{0} \] 因此对于上面的式子，我们有 $$ \[\begin{aligned} \mathbf{L} &= \mathbf{L}_{1}\mathbf{L}_{2} \cdots \mathbf{L}_{n-1} \\ &= (\mathbf{I} + \mathbf{l}_{1} \mathbf{e}_{1}^{T}) (\mathbf{I} + \mathbf{l}_{2} \mathbf{e}_{2}^{T}) \cdots (\mathbf{I} + \mathbf{l}_{n-1} \mathbf{e}_{n-1}^{T}) \\ &= (\mathbf{I} + \mathbf{l}_{1} \mathbf{e}_{1}^{T} + \mathbf{l}_{2} \mathbf{e}_{2}^{T}) \cdots (\mathbf{I} + \mathbf{l}_{n-1} \mathbf{e}_{n-1}^{T}) \\ &= (\mathbf{I} + \mathbf{l}_{1} \mathbf{e}_{1}^{T} + \mathbf{l}_{2} \mathbf{e}_{2}^{T}+ \mathbf{l}_{3} \mathbf{e}_{3}^{T}) \cdots (\mathbf{I} + \mathbf{l}_{n-1} \mathbf{e}_{n-1}^{T}) \\ &\cdots \\ &= \mathbf{I} + \mathbf{l}_{1} \mathbf{e}_{1}^{T} + \cdots + \mathbf{l}_{n-1} \mathbf{e}_{n-1}^{T} \end{aligned}\]

\[ 即 \] =_1 2 {n-1}=$$ 得证。

单位下三角矩阵的性质

1. 多个单位下三角矩阵的乘积仍为单位下三角矩阵

   证明：先以两个单位下三角矩阵的乘积为例，假设 \(\mathbf{A}\) 和 \(\mathbf{B}\) 是两个 n 维的单位下三角矩阵，根据矩阵乘积性质，\(\mathbf{AB}\) 的每一行均是 \(\mathbf{B}\) 的行的线性组合，\(\mathbf{AB}\) 的第 \(i\) 行等于 \(a_{i1} \mathbf{b}_{1}^{T} + a_{i2} \mathbf{b}_{2}^{T} + \cdots + \mathbf{b}_{i}^{T}\) ，易得 \(\mathbf{AB}\) 的对角线元素均为 1，因此 \(\mathbf{AB}\) 为单位下三角矩阵，这可以推广至多个下三角矩阵的乘积。

2. 单位下三角矩阵的逆矩阵仍为单位下三角矩阵

   证明：根据上面的推导，对于任意一个单位下三角矩阵 \(\mathbf{L}\) ，其可以分解为 \(\mathbf{L}=\mathbf{L}_1 \mathbf{L}_2 \ldots \mathbf{L}_{n-1}\) ，因此 \(\mathbf{L}^{-1} = \mathbf{L}_{n-1}^{-1} \cdots\mathbf{L}_{1}^{-1}\) ，由于多个单位下三角矩阵的乘积仍为单位下三角矩阵，因此 \(\mathbf{L}^{-1}\) 也是单位下三角矩阵。

高斯消元的时间复杂度

假设存在一个 \(100 \times 100\) 的矩阵，由于一般的数学计算都是乘法和减法合并在一块，因此这里我们只考虑乘法的次数。

对于第一步，消除第一列的计算次数差不多是 \(100^{2}\) (准确次数是 \(99 \times 100\) ，因为不考虑第一行)，消除第二列的计算次数差不多是 \(99^{2}\) (准确次数是 \(98 \times 99\) ），以此类推。

一般化得到，对于一个维度为 n 的矩阵，高斯消元的计算次数大约为 \[ n^{2} + \cdots + 1^{2} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6} \approx \frac{n^{3}}{3} \]

参考文献

1. MIT-线性代数课程
2. 矩阵的LU分解