∑MathAdvanced

Gaussian Elimination over GF(2)

Key Points

  • •
    Gaussian elimination over GF(2) is ordinary Gaussian elimination where addition and subtraction are XOR and multiplication is AND.
  • •
    Every integer (or bitset) is a vector of bits, and any XOR of elements is a linear combination over GF(2).
  • •
    A linear (XOR) basis lets you answer maximum XOR subset, membership, and counting queries in near-linear time for 64-bit data.
  • •
    Using bitsets, elimination on an n×n system runs about /64 operations because each row XOR costs n/64 machine words.
  • •
    The rank r of your set tells you that exactly 2^r distinct XOR results are possible and that each representable target has 2^{n−r} generating subsets.
  • •
    Consistency of a system Ax = b over GF(2) is checked by elimination: a zero row with RHS 1 means no solution.
  • •
    Back substitution over GF(2) is the same as usual but with XOR, and free variables give 2^{nullity} solutions.
  • •
    A careful pivot order (highest set bit first) and word-packed operations give fast, cache-friendly implementations in C++.

Prerequisites

  • →Bitwise operations (XOR, AND, shifts) — GF(2) arithmetic maps directly to bitwise operations; understanding XOR semantics is essential.
  • →Basic linear algebra (rank, basis, Gaussian elimination) — The entire method mirrors standard elimination; terminology like pivots and rank is reused.
  • →Time complexity and word-level parallelism — Bitset acceleration relies on operations per machine word rather than per bit.
  • →Modular arithmetic — Counting representations often requires returning answers modulo a large prime.
  • →C++ standard library (std::bitset, array, vector) — Efficient and safe implementations use these containers and their bitwise operations.
  • →Binary representations of integers — Integers are viewed as bit-vectors; leading bit and bit lengths are central concepts.
  • →Back substitution — Constructing particular solutions from RREF requires back-substitution intuition.

Detailed Explanation

Tap terms for definitions

01Overview

Gaussian elimination over GF(2) is the backbone of many XOR-based problems in competitive programming and computer science. In GF(2), you only have two numbers, 0 and 1, and the arithmetic rules are simple: addition equals XOR, subtraction also equals XOR, and multiplication is just AND. Because these operations map perfectly to bit operations on modern CPUs, we can treat each integer or bitset as a vector and perform fast linear algebra. The goal of elimination is the same as over the reals: transform a matrix to an echelon form to reveal rank, solve systems, or build a basis.

This tool is especially powerful when your data is “just bits”: edge parities in graphs, parity constraints, or maximizing XOR values. A popular data structure, the XOR (linear) basis, stores a set of independent vectors (numbers) with distinct leading bits, enabling you to quickly answer queries like maximum XOR subset or whether a target XOR can be formed. With word-level parallelism (bitsets or 64-bit words), elimination can be made extremely fast, turning cubic behavior into roughly cubic divided by the machine word size.

In short, Gaussian elimination over GF(2) lets you reason about XOR as linear algebra, providing a unifying approach to optimization, decision, and counting problems involving parity.

02Intuition & Analogies

Imagine a room with many light switches. Each switch toggles certain lamps: flip it once and those lamps change state; flip it again and they go back. You never dim a lamp—each lamp is either ON or OFF. That is GF(2): toggling is XOR, and the state depends on whether you flipped a switch an even or odd number of times.

Now, suppose you want to reach a certain lighting pattern. Some switches are redundant: their effect can be reproduced by flipping a combination of others. A minimal set of independent switches that can recreate all achievable patterns is your basis. Flipping any subset of those independent switches yields all reachable states; flipping a redundant one adds nothing new.

Gaussian elimination is just the systematic process of finding these independent switches. You look for a switch that controls some lamp no other chosen switch controls first (a pivot). Keep it. Then use it to cancel that lamp from other switches’ effects (XOR rows). Repeat for other lamps. By the end, each kept switch is responsible for a unique lamp (a unique leading bit), and together they generate every reachable pattern. If your desired pattern needs a lamp no chosen switch can control, it’s impossible (inconsistent); if it only uses lamps that are covered, there are many ways to get it—every extra, unused switch is a free choice, doubling the number of solutions.

03Formal Definition

Let GF(2) be the field with elements {0,1}, with addition and multiplication defined as 1+1=0, 1·1=1, and 1+0=1. For bit-vectors v ∈ GF(2)^d, addition is component-wise modulo 2, which is exactly the bitwise XOR operation. Given a matrix A ∈ GF(2)^{m×n} and a vector b ∈ GF(2)^m, Gaussian elimination applies elementary row operations over GF(2): swap two rows; add one row to another (ro ← ro ⊕ ro). Multiplying rows by nonzero scalars is trivial since the only nonzero scalar is 1. A pivot in column j is a row with a 1 in column j after suitable row permutations such that all rows below it have 0 in column j (row-echelon form). The number of pivots is the rank ). The solution set of exists iff each zero row in the reduced matrix has RHS 0. When solutions exist, there are n − r free variables (nullity), and the solution space is an affine subspace of dimension n − r. A linear (XOR) basis for a set S ⊆ GF(2)^d is a set of vectors B = {,…,} that is linearly independent and spans span(S). In a standard maintained form, each has a distinct highest set bit (pivot position). Any vector x is representable iff reducing x by greedily XORing pivot vectors that share its highest set bit yields 0.

04When to Use

Use GF(2) elimination or an XOR basis whenever your constraints are parity-based or your combination operator is XOR. Common scenarios include:

  • Maximum XOR subset: given numbers a_i, find max XOR over all subsets. Build an XOR basis and greedily combine pivots to maximize the value.
  • Counting subsets that XOR to a target t: reduce t by the basis; if it becomes 0, the count is 2^{n−rank}, otherwise 0.
  • Solving linear systems with parity constraints: problems like finding a labeling of nodes with bits to satisfy edge equations, or reconstructing original bits from parity checks.
  • Graph cycle spaces: each cycle corresponds to a XOR relation of edges; the cycle basis size equals m−n+c (edges−nodes+components), and queries about path XORs reduce to basis operations.
  • Large bit-dimension constraints: with bitset-packed rows, elimination runs in about O(min(m,n)·m·n/word_size), which is often fast enough for n up to a few thousands.

If you only need rank or maximum XOR, prefer the incremental XOR basis on 64-bit words; if you need full solutions Ax = b for thousands of variables, use bitsets.

⚠️Common Mistakes

  • Mixing OR with XOR: addition in GF(2) is XOR, not OR. Using OR destroys linearity; two identical 1s should cancel, not persist.
  • Forgetting pivot order/invariants: when maintaining a basis, ensure each stored vector has a unique highest set bit. Insert by clearing higher bits via existing pivots; only store if a new high bit remains.
  • Assuming every target is representable: always reduce the target by the basis. If any required bit lacks a pivot, there is no solution and the count is zero.
  • Mishandling counts: the number of subsets yielding a representable target is 2^{n−rank}, not 2^{rank}. The latter is the number of distinct XOR values, not the multiplicity for a fixed value.
  • Signed vs unsigned overflow: use unsigned (e.g., uint64_t) for 64-bit bases. Signed shifts or overflows can introduce UB or negative comparisons.
  • Bitset size mismatch: std::bitset<N> must match your column count; off-by-one when adding the RHS column is common.
  • Not checking inconsistency: in Ax = b, a zero row with RHS 1 after elimination means no solution; don’t proceed to back substitution.
  • Inefficient elimination: clearing only below the pivot complicates reconstruction; clearing both above and below yields RREF and simplifies a particular solution. Also, pack bits to use O(n^3/64) instead of O(n^3).

Key Formulas

XOR as GF(2) addition

Explanation: Component-wise XOR equals component-wise addition modulo 2. This justifies treating XOR problems as linear algebra over GF(2).

Rank-Nullity Theorem

Explanation: For an m×n matrix A over any field (including GF(2)), the dimension of the column space plus the dimension of the null space equals the number of variables n.

Size of Span

Explanation: If a basis B has r independent vectors, then every coefficient is 0 or 1, leading to 2^r distinct linear combinations (XORs).

Number of Solutions

Explanation: If Ax = b has at least one solution, every free variable doubles the number of solutions, hence 2^{n−rank}. If inconsistent, there are no solutions.

Subset XOR Counting

Explanation: Given n vectors with rank r, each representable target is produced by exactly 2^{n−r} subsets; non-representable targets are impossible.

Bitset Elimination Cost (rough)

Explanation: Row operations cost d/w word XORs. Across r pivots, touching O(m+n) rows/columns yields this rough complexity; in square cases it becomes about O(/w).

Square Matrix Complexity

Explanation: For an n×n system with bitset packing, each of the O() eliminations costs about n/w word XORs, leading to /w.

64-bit Basis Build

Explanation: Inserting each 64-bit vector checks up to 64 pivot positions, each step is constant time, so the total is linear in n with a small constant.

Complexity Analysis

Two main regimes matter. 1) 64-bit XOR basis: Each vector is a 64-bit unsigned integer. Insertion tries to clear its highest set bit using existing pivots. You test at most 64 bit positions, and each XOR is O(1). Therefore, building the basis for n numbers takes O(n · 64) = O(n) time and O(64) space for the pivot array plus O(1) per vector if you only store pivots. Queries (maximize, membership, maximizeAgainst a mask) also cost O(64) each. This is ideal for classical problems like maximum XOR subset. 2) General d-bit systems with bitsets: Represent each row as a bitset of length d (or d+1 with RHS). A single row XOR then costs O word operations, where w is the machine word size (typically 64). Gaussian elimination performs O(r · (m+n)) such XORs across r pivots, which for square systems (m ≈ n ≈ d) leads to the well-known O(/w) bound. In practice, constants are small, and performance is often dominated by memory bandwidth and cache friendliness. Space complexity is O(m · ⌈d/w⌉) to store the matrix as bitsets. If you also maintain RREF, you keep the same asymptotic space. For the 64-bit basis, space is O(d) = O(64) for pivots; if you require reconstruction of generating subsets, you may need to store additional provenance (masks or indices), increasing space to O(n · ⌈n/w⌉) if you keep full combination masks. Edge cases: When n ≫ d, time tightens to about O(n · / w) for elimination since rank when d ≫ n, it is about O( · d / w).

Code Examples

XOR Linear Basis (64-bit): Max XOR, Membership, and Counting
1#include <bits/stdc++.h>
2using namespace std;
3
4struct XorBasis64 {
5    // basis[i] stores a vector whose highest set bit is i (0..63). 0 means empty.
6    array<uint64_t, 64> basis{}; // zero-initialized
7    int r = 0;                   // rank
8    long long n_inserted = 0;    // number of original vectors inserted
9
10    void insert(uint64_t x) {
11        ++n_inserted;
12        for (int i = 63; i >= 0; --i) {
13            if (((x >> i) & 1ULL) == 0ULL) continue; // bit i is not set
14            if (basis[i] == 0) {
15                basis[i] = x; // new pivot with highest bit i
16                ++r;
17                return;
18            }
19            x ^= basis[i]; // eliminate bit i using existing pivot
20        }
21        // if x becomes 0, it was dependent; rank unchanged
22    }
23
24    bool canRepresent(uint64_t x) const {
25        // Reduce x by the basis from high to low; if it becomes 0, it's in the span.
26        for (int i = 63; i >= 0; --i) {
27            if (((x >> i) & 1ULL) && basis[i]) x ^= basis[i];
28        }
29        return x == 0;
30    }
31
32    uint64_t maximize() const {
33        // Maximum XOR value achievable from any subset of inserted numbers.
34        uint64_t ans = 0;
35        for (int i = 63; i >= 0; --i) if ((ans ^ basis[i]) > ans) ans ^= basis[i];
36        return ans;
37    }
38
39    uint64_t maximizeAgainst(uint64_t x) const {
40        // Maximize x XOR (subset XOR). Equivalent to adding any vector from span(basis) to x.
41        uint64_t ans = x;
42        for (int i = 63; i >= 0; --i) if ((ans ^ basis[i]) > ans) ans ^= basis[i];
43        return ans;
44    }
45
46    long long rank() const { return r; }
47
48    // Count of subsets that produce a given representable target is 2^(n - r).
49    static long long modpow(long long a, long long e, long long mod) {
50        long long res = 1 % mod;
51        while (e > 0) {
52            if (e & 1) res = (__int128)res * a % mod;
53            a = (__int128)a * a % mod;
54            e >>= 1;
55        }
56        return res;
57    }
58
59    long long countWaysMod(long long mod) const {
60        return modpow(2, n_inserted - r, mod);
61    }
62};
63
64int main() {
65    ios::sync_with_stdio(false);
66    cin.tie(nullptr);
67
68    // Demo dataset
69    vector<uint64_t> a = {5, 7, 10, 25, 13}; // 0101, 0111, 1010, 11001, 01101
70    XorBasis64 B;
71    for (auto x : a) B.insert(x);
72
73    cout << "Rank = " << B.rank() << "\n";
74    cout << "Maximum XOR over all subsets = " << B.maximize() << "\n";
75
76    uint64_t target = 12; // 01100
77    bool ok = B.canRepresent(target);
78    cout << "Can represent target " << target << "? " << (ok ? "YES" : "NO") << "\n";
79
80    const long long MOD = 1'000'000'007LL;
81    if (ok) {
82        cout << "Number of subsets achieving target (mod 1e9+7) = " << B.countWaysMod(MOD) << "\n";
83    } else {
84        cout << "Number of subsets achieving target (mod 1e9+7) = 0\n";
85    }
86
87    uint64_t mask = 9; // try to maximize x XOR subset
88    cout << "Maximize (" << mask << ") XOR subset = " << B.maximizeAgainst(mask) << "\n";
89
90    return 0;
91}
92

We maintain a 64-bit XOR basis in reduced high-bit form: each stored vector has a unique highest set bit. Insertion either discovers a new pivot (increasing rank) or reduces to zero (dependent). Membership reduces the target by available pivots; maximum XOR greedily improves the answer using pivots from high to low. The number of subsets that yield any representable target is 2^{n−rank}.

Time: O(n + Q) with small constants (each operation O(64))Space: O(64)
Gaussian Elimination over GF(2) with std::bitset (solve Ax = b, count solutions)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Solve Ax = b over GF(2) using bitset-packed rows. Produces one solution if consistent.
5// MAXM: maximum number of variables (columns). We store m variables + 1 RHS bit per row.
6static const int MAXM = 512; // adjust as needed
7
8struct GF2System {
9    int m; // number of variables (columns)
10    vector< bitset<MAXM + 1> > rows; // each row has m variable bits and 1 RHS bit at index m
11
12    GF2System(int m_, int n_eq) : m(m_), rows(n_eq) {}
13
14    // Set A[i][j] and b[i] from integers 0/1.
15    void set_coeff(int i, int j, int val) { rows[i][j] = (val & 1); }
16    void set_rhs(int i, int val) { rows[i][m] = (val & 1); }
17
18    // Returns (rank, consistent). Also writes one solution to sol (free vars = 0).
19    pair<int,bool> solve(vector<int> &sol) {
20        int n = (int)rows.size();
21        vector<int> where(m, -1); // where[j] = pivot row for column j, or -1
22        int row = 0, rank = 0;
23
24        // Forward elimination to REF
25        for (int col = 0; col < m && row < n; ++col) {
26            int sel = -1;
27            for (int i = row; i < n; ++i) if (rows[i][col]) { sel = i; break; }
28            if (sel == -1) continue; // no pivot in this column
29            swap(rows[sel], rows[row]);
30            where[col] = row;
31            // Eliminate this column from all other rows to form RREF directly
32            for (int i = 0; i < n; ++i) if (i != row && rows[i][col]) rows[i] ^= rows[row];
33            ++row; ++rank;
34        }
35
36        // Check consistency: any 0 = 1 row?
37        for (int i = 0; i < n; ++i) {
38            bool all_zero = true;
39            for (int j = 0; j < m; ++j) if (rows[i][j]) { all_zero = false; break; }
40            if (all_zero && rows[i][m]) return {rank, false};
41        }
42
43        // Back-substitute to get one solution (set free variables to 0)
44        sol.assign(m, 0);
45        for (int j = 0; j < m; ++j) {
46            if (where[j] != -1) {
47                int i = where[j];
48                int val = rows[i][m]; // RHS
49                // Since we made RREF, other pivot columns are already cleared in this row.
50                sol[j] = val;
51            } // else free variable stays 0
52        }
53        return {rank, true};
54    }
55};
56
57int main() {
58    ios::sync_with_stdio(false);
59    cin.tie(nullptr);
60
61    // Example: Solve a small system over GF(2)
62    // x0 ^ x2 = 1
63    // x0 ^ x1 ^ x2 = 0
64    // x1       = 1
65    int m = 3; // variables x0, x1, x2
66    int n = 3; // equations
67    GF2System sys(m, n);
68
69    // Row 0: x0 ^ x2 = 1
70    sys.set_coeff(0, 0, 1);
71    sys.set_coeff(0, 2, 1);
72    sys.set_rhs(0, 1);
73
74    // Row 1: x0 ^ x1 ^ x2 = 0
75    sys.set_coeff(1, 0, 1);
76    sys.set_coeff(1, 1, 1);
77    sys.set_coeff(1, 2, 1);
78    sys.set_rhs(1, 0);
79
80    // Row 2: x1 = 1
81    sys.set_coeff(2, 1, 1);
82    sys.set_rhs(2, 1);
83
84    vector<int> sol;
85    auto [rank, ok] = sys.solve(sol);
86    cout << "Rank = " << rank << ", consistent = " << (ok ? "YES" : "NO") << "\n";
87    if (ok) {
88        cout << "One solution (free vars = 0): ";
89        for (int j = 0; j < m; ++j) cout << sol[j] << (j+1<m?' ':'\n');
90        int nullity = m - rank;
91        cout << "Number of solutions = 2^" << nullity << " (if counting over GF(2))\n";
92    }
93
94    return 0;
95}
96

We pack the matrix into bitsets (variables plus one RHS bit). Elimination chooses a pivot per column, swaps the pivot row in place, and XORs it into all other rows to form RREF directly. Consistency is detected by a zero row with RHS 1. A particular solution is read off by setting free variables to 0. The number of solutions is 2^{m−rank}.

Time: O(n · m · min(n, m) / 64) ≈ O(n^3 / 64) for n ≈ mSpace: O(n · m / 64)
Prefix XOR Basis with Online Queries: Maximize (x XOR subset)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct XorBasis64 {
5    array<uint64_t, 64> b{};
6    void insert(uint64_t x) {
7        for (int i = 63; i >= 0; --i) {
8            if (((x >> i) & 1ULL) == 0ULL) continue;
9            if (!b[i]) { b[i] = x; return; }
10            x ^= b[i];
11        }
12    }
13    uint64_t maximizeAgainst(uint64_t x) const {
14        uint64_t ans = x;
15        for (int i = 63; i >= 0; --i) if ((ans ^ b[i]) > ans) ans ^= b[i];
16        return ans;
17    }
18};
19
20int main() {
21    ios::sync_with_stdio(false);
22    cin.tie(nullptr);
23
24    // Maintain a prefix basis and answer queries of the form: max (query ^ subset)
25    vector<uint64_t> a = {3, 8, 2, 15, 6, 9};
26    vector<pair<int,uint64_t>> queries = {
27        {2, 5}, // after inserting a[0..2), maximize 5 ^ subset
28        {4, 7}, // after a[0..4)
29        {6, 1}  // after a[0..6)
30    };
31
32    XorBasis64 B;
33    size_t qi = 0;
34    for (size_t i = 0; i <= a.size(); ++i) {
35        while (qi < queries.size() && (size_t)queries[qi].first == i) {
36            uint64_t x = queries[qi].second;
37            cout << "After prefix " << i << ", max (" << x << " XOR subset) = " << B.maximizeAgainst(x) << "\n";
38            ++qi;
39        }
40        if (i < a.size()) B.insert(a[i]);
41    }
42    return 0;
43}
44

This program builds an XOR basis incrementally over array prefixes and answers queries to maximize x XOR any subset from the current prefix. The greedy augmentation over basis pivots yields the maximum reachable value of x XOR span(basis).

Time: O((n + q) · 64)Space: O(64)