线代 A1 笔记 第 9 部分（矩阵的分块）

定义及运算法则

按照某种特征，将矩阵的行和列分成若干组，分割为若干子阵。可以理解为，分块矩阵的元素是小矩阵。

加法（需要分块完全一致）和数乘的规则是显然的。

转置需要把每个子矩阵也转置，例如

$$\begin{bmatrix} A & B \\ C & D \\\end{bmatrix}^T=\begin{bmatrix} A^T & C^T \\ B^T & D^T \\\end{bmatrix}$$

做乘法的唯一前提：左阵列分组与右阵行分组一致，例如

$$\begin{bmatrix} A & B & C \\ D & E & F \\ \end{bmatrix} \begin{bmatrix} X \\ Y \\ Z \\\end{bmatrix}=\begin{bmatrix} AX+BY+CZ \\ DX+EY+FZ \\\end{bmatrix}$$

左乘和右乘不能搞反。

小应用：考虑 $\operatorname{rref}(A)=\begin{bmatrix} I_m & B \\\end{bmatrix}$，则 $AX=0$ 的解空间为 $\begin{bmatrix} -B \\ I_{n-m} \\\end{bmatrix}$ 的列空间。为何？

$$\begin{bmatrix} I_m & B \\\end{bmatrix}\begin{bmatrix} -B \\ I_{n-m} \\\end{bmatrix} = -I_mB + BI_{n-m} = 0$$

举个例子：对于

$$\operatorname{rref}(A) = \begin{bmatrix} \color{red} 1 & \color{red} 0 & \color{green}-1 & \color{red} 0 & \color{green}3 \\ \color{red} 0 & \color{red} 1 & \color{green}2 & \color{red} 0 & \color{green}4 \\ \color{red} 0 & \color{red} 0 & \color{green} 0 & \color{red} 1 & \color{green}-5 \\ \color{red} 0 & \color{red} 0 & \color{green}0 & \color{red} 0 & \color{green}0 \end{bmatrix}$$

则

$$\mathcal{N}(A) = \mathcal{C}\left(\begin{bmatrix} \color{red}1&\color{red}-3 \\ \color{red}-2&\color{red}-4 \\ \color{green}1 &\color{green}0\\ \color{red}0&\color{red}5 \\ \color{green}0&\color{green}1 \\\end{bmatrix}\right)$$

分组不必连续但必须一致。

自由变量对应的行的部分写单位矩阵

和之前提到过的写解空间基底的感觉很像。所以之后解方程的时候就可以直接写解空间了。

再看一个例子（满秩分解）

$$\begin{aligned} \begin{bmatrix} \color{red}2 & \color{plum}-1 & 5 & \color{skyblue}2 & -1 \\ \color{red}4 & \color{plum}-1 & 9 & \color{skyblue}3 & 4 \\ \color{red}3 & \color{plum}-2 & 8 & \color{skyblue}-2 & 1 \\ \color{red}1 & \color{plum}1 & 1 & \color{skyblue}4 & 4 \\ \color{red}3 & \color{plum}1 & 5 & \color{skyblue}8 & 6 \\\end{bmatrix} &= \begin{bmatrix} \color{red}2 & \color{plum}-1 & \color{skyblue}2\\ \color{red}4 & \color{plum}-1 & \color{skyblue}3\\ \color{red}3 & \color{plum}-2 & \color{skyblue}-2\\\color{red}1 & \color{plum}1 & \color{skyblue}4\\\color{red}3&\color{plum}1&\color{skyblue}8\end{bmatrix}\begin{bmatrix} \color{red}1 & & 2 & & 3 \\ & \color{plum}1 & -1 & & 5 \\ & & & \color{skyblue}1 & -1 \\ & & & & \\ & & & & \\\end{bmatrix}\\ &=\begin{bmatrix} \color{red}{2} \\ \color{red}{4}\\ \color{red}{3} \\ \color{red}{1} \\ \color{red}{3} \\\end{bmatrix}\begin{bmatrix} 1 & 0 & 2 & 0 & 3 \\\end{bmatrix} + \begin{bmatrix} \color{plum}-1 \\ \color{plum}-1 \\ \color{plum}-2 \\ \color{plum}1 \\ \color{plum}1 \\\end{bmatrix}\begin{bmatrix} 0 & 1 & -1 & 0 & 5 \\\end{bmatrix}\\&+ \begin{bmatrix} \color{skyblue}2 \\ \color{skyblue}3 \\ \color{skyblue}-2 \\ \color{skyblue}4 \\ \color{skyblue}8 \\\end{bmatrix}\begin{bmatrix} 0 & 0 & 0 & 1 & -1 \\\end{bmatrix} \end{aligned}$$

应用：JPEG 图像压缩

为了方便，这里只考虑 8-bits 的灰度图像。

首先，将整个图像拆分为若干 $8\times 8$ 的子阵考虑（选择这个大小是出于某种对压缩速度和图像质量的平衡）。

第一步是余弦变换。将值域变换到频域上，即用另一个基底来表示原来的矩阵。余弦变换矩阵为

$$C= \frac{1}{2}\begin{bmatrix} \frac{1}{\sqrt{2}} & \cos \frac{\pi}{16} & \cos \frac{2\pi}{16} & \cdots & \cos \frac{7\pi}{16} \\ \frac{1}{\sqrt{2}} & \cos \frac{3\pi}{16} & \cos \frac{6\pi}{16} & \cdots & \cos \frac{7\times 3\pi}{16} \\ \frac{1}{\sqrt{2}} & \cos \frac{5\pi}{16} & \cos \frac{10\pi}{16} & \cdots & \cos \frac{7\times 5\pi}{16} \\ \vdots & \vdots & \vdots & & \vdots \\ \frac{1}{\sqrt{2}} & \cos \frac{15\pi}{16} & \cos \frac{30\pi}{16} & \cdots & \cos \frac{7\times 15\pi}{16} \\\end{bmatrix}$$

列向量由低频向高频排列，$\left\{ \alpha_i\alpha_j^T \right\}$ 构成线性空间 $M_{8\times 8}(\mathbb{R})$ 的基底。左上角低频、右下角高频。这个矩阵是正交的。

现在我们面临的问题就是，设 $X = \displaystyle \sum_{0<\le i,j\le 7} b_{ij}\alpha_i\alpha_j^T$，求表出系数 $b_{ij}$。而若使用分块乘法，上面可以拆成：

$$\begin{aligned} X&= \begin{bmatrix} \alpha_0 & \alpha_1 & \cdots & \alpha_7 \\\end{bmatrix} \begin{bmatrix} b_{00} & b_{01} & \cdots & b_{07} \\ b_{10} & b_{11} & \cdots & b_{17} \\ \vdots & \vdots & & \vdots \\ b_{70} & b_{71} & \cdots & b_{77} \\\end{bmatrix}\begin{bmatrix} \alpha_0^T \\ \alpha_1^T \\ \vdots \\ \alpha_7^T \\\end{bmatrix}\\ &= CBC^T \end{aligned}$$

注意到 $C$ 为正交矩阵，$C^{-1} = C^T$。两边左乘 $C^T$，右乘 $C$，即得到 $B = C^TXC$。

（一开始不要忘记平移定义域至 $[-128,127]$，以方便余弦函数的操作）余弦变换完了之后，信息此时还没有丢失，只是换了个基底而已（当然硬说浮点运算确实也是带来了损失的），但是很重要的一点就是此时矩阵的左上角储存低频信息，右下角高频信息。

基于人眼对高频信息不那么敏感的事实，我们可以通过舍弃高频信息来实现对图像的压缩。具体地，我们有量化矩阵 $Q$，这个矩阵的左上角元值较小，右下角元较大，将矩阵的每个 $(i,j)$ 元除以量化矩阵中对应的 $(i,j)$ 元再四舍五入，得到的就是高度压缩化后的矩阵。此时右下角应该会有很多 $0$。

再之后用 zig-zag 的方式将二维的矩阵变换成一维序列，再用特定的压缩方式（如 Huffman 编码）压缩即可。

分块矩阵的初等变换

1. 把一个块行的左 $P$ 倍（$P$ 是矩阵）加到另一个块行上。形如 $\begin{bmatrix} I_1 & & \\ A & I_2 & \\ & & I \\\end{bmatrix}$。
2. 两个块行互换。$\begin{bmatrix} & I_2 & \\ I_1 & & \\ & & I \\\end{bmatrix}$
3. 用一个可逆矩阵左乘某一块行：$\begin{bmatrix} I_1 & & \\ & C & \\ & & I \\\end{bmatrix}$

做初等行变换，就是用初等分块矩阵左乘；相应地做列变换就是右乘。

例：$A$，$B$ 分别是 $m$ 阶，$n$ 阶方阵，$C$ 为 $m\times n$ 矩阵，则 $\begin{bmatrix} A & B \\ 0 & C \\\end{bmatrix}$ 可逆当且仅当 $A$ 和 $C$ 均可逆（考虑行列式）。

求其逆的过程和求数值矩阵的逆可以说是完全一样：

$$\left[ \begin{array}{cc|cc}A&B&I_m&\\ 0&C&&I_n\end{array} \right] \to \left[ \begin{array}{cc|cc}I_m&A^{-1}B&A^{-1}&\\ 0&I_n&&C^{-1}\end{array} \right]\\ \to\left[ \begin{array}{cc|cc}I_m&0&A^{-1}&-A^{-1}BC^{-1}\\ 0&I_n&&C^{-1}\end{array} \right]$$

故

$$\begin{bmatrix} A & B \\ 0 & C \\\end{bmatrix}^{-1} = \begin{bmatrix} A^{-1} & -A^{-1}BC^{-1} \\ 0 & C^{-1} \\\end{bmatrix}$$

同时利用分块初等变换还可以处理之前的一个经典结论：

求证：设 $A\in M_{m\times n}(K)$，$B\in M_{n\times k}(K)$，则 $\operatorname{rank}(A) + \operatorname{rank}(B)\le \operatorname{rank}(AB) + n$。

考虑 $\operatorname{rank}\left( \begin{bmatrix} A & 0 \\ I_n & B \\\end{bmatrix} \right) \ge \operatorname{rank}(A) + \operatorname{rank}(B)$，且 $\operatorname{rank}\left( \begin{bmatrix} AB & 0 \\ 0 & I_n \\\end{bmatrix} \right) = \operatorname{rank}(AB) + n$。

而 $\begin{bmatrix} A & 0 \\ I_n & B \\\end{bmatrix}$ 第一行减去第二行左乘 $A$ 倍，得到 $\begin{bmatrix} 0 & -AB \\ I_n & B \\\end{bmatrix}$，再然后第二列减去第一列左乘上 $B$ 得到 $\begin{bmatrix} 0 & -AB \\ I_n & 0 \\\end{bmatrix}$，第二列乘上 $-1$ 倍，再和第一列交换位置即得到 $\begin{bmatrix} AB & 0 \\ 0 & I_n \\\end{bmatrix}$。

初等变换不改变秩，证毕。

接下来再看一个应用：

设 $A\in M_{m\times n}(K)$，$B\in M_{n\times m}$，求证 $\left\vert I_m - AB \right\vert =\left\vert I_n-BA \right\vert$。

仍旧是考虑初等变换。

$$\begin{aligned} \begin{bmatrix} I_n & \\ -A & I_m \\\end{bmatrix}\begin{bmatrix} I_n & B \\ A & I_m \\\end{bmatrix} &= \begin{bmatrix} I_n & B \\ & I_m - AB \\\end{bmatrix}\\ \begin{bmatrix} I_n & -B \\ & I_m \\\end{bmatrix}\begin{bmatrix} I_n & B \\ A & I_m \\\end{bmatrix} &= \begin{bmatrix} I_n - BA & \\ A & I_m \\\end{bmatrix} \end{aligned}$$

同时取行列式，即证。

这就引申出了一个结论：如果 $I_m - AB$ 可逆，则 $I_n - BA$ 也可逆，如何构造？

考虑下面这个式子：

$$\begin{aligned} \frac{1}{1-ba} &= 1 + ba + baba + bababa + \cdots \\ &= 1 + b(1 + ab + abab + \cdots )a\\ &= 1 + b(1-ab)^{-1}a \end{aligned}$$

所以

$$(I_n - BA)^{-1} = I_n + B(I_m - AB)^{-1}A$$

通过展开不难验证其正确性。口诀：改号拉开填逆。

Cauchy-Binet 公式

定理内容：设 $A\in M_{m\times n}(K)$，$B\in M_{n\times m}(K)$，则

1. 若 $m > n$，则 $|AB| = 0$；

2. 否则，则

   $$|AB| = \sum_{1\le \nu_1<\cdots<\nu_m\le n}A\begin{pmatrix} 1, \cdots ,m \\ \nu_1, \cdots ,\nu_m \\\end{pmatrix}B\begin{pmatrix} \nu_1, \cdots ,\nu_m \\ 1, \cdots ,m \\\end{pmatrix}$$

   即，$|AB|$ 等于所有 $A$ 的 $m$ 阶子式与对应的 $B$ 的 $n$ 阶子式乘积之和。

证明：考虑若 $m>n$，则显然乘出来的 $m$ 级方阵不满秩，行列式为 $0$。

否则考虑下列 $n+m$ 级分块矩阵，然后将第一行左乘上 $-A$ 加到第二行上：

$$\begin{bmatrix} I_n & 0 \\ -A & I_m \\\end{bmatrix}\begin{bmatrix} I_n & B \\ 0 & AB \\\end{bmatrix} = \begin{bmatrix} I_n & B \\ -A & 0 \\\end{bmatrix}$$

两边同时取行列式得到 $|AB| = \begin{vmatrix} I_n & B \\ -A & 0 \\\end{vmatrix}$。

接下来做两次 Laplace 展开立得。具体地先按后 $m$ 行展开：

$$\begin{vmatrix} I_n & B \\ -A & 0 \\\end{vmatrix} = \sum_{1\le \nu_1 < \cdots < \nu_m\le n}(-A)\begin{pmatrix} 1, \cdots ,m \\ \nu_1, \cdots ,\nu_m \\\end{pmatrix}(-1)^{\sum_{k=1}^m(n+k)+\sum_{k=1}^m\nu_k} \begin{vmatrix}\varepsilon_{\mu_1}&\cdots&\varepsilon_{\mu_{n-m}}&B\end{vmatrix}$$

其中 $\left\{ \mu_1, \cdots ,\mu_{n-m} \right\} = \left\{ 1, \cdots ,n \right\} \backslash \left\{ \nu_1, \cdots ,\nu_m \right\}$。再接下来把 $\begin{vmatrix}\varepsilon_{\mu_1}&\cdots&\varepsilon_{\mu_{n-m}}&B\end{vmatrix}$ 按前 $n-m$ 行展开。有 $1$ 的堪称很少：

$$\begin{vmatrix}\varepsilon_{\mu_1}&\cdots&\varepsilon_{\mu_{n-m}}&B\end{vmatrix} = |I_{n-m}|(-1)^{\sum_{k=1}^{n-m}\mu_k + \sum_{k=1}^{n-m}k}B\begin{pmatrix} \nu_1, \cdots ,\nu_m \\ 1, \cdots ,m \\\end{pmatrix}$$

综上，

$$\begin{aligned} \begin{vmatrix} I_n & B \\ -A & 0 \\\end{vmatrix} &= \sum_{1\le \nu_1 < \cdots < \nu_m\le n}(-A)\begin{pmatrix} 1, \cdots ,m \\ \nu_1, \cdots ,\nu_m \\\end{pmatrix}(-1)^{\sum_{k=1}^m(n+k)+\sum_{k=1}^m\nu_k} (-1)^{\sum_{k=1}^{n-m}\mu_k + \sum_{k=1}^{n-m}k}B\begin{pmatrix} \nu_1, \cdots ,\nu_m \\ 1, \cdots ,m \\\end{pmatrix} \\ &= \sum_{1\le \nu_1<\cdots<\nu_m\le n}(-1)^{n+n^2+m+m^2}A\begin{pmatrix} 1, \cdots ,m \\ \nu_1, \cdots ,\nu_m \\\end{pmatrix}B\begin{pmatrix} \nu_1, \cdots ,\nu_m \\ 1, \cdots ,m \\\end{pmatrix}\\ &= \sum_{1\le \nu_1<\cdots<\nu_m\le n}A\begin{pmatrix} 1, \cdots ,m \\ \nu_1, \cdots ,\nu_m \\\end{pmatrix}B\begin{pmatrix} \nu_1, \cdots ,\nu_m \\ 1, \cdots ,m \\\end{pmatrix} \end{aligned}$$

证毕。

下面看一个小应用：

用 Cauchy-Binet 公式证明 Lagrange 恒等式；

$$\left( \sum_{i=1}^n a_i^2 \right)\left( \sum_{i=1}^nb_i^{2} \right) - \left( \sum_{i=1}^na_ib_i \right) ^{2} = \sum_{1\le i<j\le n}\begin{vmatrix} a_i & a_j \\ b_i & b_j \\\end{vmatrix}^{2}$$

注意到其实际就是 Cauchy 不等式的形式，只不过把不等号变成了等号且给出了很具体的值。

证明：$\text{L.H.S.} = \begin{vmatrix} \displaystyle \sum_{i=1}^n a_i^2 & \displaystyle \sum_{i=1}^na_ib_i \\ \displaystyle \sum_{i=1}^nb_ia_i & \displaystyle \sum_{i=1}^nb_i^2 \\\end{vmatrix} = \left\vert \begin{bmatrix} a_1 & a_2 & \cdots & a_n \\b_1&b_2&\cdots&b_n\end{bmatrix}\begin{bmatrix} a_1&b_1 \\ a_2&b_2 \\ \vdots&\vdots \\ a_n&b_n \\\end{bmatrix} \right\vert$，然后用 Cauchy-Binet 公式即可。

这个公式在 $n=2$ 的形式可能大家会更为熟悉：$(a_1^2+a_2^{2})(b_1^{2}+b_2^{2}) = (a_1b_1+a_2b_2)^{2} + (a_1b_2-a_2b_1)^{2}$