正交空间小记

· · 算法·理论

正交空间是线性代数中的一个重要概念，其延伸出的正交线性基是解决线性基求交等问题的利器。本文将简要介绍其定义和性质，给出一个正交线性基的构造算法，并讨论其与 FWT 的关系。

下文中我们讨论的所有线性空间都是 U=\mathbb{F}_2^n 的子空间，其中点积定义为：

x\cdot y=(\sum x_iy_i) \bmod2

正交则定义为 x\cdot y=0.

定义与基本性质

对于一个线性空间 S，定义其正交空间 S^\perp 为：

\{x\in U|\forall y\in S,x\perp y\}

由于正交性是线性的，故上述集合构成线性空间。

对于一个线性基 B，定义其正交线性基为 \mathrm{span} (B)^\perp 的一组线性基。

接下来我们说明这个结构的一些性质：

Prop. 1

对于任意空间 S，

证明：取 S 的所有元素，以其为行组成一个 |S| \times n 的矩阵 M。显然有 \mathrm{rank} \kern{2pt} M=\dim S，而其零空间根据定义是 S^\perp，故根据秩-零化度定理，有：

\dim S+\dim S^\perp=\mathrm{rank} \kern{2pt} M+\dim \ker M=\dim U

Prop. 2

对于任意空间 S，(S^\perp)^\perp=S.

证明：由定义知 \forall x \in S,\forall y \in S^\perp, x\perp y，故 (S^\perp)^\perp \supseteq S，而由 Prop. 1 知 \dim [(S^\perp)^\perp]= \dim S，故 (S^\perp)^\perp=S.

Prop. 3

对于任意空间 A,B，A^\perp \cap B^\perp=(A+B)^\perp.

证明：对于 u\in (A+B)^\perp，有 \forall a\in A,b\in B,(a+b)\perp u，等价于 \forall a\in A,a\perp u;\forall b\in B,b\perp u，即 u \in A^\perp \cap B^\perp.

该命题结合 Prop. 2 可以得到对称的 A^\perp + B^\perp=(A \cap B)^\perp. 据此我们就可以将线性基求交转化为简单的线性基求并。

由于这些性质与补集的相似性，正交空间也被称为正交补。

构造算法

这里介绍一个构造正交线性基的在线算法，与主流求法有一定差异。

维护当前的正交空间的一个基 \alpha，初始化时可以任意取一个 U 的基。每次插入一个数 v 时，先删去 \{x\in \alpha|x\not\perp v\}，设为 p_{1...k}. 若这样的基向量不存在，说明本次插入并未改变原线性空间。否则，将 p_2+p_1,p_3+p_1,...,p_k+p_1 插回 \alpha，容易说明此时 \alpha 中所有基向量彼此线性独立且与 v 正交。该算法单次插入复杂度为 \mathcal{O}(n^2/w)，与普通线性基相同。

与 FWT 的关系

设 F_S(x)=\sum_{p\in S} x^p，其中 S 为一线性空间，F_S 为其对应的集合幂级数。

考虑沃尔什变换：

[x^u]\hat F=\sum_v (-1)^{u\cdot v}[x^v]F

可以发现容斥系数是点积的形式，和正交性有密切联系。事实上我们有：

Prop. 4

对于任意空间 S，\hat F_S=|S|F_{S^\perp}.

证明：若 u\in S^\perp，由定义有 [x^u]\hat F_S=\sum_{v\in S} (-1)^{u\cdot v}=|S|；否则，设 S'=\{p\in S| p \not\perp u\}，并任取 z \in S'，则可构造 S' 到 S\setminus S' 的双射 x \mapsto x+z，故 |S'|=|S\setminus S'|，[x^u]\hat F_S=0. 综上所述，\hat F_S=|S|F_{S^\perp}.

参考文献

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