用户: Cybcat/虚张声势的线性代数

我们大谈特谈在组合数学中出现的虚张声势的线性代数. 这里有很大一部分来自 Laszlo Babai 和 Peter Frankl 的一个笔记 LINEAR ALGEBRA METHODS IN COMBINATORICS.

1小镇

最标准的问题就是奇镇偶镇系列的, 让我们从标准情形开始介绍, 作为良好的热身:

定理 1.1 (偶偶镇). 一个城市有 $n$ 个居民, $n$ 是个正整数. 现在有一些俱乐部, 满足一系列规则:

(偶员) 每个俱乐部有偶数个居民成员 (允许为空).

(偶交) 两个不同俱乐部的公共成员有偶数人 (允许为空).

(互异) 没有两个俱乐部具有完全一致的人员构成.

则俱乐部的数量上界为 $2^{\lfloor n/2\rfloor }$.

证明. 为证明上界可取到, 首先不妨设 $n=2m$, 如果总人数是奇数就让一人不要加入任何俱乐部. 现在设这些人为 $A_1,B_1,\cdots ,A_m,B_m$. 那么我们可以构建 $2^m$ 个俱乐部, 对每个 $\{1,\cdots ,m\}$ 的子集, 构造一个俱乐部, 容纳下标 $i$ 属于该子集的 $A_i,B_i$. 这样两两的交以及每个俱乐部的人数总是偶数.

接下来为了证明是上界, 假设现在有 $N$ 个俱乐部符合条件, 在域 ${\mathbb{F}}_2$ 上的 $n$ 维线性空间 ${\mathbb{F}}_2^n$ 上, 记一组基 $e_1,\cdots ,e_n$ 我们用向量 $v_1,\cdots ,v_N$ 来表示它们, 我们将 $i$ 号俱乐部包含成员 $s$ 对应下标的 $e_s$ 加起来记作 $v_i$, 以后我们管这样构造的 $v_i$ 叫示性向量. 现在我们不难发现标准内积下 $v_i\cdot v_j=0$ 对一切 $i,j$. 设这些向量张成线性子空间 $V\subset {\mathbb{F}}_2^n$, 那么 $V\subset V^{\perp }$ 且 $V\oplus V^{\perp }\cong {\mathbb{F}}_2^n$ 从而 ${\dim }_{{\mathbb{F}}_2}V\le \lfloor n/2\rfloor$, 由此可知俱乐部数量有 $N\le \#V\le 2^{\lfloor n/2\rfloor }$.

$\square$

定理 1.2 (奇偶镇). 一个城市有 $n$ 个居民, $n$ 是个正整数. 现在有一些俱乐部, 满足规则 (奇员) (偶交) (互异), 则俱乐部的数量上界为 $n$.

证明. 这里构造就很容易, 每个俱乐部都只有一个人就是符合条件的构造. 延续记号, 证明是上界只需注意到这里 $v_1,\cdots ,v_N$ “正交” 从而线性无关. 即: $$V:=\left[\begin{array}{ccc}-& v_1& -\\ & \cdots & \\ -& v_N& -\end{array}\right],V{V}^{\text{T}}={\mathrm{id}}_N.$$这样用矩阵乘积的秩不等式就能轻松得到想要的结论.

$\square$

上面两个都要求相交人数为偶数, 是非常经典的问题. 在此基础上, 将相交人数改为奇数对这个问题本身的影响其实不大, 使用一些小技巧, 实则我们有这些结果 (可以作为习题):

定理 1.3 (偶奇镇). 一个城市有 $n$ 个居民, $n$ 是个正整数. 现在有一些俱乐部, 满足规则 (偶员) (奇交) (互异), 则俱乐部的数量上界为 $n$ ($n$ 为奇数时) 或 $n-1$ ($n$ 为偶数时).

证明.

证明. 构造也很简单, 不妨设 $n=2m+1$, 然后将所有的 $2m$ 元子集作为俱乐部. 延续记号, 为了证明上界, 如果 $n$ 为奇数, 那么用 $s={\sum }_{i=1}^n{e}_i$ 来减去全体 $v_i$, 问题转化为偶奇镇问题; 如果 $n$ 为偶数, 设 $J$ 是全为 $1$ 的矩阵, 那么 $V{V}^{\text{T}}=J-I$, 而计算行列式可知偶数阶的这种矩阵非退化, 故得知 $N\le n$, 不能取等的理由在于这些向量不能成为一组基, 它们不能生成分量和为奇数的向量, 这表明此时 $N\le n-1$.

$\square$

定理 1.4 (奇奇镇). 一个城市有 $n$ 个居民, $n$ 是个正整数. 现在有一些俱乐部, 满足规则 (奇员) (奇交) (互异), 则俱乐部的数量上界为 $2^{(n-1)/2}$ ($n$ 为奇数时) 或 $2^{n/2-1}$ ($n$ 为偶数时).

证明.

证明. 和先前的策略一样, $n$ 是奇数的时候用 $s={\sum }_{i=1}^n{e}_i$ 来减去全体 $v_i$ 从而转化为偶偶镇; 对 $n$ 是偶数的情况, 这时候的 $v_i$ 构成仿射空间 (线性空间的平移), 换一个说法, 设 $V$ 是 $v_i-v_j$ 者构成的线性空间, 仍然有 $V\subset V^{\perp }$, 现在只需证明 $V⊊V^{\perp }$. 倘若 $V=V^{\perp }$ 是极大迷向子空间, 则 $(v_i,v_i-v_j)=0$ 从而 $v_i$ 也在 $V^{\perp }$ 中进而在 $V$ 中, 从而 $(v_i,v_i)=0$ 矛盾.

$\square$

很容易提出一些类似的变种问题, 从而自然地引入所谓 Fisher 不等式, 展开来说:

定理 1.5 (Fisher). $n$ 个居民和一些俱乐部, 这些俱乐部除了满足 (互异) 还满足如下规则:

(同交) 存在一个整数 $k$, 任意两个不同的俱乐部的公共成员都是 $k$ 人.

则俱乐部的数量不超过 $n$.

证明. 仍和先前一样定义 $v_i$, 不过此次基域为 $\mathbb{R}$, 现在 $v_i\cdot v_j=k$ 对 $i\ne j$, 我们仍去证明诸 $v_i$ 线性无关. 若不然设 ${\sum }_{i=1}^N{a}_i{v}_i=0$, 那么计算得到$$0=\left(\sum _{i=1}^N{a}_i{v}_i\right)\cdot \left(\sum _{i=1}^N{a}_i{v}_i\right)=k{\left(\sum _{i=1}^N{a}_i\right)}^2+\sum _{i=1}^N{\alpha }_i^2(v_i^2-k).$$由于两个求和项的贡献非负, 而且除了人数最少的俱乐部, 其他俱乐部都严格超过 $k$ 人, 因此已经得知除了一个 ${\alpha }_j$ 以外其他 ${\alpha }_i=0$, 而全体 ${\alpha }_i$ 求和为 $0$, 故只能全是 $0$.

$\square$

这一系列结果会有一些莫名其妙的应用, 比如说:

推论 1.6. 设 $G$ 是 $n$ 元集的全体 $3$ 元子集为顶点的一个图, 对顶点 $A,B$, 若对应的 $3$ 元集相交恰是 $1$ 个元素, 则连边. 那么这么一个图的最大团 (完全子图) 和最大独立集 (完全图的补图作为子图) 的大小不超过 $n$.

证明. 最大团的结果是 Fisher 定理, 最大独立集的结果是奇偶镇的定理.

$\square$

推论 1.7. $n$ 个居民和一些俱乐部, 这些俱乐部满足 (互异), 此外还满足如下规则:

(单同) 任意两个不同的居民公共参与的俱乐部恰有一个.

假设没有一个俱乐部包含所有人, 则俱乐部的数量至少为 $n$. 用人话说, $K_n$ 完全图划分为完全真子图的无交并至少需要 $n$ 个.

证明. 设有 $N$ 个俱乐部, 定义 $N$ 元集的 $n$ 个子集如下: 对第 $i$ 个居民, 它参与的俱乐部作为 $N$ 元集的第 $i$ 个子集. 我们只需说明这 $n$ 个子集互不相同, 则由 Fisher 定理 $n\le N$. 假如两个居民参与的俱乐部相同, 由于他们只能公共参加一个俱乐部, 从而这两个居民只参加了一个俱乐部, 记作 $A$. 现在为了让其他居民和他们也公共参加一个俱乐部, 将导致所有人都参加了 $A$ 从而矛盾.

$\square$

类似上一个定理的形式, 又会自然地提出将完全图分为完全二分图的版本:

定理 1.8 (Graham–Pollak). $K_n$ 完全图划分为完全二分子图 $K_{a_i,b_i}$ 的无交并至少需要 $n-1$ 个.

证明. 比较经典的证明是在线性代数上观察邻接矩阵, 对一个二部子图, 记两部分的示性 (列) 向量 $v_i,w_i$, 这样子图的邻接矩阵就是 $A_i:=v_i{w}_i^{\text{T}}+w_i{v}_i^{\text{T}}=2v_i{w}_i^{\text{T}}+S_i$, 其中 $S_i=w_i{v}_i^{\text{T}}-v_i{w}_i^{\text{T}}$ 反对称. 现在 $A:=J_n-I_n$ 是完全图的邻接矩阵, 于是 $A={\sum }_{i=1}^N{A}_i$. 现在 $I+A_1+\cdots +A_N=J$, 依照上面的写法代入得到$$I_n+(S_1+\cdots +S_n)=J_n-2(v_1{w}_1^{\text{T}}+\cdots +v_N{w}_N^{\text{T}}).$$首先左边是可逆矩阵, 因为正定矩阵与反对称矩阵的加和非退化, 因此秩为 $n$, 但是右边每项秩 $1$, 因此 $N+1\ge n$.

$\square$

这一定理还能推广, 成为这样的形式

定理 1.9 (Witsenhausen). 任意一个无圈 (没有一个顶点连接自己的边) 的有限无向图 $G$ (甚至不一定是简单图) 划分为完全二分子图的无交并, 其数量至少为 $G$ 邻接矩阵正特征值的数目 (按重数), 也至少是负特征值的数目 (按重数).

证明. 这回采用这样一种证法, 设 $U,W\subset {\mathbb{R}}^n$ 是这样两个子空间: 记 $U$ 为 $G$ 邻接矩阵 $A$ 全体正特征子空间的直和. 显然由可对角化知 $\dim A$ 就是正特征值的数目. 记 $W:=\{w\in {\mathbb{R}}^n:v_i^{\text{T}}w=0\forall i\}$.

显然 $\dim W\ge n-N$. 现在只需证明 $U\cap W=0$, 下面的证明方法改成负特征值也类似, 若这已证出, 则 $n-N+\dim U\le \dim U+\dim W\le n$ 故 $N\ge \dim U$.

而为了证明此事只需观察如下两个断言, 其一是 $A$ 作为双线性型限制在 $U$ 上正定, 其二是 $A$ 作为双线性型限制在 $W$ 上恒 $0$, 而这只需注意到 $w^{\text{T}}{A}_{j}w=0$ 对一切 $A_j$. 很显然这一论证手段在负特征上仍适用.

$\square$

注意到 $J_n-I_n$ 的特征值是 $n-1$ 个 $-1$ 和一个 $1-n$, 于是它是前一定理的推广.

2几何

有很多莫名其妙的几何问题也有精妙的线性代数方法.

定理 2.1. 平面上 $n$ 个点至少确定 $n$ 条互异直线.

证明. 注意到任两点唯一确定一条直线, 于是将直线看作俱乐部, 成员为其上的点, 则这正是前面的推论 1.7.

$\square$

3游戏

接下来是一个标准的益智游戏. 我们先来看一个最一般的:

定理 3.1. 给定 $G$ 是任意一个有限简单图. 假设 $G$ 的每个顶点上有一盏灯, 只有亮和灭两种状态. 现在定义对顶点 $v$ 进行一次操作, 指的是将 $v$ 和它的所有邻居上的灯同时改变状态. 现在 $G$ 的所有灯都灭, 证明总能在有限次操作内点亮所有灯.

证明. 设 $G$ 的邻接矩阵为 $A\in {\mathbb{M}}_n(F_2)$ 是一个对角线全是 $1$ 的对称矩阵. 那么要证明全是 $1$ 的列向量 $v$ 在像中只需证明若列向量 $x$ 使 $x^{\text{T}}A=0$ 则 $x^{\mathrm{T}}v=0$, 这是因为 $A$ 的像空间完全被能零化它的线性泛函决定. 结合 $A$ 对称, $x^{\text{T}}A=0$ 就是 $Ax=0$. 翻译回组合语言, 只需证明若一系列操作仍使所有灯的状态保持不变, 那么操作次数为奇数的灯数量为偶数. 那么只考虑这些被操作奇数次的灯构成的子图, 因为全操作一次后状态不变, 故子图每个顶点度数为奇数, 故子图顶点数为偶数.

$\square$

4一般位置

5规则类怪谈

第一个规则类怪谈来自于图论设计.

在图论设计上为了追求美感, 我们会要求这个图具有一些较为特殊的性质. 最直接地, 我们要求研究的对象是正则图, 即每个顶点度数一样的图, 而且不只是一般的正则图, 还有一个第一眼看起来比较奇怪的要求: 我们希望这个图最小的圈长度 (英文 girth) 是 $5$. 假设度数为 $r$, 那么这样的一个图至少要有多少个顶点呢?

首先一个点 $v$ 的邻居共 $r$ 个, 而且这 $r$ 个点除了 $v$ 以外不能有公共邻居, 否则会导致出现长度 $4$ 的圈, 这样一来至少需要的顶点数为 $1+r+r(r-1)=r^2+1$. 有意思的是, 这种顶点数最少的图往往出奇地有良好的对称性. 平凡例子是 $r=2$, 此时必是五边形, 对称群为 $D_5$; 稍不平凡的例子是 $r=3$, 此时不难证明必为 Peterson 图, 对称群为 $S_5$(为什么?), 一个乐子是尽管它这么好, 但是仍没有 Hamilton 圈.

在历史上一段漫长的时间内, 对更大的 $r$, 人们以为不再有这样的图, 数学家们努力试过了 $r=4,5,6$ 发现都不大行. 结果 1960 年 A. J. Hoffman 和 R. R. Singleton 忽然发现 $r=7$ 竟然是可行的. 通过将一系列 Peterson 图巧妙地拼起来就能得到所谓的 Hoffman–Singleton 图, 它的对称群大小为 $252000$. 可能很多读者都不熟悉这个图, 一个简单的描述是, 设 $P_0,P_1,P_2,P_3,P_4$ 是按照 $0-2-4-1-3-0$ 连接的五边形, $Q_0,Q_1,Q_2,Q_3,Q_4$ 是按照 $0-1-2-3-4-0$ 连接的五边形; 对 $k=0,1,2,3,4$ 再连上 $P_j$ 的 $i$ 号顶点和 $Q_k$ 的 $i+jk(\mathrm{mod}5)$ 号顶点即可得到.

这又一次激励了人们搜索这种图, 为了聪明地找这些图, Hoffman 和 Singleton 还指出了如下定理:

定理 5.1 (Hoffman–Singleton). 度数 $r$, 顶点数 $r^2+1$, 最小圈长度 $5$ 的图只可能对 $r=2,3,7,57$ 存在.

至于 $r=57$, 人类至今没找到符合条件的图. 容我吐槽一句, 人类的计算能力 (包括发明的工具, 诸如计算机) 属实是有点拉跨了 (@Erdos), 外星人随便让人类算点什么玩意都可能要了人类的小命, Ramsey 数 $R(5,5)$ 都没算出来, 更别说 $r=57$. 顺便把 Erdos 的英文原文放出来, 可能也有很多人没看过:

Imagine an alien force, vastly more powerful than us, demanding the value of $R(5,5)$ or they will destroy our planet. In that case, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for $R(6,6)$. Then we should attempt to destroy the aliens.

——Paul Erdos

证明.

$\square$

第二个规则类怪谈则讨论 Banach 空间在同胚下的表现.

引理 5.2 (Kuratowski). $X$ 度量空间, $Y$ 是完备度量空间. $A\subset X$ 且 $f:A\to Y$ 连续. 则存在介于 $A$ 和 $\overline{A}$ 的 $G_{\delta }$ 集合 $G$, 其上有一个 $g:G\to Y$ 是 $f$ 的连续延拓.

证明. 定义 ${\mathrm{osc}}_f(x)=\inf \{\mathrm{diam}(f(U)):U\text{是}x\text{的开邻域}\}$. 那么 $G=\overline{A}\cap \{x:{\mathrm{osc}}_f(x)=0\}={\bigcap }_{n\in \mathbb{N}}\{x:{\mathrm{osc}}_f(x)<\frac{1}{n}\}\cap \{x:d(x,\overline{A})<\frac{1}{n}\}$ 是 $X$ 中的 $G_{\delta }$ 集. 对 $x\in G\subset \overline{A}$, 取一列 $x_n\in A$ 趋于 $x$, 不难检查 $f(x_n)$ 是 $Y$ 中的 Cauchy 列. 不妨设 $g(x):={\lim }_{n}f(x_n)\in Y$, 易知 $g$ 良定, 为证 $g$ 连续只需检查 ${\mathrm{osc}}_g(x)=0$ 对一切 $x\in G$. 注意对 $X$ 中的开集 $U$, $g(U)\subset \overline{f(U)}$, 因此 $\mathrm{diam}(g(U))\le \mathrm{diam}(f(U))$, 从而 ${\mathrm{osc}}_g(x)\le {\mathrm{osc}}_f(x)=0$.

$\square$

定理 5.3. 如果一个赋范线性空间 $E$ 同胚于度量完备的拓扑空间 $F$, 则 $E$ 是 Banach 空间.

证明. 考虑 $E\subset \overline{E}$, 其中 $\overline{E}$ 是 $E$ 在范数下完备化得到的 Banach 空间. 那么 $E$ 在 $\overline{E}$ 中的子空间拓扑和度量拓扑是一致的, 而且也和 $F$ 一致. 我们声称 $E$ 是 $\overline{E}$ 中的 $G_{\delta }$ 集, 对 ${\mathrm{id}}_E:E\to E\cong F$ 使用上述引理 5.2, 得知存在 $G_{\delta }$ 集 $G$ 满足 $E\subset G\subset \overline{E}$, $g:G\to E\subset \overline{E}$ 延拓 $E$ 上的恒同映射, 因为 $E$ 在 $G$ 中稠密故 $g={\mathrm{id}}_G$ 于是 $E=G$.

若 $E\ne \overline{E}$, 任取 $x\in \overline{E}\backslash E$. 由于 $\overline{E}$ 完备, 用 Baire 纲定理不难得知 $\overline{E}\backslash E$ 是第一纲的, 类似的 $\overline{E}\backslash (E+x)$ 也是第一纲的, 其中 $E+x$ 是 $E$ 用 $x$ 作平移. 但是 $(\overline{E}\backslash E)\cup (\overline{E}\backslash (E+x))=\overline{E}$ 矛盾.

$\square$

于是这里就有一些莫名其妙的应用, 例如 $C[0,1]$ 在 $1$-范数和 $\infty$-范数下的空间是不同胚的. 接下来还可以关心一些其他问题, 例如 $L^p(\mathbb{R})$ 对 $1\le p<+\infty$ 都是同胚的, 例如从 $L^p\to L^q$ 的映射为 $f\mapsto \mathrm{sgn}(f)|f{|}^{q/p}$. 而 $p=+\infty$ 者不可分从而和他们不同胚. 实际上, 我们接下来试图努力证明这样一个结果:

定理 5.4. 可分无限维 Banach 空间都是同胚的.

有一个有趣的小结果, 也来自泛函:

定理 5.5 (Mazur–Ulam, 1932). 实赋范空间 $X$, 和映射 $f:X\to X$. 假设 $f$ 是等距双射, 则 $f$ 是仿射映射.

简单地解释一些细节, 首先等距映射的条件即对任意 $x,y\in X$ 都有 $\Vert f(x)-f(y)\Vert =\Vert x-y\Vert$. 该条件保证 $f$ 是单射, 所以条件保证也是满射. 然后仿射指的是它符合$$f((1-t)x_1+t{x}_2)=(1-t)f(x_1)+tf(x_2).$$实际上考虑 $f(x)-f(0)$ 就得到一个线性映射, 也可以反过来用和线性映射差一个平移作为仿射的定义. 我们的证明来自 Bogdan Nica 2013 年的一篇小文章 The Mazur–Ulam Theorem, 他声称这个证明的想法来自 Vaisala, 而这又来自 Vogt. 和原始证明相比, 该证明则不需要前置, 显得较为简洁.

证明. 首先任意取定两个点 $x_1,x_2\in X$, 我们只需证明 $\alpha ((x_1+x_2)/2)=(\alpha (x_1)+\alpha (x_2))/2$. 然后借助 $f$ 等距可知连续, 从而利用 $2^n$ 分母的分数稠密以及 $x_1,x_2$ 的任意性可得到需要的仿射性结论. 于是我们对于任意等距 $\alpha :X\to X$, 自然地定义$$\mathrm{def}(\alpha )=\Vert \alpha \left(\frac{x_1+x_2}{2}\right)-\frac{\alpha (x_1)+\alpha (x_2)}{2}\Vert .$$英文原文称之为 affine defect(仿射缺陷) 所以叫它 $\mathrm{def}$. 用三角不等式容易估计$$\mathrm{def}(\alpha )\le \frac{1}{2}\Vert \alpha \left(\frac{x_1+x_2}{2}\right)-\alpha (x_1)\Vert +\frac{1}{2}\Vert \alpha \left(\frac{x_1+x_2}{2}\right)-\alpha (x_1)\Vert =\frac{\Vert x_1-x_2\Vert }{2}.$$下面就是神秘的魔法, 对于给定的等距双射 $\alpha$, 我们来定义另一个等距双射 ${\alpha }^{\prime }$: 设 $\rho$ 是以 $\frac{1}{2}(\alpha (x_1)+\alpha (x_2))$ 为中心定义的中心对称, 即$$\rho (z)=\alpha (x_1)+\alpha (x_2)-z.$$现在记 ${\alpha }^{\prime }={\alpha }^{-1}\rho \alpha$ 是三个等距双射的复合所以仍是等距双射. 容易计算得到 ${\alpha }^{\prime }(x_1)=x_2,{\alpha }^{\prime }(x_2)=x_1$, 此外依定义以及 $\alpha$ 是等距展开得到$$\begin{array}{rl}\mathrm{def}({\alpha }^{\prime })& =\Vert {\alpha }^{-1}\left(\alpha (x_1)+\alpha (x_2)-\alpha \left(\frac{x_1+x_2}{2}\right)\right)-\frac{x_1+x_2}{2}\Vert \\ & =\Vert \alpha (x_1)+\alpha (x_2)-\alpha \left(\frac{x_1+x_2}{2}\right)-\alpha \left(\frac{x_1+x_2}{2}\right)\Vert =2\mathrm{def}(\alpha ).\end{array}$$如果 $\mathrm{def}(\alpha )\ne 0$, 那么不断用上述操作即可得到一列 $\mathrm{def}$ 无界的等距双射, 与一开始三角不等式估计的与 $\alpha$ 无关的一致界矛盾.

$\square$