版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: 笔记 - 异或线性基 categories:

{% post_link hamel-basis 理论笔记 %}

令 $V\subseteq\mathbb{Z}_2^n$, 异或线性基即为线性空间 $V$ 上满足一定条件的一组 Hamel 基 $(\epsilon_0,\epsilon_1,\dots,\epsilon_n)$

<!-- more -->

{% note warning %} https://cplib.tifa-233.com/src/code/math/basis_z2.hpp 存放了笔者对该算法/数据结构的最新实现, 建议前往此处查看相关代码 {% endnote %}

线性基

定义

令 $V\subseteq\mathbb{Z}_2^n$, 线性基即为线性空间 $V$ 上满足如下条件的一组"基底" $(\epsilon_0,\epsilon_1,\dots,\epsilon_n)$

  1. 排除 $\epsilon_0,\epsilon_1,\dots,\epsilon_n$ 中所有零向量后的向量组线性无关
  2. $\epsilon_i(i+1..n)=0$
  3. 若 $\epsilon_i(i)=1$, 则 $\forall j,~\epsilonj(i)=\delta{ij}$

对 $\alpha\in\mathbb{P}^n$, $\alpha(x)$ 即为 $\alpha$ 第 $x$ 维的元素, $\alpha(x..y)$ 即为 $\alpha$ 第 $x$ 维到第 $y$ 维所有元素构成的向量

写成矩阵来看更直白些, 矩阵看起来就像是缺了几列的三角形

比如这样

$$ (\epsilon_0,\epsilon_1,\dots,\epsilon_6)=\begin{bmatrix} & & & & &1\ & & & &1& \ & & &0&1&1\ & &1& & & \ &1& & & & \ 1& & & & & \ \end{bmatrix} $$

性质

构造方法

我们以插入元素的方法构造

对前设的 $V$, 设当前我们已完成构建的线性空间为 $V'\subseteq V$, 对应的线性基为 $(\epsilon'_0,\epsilon'_1,\dots,\epsilon'_n)$, 接下来我们在 $V\setminus V'$ 中选取一个向量 $\alpha$, 进行如下操作直到 $|V'|=|V|$ 为止

$\begin{array}{r|l:l} 1 & \textbf{for}~ i \gets n ~\textbf{downto}~ 1 ~\textbf{do} \ 2 & \quad \textbf{if}~ \alpha(i) = 1 ~\textbf{then}\ 3 & \quad \quad \textbf{if}~ \epsilon'_i(i) = 1 ~\textbf{then}~ \alpha\gets\alpha+\epsilon'_i & flip~\alpha(i)\ 4 & \quad \quad \textbf{else} & prepare~to~replace~\epsilon'_i~with~\alpha\ 5 & \quad \quad \quad \textbf{for}~ j \gets 0 ~\textbf{to}~ i-1 ~\textbf{do} \ 6 & \quad \quad \quad \quad \textbf{if}~ \alpha(j) = 1 ~\textbf{then}~ \alpha\gets\alpha+\epsilon'_j & flip~\alpha(j)\ 7 & \quad \quad \quad \textbf{end}~\textbf{for} \ 8 & \quad \quad \quad \textbf{for}~ j \gets i+1 ~\textbf{to}~ n ~\textbf{do} \ 9 & \quad \quad \quad \quad \textbf{if}~ \epsilon'_j(i) = 1 ~\textbf{then}~ \epsilon'_j\gets\alpha+\epsilon'_j & flip~\epsilon'_j(i)\ 10 & \quad \quad \quad \textbf{end}~\textbf{for} \ 11 & \quad \quad \quad \epsilon'_i\gets\alpha & replace\ 12 & \quad \quad \quad \textbf{goto}~ line~ 16 \ 13 & \quad \quad \textbf{end}~\textbf{if} \ 14 & \quad \textbf{end}~\textbf{if} \ 15 & \textbf{end}~\textbf{for} \ 16 & restore~\alpha~and~insert~\alpha~to~V',~delete~\alpha~from~V \end{array}$

正确性

可用归纳法证明

复杂度

令 $n$ 为维数

代码

众所周知, $\mathbb{Z}_2$ 上的加法即为异或, 故代码实现时可以将 $V$ 中元素写为无符号整形或 std::bitset, 加法即为异或

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp xor-basis/Xor_base.hpp %} </details>

例题