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

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

证明LU分解

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

举个例子，考虑下面的矩阵

消元的过程等于左乘一个初等矩阵

这样就能一次性得到 矩阵了。

但是如果我们要得到 , 那么我们就需要 求逆放在右手项中，在这个例子中， 的逆矩阵只需要将 -4 改为 4，即

这是最简单的 的情况。

这里我们可以换一个格式来证明，使用高斯变换矩阵，高斯变换矩阵是只有某一列存在非零元素的单位下三角矩阵，即

其可以写为

其中

其逆矩阵为 ， 因为 。

所以其逆矩阵仍为高斯变换矩阵，如下

这一点很好理解，左乘 的作用是对 到 行均加上了第 行的倍数，而左乘 的作用是对 到 行均减去了第 行的相应倍数，因此就还原了原来的矩阵，因此 。

对于一个 的矩阵 ，经过了消元之后（假设没有换行），则有

因此我们有

这里我们可以证明，对于 ，存在

因此对于上面的式子，我们有

即

得证。

单位下三角矩阵的性质

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

   证明：先以两个单位下三角矩阵的乘积为例，假设 和 是两个 n 维的单位下三角矩阵，根据矩阵乘积性质， 的每一行均是 的行的线性组合， 的第 行等于 ，易得 的对角线元素均为 1，因此 为单位下三角矩阵，这可以推广至多个下三角矩阵的乘积。

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

   证明：根据上面的推导，对于任意一个单位下三角矩阵 ，其可以分解为 ，因此 ，由于多个单位下三角矩阵的乘积仍为单位下三角矩阵，因此 也是单位下三角矩阵。

高斯消元的时间复杂度

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

对于第一步，消除第一列的计算次数差不多是 (准确次数是 ，因为不考虑第一行)，消除第二列的计算次数差不多是 (准确次数是 ），以此类推。

一般化得到，对于一个维度为 n 的矩阵，高斯消元的计算次数大约为

参考文献

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