1883 年, Georg Cantor 提出了 良序原理. 由于他所谓的 法则 并未立即得到接受, Cantor 发现自己不得不寻求证明. 为了提供这样的证明, 选择公理 $\textsf{AC}$ 在 1904 年由 Ernst Zermelo 首次明确表述出来.

对于任意非空集合族 $\mathscr{F}$, 存在一个选择函数 $f$ 为每个 $A \in \mathscr{F}$ 分配一个元素 $f(A) \in A$.

$\gdef\spaces#1{~ #1 ~}$

此问题 来自一本名为 The Canterbury Puzzles 的书, 是其中的 “The Puzzle of the Doctor of Physic” 的重述. 本文希望以此问题为起点, 介绍历史上若干算术问题的几何方法.

Problem 1.1.1. 古代物理学博士问题 [canterbury-2A][edit]

• December 26, 2024
• kokic
• Pearls

$\gdef\spaces#1{~ #1 ~}$

有两个正方体, 一个边长为 $1$, 另一个边长为 $2$. 请找到另外两个边长为有理数的正方体使它们的体积总和相同. 换言之, 求下述方程的一组 (正) 有理解.

$$ x^3 + y^3 \spaces= 9 \quad \color{gray}{(= ~ 1^3+2^3)} $$

我们先画出 $x^3 + y^3 = 9$. 然后由已知的 $P=(1,2)$ 出发做切线得到 $2P$, $4P$, $8P$. 这种几乎全凭借运气的操作是 Fermat 及 Viète 研究此类问题的方式.

如图, 随后注意到 $8P$ 恰好位于 $x > 0,y > 0$ 的区域, 现在计算其坐标.

$$ 8P \spaces= \left(\frac{1243617733990094836481}{609623835676137297449}, \frac{487267171714352336560}{609623835676137297449}\right) $$

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$

我们对于 $\R$ 上的单位圆周曲线 $C(\R):x^2+y^2=1$ 和它关于角度 $\theta$ 的参数化 $\theta \mapsto (\cos\theta, \sin\theta)$ 是不陌生的. 通过计算这类统称为三角函数或者圆函数的映射, 很容易就能发现圆上的一些不同寻常的点

$$ (\tfrac1{\sqrt2}, \tfrac1{\sqrt2}), \quad (\tfrac{1+\sqrt5}4, \sqrt{\tfrac58 - \tfrac{\sqrt5}8}), \quad (\tfrac{\sqrt3}2, \tfrac12) $$

但是如果我们希望找到 $C(\Q)$ 上的点, 这个参数化就没有那么有用了. 考虑 $C(\Q):x^2+y^2=r^2$, 我们从点 $P(-r, 0)$ 出发, 任选一个 $t \in \Q$ 作为过 $P$ 点直线的斜率, 即 $y = t(x+r)$, 随后联立之.

$$ (1+t^2)x^2 + 2rt^2x + r^2t^2 - r^2 = 0 $$

由于我们已经知道它的一个根 $x_1 = -r$. 且根与系数的关系给出

$$ x_1 + x_2 = -\frac{2rt^2}{1+t^2} $$

立得 $x_2 = r \cdot \frac{1-t^2}{1+t^2}$. 从而给出一个熟知的有理参数化

$$ t \quads\mapsto r \cdot \bigg(\frac{1-t^2}{1+t^2}, \frac{2t}{1+t^2}\bigg) $$

这样一种寻找点的方式, 通常被称为弦切法.

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\d{\operatorname{d}}$ $\gdef\E{\operatorname{E}}$ $\gdef\arc{\text{arc}}$ $\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$

考虑半径为 $r$ 的实圆周 $x^2+y^2=r^2$，其在上半平面的轨迹可表为函数 $y=\sqrt{r^2-x^2},x\in[-r,r]$，长度 为

$$ L \spaces= \int_{-r}^r\dfrac{r}{\sqrt{r^2-x^2}}\d x \spaces= r\arcsin\dfrac{x}{r}\bigg|_{-r}^r \spaces= \pi r $$

因而圆的弧长定义了反正弦函数，即

$$ \arcsin x \spaces= \int_0^x\dfrac{1}{\sqrt{1-t^2}}\d t $$

其反函数被称为正弦函数，统称圆函数或者三角函数.

现在, 注意到 $\cot(x)$ 和 $\cot^\prime(x)$ 满足 $\cot^2(x) + \cot^\prime(x) = 1$, 令 $(\cot(x), \cot^\prime(x)) \mapsto (x,y)$, 即 $y=c-x^2$.

其他三角函数及其导数也有类似的关系, 以下列出.

$$\def\arraystretch{2}\begin{array}{|c|c|c|c|} \hline u & (u, u^\prime) \mapsto (x,y) & g & \int \frac{\d x}{y} \\ \hline \cot & y = -x^2-1 & 0 & -\tan^{-1} x \\ \hline \tan & y = x^2 + 1 & 0 & \tan^{-1} x \\ \hline \cos, \sin & y^2 = 1-x^2 & 0 & \tan^{-1}\dfrac{x}{\sqrt{1-x^2}} \\ \hline \sec, \csc & y^2 = x^4-x^2 & 0 & \dfrac{x\sqrt{x^2-1} \tan^{-1}(\sqrt{x^2-1})}{\sqrt{x^4-x^2}} \\ \hline \end{array}$$

现在取 $C(\Q): y=x^2+1$ 上一定点 $(0, 1)$, 固定斜率 $t$ 从而有直线 $\ell(\Q): y=tx+1$, 类似地求曲线 $\ell(\Q) \cdot C(\Q) = 0$ 的交点, 得到 $(t, t^2+1)$.

如果我们对抛物线 $C(\R)$ 求弧长, 所得到的将是 $\log$ 或 $\sinh^{-1}$ 的代数函数. 当然, $\sinh^{-1}$ 实际上也是 $\log$ 的代数函数. $$ \begin{aligned} s &\spaces= \int\sqrt{1+(2x)^2}\d x \\ &\spaces= \frac12 \sqrt{1+4x^2} + \frac14\sinh^{-1}(2x) \end{aligned} $$

现在重新回顾

$$ \int\dfrac{\d x}{y}, \quad y = \sqrt{r^2-x^2} $$

积分号内的项是 $x,y$ 的有理函数, $y$ 是 $x$ 的代数函数, 同时我们已经知道 $x,y$ 满足的代数方程有一个 有理参数化, 也就是说

$$ \begin{aligned} \int\dfrac{\d x}{y} &\spaces= \int \frac{\d{(\frac{1-t^2}{1+t^2})}}{\frac{2t}{1+t^2}} \\ &\spaces= \int -\frac{4t}{(1+t^2)^2} \cdot \frac{1+t^2}{2t} \d t \\ &\spaces= \int -\frac{2}{1+t^2} \d t \\ &\spaces= -2\tan^{-1} t \end{aligned} $$

这是 切线半角换元 或者按俄罗斯与国内更流行的称呼则是万能三角换元. 另一方面, 我们知道 $t = \pm\frac{\sqrt{1-x}}{\sqrt{1+x}}$. 这就意味着 $\arcsin x$ 和 $-2\tan^{-1} t$ 之间最多只相差一个常数, 容易计算这个常数正是 $\frac{\pi}2$, 则有

$$ \arcsin x \spaces= \frac{\pi}2-2\arctan\frac{\sqrt{1-x}}{\sqrt{1+x}} $$

双曲线时的情况略有不同. 考虑 $C(\R):x^2-y^2=1$, 如果朴素地计算平面直角坐标系上的积分, 将得到一个会被归类为椭圆积分的表达式

$$ \int \sqrt{\frac{2x^2-1}{x^2-1}} \d x \spaces= \int \frac{4x^4-1}{\sqrt{x^2-1}\sqrt{2x^2+1}} \d x $$

由于分子部分的 $4x^4-1$ 是多项式函数, 因此整个积分的核心就在于下面这一项

$$ \int \frac1{\sqrt{(x^2-1)(2x^2+1)}} \d x \tag{1} $$

椭圆积分的经验 很容易让我们认为最后的结果当中势必会出现 椭圆函数. 事实正是如此, 注意这个时候 $y^2 = (x^2-1)(2x^2+1)$ 的 $g$ 是 $1$, 而且实际上在引入椭圆函数后, $(1)$ 的表达式要远比弧长的表达式复杂.

现在考虑双曲线 $C(\R)$ 的一个参数化 $$ (x,y) \quads\mapsto (\cosh t, \sinh t) $$

相应的, 关于 $x \in [a,b]$ 弧长积分变为 $t \in [\cosh^{-1}a, \cosh^{-1}b]$ 的积分

$$ \begin{aligned} \int \sqrt{\sinh^2 t + \cosh^2 t} \d t &\spaces= \int \sqrt{\cosh 2t} \d t \\ &\spaces= -i \E(it \mid 2) \\ &\spaces= -i \E(i \cosh^{-1}x \mid 2) \\ &\spaces= \E(\sin^{-1}x \mid 2) \\ \end{aligned} $$

$\gdef\spaces#1{~ #1 ~}$

对于周期 $1$. 下面这个观察因为 Weierstraß 的使用而变得广为人知. 具体来说, 可以从这样一个级数出发

$$ f(x) \spaces= \sum_{n \in \Z} \frac1{(n-x)^2}, \quad x \notin \Z $$

因为 $n$ 取遍了所有整数, $f(x)$ 在映射 $n \mapsto n + k$, $k \in \Z$ 下不变. 这样一来, 如果 $x$ 被选定为任意一个整数, 总会存在 $n-x$ 为零的项使整个级数发散, 这就要求 $x \notin \Z$. 同样的, $f(x)$ 在映射 $x \mapsto x + k$, $k \in \Z$ 下不变, 这就意味着 $f(x)$ 以 $1$ 为周期. 现在我们当然知道这个 $f(x)$ 其实就是 $\pi^2\csc^2(\pi x)$.

由于 $(n-x)^2 \ge x^2-n^2$, 这使得如下级数也是收敛的

$$ \sum_{n \in \Z} \frac{x}{x^2-n^2} \quad (= ~ \pi\cot(\pi x)) $$

$\gdef\R{\mathbf{R}}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\spaces#1{~ #1 ~}$

我们要求两个 $\R$-周期 $T_1,T_2$ 是 $\R$-线性无关的, 否则周期之比 $\frac{T_1}{T_2} = \frac{p}{q} \in \Q$, $\gcd(p,q) = 1$, 这意味着 $T_i$ 生成的周期集合退化

$$ \begin{aligned} \{ nT_1 + mT_2 : n,m \in \Z \} &\spaces= \left\{ \left(\frac{np}{q} + m \right) T_2 : n,m \in \Z \right\} \\ &\spaces= \left\{ (np + mq) \cdot \frac{T_2}{q} : n,m \in \Z \right\} \end{aligned} $$

此时 $np + mq \in \Z$, 所以该集合被周期 $\frac{T_2}{q}$ 生成, 矛盾.

$\gdef\spaces#1{~ #1 ~}$

二叉树意味树的每个结点最多两个子树. 其类型由两个构造器归纳给出

inductive Tree α
  | leaf : Tree α
  | node : α → Tree α → Tree α → Tree α

叶结点构造器 leaf 用于构造出一棵空树, 空树作为某个结点的所有子结点时, 该结点正是叶结点. 相应的, 二叉树的值存储在非叶结点中. 每个 (非空, 无标记) 二叉树类型的值要么是一个单结点 $\{\text{pt}\} = 1$, 要么等价于二叉树的有序配对 $B \times B = B^2$. 即 $B \xrightarrow{\sim} \{\text{pt}\} \sqcup B^2$.

换言之, 二叉树可定义为某种满足 $B=1+B^2$ 的 (代数) 结构. 回顾 $6$ 次分圆多项式 $$ \Phi_6(x) \spaces= x^2-x+1 $$ 其复根 $\zeta_6$, $\zeta^{-1}_6$ 是所谓的 $6$ 次本原单位根.

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

记 $B$ 是二叉树类型, 则存在一个 “极精确的双射” $B \xrightarrow{\sim} B^7$.

显然并非所有 $\zeta_6$ 满足的等式都能提升到 $B$ 之间的同构, 如 $B^6 \ncong 1$. 自然的问题是, 哪些等式能提升到同构? 这个问题由下面的 Fiore–Leinster 定理 回答.

特别的, 取 $f(x)=1+x^2$, Fiore–Leinster 定理 表明, 若在 $\N[x]/(x=1+x^2)$ 中成立 $f(x) = g(x)$, 则存在 “极精确的双射” $f(B) \cong g(B)$. 在 $\N[x]/(x=1+x^2)$ 中可以演绎得到 $x=x^7$ 但无法给出 $1=x^6$. 对于前者 $x^7-x = (x^2-x+1)(x^5+x^4-x^2-x) = 0$. 再看 $x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)$, 这给出 $B^4+B^2+1 \ncong 0$, $B^4+B^2+B+1=B$.

这套想法亦可应用于其他树结构, 如有根平面树, 其每个结点有 $0$, $1$ 或 $2$ 个子结点, 即 $T \cong 1+T+T^2$. 由 Fiore–Leinster 定理, 存在 “极精确的双射” $T \cong T^5$.

栈置换 (stack permutation) 也称作栈混洗 (stack shuffle). 给定一个非空栈 $A$ 和空栈 $B$ 与 $S$, 每次只允许 $(i)$ 弹出 $A$ 并压入 $S$. $(ii)$ 弹出 $S$ 并压入 $B$. 可以想见, 最终 $A$ 的元素一定会全部进入 $B$. 这样的 $B$ 就称为 $A$ 的一个栈置换.

以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码.

• 1 表示添加当前树节点的左子树. 例如 111 表示的树为 (⋅ (⋅ (⋅))).
• 01 表示添加当前树节点的右子树. 例如 10101 表示的树为 (⋅ _ (⋅ _ (⋅))).
• 而对于 01 前的 $k$ 个 0, 这些 0 用于表示将当前树节点回溯到前 $k$ 层. 例如 11001 表示的树为 (⋅ (⋅) (⋅)).

注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲.

以下写出三节点二叉树的所有 $5$ 种情况, 以展示这些树的二进制序列如何对应到栈置换. 此处二进制序列按栈弹空为标准, 补充了末尾的零.

首先容易验证的是, 中序遍历总是能够给出二叉树 $b \in B$ 到栈置换 $s \in S$ 的映射, 而对于每一个栈置换 $s \in S$, 都能够写出唯一的二进制序列, 即栈编码 $c \in C$. 不考虑末尾连续的 0, 当栈编码 $c$ 与二叉树 $b$ 的 Hille 编码 $h \in H$ 相同时, 对 $B$ 直接进行中序遍历便能得出正确的 Hille 编码.

$$ \begin{CD} B @>>> S \\ @VVV @VVV \\ H @>>> C \end{CD} $$

现在, Hille 原文所使用的 encode 算法就是 $h \circ g: B \to C$, 而预期的正确实现则是 $f$, 因此两者在结果上相差一个同构.

$\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$ $\gdef\spaces#1{~ #1 ~}$

所有 $n$ 节点二叉树的 Hille 编码构成的集合记为 $H_n$, 所有 $n$ 节点二叉树的栈编码构成的集合记为 $C_n$. 对于 $H_n \cap C_n$ 的大小 $a_n \eqdef |H_n \cap C_n|$, 我们有如下刻画.

$$ a_n \spaces= \sum_{k = 0}^{n-1} \sum_{j = 0}^{n-k} \frac{1}{j+1}\binom{n-k-j}j \binom kj \binom{k+j+2}j $$

记 $N = n+1$. 等式的证明可以通过分析一个半长为 $N$ 且不包含 UUDD 子序列的 Dyck 路径得到. 同时这也是从 $(0,0)$ 到 $(N,N)$ 不越过对角线且允许步长 $(1,k), (k,1), k \geqslant 1$ 的格路径的个数. 或者更简单地说, 是长度为 $N$ 的斜 Motzkin 路径的个数.

记 Catalan 数为 $c_n$, 也即 $H_n$ 或 $C_n$ 的个数. 自然要问 $|H \cap C_n|$ 在全体 $n$ 节点二叉树个数中所占的比例与 $n$ 的关系. 根据 相交数 与 Catalan 数的渐进估计 $a_{n} \sim \frac{\sqrt{2 + r}}{2\sqrt{\pi}n^{3/2}r^{n}}$, $c_n \sim \frac{4^n}{\sqrt\pi n^{3/2}}$ 可以知道 $\lim\limits_{n\to\infty} \frac{a_n}{c_n} = 0$. 并且事实上只要二叉树的节点个数 $n$ 大于 $8$, $H_n$ 与 $C_n$ 相同的部分就会少于整体的一半.

$\gdef\spaces#1{~ #1 ~}$

一个可供探究的问题是, 给定 $n$ 节点二叉树, 询问其 Hille 编码 $H_n$ 有效长度 $\ell(H_n)$ 的范围. 这里的有效不外乎是指去除末尾连续的 0. 我们将对此问题给出确切的回答.

任意 $n$ 节点二叉树的 Hille 编码的有效长度满足下面的不等式

$$n \spaces\leqslant \ell_{n} \spaces\leqslant \max(0,2n - 1,3n - 4)$$

下界 $n$ 的验证是容易的, 构造一棵 $n$ 节点二叉树最少也需要 $n$ 个 1. 由于 此处 的讨论, 我们只需要验证 $n \geqslant 3$ 时 Hille 编码的有效长度至多是 $3n - 4$.

Proof. [bounds-pf][edit]

• November 06, 2024
• kokic

注意到为使有效长度最大, 相应的二叉树中的右节点个数和回溯次数要尽可能多. 同时满足这两个要求意味着 $(i)$ 除根节点外至少有一个左结点 ¹. $(ii)$ 该二叉树必有一个位于根节点右侧的节点 ². 如下图所示

由此出发, 我们将剩余的所有 $n-3$ 个节点全部添加到树中唯一的左节点的右侧. 即

下面我们只需算出 $\ell(M)$, 便可得到 $\ell_n$ 的最大值. 不妨直接写出 $h(M)$

立刻看出 $\ell(M) = 2 + 2(n-3) + (n-2) + 2 = 3n-4$.

¹

如若不然, 这颗二叉树只会形如 1010101$\cdots$, 其长度为 $2n - 1$.

²

否则回溯贡献的长度便不是最大值 $n-2$.

反过来, 从树 $M$ 出发, 也可以验证任何使得节点总数不变的操作都不会增加其 Hille 编码的有效长度. 更进一步, 我们可以断言任何使得节点总数不变的操作都将严格减小其 Hille 编码的有效长度. 换言之, 使得 $\ell(B) = 3n-4$ 的二叉树 $B$ 的结构是唯一的, 即 $M$.

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

我们首先观察朴素的数值微分的计算过程. 待微分函数为 $(x+3)^2$, 此处不妨取 $x=-2$, $h=10^{-5}$, 这一位置的导数 $A$ 近似为

$$ A \quads\approx \frac{f(x+h)-f(x)}h \eqq \frac{(1 + 10^{-5})^2 - 1^2}{10^{-5}} \eqq 2.00001 $$

并且如果试图得到与预期的 $A=2$ 更接近的结果, 则须将无穷小近似 $h$ 选取为更靠近 $0$ 的数值, 这对于浮点精度有限的计算机来说极为不利.

而常规符号微分程序视表达式为树结构, 通过遍历树并对符合模式的节点应用求导规则 $(uv)' = u'v+uv'$. 即

$$ \begin{aligned} (x+3)^2 & \spaces\to (x+3)'(x+3) + (x+3)(x+3)' \\ & \spaces\to 1 \cdot (x+3) + (x+3) \cdot 1 \\ & \spaces\to 2x+6 \end{aligned} $$

此时再应用 $x=-2$ 得到 $A=2$. 这个做法在结果上可行, 但处理复杂的表达式时, 复合求导的中间过程本身会产生大量新的结点, 使递归遍历的实际时间达到指数级 $\mathcal{O}(2^N)$.

有没有方法可以既避免递归又减少中间结点呢? 我们先看一个涉及复数域的观察.

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

Mathworks 的创始人 Cleve Moler 约 60 年 ¹ 前提出了借用虚数单位 $i$ 的数值微分, 相关文献称为 complex step 微分法 ². 考虑光滑函数 $f(x)$, 其在 $x=a$ 处可表为关于 $X$ 的 Taylor 级数 ³ $f(a) + f'(a)(X-a) + \text{etc.}$, 注意

$$ f(a+i h) \spaces= f(a) + i h f'(a) - \frac{h^2}{2!}f''(a) - \frac{ih^3}{3!}f'''(a) + \cdots $$

这个其实就是将 Taylor 级数的每一项完全展开, 在 后续 的计算中也会继续用到. 如此便有 $$ \frac{\partial f}{\partial x} \spaces= \frac{\Im f(x+ih)}{h} + \mathcal{O}(h^2) \quads\implies \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

这个方法最初被设计用于处理数值微分问题, 但稍加思考就能发现, 该过程也适用于符号微分. 与前一个问题所改进的结果的精度不同, 用于 符号微分 时, 所取得的优势是更精简的中间表达式和非递归的计算过程.

$\gdef\C{\mathbf{C}}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

选取同样的 $h=10^{-5}$, 以下计算表明 Moler 的方法 相比 此处 基于有限差分的数值微分方法能够很好的避免精度损失.

$$ \frac{\Im(1 + 10^{-5}i)^{2}}{10^{-5}} \eqq \frac{\Im(\square + 2 \times 10^{- 5}i)}{10^{- 5}} \eqq 2 $$

实际上此处 $h$ 的选取, 只要其非零, 从而带有 $i$ 的项不消失, 就不会影响到最终的结果. 换言之, 这个方法从根本上来说, 是无关于 $h \in \R\smallsetminus\{0\}$ 和 $i$ 的, 只是在数值计算时借由复数算术和复函数值可以免去一些幂零结构的讨论. 一旦意识到这一点, 我们便可以将 复步微分法 的

$$ \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

中的近似 “$\approx$” 修正 为严格等于 “$=$”, 这只需要将 $\{z \in \C : z^2 = -1\}$ 替换为 $D = \{x \in R : x^2 = 0\}$, 问题就来到了如何构造这样的 $R$ 使得 $D$ 中有非零的元素, 这样的结构实际上会 动摇 经典逻辑中对于排中律的看法.

$\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$

一种通俗的讲法是, 认为对偶数 $R[x]/(x^2)$ 可以作为复数 $\R[x]/(x^2+1)$ 的类比. 如果有读者能轻率地暂时忽略 $R[x]/(x^2)$ 这种结构的存在性, 或者说接受了下面的 $d$ 的定义

$$ \exists ~ d \in R\smallsetminus\{0\}, ~ d^2 = 0 $$

不能接受也很正常, 因为这轻易就会导致某个经典逻辑中的 矛盾. 相比之下满足 $x^2 = -1$ 的 $x$ 对于大众而言要更容易接受的多, 甚至对于三次方程是 必须品. 为此我们需要下面的准备工作.

Axiom 2.4.1. Kock–Lawvere [kock-lawvere][edit]

• May 13, 2024
• kokic

$\gdef\spaces#1{~ #1 ~}$ $\gdef\R{\mathbf{R}}$

首先需要强调的是, 这个公理所涉及到的结构的有效性全都依赖于 意象理论, 而相关基础的严格性保证基本上在 1970 年之前就已经由 William Lawvere 完工. 记 $\mathcal{E}$ 是光滑空间之间的光滑映射构成的范畴, 同时假定 $\mathcal{E}$ 还是笛卡尔闭范畴, 也就是 $\mathcal{E}$ 中的箭头对笛卡尔积封闭.

我们可以从 $\mathcal{E}$ 中选出一条几何直线 $R$, 通过指定 $R$ 上两点 $0$ 和 $1$ 之间的距离作为单位长度来确定其他线段的长度. 发挥一些古希腊精神, 线段的移动可以给出 $R$ 上的加法, 尺规作图所构造的 相似三角形 能给出 $R$ 上的乘法 $\gamma = \alpha\beta$.

因此 $R$ 带有交换环结构, 并且允许经典数学中的对象实数环 $\R$ 成为 $R$ 的模型, 注意这里我们只能考虑 $\R$ 作为环的部分, 因为 $R$ 中存在着幂零元.

Kock–Lawvere 公理说的是, 对任意映射 $f: D \to R$, 存在唯一的 $a,b \in R$, 使得

$$ f(\epsilon) \spaces= a + b \epsilon, \quad \forall \epsilon \in D $$

将这里的 $a$ 换成 $f(0)$, 并完全使用量词叙述, 则是

$$ \forall ~ f \in R^D, ~ \exists! ~ b ~ \text{s.t.} ~ \forall ~ d \in D \quad (f(d) = f(0) + b d) $$

如果说这个公理的形式还不足以暗示它的目的, 那么下面这个推论就完全能做到了.

Corollary. 所有函数都光滑 [smooths][edit]

• May 13, 2024
• kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

对任意函数 $f:R \rightarrow R$, 存在唯一的函数 $f':R \rightarrow R$ 满足

$$ f(x + \varepsilon) \spaces= f(x) + f'(x)\varepsilon,\quad \forall ~ x \in R, ~ \forall ~ \varepsilon \in D $$

这个通常作为 Kock–Lawvere 公理 的推论出现, 不过从 $\mathcal{E}$ 的定义来看, 这才是整套框架真正的目的之一. 即, 为全体函数恢复牛顿时期 “幂零无穷小量” 计算上的直观, 而不导致矛盾.

Axiom is incompatible with the law of excluded middle. Either the one or the other has to leave the scene. In Part I of this book, the law of excluded middle has to leave, being incompatible with the natural synthetic reasoning on smooth geometry to be presented here. In the terms which the logicians use, this means that the logic employed is ‘constructive’ or ‘intuitionistic’. We prefer to think of it just as ‘that reasoning which can be carried out in all sufficiently good cartesian closed categories’.

— Anders Kock, Synthetic Differential Geometry

无论是单纯接受这个 公理 还是认可该公理存在的舞台 $\mathcal{E}$, 其实都会导致完全相同的结果, 那就是 $\mathcal{E}$ 当中一般函数的性质发生了变化, 让所有的函数都变得光滑. 与之相对的, 这样的好性质所要求的代价是, $\mathcal{E}$ 当中不能使用经典逻辑中的选择公理、排中律、反证法等命题.

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Mat{\operatorname{Mat}}$

我们来观察对于交换环 $R$ 和对应的 $\Mat_{2\times 2}(R)$ 中的矩阵, $(I_3 \circ I_2 \circ I_1)^2$ 具体做了些什么. 令 $\varphi = I_3 \circ I_2 \circ I_1$, 则 $\varphi(M)$ 可以算出是

$$ \varphi: ~ M ~\leadsto~ \det M \cdot S I_2(M) S^T $$

其中 $S = (\begin{smallmatrix}0 & -1 \\ 1 & ~~~0\end{smallmatrix})$ 是一个行列式为 $1$ 的反对称矩阵 ¹, 记 $\tau: M \leadsto SI_2(M)S^T$, 可以验证 $\tau \circ \tau = \text{id}$. 现在我们来计算 $\varphi^2(M)$.

$$ \begin{aligned} \varphi^2(M) &\spaces= \varphi(\det M \cdot SI_2(M)S^T) \\ &\spaces= \det(\det M \cdot SI_2(M)S^T) \cdot S I_2(\det M \cdot SI_2(M)S^T) S^T \\ &\spaces= (\det M)^2 \det(SI_2(M)S^T) \cdot (\det M)^{-1}M \\ &\spaces= \det M \det(SI_2(M)S^T) \cdot M \\ &\spaces= \det M \det(I_2(M)) \cdot M \end{aligned} $$

也就是说 $\varphi^2(M)$ 实际上会是 $M$ 的常数倍, 并且这个常数是

$$ \det M \det(I_2(M)) \spaces= (ad-bc)\Big(\frac1{ad}-\frac1{bc}\Big) $$

$\gdef\spaces#1{~ #1 ~}$

注意, $x^* M x$ 和 $x^*x = \|x\|$ 当然都是标准二次型. 特别的, 取 $x = \left( x_{1},\cdots,x_{n} \right)^{T}$, 则

$$ x^{\ast}Mx \spaces= \sum_{1 \leqslant i \leqslant n}\lambda_{i}x_{i}^{2},\quad x^{\ast}x \spaces= \sum_{1 \leqslant i \leqslant n}x_{i}^{2} $$

Rayleigh 商定理正是在说

$$ \min\limits_{1 \leqslant i \leqslant n}\lambda_{i} \spaces\leqslant \frac{\sum_{1 \leqslant i \leqslant n}\lambda_{i}x_{i}^{2}}{\sum_{1 \leqslant i \leqslant n}x_{i}^{2}} \spaces\leqslant \max\limits_{1 \leqslant i \leqslant n}\lambda_{i} $$

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

考虑 $M = \scriptsize\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$, 将 $M$ 对角化得到 $D = \scriptsize\begin{pmatrix} 3 & ~~~0 \\ 0 & -1 \end{pmatrix}$, 相应的正交矩阵是 $\frac1{\sqrt{2}}\scriptsize\begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix}$. 注意, $(uP)^*M(uP) = u^{2}P^*MP$, 因此我们通过 $P^*MP$ 来计算 $Q^*MQ$ ¹:

$$ \frac12 \begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix}^*\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}\begin{pmatrix} 1 & ~~~1 \\ 1 & -1 \end{pmatrix} \spaces= \frac12 \begin{pmatrix} 6 & ~~~0 \\ 0 & -2 \end{pmatrix} \spaces= \begin{pmatrix} 3 & ~~~0 \\ 0 & -1 \end{pmatrix} $$

那么, 这就得到了 $M$ 的 Rayleigh 商之值域

$$ \frac{a^{2} + 4ab + b^{2}}{a^{2} + b^{2}} \quads\to \frac{3a^{2} - b^{2}}{a^{2} + b^{2}} \quads\in \lbrack - 1,3\rbrack $$

下面讨论 $A = \scriptsize\begin{pmatrix} p & q \\ q & p \end{pmatrix}$ 的对角化问题. 依然取正交矩阵 $Q = \frac1{\sqrt2} \scriptsize\begin{pmatrix} 1 &~~~1 \\ 1 & -1 \end{pmatrix}$, 相应的 $Q^*AQ = \scriptsize\begin{pmatrix} p + q & 0 \\ 0 & p - q \end{pmatrix}$. 故

$$ \begin{aligned} \frac{pa^{2} + 2qab + pb^{2}}{a^{2} + b^{2}} \quads\to & \frac{(p + q)a^{2} + (p - q)b^{2}}{a^{2} + b^{2}} \\ \quads\in & [p-q, p + q] \end{aligned} $$

最后, 对于对称矩阵 $\scriptsize\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ 也就是二次形 $ax^2 + 2bxy + cy^2$. 其对角化为

$$ \begin{pmatrix} a & b \\ b & c \end{pmatrix} \quads\mapsto \frac12 \begin{pmatrix} r - \sqrt{s} & 0 \\ 0 & r + \sqrt{s} \end{pmatrix} $$

这里 $r = a + c$, $s = (a-c)^2 + 4b^2$.

$\gdef\spaces#1{~ #1 ~}$

我们要求解问题可以叙述成下面的形式

$$ F \spaces= \frac{3a^2 + 4ab + 3b^2}{4a^2 + 12ab + 34b^2}, \quad \min_\R F, \quad \max_\R F $$

这里相应的 $A = \scriptsize\begin{pmatrix} 3 & 2 \\ 2 & 3 \end{pmatrix}$, $B = \scriptsize\begin{pmatrix} 4 & ~~6 \\ 6 & 34 \end{pmatrix}$. 我们首先对 $B$ 进行 Cholesky 分解, 得到 $C = \scriptsize\begin{pmatrix} 2 & 0 \\ 3 & 5 \end{pmatrix}$ 使得 $B = CC^*$. 接下来通过 $C^{-1} A C^*{}^{-1}$ 求出 $D$ 及其对角化 $E$, 这样就结束了此问题.

$$ \begin{aligned} D \spaces= \frac14 \begin{pmatrix} ~~~3 & -1 \\ -1 & ~~~\frac35 \end{pmatrix}, ~~ E \spaces= & \begin{pmatrix} 9-\sqrt{61} & 0 \\ 0 & 9+\sqrt{61} \end{pmatrix} \cdot \frac1{20} \\ \spaces= &\begin{pmatrix} \min_\R F & 0 \\ 0 & \max_\R F \end{pmatrix} \end{aligned} $$

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$ $\gdef\spaces#1{~ #1 ~}$

固定有限字母表 $\Sigma$, 正则语言集 $\textbf{Reg}_\Sigma$ 可定义如下

• 空集 $\varnothing$ 是正则语言, 作为加法单位 $0_\Sigma$.
• 只包含空字符串的集合 $\{\epsilon\}$ 是正则语言, 作为乘法单位 $1_\Sigma$.
• 对于 $a \in \Sigma$, $\{a\}$ 是正则语言.
• 对于正则语言 $A$, $B$. $A \cup B$, $A \times_\Sigma B$ 和 $A^*$ 是正则语言.
• $\Sigma$ 上不存在其它正则语言.

这里 $A \times_\Sigma B$ 基本就是 $A \times B = \{ (a, b) : a \in A, b \in B \}$, 但将配对 $(a, b)$ 视为字符串拼接 $a b$. $A$ 的闭包 $A^*$ 定义为满足如下性质的最小集合.

$\quad (i)$ 匹配空. 即 $\epsilon \in A^*$. $\quad (ii)$ 对拼接封闭. 即 $A \times_\Sigma A \times_\Sigma \cdots \times_\Sigma A \subset A^*$.

这里的 $\square^*$ 通常被称为 Kleene 星运算, 按照数学的习惯, $A^*$ 也被称为集合 $A$ 的自由幺半群. 约定 $A^0 = \{\epsilon\}, A^1 = A, A^{i+1} = \{wv : w \in V^i, v \in V \}$, $i \ge 1$. 同样的, 如果 $A$ 是一个字母表或形式语言, $A^i$ 收集的就是所有长度为 $i$ 且字符属于 $V$ 的字符串. 于是 $A^*$ 也可以定义成如下形式

$$ A^* \eqq \bigcup_{i \ge 0} A^i $$

从直觉上说, $A^*$ 是为了刻画 $A$ 的零次或多次重复. 如果读者熟悉正则表达式, 那么显然此处的 $\cup$ 就是 $+$ 的别名, 对应匹配器的或运算, 于是我们也用 $+_\Sigma$ 表示 $\cup$. 注意这里的 $\cup$ 有无穷多个, 从这个定义可以直接看出 $(A^*)^* = A^*$, 这样一来, $\square^*$ 就会是一个幂等运算.

可以验证, 正则语言集 $\textbf{Reg}_\Sigma$ 连同其上的加法 $+_\Sigma$ 和乘法 $\times_\Sigma$ 构成一个半环 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma, 0_\Sigma, 1_\Sigma)$. 从匹配的角度, 我们还能明白以下两点为何是必须的.

$\quad (i)~$ 加法单位 $0_\Sigma$ 对于乘法运算 $\times_\Sigma$ 的吸收性.
$\quad (ii)$ 加法 $+_\Sigma$ 是幂等运算, 即 $a+a = a$.

现在, 从半环 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma)$ 出发, 在其上定义偏序 $a \le b$ $\iff$ $a+b=b$, 等价地 $\exists ~ x$ 使得 $a+x = b$. 最后, 可以验证 $\square^*$ 与定义的偏序还满足下面的公理.

$$ \begin{aligned} (1) &~~ 1+aa^* \le a^* \\ (2) &~~ 1+a^*a \le a^* \\ (3) &~~ ax \le x \implies a^* x \le x \\ (4) &~~ xa \le x \implies xa^* \le x \end{aligned} $$

这使 $\textbf{Reg}_\Sigma$ 成为 Kleene 代数 $(\textbf{Reg}_\Sigma, +_\Sigma, \times_\Sigma, \square^*)$. 反过来, 按照公理化定义的顺序, 从正则语言集的性质 $(1)\sim(4)$ 能够直接得出 Kleene 星运算 $\square^*$ 的定义, 正则语言集本身就是 Kleene 代数的一个模型. Kleene 代数的另一个简单例子是 Boole 代数, 其中的 $a^* = 1$. 而热带半环尽管有幂等加法, 但可以验证它并非 Kleene 代数.

$\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$ $\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$ $\gdef\Mat{\operatorname{Mat}}$

半环取消了环中加法逆的存在, 仅仅从定义上来看, 可能很难认识到半环的作用, 并轻率地认为半环是一种性质不够好的结构, 哪怕考虑一些具体的例子如布尔代数和 $\N$ 也难以影响这样的印象. 但是人们对于环的印象就完全不同, 因为环总是与域紧密关联着, 为此人们可能会列举出下面的证据:

$\quad (i)$ 整数环 $\Z$ 处于数论研究的中心位置, 它的分式域是有理数域 $\Q$, 这种构造适用于任何整环 $R$, 通过商 $(R \times R \smallsetminus \{0\})/\sim$ 来完成, 此处 $(a,b) \sim (c,d) \iff ad = bc$. 从域 $\Q$ 出发, 构造以它为系数的多项式, 这些多项式将形成一个新的环结构 $\Q[x]$. 现在我们从中取一个不可约多项式 $p(x)$, 然后再利用 $\Q[x]$ 对 $p$ 生成的理想 $(p)$ 的商, 于是我们又得到一个新的域 $\Q[x]/(p)$. 另一方面, 记 $p(x)$ 在商环中的一个根为 $r$, 能够验证 $\Q[r] \cong \Q[x]/(p)$. $\Q[r]$ 的重要之处在于, 它是包含 $\Q$ 和 $r$ 的最小的域. 如果我们把这个步骤中的 $\Q$ 换成 $\R$ 并让 $p(x) = x^2+1$, 我们就得到了 $\C$.

$\quad (ii)$ 同样从域 $\Q$ 出发, 另一种从域中产生环的方法是考虑以它为元素的矩阵. 类似的, 所有的这些矩阵构成矩阵环 $\Mat(\Q)$. 不同于一般是交换环的多项式环, 矩阵环往往非交换. 仅从统计的意义上说, 在数学之外的领域, 恐怕很少有什么结构能够比矩阵更为重要.

现在请回忆, 正如我们可以把 $(i)$ 当中用于构造多项式环的域 $\Q$ 更换为一般的交换环 $R$, 这个时候 $R[x]$ 仍然是交换环. 当我们把 $(ii)$ 的域 $\Q$ 更换为半环 $\mathcal{Q}$ 时, $\Mat_{n \times n}(\mathcal{Q})$ 能够恰好地成为半环. 这个事实导致了半环上能够操作相当一部分的线性代数, 并且在很多场景下激发了半环结构的用途 ¹. 另外值得注意的一点是, 矩阵半环上可以通过 Leibniz 律定义导子.

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$

$\gdef\Q{\mathbf{Q}}$ $\gdef\R{\mathbf{R}}$

仅仅只是为半环添加闭包或者说 Kleene 星运算, 所得到的结构称为星半环. 与 Kleene 代数 类似, 星半环也通过递归公理定义星运算. 但是 Kleene 代数 所要求的幂等加法对于很多数字系统如 $\Q, \R$ 而言都难以实现, 因为这破坏了 Archimedes 性. 如果我们取消幂等加法这一点, 此时所得到的结构是完备星半环或称为闭半环, 因为 Kleene 代数 本身还允许了无穷和 $\sum_{i \ge 0}a^i$ 以及 $a^*$ 的存在性, 这就是称它 “完备” 或者 “闭” 的原因.

下面来介绍一个重要的例子. 非负扩展实数集 $\R_{\ge 0} \cup \{\infty\}$ 也即 $\R_{\ge 0}$ 的单点紧化连同实数的通常加法和乘法构成闭半环, 其中 $a \ne 1$ 时 $a^* = \frac1{1-a}$, 否则 $a^* = \infty$. 注意这个结构中不存在非零的加法逆 $-a$, 而乘法逆 $a^{-1}$ 则是未必存在. $\frac1{1-a}$ 应当被认为是一个整体记号, 或者说它实际上是无穷和 $1 + a + a^2 + \cdots$ 在 $\R_{\ge 0}$ 被添入全体非零加法逆 $\R_{\lt0}$ 后所得的环 $\R$ 中于 $(-1,1)$ 处收敛的结果. 然后由于

$$ \R_{\ge 0} ~ \cap ~ \{a < 1 : a \in \R_{\ge 0}\} \quads= [0, 1) \spaces\subset (-1,1) $$

从而在闭半环的 $a<1$ 处继续沿用这个记号. 这样, 一旦当我们扩大到环 $\R$ 时, 闭半环 $\R_{\ge 0} \cup \{\infty\}$ 当中得出的结果仍然有效. 我们在这里要求 $\R_{\ge 0} \cup \{\infty\}$ 还有另一个原因, 如果对所有 $a$ 都定义 $a^* = \frac1{1-a}$, 那么 $a^{***} = a$, 即 $\square^*$ 是 $3$-幂等的运算, 这会让 Kleene 闭包和正则表达式的概念无从谈起.

我们的论证可以直接拓展到一般的闭半环 $(\mathcal{Q}, +, \times, \square^*)$. 当其中的半环 $(\mathcal{Q}, +, \times)$ 被替换为环 $(R, +, \times)$ 时, 如果 $R$ 当中的 $\frac1{1-a}$ 在 $\mathcal{Q}$ 当中存在, 则 $\mathcal{Q}$ 当中的 $a^*$ 对应于 $R$ 当中的 $\frac1{1-a}$. 当然, 隐含的条件是, $R$ 的加法和乘法与 $\mathcal{Q}$ 兼容.

$\gdef\spaces#1{~ #1 ~}$ $\gdef\Mat{\operatorname{Mat}}$ $\gdef\R{\mathbf{R}}$ $\gdef\str#1{{\footnotesize #1}}$ $\gdef\sstr#1{~{\footnotesize #1}~}$

记 $\R_{\ge 0}^* = \R_{\ge 0} \cup \{\infty\}$. 从现在起, 我们对于 $\R_{\ge 0}^* ~ (= \mathcal{Q})$ 当中的许多有用的观察可以安全地转移到 $\R ~ (= R)$. 根据 半环注释, 我们优先考虑 $\Mat_{n \times n}(\mathcal{Q})$, 从最小的非平凡情况 $n=2$ 开始, 由于我们的目的是计算矩阵的逆, 故取这个半环的可逆子集也即幺半群 $\Mat_{n \times n}(\mathcal{Q})^\times$, 其中的元素会形如

$$ M \spaces= \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \quad ad - bc \spaces\neq 0 $$

请注意, 接下来应该考虑的是 $\square^*$. 因为我们要利用 $X^* = \frac1{1-X}$ 这个关系间接地计算 $M^{-1}$. 只要取 $X = 1-M$, 我们就得到了

$$ (1-M)^* \spaces= \frac1M \quad (= ~ M^{-1}) $$

此处的 $1-M$ 非常微妙, 因为一般情况下它只能存在于 $\Mat_{n \times n}(R)$ 而非 $\Mat_{n \times n}(\mathcal{Q})$. 如果我们暂时忽略这个问题, 那么根据 半环注释, 由于矩阵的加法直接就是 $\mathcal{Q}$ 或者 $R$ 的加法, 而乘法来自线性空间. 此时 $M$ 与 $M^*$ 之间存在一种直接的关系, 可以说成 $(M^*)_{ij} = $ 有向图 $G$ 中所有 $i \to j$ 的路径.

具体的说, 固定下标 $i,j$, 分量 $(M^*)_{ij}$ 的值会等于以 $M$, $M^*$ 为结点, $M_{ij}$ 为箭头的 $G$ 中所有 $i \to j$ 的路径 $\hom(i,j)$ 的正则表达式. 并且从这些路径中我们也能够写出 $\hom(i,j)$ 对应的正则表达式, 这就为计算 $(M^*)_{ij}$ 提供了可能.

$$\begin{aligned} 1 \longrightarrow 1 &: \quad (a+b d^*c)^* \\ 1 \longrightarrow 2 &: \quad (a+b d^*c)^*b d^* \\ 2 \longrightarrow 1 &: \quad d^* c(a+b d^*c)^* \\ 2 \longrightarrow 2 &: \quad d^* + d^*c(a+b d^*c)^*b d^* \\ \end{aligned}$$

简单起见记 $\alpha = (a+b d^*c)^*$, 那么上一段的讨论就是在说

$$ M^* \spaces= \begin{pmatrix} \alpha & \alpha b d^* \\ d^* c \alpha & \quad d^* + d^*c \alpha b d^* \tag{1.1} \end{pmatrix} $$

这里有两个不应忽视的问题. 其一, 虽然我们考虑的是 $\Mat_{n \times n}(\mathcal{Q})$ 上的 Kleene 星运算 $\square^*$, 但右侧的表达式中涉及了 $\mathcal{Q} ~ (= \R_{\ge 0}^*)$ 上的 Kleene 星运算 $\square^*$, 根据之前的内容, 我们可以自然地确定它就是 $a \mapsto \frac1{1-a}$. 这允许我们从 $M$ 的各个分量 $M_{ij}$ 计算出 $M^*$. 更加重要的是, 由于 $\Mat_{n \times n}(\mathcal{Q})$ 也能通过这样的方式构成闭半环, 这实际上允许我们将 $(1.1)$ 的适用范围拓展到任意大小的方阵 $\Mat_{n \times n}(\mathcal{Q})$, 此时的 $a,b,c,d$ 能够选取为 $M$ 的分块矩阵. 其二, $d^* + d^*c \alpha b d^*$ 在一般的星半环中不能直接替换为 $(d+ca^*b)^*$, 可替换的前提被称为 Conway 条件.

$\gdef\spaces#1{~ #1 ~}$

作为热身运动, 我们现在来恢复一个经典的事实, 即二阶矩阵的逆. 对于二阶可逆矩阵 $M$, 其逆 $M^{-1}$ 可以由它的四个分量 $a,b,c,d$ 经由 $M \to 1-M \to (1-M)^*$ 这样的过程得到, 这里 $1$ 当然是单位矩阵.

$$ \begin{aligned} M^{-1} &\spaces= (1-M)^* \\ &\spaces= \begin{pmatrix}1 - a & -b \\ -c & 1 - d\end{pmatrix}^* \\ &\spaces= \begin{pmatrix} (1 - a + b(1-d)^*c)^* & \quad \cdots \quad \\ \quad \cdots \quad & \quad \cdots \quad \end{pmatrix} \\ &\spaces= \frac{1}{a d - b c} \begin{pmatrix}d & -b \\ -c & a\end{pmatrix} \end{aligned} $$

$\gdef\spaces#1{~ #1 ~}$

我们下面来处理 $n \times n$ 矩阵 ($n \ge 3$) 的逆, 将其分块并假定后续要取逆的矩阵都是非奇异的

$$ M \spaces= \begin{pmatrix} A & B \\ C & D \end{pmatrix}, \quad 1-M \spaces= \begin{pmatrix} 1-A & -B \\ -C & 1-D \end{pmatrix} $$

我们还是直接计算 $(1-M)^*$, 实际上这非常容易. 回顾 $M^*$

$$ M^* \spaces= \begin{pmatrix} (A+BD^*C)^* & (A+BD^*C)^*BD^* \\ D^*C(A+BD^*C)^* & D^* + D^*C(A+BD^*C)^*BD^* \end{pmatrix} $$

类似的记 $\alpha_\square$ 为方阵 $\square$ 分为 $4$ 块后的左上角第 $1$ 部分. $\alpha_{M^*} = (A+BD^*C)^*$, $\alpha_{M^{-1}} = \alpha_{(1-M)^*}$, 则

$$ \begin{aligned} \alpha_{M^{-1}} &\spaces= (1 - A + B(1-D)^*C)^* \\ &\spaces= (1 - A + BD^{-1}C)^* \\ &\spaces= (1 - (A - BD^{-1}C))^* \\ &\spaces= (A - BD^{-1}C)^{-1} \end{aligned} $$

同样, 考虑分块的其他部分

$$ \begin{CD} M @>>> 1-M \\ @VVV @VVV \\ M^* @>>> (1-M)^* \end{CD} $$

在 $M \to 1-M$ 这个箭头下, $M$ 当中所有的 $D$ 会被替换为 $1-D$, 因此 $M^*$ 当中所有的 $D^*$ 可以直接替换为 $D^{-1}$. 而 $B, C$ 在 $M \to 1-M$ 下替换为 $-\square$, 于是现在立刻有

$$ \begin{aligned} M^{-1} &\spaces= \begin{pmatrix} \alpha_{M^{-1}} & -\alpha_{M^{-1}} BD^{-1} \\ -D^{-1}C \alpha_{M^{-1}} & D^{-1} + D^{-1}C \alpha_{M^{-1}} BD^{-1} \end{pmatrix} \\ &\spaces= \begin{pmatrix} (A - BD^{-1}C)^{-1} & -(A - BD^{-1}C)^{-1} BD^{-1} \\ -D^{-1}C (A - BD^{-1}C)^{-1} & D^{-1} + D^{-1}C (A - BD^{-1}C)^{-1} BD^{-1} \end{pmatrix} \\ \end{aligned} $$

在这里, 我们得到了一个相当经典且重要的结果, 即分块求逆.