与矩阵行列式有关的计数定理

· · 算法·理论

为了方便, 只叙述无边权的版本.

Binet–Cauchy 公式

实际上是把外幂 \bigwedge^m 的同态性用基展开. 对 F : \mathbb R^m \to \mathbb R^n, G : \mathbb R^n \to \mathbb R^m, 考虑到

\text{$\bigwedge^m G$} = \sum_{|S| = m} \det(F[S:]) S,

其中 F[S:] 是 F 的 [m] \times S 子矩阵, {\{a,b,c,\dots\}} = a \wedge b \wedge c \wedge \cdots. 进而计算得到:

\det(GF) = \sum_{|S| = m} \det(G[:S]) \det(F[S:]).

Kirchoff 矩阵森林定理

对于一个无向图 \Gamma, 考虑其任意一个定向, 得到有向图 \vec \Gamma. 定义:

\partial : R^E \to R^V, \quad e \mapsto (\mathrm{tail} - \mathrm{head}).

同时通过一些不太雅观的偷换认为 R^{E \vee} = R^E, R^{V \vee} = R^V, 这样我们可以定义 Laplace 矩阵 L = \partial \partial^\vee \in \mathrm{End}(R^V). Kirchoff 矩阵森林定理指的是

定理. \Gamma 的有根生成森林数等于 \det(1+L).

取一个环 R. 为了证明这个定理, 我们构造了一个辅助量 \Sigma : R^V \oplus R^E \to R^V, 定义作 \Sigma(p_v,p_e) = p_v + \partial p_e. 那么不难计算得到 \Sigma \Sigma^\vee = 1+L. 因此用 Binet–Cauchy,

\det \Sigma = \sum_{|X| = n} \det(\Sigma[X:])^2,

其中 n = |V|. 考虑取某一个特定的 X \subseteq V \sqcup E, 取 V_X = X \cap V, X = X \cap E. 那么 \Sigma[X:] 实际上就是 \partial_X : R^{X} \to R^V 和包含映射 \iota_X : R^{V_X} \to R^V 的组合.

现在证明: \det(\Sigma[X:])^2 = 1 当且仅当 X 构成一个森林, 且对于每一个连通块, 恰好包含一个 V_X 的元素, 否则 \det(\Sigma[X:]) = 0.

很明显, 若 X 中存在一个圈 C= \{0,1,\dots\} \subset X, \partial_X \sum_{e \in C} e = 0, 使得 \Sigma[X:] 不是一个模同构. 因此若 \det(\Sigma[X:]) \ne 0, 则 X 一定是一个森林.

设 D 是 X 的所有的连通分量. 设 q_X : R^V \to R^D 映 v 为其所在的连通分量. 则 \partial_X q_X = 0. 这样, 不难验证有一个正合列

0\to R^{X} \xrightarrow{\ \partial_X\ } R^{V_X} \xrightarrow{\ q_X\ } R^{D}\to 0,

并将其对 \operatorname{im} \partial 取商, 则可以发现: \Sigma[X:] 是一个模同构当且仅当 q_X \circ \iota_X 是, 进而当且仅当 V_X 中恰好包含每个连通分量的一个元素.

在上述论断中, 若 R = \mathbb Q, 得到的结果说明 \det(\Sigma[X:]) 不等于 0 当且仅当它满足上述条件, 在这个条件下再取 R = \mathbb Z, 得到的结果表明 \det(\Sigma[X:]) \in \{\pm 1\}.

把 V_X 看成森林 X 的根, 就得到了所需要的结果.

Lindström–Gessel–Viennot 引理

设 \Gamma 是一个有向无环图. 设一个算子 P : \mathbb Z^V \to \mathbb Z^V.

P(a) = \sum_{b \in V} \text{path}(a,b) \cdot b,

其中 \rm path 指代路径数. 如果 A 是邻接矩阵算子 a \mapsto \sum_{a \to b} b, 则 P = (1-A)^{-1}.

设

a_0,a_1,\dots,a_{n-1},b_0,b_1,\dots,b_{n-1} \in V,

则 Lindström–Gessel–Viennot 引理 断言: 对于矩阵 c_{ij} = \mathrm{path}(a_i,b_j), 有

\det C = \sum_{\sigma \in \mathfrak S_n} \operatorname{sgn}(\sigma) \sum_{p_i : a_i \to b_{\sigma(i)}\ \text{点不交}} 1.

证明. 取一个拓扑序 \prec, 考虑将路径分解成

\begin{aligned} \varphi_v : \mathbb Z^V \to \mathbb Z^V, \quad x \to x\ (x \ne v), \quad v \mapsto v + \sum_{e : v \to w} w, \\ P = \prod_{\text{字典序顺序}} \varphi_v. \end{aligned}

现在在全外代数 \bigwedge \mathbb Z^V 上做操作. 两个基本操作是:

\begin{aligned} \varepsilon_v : \omega \mapsto v \wedge \omega \\ \iota_v : \omega \mapsto \mathrm{contract}(\omega, v). \end{aligned}

组合出

\bigwedge \varphi_v = 1 + \sum_{e : v \to w} \varepsilon_w \iota_v, \quad \bigwedge P= \prod_{\text{按字典序}} \left(1 + \sum_{e : v \to w} \varepsilon_w \iota_v\right).

考虑其展开后的任何一项. 若 \alpha 是某一个齐次外代数元素, \varepsilon_w \iota_v(\alpha) 能不为 0, 要依靠 \alpha \wedge v = 0, 并且 \alpha \wedge w \ne 0. 因此实际上 \varepsilon_w \iota_v 连续复合的含义是边不交路径.

因此如果我们设

\mathrm A = a_0 \wedge a_1 \wedge \dots \wedge a_{n-1}, \Omega = b_0 \wedge b_1 \wedge \dots \wedge b_{n-1},

那么我们要做的是提取 \left(\bigwedge P\right) \mathrm A 的 \Omega 分量. 由于我们没法保证 a_i 对应于 b_i, 所以它可能对应于 b_{\sigma(i)}, 形成一个

b_{\sigma(0)} \wedge \dots \wedge b_{\sigma(n-1)} = \mathrm{sgn}(\sigma) \cdot \Omega.

因此提取的结果直接等于

\sum_{\sigma \in \mathfrak S_n} \operatorname{sgn}(\sigma) \sum_{p_i : a_i \to b_{\sigma(i)}\ \text{点不交}} 1,

而按照提取系数和行列式的对应关系可以看出 \det C 就是这个值.

BEST 引理

为什么我不写全名了呢? 因为它的全名叫 de Brujin–van Aardenne-Ehrenfes–Smith–Tutte 定理, 还是太长了.

它的叙述是: 若 \Gamma 是一个有向图, 其 Euler 回路数量 N \ne 0. 选取一个点 x, 它有 F(x) 个以 x 为根的内向生成树, 那么

N = F(x) \prod_{v \in V} (d^+(v) - 1)!

成立.

先定好一个根节点 x, 还有从 x 出发的第一条边 e_0.

那么, 从 x 出发并且不妨钦定第一条边 e_0, 得到的 Euler 回路, 跟下面的资料其实是一回事: 一棵以 x 为根的向内生成树 T, 还有每个点上所有出边的一个先后顺序, 满足两个条件: 对每个不是 x 的点 v, 它在树里的那条出边 t(v) 必须排在它自己顺序里的最后一位; 而在 x 那里, 边 e_0 必须排在第一位. 这给出一个双射.

先从 Euler 回路说起. 取一个 Euler 回路, 在每个点记下它离开时用各条出边的顺序. 然后看每个非根点 v, 它最后一次离开用的是哪条边, 把这那条边叫做 t(v). 这些最后离开边会构成一棵以 x 为根的内向生成树.

这是因为顺着 t(v) 从 v 走到 u, 最后一次离开的时刻只会越来越晚. 因为一旦从 v 最后一次离开, 就再也回不到 v 了, 可是后面还需要从 u 最后一次离开. 所以沿着这些 t(v) 走, 时间一直增加, 不可能出现有向环. 而且每个非根点恰好贡献一条出边, 所以这些边汇起来就是一棵流向 x 的树.

所以说, 每个 Euler 回路自然就带出了一棵内向生成树, 还有每个点上的出边顺序.

反过来, 如果已经有了上面说的那两样东西: 一棵内向生成树 T 和每个点上的出边顺序, 那么对每个非根点 v, 把树边 t(v) 当作留到最后才用的边, 也就是说, 所有其他出边必须在它之前用掉.

这样就可以构造一个贪心算法: 从 x 出发, 先走 e_0. 每到一个点, 就按那个点规定的顺序, 挑第一条还没用过的出边往前走.

那些留到最后才用的树边, 能防止半路卡住. 因为只要某个非根点 v 还有没用过的出边, 它那条预留的 t(v) 就肯定还没用. 所以在还没用的边组成的子图里, 每个这样的点都能顺着预留的树边一路走到 x.

先看第一点: 它不会停在 x 以外的地方. 假设一个路径从 x 出发, 最后停在了 x \neq w. 那么在 x 那里, 用掉的入边比出边多一条. 可 $, 每个点的入度等于出度, 这要求 x 一定还有没用过的出边. 所以它根本不可能停在那里. 因此, 这条路径只能停在 x$.

再看第二点: 它不会还没走完所有边就提前回到 x. 假设它回到了 x, 可是还剩一些边没用. 这时候走过的是一个回路, 剩下没用的边构成的子图仍然是 Euler 的. 随便找一个还有出边没用的点, 顺着预留的树边走, 就能找到一条还没用过的有向路径通往 x. 所以在剩下的图里, x 有没用的入边; 又因为这个子图是 Euler 的, x 也一定还有没用的出边. 要是这样, 贪心走法根本不该在 x 停下, 矛盾了.

所以贪心走法恰好每条边都用一次, 给出一个 Euler 回路.

拿一棵以 x 为根的内向生成树 T 来说: 在每个非根点 v, 树边被强制放在最后, 其余出边的顺序有 (d^+(v)-1)! 种排法; 在 x 那里, e_0 被强制放在最前, 其余出边的顺序有 (d^+(w)-1)! 种排法. 所以每一棵 T 贡献的环游数目就是

\prod_{v\in V}(d^+(v)-1)!

把所有可能的内向生成树 T 加起来, 就得到

N=F(x) \prod_{v\in V}(d^+(v)-1)!

这个公式成立.