https://koikuchi3.hatenablog.com/entry/2022/03/10/192835

はじめに

自然数全体の集合 $\mathbb{N}=\{0,1,2,\dots\}$ は、以下のように和とスカラー倍を定めることにより、体 $\mathbb{F}_2=\{0,1\}$ 上のベクトル空間と見なせます。このベクトル空間を $\mathbb{N}_\mathrm{XOR}$ と書きます。

和は、bitwiseのXOR演算（以下では単に $+$ と書く）
スカラー倍は、 $0a=0,\;1a=a$

本記事では、 $\mathbb{N}_\mathrm{XOR}$ の部分空間の基底を管理するのに便利なアルゴリズムと、その正当性についてまとめています。

アルゴリズムの実装

struct XorVecSpace {
    // 部分空間の基底を蓄える配列
    vector<int> basis;

    // 部分空間の生成元を追加、basisのサイズ（部分空間の次元）が大きくなったらtrueを返す
    bool add(int v) {
        int mn = minimize(v);
        if (mn) basis.push_back(mn);
        return mn != 0;
    }

    // 部分空間の元であるかを判定
    bool is_element(int v) const { return minimize(v) == 0; }

    // 部分空間の元とvとの和の最小値を計算
    int minimize(int v) const {
        for (int eb : basis) {
            v = min(v, v ^ eb);
        }
        return v;
    }

    // 部分空間の元とvとの和の最大値を計算
    int maximize(int v) const {
        for (int eb : basis) {
            v = max(v, v ^ eb);
        }
        return v;
    }

    // 部分空間の次元を返す
    int dim() const { return basis.size(); }
};

以下では、自然数の集合 $S\subset\mathbb{N}$ が生成する $\mathbb{N}_\mathrm{XOR}$ の部分空間を $\mathrm{span}(S)$ と書きます。

配列 basis（以下では $b$ と書くことにします）に現在管理している部分空間の基底が蓄えられます。
add：部分空間の生成元として $v$ を追加し、次元が大きくなったか否かを返します。このとき、渡した元そのものが $b$ に入るわけではないので、未加工の元からなる基底が欲しい場合は別途管理する必要があります。
is_element： $v\in\mathrm{span}(b)$ であるかを判定します。
minimize：集合 $\{v+w\;|\;w\in\mathrm{span}(b)\}$ の最小元を返します。
maximize：集合 $\{v+w\;|\;w\in\mathrm{span}(b)\}$ の最大元を返します。
dim：部分空間の次元を返します。

アルゴリズムの正当性

まず、add関数の正当性を示すことを考えます。add関数でやっていることは、集合 $\{v+w\;|\;w\in\mathrm{span}(b)\}$ の最小元 $m$ を求め、 $m\neq 0$ ならば $m\not\in\mathrm{span}(b)$ なので $b$ に $m$ を追加する、ということです。よって、minimize関数の正当性を示せばよいです。

$b=(b_1,b_2,\dots,b_n)$ とし、 $b_i$ の最上位ビットを $d_i$ 桁目とします。minimize関数でやっていることは、 $i=1,2,\dots,n$ の順に、以下で定義される操作 $\mathrm{op}_i$ を $v$ に施すということです。

操作 $\mathrm{op}_i$ ： $v$ の $d_i$ 桁目が $1$ ならば $v$ に $b_i$ を足す。

このアルゴリズムで集合 $\{v+w\;|\;w\in\mathrm{span}(b)\}$ の最小元を求められるのは、add関数によって蓄えられる基底 $b$ がもつ以下の性質によります。

性質

$b_j$ において $d_i\;(i\lt j)$ 桁目は $0$ である。

（性質の証明）基底 $b$ のサイズ $n$ に関する帰納法による。 $b$ のサイズが $n-1$ のとき性質が成り立つことを仮定する。add関数で $b$ に $b_n$ が追加されたとき、 $b_n$ の $d_i\;(i=1,2,\dots,n-1)$ 桁目は $0$ であることを示せばよい。minimize関数において、操作 $\mathrm{op}_i$ の直後、 $v$ の $d_i$ 桁目は $0$ であるが、帰納法の仮定により、以降の操作で $d_i$ 桁目に干渉することはないため、 $b_n$ においても $d_i$ 桁目は $0$ になる。 □

さて、この性質を使うことでminimize関数の正当性を示すことができます。minimize関数でやりたいことは、 $i=1,2,\dots,n$ の順に、 $v$ に $b_i$ を足すor足さないの操作をすることで、 $v$ の最終的な値を最小化するということです。性質より、 $v$ の $d_i$ 桁目は $i$ 番目よりあとの操作で不変です。つまり、 $i$ 番目の操作によって $v$ の $d_i$ 桁目の最終的な値を決めることができます。また、 $i$ 番目の操作では $v$ の $d_i$ 桁目より上の桁には干渉しません。これらを踏まえると、 $v$ の最終的な値を最小化するには、操作 $\mathrm{op}_i$ のようにすればよいです。したがって、minimize関数の正当性がわかりました。

maximize関数の正当性もminimize関数の正当性と同様に理解することができます。

おまけ

bitsetバージョンの実装例です。bitsetのmsbを求める関数がないのはなぜでしょうか？std::bitset::_Find_firstでlsbは求まるので、次元を求めるだけならこれを使って実装してもよいと思います。ただし、最小化、最大化などは壊れてしまいます。

template <int N>
struct XorVecSpace {
    using bs = bitset<N>;

    // 部分空間の基底を蓄える配列
    vector<bs> basis;
    // 基底のmsbをもっておく
    vector<size_t> msb;

    // 部分空間の生成元を追加、basisのサイズ（部分空間の次元）が大きくなったらtrueを返す
    bool add(const bs& v) {
        bs mn{minimize(v)};
        if (mn.none()) return false;
        basis.emplace_back(mn);
        msb.emplace_back(N - 1);
        while (!basis.back().test(msb.back())) --msb.back();
        return true;
    }

    // 部分空間の元であるかを判定
    bool is_element(const bs& v) const { return minimize(v).none(); }

    // 部分空間の元とvとの和の最小値を計算
    bs minimize(bs v) const {
        for (int i = 0; i < (int)basis.size(); ++i) {
            if (v.test(msb[i])) v ^= basis[i];
        }
        return v;
    }

    // 部分空間の元とvとの和の最大値を計算
    bs maximize(bs v) const {
        for (int i = 0; i < (int)basis.size(); ++i) {
            if (!v.test(msb[i])) v ^= basis[i];
        }
        return v;
    }

    // 部分空間の次元を返す
    int dim() const { return basis.size(); }
};

おわりに

掃き出し法の文脈で出てくる「標準形」に対して、このアルゴリズムでは、行のswapをしない標準形、いわば「準標準形」で基底が蓄えられていくのが面白いです。このアイデア自体はXORの掃き出しをする場合に限ったものではないと思いますが、XORの場合は簡単に実装できるという話でした。

参考にした記事

XORの基底をめっちゃ楽に求める方法があるらしい！！！？？？ - Qiita