浅谈「正交线性基」：解决线性基求交和正交补空间的新利器

Sooke · 2023-02-03 21:51:44 · 算法·理论

0. 摘要

本篇文章源于笔者在役期间的偶然研究成果，希望用通俗的语言呈现线性基的一个变种——正交线性基，并以此解决一些经典问题。碍于学识问题，文中会存在不专业的术语及表达，敬请谅解。

1. 回顾

1.1 线性基

在算法竞赛中，线性基通常指 \mathbb{Z}_2^{n} 下的一组线性无关的向量，而向量用二进制数简易表示。原向量的二元运算能方便地迁移到数上来。

加法 (u + v)

即两个数各个位进行不进位加法，等价于异或运算。

内积 (u · v)

即两个数各个位相乘再累加，等价于 \text{popcount}(u\ \&\ v)_{} \bmod 2，该值为 0 则 u,v 正交。因为是 \mathbb{Z}_2^{n}，此处向量意义外的数应 \bmod\,2，下略。

显然，迁移后的定义仍然满足分配律：(u+v)·w=u·w+v·w。

下文将用大写字母 (A,B,\ldots) 表示线性基，用 \text{span}(A) 表示线性基 A 张成的空间，即能用若干基的加法得到的数集。

高斯消元

针对线性基的高斯消元，目的在于使各个基的最高 1 位被各自独占，其余基的该位均为 0，以便解决诸如线性基第 k 大等问题。这些最高位称为关键位，其余位即非关键位。

1.2 集合幂级数

集合幂级数可以简单理解成 [x^u] 指标 u 为 \mathbb{Z}_2^{n} 下的向量、二进制数的多项式。

快速沃尔什变换 (FWT)

对于集合幂级数 F，记 \hat{F}=\text{FWT}[F]。由算法知，对于 F 的 [x^u] 一项，若 u,w 正交，其对 \hat{F} 的 [x^w] 一项贡献为正，否则为负，系数即 (-1)^{u·w}。

求 F 与 G 的异或卷积 H 时，我们对 \hat{F},\hat{G} 逐项相乘得到 \hat{H} 的本质是什么呢？考察 [x^{u}]F 和 [x^{v}]G 变换到 [x^w] 相乘的情形，由分配律，新系数为 (-1)^{u·w}\times(-1)^{v·w}=(-1)^{(u+v)·w}，恰好对应 [x^{u+v}]H 变换到 [x^w] 的系数。用分配律提取加法的思想在下文的证明中会再次出现。

2. 定义

正交线性基的定义可参照线性代数。对于 \mathbb{Z}_2^{n} 下秩为 k 的线性基 A，其正交线性基 A^{\perp} 满足 \text{span}(A^{\perp}) 是 \text{span}(A) 的正交补空间，也即，A^{\perp} 的秩为 n-k 且 A 的基与 A^{\perp} 的基一定正交。

与原线性基相反，正交线性基的各个基一般按最低 1 位存储。

正交线性基的构造十分简单，先对 A 高斯消元得到 k 个关键位，A^{\perp} 的 n-k 个正交基各自独占 n-k 个非关键位的 1，其中最低 1 位为第 i 位的正交基第 j 位为 1 当且仅当最高 1 位为第 j 位的原始基第 i 位为 1，类似转置。一种可行实现如下：

// Fennec's Algorithm
for (int i = n - 1; i >= 0; i--) {
    for (int j = i - 1; j >= 0; j--) {
        if (A[i] >> j & 1) { A[i] ^= A[j]; }
    }
}
for (int i = n - 1; i >= 0; i--) {
    if (A[i] == 0) {
        B[i] = 1 << i;
        for (int j = n - 1; j > i; j--) {
            if (A[j] >> i & 1) { B[i] |= 1 << j; }
        }
    }
}

构造算法时间复杂度为 O(n^2)。该算法笔者瞎起名为 \text{Fennec's Algorithm}（耳廓狐的算法），读者大可选择性忽略。

3. 应用

3.1 线性基求「点值」

同为异或相关算法，线性基、快速沃尔什变换先前很难建立起联系，而正交线性基恰巧提供了这个桥梁。

首先，我们不妨定义 \mathbb{Z}_2^{n} 下秩为 k 的线性基 A 的集合幂级数：若 u \in \text{span}(A)，则 [x^u]A 为 1，否则为 0。此时对 A 做 \text{FWT} 获得的 \hat{A} 有何价值呢？

引理

对于 \mathbb{Z}_2^{n} 下的任意二进制数 w，[x^w]\hat{A} 只可能等于 0 或 2^{k}。

证明：由线性空间的加法封闭性知，A * A=A \times 2^k，那么 \hat{A} \times \hat{A}=\hat{A} \times 2^k，解得 [x^w]\hat{A} \in \{0,2^k\}。

结论