从两个小公式开始

乘积的逆要反序

如果 $A$、$B$ 都可逆，那么

$$(AB)^{-1}=B^{-1}A^{-1}.$$

验证：

$$(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=I.$$

顺序必须反过来，就像脱鞋和脱袜子：先脱鞋再脱袜，恢复时先穿袜再穿鞋。

转置与求逆可以交换顺序

从 $A^{-1}A=I$ 出发，两边转置：

$$(A^{-1}A)^T=I^T=I.$$

而 $(A^{-1}A)^T=A^T(A^{-1})^T$，所以

$$A^T(A^{-1})^T=I,$$

即

$$(A^T)^{-1}=(A^{-1})^T.$$

对单个矩阵，转置和求逆谁先谁后都一样。

时间轴

核心：$A=LU$

假设消元过程中不需要交换行，主元都不为零。每一步消元都是一个初等矩阵 $E_{ij}$，最后

$$E_{32}E_{31}E_{21}A=U.$$

把左边的乘积记作 $E$，则 $EA=U$。要在右边得到 $A$，两边左乘 $E^{-1}$：

$$A=E^{-1}U.$$

而 $E^{-1}$ 要按相反顺序拆开：

$$E^{-1}=(E_{32}E_{31}E_{21})^{-1} =E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}.$$

这个乘积就是 $L$：

$$A=LU.$$

$U$ 是上三角，$L$ 是下三角，对角线上全是 $1$。

二阶例子

$$A=\begin{bmatrix}2&1\\8&7\end{bmatrix}.$$

第一个主元是 $2$，要用它消掉左下角的 $8$，乘数是 $8/2=4$。于是

$$E_{21}=\begin{bmatrix}1&0\\-4&1\end{bmatrix}, \qquad U=\begin{bmatrix}2&1\\0&3\end{bmatrix}.$$

验证 $E_{21}A=U$：第二行是 $-4$ 倍第一行加第二行，即 $[8,7]-4[2,1]=[0,3]$。

$L$ 是 $E_{21}^{-1}$，把减 4 改成加 4：

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}.$$

于是

$$A=\begin{bmatrix}1&0\\4&1\end{bmatrix} \begin{bmatrix}2&1\\0&3\end{bmatrix} = \begin{bmatrix}2&1\\8&7\end{bmatrix}.$$

还可以再拆出主元：$LDU$

把 $U$ 的对角线提出来：

$$U= \begin{bmatrix}2&0\\0&3\end{bmatrix} \begin{bmatrix}1&1/2\\0&1\end{bmatrix} =D U'.$$

于是 $A=LDU'$，两侧都是单位三角矩阵，中间是对角矩阵。MATLAB 两种形式都可能给出；课程主要使用 $LU$。

三阶情形：为什么 $L$ 里直接是乘数

三阶时，消元顺序是

$$E_{32}E_{31}E_{21}A=U,$$

所以

$$A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU.$$

关键问题是：为什么 $L$ 比 $E$ 好用？

取一个典型例子。设

$$E_{21}=\begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix}, \qquad E_{31}=I, \qquad E_{32}=\begin{bmatrix}1&0&0\\0&1&0\\0&-5&1\end{bmatrix}.$$

先算 $E=E_{32}E_{21}$：

$$E= \begin{bmatrix} 1&0&0\\ -2&1&0\\ 10&-5&1 \end{bmatrix}.$$

第三行第一列出现了 $10$。它是怎么来的？先减去 $2$ 倍第一行到第二行，再减去 $5$ 倍新的第二行到第三行，于是有 $5\times 2=10$ 倍第一行被间接减掉。

这不是错误，但让 $E$ 变得难读：乘数 $2$ 和 $5$ 混在了一起。

现在按相反顺序求逆：

$$L=E_{21}^{-1}E_{32}^{-1} = \begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix} \begin{bmatrix}1&0&0\\0&1&0\\0&5&1\end{bmatrix} = \begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&5&1 \end{bmatrix}.$$

乘数 $2$ 和 $5$ 原封不动地待在它们该在的位置，$(3,1)$ 位置是 $0$。

一句话总结： 不用交换行时，$L$ 就是一本乘数账本——消元时用了什么乘数，就直接写进 $L$ 的对应位置。

这也解释了为什么 $LU$ 是消元的正确记录方式：消元结束后，$A$ 的信息完整地保存在 $L$ 与 $U$ 中，原矩阵可以丢掉。

运算量：为什么是 $n^3/3$

消元有多贵？对 $n\times n$ 矩阵，第一步要更新大约 $n^2$ 个数；第二步处理剩下的 $(n-1)\times(n-1)$，约 $(n-1)^2$ 次；依此类推：

$$n^2+(n-1)^2+\cdots+2^2+1^2.$$

这个和的首项是 $n^2$，共有 $n$ 项，所以上界是 $n^3$；更精确地，

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}\approx\frac{n^3}{3}.$$

用积分看更直观：

$$\int_0^n x^2\,dx=\frac{n^3}{3}.$$

所以消元是 $O(n^3)$。右端向量 $\mathbf{b}$ 只有一列，处理它的代价是 $O(n^2)$。

这带来一个实用结论：如果有很多个右端向量共享同一个 $A$，先做一次 $LU$ 分解，再对每个 $\mathbf{b}$ 做 $O(n^2)$ 的前代与回代，比每次重新消元便宜得多。

需要交换行时：排列矩阵

如果主元位置出现 $0$，就要交换行。交换行由排列矩阵 $P$ 完成，它由单位矩阵重排行得到。

$3\times 3$ 的排列矩阵一共有 $3!=6$ 个；$4\times 4$ 有 $4!=24$ 个。它们构成一个群：

• 两个排列矩阵相乘，结果仍是排列矩阵；
• 每个排列矩阵都可逆，且逆仍是排列矩阵；
• 特别地，$P^{-1}=P^T$。交换两行的操作再做一次就还原，所以很多 $P$ 是自己的逆；更一般地，逆等于转置。

有行交换时，分解写成

$$PA=LU.$$

先记录交换，再做消元；$P$ 把行的顺序整理好，$L$ 与 $U$ 的结构不变。

本讲结论

• $(AB)^{-1}=B^{-1}A^{-1}$，顺序必须反过来。
• $(A^T)^{-1}=(A^{-1})^T$。
• 无行交换时，$E_{32}E_{31}E_{21}A=U$，因此 $A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU$。
• $L$ 的对角线为 $1$，非对角元就是消元乘数；$U$ 的对角线是主元。
• $A=LDU'$ 是把主元单独提出来的一种变体。
• 消元的运算量约为 $n^3/3$，每个右端向量约 $n^2$。
• 有行交换时写作 $PA=LU$；$n\times n$ 排列矩阵共有 $n!$ 个，且 $P^{-1}=P^T$。

理解检验

1. 验证 $(AB)^{-1}=B^{-1}A^{-1}$，并说明为什么顺序不能反过来。

参考答案：直接相乘验证：

$$(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=I,$$

所以 $B^{-1}A^{-1}$ 确实是 $AB$ 的逆。顺序不能换，因为

$$(AB)(A^{-1}B^{-1})=A(BA^{-1})B^{-1},$$

中间的 $BA^{-1}$ 一般不等于 $A^{-1}B$，除非两个矩阵恰好可交换，结果就不再是 $I$。直观上像穿脱衣服：先穿袜子再穿鞋，脱的时候必须先脱鞋、再脱袜，顺序必须反过来。

2. 对 $A=\begin{bmatrix}2&1\\8&7\end{bmatrix}$ 写出 $E_{21}$、$U$、$L$，并验证 $A=LU$。

参考答案：主元是 $2$，要消掉左下角的 $8$，乘数为 $8/2=4$，所以

$$E_{21}=\begin{bmatrix}1&0\\-4&1\end{bmatrix},\qquad U=\begin{bmatrix}2&1\\0&3\end{bmatrix}.$$

验证 $E_{21}A=U$：第二行是 $[8,7]-4[2,1]=[0,3]$。$L$ 是 $E_{21}^{-1}$，把 $-4$ 改成 $+4$：

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}.$$

于是

$$LU=\begin{bmatrix}1&0\\4&1\end{bmatrix}\begin{bmatrix}2&1\\0&3\end{bmatrix} =\begin{bmatrix}2&1\\8&7\end{bmatrix}=A.$$

3. 在三阶例子中，$E$ 的 $(3,1)$ 元素为什么是 $10$？为什么 $L$ 里是 $0$？

参考答案：$E=E_{32}E_{21}$。第二行经过 $E_{21}$ 后变成原第二行减去 $2$ 倍第一行；接着 $E_{32}$ 让第三行减去 $5$ 倍新的第二行，于是第三行一共减掉了 $5\times2=10$ 倍第一行，$(3,1)$ 位置因此出现 $-5\cdot(-2)=10$。也就是说，$E$ 把两步的乘数相乘混合在了一起。$L=E_{21}^{-1}E_{32}^{-1}$ 则是按相反顺序作用：先补回 $5$ 倍第二行，再补回 $2$ 倍第一行。此时乘数 $2$ 和 $5$ 各归各位，$(3,1)$ 没有再被交叉乘上，保持为 $0$。这就是 $L$ 比 $E$ 好读的原因：它直接记录每一步用了什么乘数。

4. 用求和公式与积分分别解释 $n^3/3$ 的来源。

参考答案：第一步消元要更新大约 $n^2$ 个元素，第二步处理剩下的 $(n-1)\times(n-1)$ 块，约 $(n-1)^2$ 次，依此类推，总运算量是

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}=\frac{n^3}{3}+O(n^2)\approx\frac{n^3}{3}.$$

用积分看更直观：把这个和看成对 $x^2$ 在 $[0,n]$ 上的黎曼和，

$$\int_0^n x^2\,dx=\frac{n^3}{3},$$

两者只差低阶项。所以消元是 $O(n^3)$，而处理一个右端向量只要 $O(n^2)$——这正是「多个右端共享同一个 $A$ 时先做一次 $LU$」更划算的原因。

5. 为什么排列矩阵的逆等于它的转置？

参考答案：排列矩阵 $P$ 是把单位矩阵的行重新排列得到的，所以它的每一列恰好是某个标准基向量 $\mathbf{e}_{\sigma(i)}$。两个不同的列是互相垂直的单位向量，自身点积为 $1$。因此

$$P^{T}P=I,$$

即 $P^{T}$ 是 $P$ 的逆。直观上：$P$ 把行按某个置换搬动，$P^{T}$ 把它搬回去；搬过去再搬回来就是原样，所以转置恰好完成了逆的操作。

与前后课的关系

$LU$ 把消元从一个过程变成了一个对象。下一讲转向转置、排列与向量空间 $R^n$，为四个基本子空间做准备。

Two small formulas first

The inverse of a product reverses the order

If $A$ and $B$ are invertible, then

$$(AB)^{-1}=B^{-1}A^{-1}.$$

Check:

$$(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=I.$$

The order must reverse, like shoes and socks: shoes come off first, so socks go on first when undoing the process.

Transpose and inverse commute

Start from $A^{-1}A=I$ and transpose both sides:

$$(A^{-1}A)^T=I^T=I.$$

Since $(A^{-1}A)^T=A^T(A^{-1})^T$,

$$A^T(A^{-1})^T=I,$$

so

$$(A^T)^{-1}=(A^{-1})^T.$$

For a single matrix, transposing and inverting can be done in either order.

Timeline

The core: $A=LU$

Assume no row exchanges are needed and no pivot is zero. Each elimination step is an elementary matrix $E_{ij}$, and at the end

$$E_{32}E_{31}E_{21}A=U.$$

Call the product $E$, so $EA=U$. To isolate $A$, multiply on the left by $E^{-1}$:

$$A=E^{-1}U.$$

The inverse of a product reverses the order:

$$E^{-1}=(E_{32}E_{31}E_{21})^{-1} =E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}.$$

That product is $L$:

$$A=LU.$$

$U$ is upper triangular; $L$ is lower triangular with ones on the diagonal.

A $2\times 2$ example

$$A=\begin{bmatrix}2&1\\8&7\end{bmatrix}.$$

The first pivot is $2$, and eliminating the $8$ below it needs multiplier $8/2=4$:

$$E_{21}=\begin{bmatrix}1&0\\-4&1\end{bmatrix}, \qquad U=\begin{bmatrix}2&1\\0&3\end{bmatrix}.$$

Check $E_{21}A=U$: the second row is $-4$ times row one plus row two, $[8,7]-4[2,1]=[0,3]$.

$L$ is $E_{21}^{-1}$: change $-4$ to $+4$.

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}, \qquad A=\begin{bmatrix}1&0\\4&1\end{bmatrix} \begin{bmatrix}2&1\\0&3\end{bmatrix} = \begin{bmatrix}2&1\\8&7\end{bmatrix}.$$

Pulling out the pivots: $LDU$

Factor the diagonal out of $U$:

$$U= \begin{bmatrix}2&0\\0&3\end{bmatrix} \begin{bmatrix}1&1/2\\0&1\end{bmatrix} =D U'.$$

Then $A=LDU'$: unit triangular matrices on both sides and a diagonal matrix in the middle. MATLAB may return either form; the course mostly uses $LU$.

The $3\times 3$ case: why $L$ holds the multipliers directly

For three dimensions the elimination sequence is

$$E_{32}E_{31}E_{21}A=U,$$

so

$$A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU.$$

The real question is why $L$ is nicer than $E$. Take a typical case:

$$E_{21}=\begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix}, \qquad E_{31}=I, \qquad E_{32}=\begin{bmatrix}1&0&0\\0&1&0\\0&-5&1\end{bmatrix}.$$

First compute $E=E_{32}E_{21}$:

$$E= \begin{bmatrix} 1&0&0\\ -2&1&0\\ 10&-5&1 \end{bmatrix}.$$

A $10$ appears in position $(3,1)$. Where from? Subtracting twice row one from row two, then five times the new row two from row three, throws $5\times 2=10$ copies of row one into row three.

Nothing is wrong, but $E$ is hard to read: the multipliers $2$ and $5$ are entangled.

Now invert in reverse order:

$$L=E_{21}^{-1}E_{32}^{-1} = \begin{bmatrix}1&0&0\\2&1&0\\0&0&1\end{bmatrix} \begin{bmatrix}1&0&0\\0&1&0\\0&5&1\end{bmatrix} = \begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&5&1 \end{bmatrix}.$$

The multipliers $2$ and $5$ sit exactly where they belong, and position $(3,1)$ is $0$.

One-sentence summary: With no row exchanges, $L$ is a ledger of multipliers — whatever multiplier elimination used goes straight into the corresponding slot of $L$.

This is why $LU$ is the right record of elimination: once it is done, all the information in $A$ lives in $L$ and $U$, and the original matrix can be discarded.

Operation count: why $n^3/3$

How expensive is elimination? For an $n\times n$ matrix, the first step updates about $n^2$ entries. The second works on the remaining $(n-1)\times(n-1)$ block, about $(n-1)^2$ operations. Continuing:

$$n^2+(n-1)^2+\cdots+2^2+1^2.$$

There are $n$ terms, the largest is $n^2$, so the crude bound is $n^3$. More precisely,

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}\approx\frac{n^3}{3}.$$

The integral makes the constant visible:

$$\int_0^n x^2\,dx=\frac{n^3}{3}.$$

So elimination is $O(n^3)$. The right-hand side $\mathbf{b}$ is a single column, so handling it costs $O(n^2)$.

That yields a practical rule: when many right-hand sides share the same $A$, factor once into $LU$, then run forward and back substitution at $O(n^2)$ per right-hand side. It is far cheaper than re-eliminating each time.

When rows must be exchanged: permutations

If a zero appears in a pivot position, rows must be swapped. A permutation matrix $P$ does the swapping; it is the identity with its rows rearranged.

There are $3!=6$ permutation matrices of size $3$, and $4!=24$ of size $4$. They form a group:

• the product of two permutations is another permutation;
• every permutation is invertible, and its inverse is also a permutation;
• in fact, $P^{-1}=P^T$. Swapping two rows twice restores the original, so many $P$ are their own inverse; in general the inverse equals the transpose.

With row exchanges, the factorization becomes

$$PA=LU.$$

The permutation records the row order first, and $L$ and $U$ keep the same structure.

Takeaways

• $(AB)^{-1}=B^{-1}A^{-1}$: the order reverses.
• $(A^T)^{-1}=(A^{-1})^T$.
• Without row exchanges, $E_{32}E_{31}E_{21}A=U$, hence $A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU$.
• $L$ has ones on the diagonal and the multipliers off it; $U$ has the pivots on its diagonal.
• $A=LDU'$ separates the pivots from the unit triangular factors.
• Elimination costs about $n^3/3$; each right-hand side costs about $n^2$.
• With row exchanges, $PA=LU$. There are $n!$ permutation matrices, and $P^{-1}=P^T$.

Check your understanding

1. Verify $(AB)^{-1}=B^{-1}A^{-1}$ and explain why the order cannot be preserved.

Reference answer: Multiply directly:

$$(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=I,$$

so $B^{-1}A^{-1}$ really is the inverse of $AB$. The order cannot be kept, because

$$(AB)(A^{-1}B^{-1})=A(BA^{-1})B^{-1},$$

and $BA^{-1}$ is generally not $A^{-1}B$ unless the two matrices commute; then the product is not $I$. The picture is getting dressed: socks first, then shoes, so undressing must remove the shoes first and the socks second — reversed order.

2. For $A=\begin{bmatrix}2&1\\8&7\end{bmatrix}$, write $E_{21}$, $U$, and $L$, and verify $A=LU$.

Reference answer: The first pivot is $2$; clearing the $8$ uses multiplier $8/2=4$, so

$$E_{21}=\begin{bmatrix}1&0\\-4&1\end{bmatrix},\qquad U=\begin{bmatrix}2&1\\0&3\end{bmatrix}.$$

Check $E_{21}A=U$: row two becomes $[8,7]-4[2,1]=[0,3]$. Then $L=E_{21}^{-1}$ changes $-4$ to $+4$:

$$L=\begin{bmatrix}1&0\\4&1\end{bmatrix}.$$

Indeed

$$LU=\begin{bmatrix}1&0\\4&1\end{bmatrix}\begin{bmatrix}2&1\\0&3\end{bmatrix} =\begin{bmatrix}2&1\\8&7\end{bmatrix}=A.$$

3. In the $3\times 3$ example, why is the $(3,1)$ entry of $E$ equal to $10$, while the same entry of $L$ is $0$?

Reference answer: Here $E=E_{32}E_{21}$. After $E_{21}$, row two is the original row two minus twice row one; then $E_{32}$ subtracts five times that new row two from row three. So row three loses $5\times2=10$ times row one in total, and the $(3,1)$ entry becomes $-5\cdot(-2)=10$: the two multipliers have been multiplied together and mixed. In $L=E_{21}^{-1}E_{32}^{-1}$ the operations are undone in reverse order — first restore five times row two, then twice row one — so the multipliers $2$ and $5$ sit in their own positions and $(3,1)$ is untouched at $0$. That is why $L$ reads as a ledger of multipliers.

4. Explain the $n^3/3$ count both with the sum of squares and with an integral.

Reference answer: The first elimination step updates roughly $n^2$ entries; the next works on the remaining $(n-1)\times(n-1)$ block, about $(n-1)^2$ operations, and so on, giving

$$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}=\frac{n^3}{3}+O(n^2)\approx\frac{n^3}{3}.$$

As an integral, the sum is a Riemann sum for $x^2$ on $[0,n]$:

$$\int_0^n x^2\,dx=\frac{n^3}{3},$$

differing only in lower-order terms. Hence elimination costs $O(n^3)$, while each right-hand side costs $O(n^2)$ — which is why one $LU$ factorization pays off when many right-hand sides share $A$.

5. Why is the inverse of a permutation matrix equal to its transpose?

Reference answer: A permutation matrix is the identity with its rows rearranged, so each column is a standard basis vector $\mathbf{e}_{\sigma(i)}$. Distinct columns are orthogonal unit vectors, and each has squared length $1$. Therefore

$$P^{T}P=I,$$

so $P^{T}$ is the inverse of $P$. In words: $P$ moves rows by a permutation, and $P^{T}$ moves them back; doing both is the identity.

How it connects

$LU$ turns elimination from a process into an object. The next lecture turns to transposes, permutations, and the vector space $R^n$, preparing the ground for the four fundamental subspaces.