GF(2) Gaussian Elimination / XOR Basis

Why GF(2) Gaussian Elimination / XOR Basis Matters

Imagine switches that toggle lights. Pressing a switch twice cancels its effect, and only the parity of the press count matters. Each light's final state becomes an equation in bits. Gaussian elimination over the two-element field $\mathrm{GF}(2)$ finds whether the target state is reachable, one valid switch selection, and every alternative selection.

A related question starts with integer bit masks: which values can be formed by XORing a subset of them? An XOR basis keeps only independent masks. It supports exact membership tests, rank, and maximum subset XOR without enumerating every subset. Both algorithms are linear algebra over the same field, organized for different queries.

We will trace a binary system with a necessary row swap and one free variable, then build an XOR basis from its row masks. The programs implement both approaches in Python, C++, and Java, using exact checks rather than floating-point tolerances. They also distinguish dependence from inconsistency, a distinction that matters whenever right-hand sides are present.

Core Concepts and Terminology

The field $\mathrm{GF}(2)=\{0,1\}$ uses arithmetic modulo $2$. Its addition table is XOR: $1+1=0$. Multiplication of bits is AND. There are no carries, approximate zeros, or numerical conditioning decisions. Every nonzero pivot is already $1$, so pivot normalization requires no division.

For an $m\times n$ binary matrix $A$ and bit vector $b$, the system $Ax=b$ means

$$ \bigoplus_{j=0}^{n-1}(A_{ij}\mathbin{\land}x_j)=b_i \quad\text{for every row }i. $$

The coefficient rank $r$ is the number of independent pivot rows. If the system is consistent, there are $d=n-r$ free variables and exactly $2^d$ solutions. A particular solution $x^{(0)}$ and a nullspace basis $h_1,\ldots,h_d$ describe them all:

$$ x=x^{(0)}\oplus t_1h_1\oplus\cdots\oplus t_dh_d, \qquad t_i\in\{0,1\}. $$

A row with all-zero coefficients and right side $0$ is redundant. The same coefficient row with right side $1$ is a contradiction. The nullspace depends only on $A$ and still exists even when the affine system is inconsistent.

An integer mask is a vector of bits. In an XOR basis, slots[k] is either zero, meaning empty, or a mask whose highest set bit is $k$. Distinct leading bits ensure independence. With rank $r$, the span has exactly $2^r$ distinct values, including zero from the empty subset.

For the same row masks, the XOR basis spans the row space of $A$, whereas solving $Ax=0$ finds its nullspace. These are different spaces. To recover which source masks XOR to a target, place the source vectors as columns of a separate system, or track selection witnesses during basis insertion.

The SageMath GF(2) matrix reference documents exact augmented binary matrices and reduced elimination, including classical and optimized M4RI-based algorithms. Our code uses simple arrays to expose each row operation.

How GF(2) Gaussian Elimination / XOR Basis Works, Step by Step

Binary Gauss–Jordan elimination. Copy the augmented rows $[A\mid b]$. Maintain a pivot-row index initially equal to zero, and scan coefficient columns from left to right:

1. Search the remaining rows for a $1$ in the current column. If none exists, skip that column; it will be a free variable.
2. Swap the selected row into the pivot position. Swap the entire augmented row, including its right-hand side.
3. For every other row containing a $1$ in that pivot column, XOR the entire pivot row into it. The pivot entry cancels because $1\oplus1=0$.
4. Record the pivot column and advance the pivot row. Earlier pivot columns remain identity columns because the new pivot row is zero in those columns.
5. After coefficient elimination, reject consistency if any zero coefficient row has right side $1$. The algorithm does not use the right-hand-side column as a coefficient pivot.
6. If consistent, set all free variables to zero and read the pivot variables from their right sides. To build a nullspace basis vector for free column $f$, set its coordinate to $1$, all other free coordinates to zero, and each pivot coordinate to that pivot row's coefficient in column $f$. In characteristic two, subtraction equals addition.

The returned rows have a reduced coefficient block with the right side carried along. For an inconsistent input, they need not be the full reduced row echelon form obtained by also pivoting on the augmented column; the contradiction test is what matters.

Incremental XOR basis. For a new mask $x$, scan bits from high to low. If its current bit is set and a basis vector exists there, XOR that vector into $x$ to clear the bit. If the slot is empty, store the reduced $x$ there and increase rank. If every bit is cleared, the input was already in the span and adds no independent direction.

Membership applies the same reduction without modifying the basis. An unmatched highest bit proves nonmembership. A reduction to zero proves membership. The query $0$ is always reachable, even for an empty basis.

For maximum subset XOR, start with zero and scan the slots high to low. Replace the answer by its XOR with the current basis vector only when that increases its numeric value. A lower-pivot vector cannot change an already decided higher bit, so the greedy decision is valid for nonnegative fixed-width masks.

flowchart TD
    A["Validate exact binary inputs"] --> B{"Task?"}
    B -->|System| C["Search remaining rows for next coefficient pivot"]
    C --> D{"Pivot found?"}
    D -->|Yes| E["Swap entire augmented rows; XOR pivot into other rows"]
    D -->|No| F["Skip column"]
    E --> G{"More coefficient columns and rows?"}
    F --> G
    G -->|Yes| C
    G -->|No| H["Check contradictions; construct particular and nullspace"]
    B -->|Basis insertion| I["Inspect next highest bit"]
    I --> J{"Current bit set?"}
    J -->|No| O{"More lower bits?"}
    J -->|Yes| P{"Slot occupied?"}
    P -->|Yes| K["XOR stored vector to clear bit"]
    K --> O
    P -->|No| L["Store reduced vector; increase rank; finish"]
    O -->|Yes| I
    O -->|No| M["Zero remainder: dependent input"]

Worked Example with a Full Trace

Use variables $x_0,x_1,x_2$ and

$$ A=\begin{pmatrix}0&1&1\\1&1&0\\1&0&1\end{pmatrix}, \qquad b=\begin{pmatrix}1\\1\\0\end{pmatrix}. $$

The equations are $x_1\oplus x_2=1$, $x_0\oplus x_1=1$, and $x_0\oplus x_2=0$. The leftmost displayed coefficient maps to the highest bit when these rows are viewed as three-bit masks.

Initial augmented state:

$$ \left(\begin{array}{ccc|c}0&1&1&1\\1&1&0&1\\1&0&1&0\end{array}\right). $$

Column $0$: choose and swap a pivot. Row $0$ has a zero in this column, so choose row $1$ and swap them:

$$ \left(\begin{array}{ccc|c}1&1&0&1\\0&1&1&1\\1&0&1&0\end{array}\right). $$

Clear the bottom row's leading $1$ by $R_2\leftarrow R_2\oplus R_0$. Its full augmented contents become $(1,0,1,0)\oplus(1,1,0,1)=(0,1,1,1)$:

$$ \left(\begin{array}{ccc|c}1&1&0&1\\0&1&1&1\\0&1&1&1\end{array}\right). $$

Column $1$: use row $1$ as pivot. First clear it from row $0$ using $R_0\leftarrow R_0\oplus R_1$:

$$ \left(\begin{array}{ccc|c}1&0&1&0\\0&1&1&1\\0&1&1&1\end{array}\right). $$

Then clear it from row $2$ using $R_2\leftarrow R_2\oplus R_1$:

$$ \left(\begin{array}{ccc|c}1&0&1&0\\0&1&1&1\\0&0&0&0\end{array}\right). $$

Column $2$: no remaining pivot. The only unused row is zero, so this column is free. There is no contradiction. Rank is $2$, and $x_2=t$ gives $x_0=t$, $x_1=1\oplus t$. The two solutions are

$$ x^{(0)}=(0,1,0)^T, \qquad x^{(0)}\oplus(1,1,1)^T=(1,0,1)^T. $$

The nullspace is spanned by $(1,1,1)^T$, and the solution count is $2^{3-2}=2$. Substituting either solution into the original three equations yields residual zero.

XOR basis from the coefficient row masks. Read the same rows as the stream $011_2=3$, $110_2=6$, $101_2=5$:

The span is $\{000,011,101,110\}$, so there are $2^2=4$ distinct values. To test $101$, XOR $110$ and then $011$, reaching zero. To test $111$, XOR $110$ to get $001$; slot $0$ is empty, so $111$ is unreachable.

For the maximum, start at $000$, use slot $2$ to reach $110=6$, then decline the slot-$1$ change because $110\oplus011=101=5$ is smaller. The maximum is $6$.

A single changed right side. Replace only the third right-hand side by $1$. The same coefficient operations produce a last row $[0,0,0\mid1]$, so there are no solutions. The coefficient rank and coefficient XOR basis remain $2$; knowing their rank alone cannot decide consistency.

Implementation in Python, C++, and Java

Each panel is a complete program implementing both a binary Gauss–Jordan solver and an XOR basis. Run Python 3, compile C++14 or newer, or save Java as Main.java. The system solver accepts a nonempty rectangular matrix of integer bits and a matching right side, preserves both inputs, and returns coefficient rank, consistency, a particular solution, a nullspace basis, and the transformed augmented rows. For an inconsistent system, the particular-solution array is empty, while the nullspace basis still describes $Ax=0$.

All pivot and residual checks are exact. A floating-point tolerance is inappropriate for this field: a bit is either zero or one. Inputs outside the bit domain are rejected instead of being silently reduced modulo two. The sample verifies the particular solution against original $A,b$ and checks every returned nullspace vector against a zero right side.

The XOR basis supports widths from $1$ to $62$ and nonnegative values smaller than $2^W$. This shared range avoids signed-order and sign-bit differences between C++ and Java. C++ uses uint64_t; Java uses long with 1L shifts; Python enforces the same range despite its larger integers. The matrix solver does not share this $62$-variable bound, since its rows use separate bit entries.

Insertion returns whether rank increased. Membership and maximum queries do not modify the basis. Inserting zero or a dependent mask returns false. The sample prints counts as powers of two, avoiding an overflowing fixed-width count when a system has many free variables. The residual helper assumes compatible binary inputs and is called only on returned solutions or nullspace vectors.

def solve_gf2(a, b):
    m = len(a)
    n = len(a[0]) if m else 0
    if n == 0 or len(b) != m or any(len(row) != n for row in a):
        raise ValueError("require a nonempty rectangular A and matching b")
    if any(not isinstance(v, int) or v not in (0, 1) for row in a for v in row):
        raise ValueError("A entries must be integer bits")
    if any(not isinstance(v, int) or v not in (0, 1) for v in b):
        raise ValueError("b entries must be integer bits")
    rows = [row[:] + [b[i]] for i, row in enumerate(a)]
    pivots = []
    rank = 0
    for col in range(n):
        pivot = next((i for i in range(rank, m) if rows[i][col]), None)
        if pivot is None:
            continue
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        for i in range(m):
            if i != rank and rows[i][col]:
                for j in range(n + 1):
                    rows[i][j] ^= rows[rank][j]
        pivots.append(col)
        rank += 1
        if rank == m:
            break
    consistent = not any(not any(row[:n]) and row[n] for row in rows)
    particular = [0] * n if consistent else []
    if consistent:
        for i, col in enumerate(pivots):
            particular[col] = rows[i][n]
    used = set(pivots)
    kernel = []
    for free in range(n):
        if free not in used:
            vector = [0] * n
            vector[free] = 1
            for i, col in enumerate(pivots):
                vector[col] = rows[i][free]
            kernel.append(vector)
    return rank, consistent, particular, kernel, rows


class XorBasis:
    def __init__(self, width):
        if not isinstance(width, int) or not 1 <= width <= 62:
            raise ValueError("width must be an integer from 1 to 62")
        self.width = width
        self.slots = [0] * width
        self.rank = 0

    def validate(self, x):
        if not isinstance(x, int) or not 0 <= x < (1 << self.width):
            raise ValueError("value must fit the nonnegative bit width")

    def insert(self, x):
        self.validate(x)
        for bit in range(self.width - 1, -1, -1):
            if x & (1 << bit):
                if self.slots[bit]:
                    x ^= self.slots[bit]
                else:
                    self.slots[bit] = x
                    self.rank += 1
                    return True
        return False

    def contains(self, x):
        self.validate(x)
        for bit in range(self.width - 1, -1, -1):
            if x & (1 << bit):
                if not self.slots[bit]:
                    return False
                x ^= self.slots[bit]
        return True

    def maximum(self):
        answer = 0
        for bit in range(self.width - 1, -1, -1):
            answer = max(answer, answer ^ self.slots[bit])
        return answer


def residual(a, x, b):
    error = 0
    for row, rhs in zip(a, b):
        value = 0
        for coefficient, variable in zip(row, x):
            value ^= coefficient & variable
        error |= value ^ rhs
    return error


def main():
    a = [[0, 1, 1], [1, 1, 0], [1, 0, 1]]
    b = [1, 1, 0]
    rank, consistent, x, kernel, rows = solve_gf2(a, b)
    basis = XorBasis(3)
    for value in [3, 6, 5]:
        basis.insert(value)
    status = "inconsistent" if not consistent else ("unique" if rank == 3 else "multiple")
    error = residual(a, x, b) if consistent else 1
    homogeneous_ok = all(residual(a, v, [0, 0, 0]) == 0 for v in kernel)
    print(f"system rank = {rank}")
    print("status = " + status)
    print("particular = " + str(x))
    print("nullspace = " + str(kernel))
    print("solution count = " + (f"2^{3 - rank}" if consistent else "0"))
    print(f"GF(2) residual = {error}")
    print(f"basis rank = {basis.rank}")
    print("contains 5 = " + str(basis.contains(5)).lower())
    print("contains 7 = " + str(basis.contains(7)).lower())
    print(f"maximum subset XOR = {basis.maximum()}")
    print(f"distinct subset XORs = 2^{basis.rank}")
    good = consistent and error == 0 and homogeneous_ok and basis.rank == rank == 2 and basis.maximum() == 6
    print("check = " + ("PASS" if good else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

using Matrix = std::vector<std::vector<int>>;
struct Result {
    std::size_t rank;
    bool consistent;
    std::vector<int> particular;
    Matrix kernel, rows;
};

Result solve_gf2(const Matrix& a, const std::vector<int>& b) {
    const std::size_t m = a.size(), n = m ? a[0].size() : 0;
    if (n == 0 || b.size() != m) throw std::invalid_argument("require nonempty A and matching b");
    for (const auto& row : a) {
        if (row.size() != n) throw std::invalid_argument("A must be rectangular");
        for (int v : row) if (v != 0 && v != 1) throw std::invalid_argument("A entries must be bits");
    }
    for (int v : b) if (v != 0 && v != 1) throw std::invalid_argument("b entries must be bits");
    Matrix rows = a;
    for (std::size_t i = 0; i < m; ++i) rows[i].push_back(b[i]);
    std::vector<std::size_t> pivots;
    std::size_t rank = 0;
    for (std::size_t col = 0; col < n; ++col) {
        std::size_t pivot = rank;
        while (pivot < m && rows[pivot][col] == 0) ++pivot;
        if (pivot == m) continue;
        std::swap(rows[rank], rows[pivot]);
        for (std::size_t i = 0; i < m; ++i) if (i != rank && rows[i][col])
            for (std::size_t j = 0; j <= n; ++j) rows[i][j] ^= rows[rank][j];
        pivots.push_back(col);
        if (++rank == m) break;
    }
    bool consistent = true;
    for (const auto& row : rows) {
        bool zero = true;
        for (std::size_t j = 0; j < n; ++j) if (row[j]) zero = false;
        if (zero && row[n]) consistent = false;
    }
    std::vector<int> x(consistent ? n : 0, 0);
    if (consistent) for (std::size_t i = 0; i < rank; ++i) x[pivots[i]] = rows[i][n];
    std::vector<bool> used(n, false);
    for (auto col : pivots) used[col] = true;
    Matrix kernel;
    for (std::size_t free = 0; free < n; ++free) if (!used[free]) {
        std::vector<int> v(n, 0); v[free] = 1;
        for (std::size_t i = 0; i < rank; ++i) v[pivots[i]] = rows[i][free];
        kernel.push_back(v);
    }
    return {rank, consistent, x, kernel, rows};
}

class XorBasis {
    int width_;
    std::vector<std::uint64_t> slots_;
    std::size_t rank_ = 0;
    void validate(std::uint64_t x) const {
        if (x >= (std::uint64_t(1) << width_)) throw std::invalid_argument("value exceeds bit width");
    }
public:
    explicit XorBasis(int width) : width_(width) {
        if (width < 1 || width > 62) throw std::invalid_argument("width must be from 1 to 62");
        slots_.assign(static_cast<std::size_t>(width), 0);
    }
    std::size_t rank() const { return rank_; }
    bool insert(std::uint64_t x) {
        validate(x);
        for (int bit = width_ - 1; bit >= 0; --bit) if (x & (std::uint64_t(1) << bit)) {
            if (slots_[bit]) x ^= slots_[bit];
            else { slots_[bit] = x; ++rank_; return true; }
        }
        return false;
    }
    bool contains(std::uint64_t x) const {
        validate(x);
        for (int bit = width_ - 1; bit >= 0; --bit) if (x & (std::uint64_t(1) << bit)) {
            if (!slots_[bit]) return false;
            x ^= slots_[bit];
        }
        return true;
    }
    std::uint64_t maximum() const {
        std::uint64_t answer = 0;
        for (int bit = width_ - 1; bit >= 0; --bit) answer = std::max(answer, answer ^ slots_[bit]);
        return answer;
    }
};

int residual(const Matrix& a, const std::vector<int>& x, const std::vector<int>& b) {
    int error = 0;
    for (std::size_t i = 0; i < a.size(); ++i) {
        int value = 0;
        for (std::size_t j = 0; j < x.size(); ++j) value ^= a[i][j] & x[j];
        error |= value ^ b[i];
    }
    return error;
}
void print_vector(const std::vector<int>& x) {
    std::cout << '[';
    for (std::size_t i = 0; i < x.size(); ++i) {
        if (i) std::cout << ", ";
        std::cout << x[i];
    }
    std::cout << ']';
}
void print_matrix(const Matrix& a) {
    std::cout << '[';
    for (std::size_t i = 0; i < a.size(); ++i) {
        if (i) std::cout << ", ";
        print_vector(a[i]);
    }
    std::cout << ']';
}
int main() {
    const Matrix a = { {0, 1, 1}, {1, 1, 0}, {1, 0, 1} };
    const std::vector<int> b = {1, 1, 0};
    const auto result = solve_gf2(a, b);
    XorBasis basis(3);
    for (std::uint64_t value : {3ULL, 6ULL, 5ULL}) basis.insert(value);
    const std::string status = !result.consistent ? "inconsistent" : (result.rank == 3 ? "unique" : "multiple");
    const int error = result.consistent ? residual(a, result.particular, b) : 1;
    bool homogeneous_ok = true;
    for (const auto& v : result.kernel) if (residual(a, v, {0, 0, 0}) != 0) homogeneous_ok = false;
    std::cout << "system rank = " << result.rank << "\nstatus = " << status << "\nparticular = ";
    print_vector(result.particular); std::cout << "\nnullspace = "; print_matrix(result.kernel);
    std::cout << "\nsolution count = " << (result.consistent ? "2^" + std::to_string(3 - result.rank) : "0")
              << "\nGF(2) residual = " << error << "\nbasis rank = " << basis.rank() << std::boolalpha
              << "\ncontains 5 = " << basis.contains(5) << "\ncontains 7 = " << basis.contains(7)
              << "\nmaximum subset XOR = " << basis.maximum() << "\ndistinct subset XORs = 2^" << basis.rank();
    const bool good = result.consistent && error == 0 && homogeneous_ok && basis.rank() == 2 && result.rank == 2 && basis.maximum() == 6;
    std::cout << "\ncheck = " << (good ? "PASS" : "FAIL") << '\n';
}

import java.util.Arrays;

public class Main {
    static class Result {
        final int rank; final boolean consistent;
        final int[] particular; final int[][] kernel,rows;
        Result(int rank,boolean consistent,int[] particular,int[][] kernel,int[][] rows) {
            this.rank=rank;this.consistent=consistent;this.particular=particular;this.kernel=kernel;this.rows=rows;
        }
    }
    static Result solveGF2(int[][] a,int[] b) {
        int m=a.length,n=m>0&&a[0]!=null?a[0].length:0;
        if(n==0||b.length!=m)throw new IllegalArgumentException("require nonempty A and matching b");
        for(int[]row:a) {
            if(row==null||row.length!=n)throw new IllegalArgumentException("A must be rectangular");
            for(int v:row)if(v!=0&&v!=1)throw new IllegalArgumentException("A entries must be bits");
        }
        for(int v:b)if(v!=0&&v!=1)throw new IllegalArgumentException("b entries must be bits");
        int[][]rows=new int[m][n+1];
        for(int i=0;i<m;++i){System.arraycopy(a[i],0,rows[i],0,n);rows[i][n]=b[i];}
        int[]pivots=new int[n];int rank=0;
        for(int col=0;col<n;++col) {
            int pivot=rank;while(pivot<m&&rows[pivot][col]==0)++pivot;
            if(pivot==m)continue;
            int[]row=rows[rank];rows[rank]=rows[pivot];rows[pivot]=row;
            for(int i=0;i<m;++i)if(i!=rank&&rows[i][col]!=0)
                for(int j=0;j<=n;++j)rows[i][j]^=rows[rank][j];
            pivots[rank++]=col;if(rank==m)break;
        }
        boolean consistent=true;
        for(int[]row:rows) {
            boolean zero=true;for(int j=0;j<n;++j)if(row[j]!=0)zero=false;
            if(zero&&row[n]!=0)consistent=false;
        }
        int[]x=new int[consistent?n:0];
        if(consistent)for(int i=0;i<rank;++i)x[pivots[i]]=rows[i][n];
        boolean[]used=new boolean[n];for(int i=0;i<rank;++i)used[pivots[i]]=true;
        int[][]kernel=new int[n-rank][n];int index=0;
        for(int free=0;free<n;++free)if(!used[free]) {
            kernel[index][free]=1;
            for(int i=0;i<rank;++i)kernel[index][pivots[i]]=rows[i][free];++index;
        }
        return new Result(rank,consistent,x,kernel,rows);
    }
    static class XorBasis {
        final int width; final long[]slots; int rank=0;
        XorBasis(int width) {
            if(width<1||width>62)throw new IllegalArgumentException("width must be from 1 to 62");
            this.width=width;slots=new long[width];
        }
        void validate(long x) {
            if(x<0||x>=(1L<<width))throw new IllegalArgumentException("value must fit nonnegative bit width");
        }
        boolean insert(long x) {
            validate(x);
            for(int bit=width-1;bit>=0;--bit)if((x&(1L<<bit))!=0) {
                if(slots[bit]!=0)x^=slots[bit];
                else{slots[bit]=x;++rank;return true;}
            }
            return false;
        }
        boolean contains(long x) {
            validate(x);
            for(int bit=width-1;bit>=0;--bit)if((x&(1L<<bit))!=0) {
                if(slots[bit]==0)return false;x^=slots[bit];
            }
            return true;
        }
        long maximum() {
            long answer=0;for(int bit=width-1;bit>=0;--bit)answer=Math.max(answer,answer^slots[bit]);return answer;
        }
    }
    static int residual(int[][]a,int[]x,int[]b) {
        int error=0;
        for(int i=0;i<a.length;++i) {
            int value=0;for(int j=0;j<x.length;++j)value^=a[i][j]&x[j];error|=value^b[i];
        }
        return error;
    }
    public static void main(String[]args) {
        int[][]a={ {0,1,1},{1,1,0},{1,0,1} };int[]b={1,1,0};Result result=solveGF2(a,b);
        XorBasis basis=new XorBasis(3);for(long value:new long[]{3,6,5})basis.insert(value);
        String status=!result.consistent?"inconsistent":(result.rank==3?"unique":"multiple");
        int error=result.consistent?residual(a,result.particular,b):1;
        boolean homogeneousOK=true;for(int[]v:result.kernel)if(residual(a,v,new int[3])!=0)homogeneousOK=false;
        System.out.println("system rank = "+result.rank);System.out.println("status = "+status);
        System.out.println("particular = "+Arrays.toString(result.particular));
        System.out.println("nullspace = "+Arrays.deepToString(result.kernel));
        System.out.println("solution count = "+(result.consistent?"2^"+(3-result.rank):"0"));
        System.out.println("GF(2) residual = "+error);System.out.println("basis rank = "+basis.rank);
        System.out.println("contains 5 = "+basis.contains(5));System.out.println("contains 7 = "+basis.contains(7));
        System.out.println("maximum subset XOR = "+basis.maximum());System.out.println("distinct subset XORs = 2^"+basis.rank);
        boolean good=result.consistent&&error==0&&homogeneousOK&&basis.rank==2&&result.rank==2&&basis.maximum()==6;
        System.out.println("check = "+(good?"PASS":"FAIL"));
    }
}

All three programs print the same twelve lines:

• system rank = 2
• status = multiple
• particular = [0, 1, 0]
• nullspace = [[1, 1, 1]]
• solution count = 2^1
• GF(2) residual = 0
• basis rank = 2
• contains 5 = true
• contains 7 = false
• maximum subset XOR = 6
• distinct subset XORs = 2^2
• check = PASS

Complexity, Correctness, and Invariants

Let the system have $m$ equations, $n$ variables, coefficient rank $r$, and nullity $d=n-r$. Validation and copying take $O(mn)$. The code searches for pivots and, for each pivot, may XOR a complete augmented row into up to $m-1$ other rows. Elimination therefore costs $O(mn+rmn)$. Explicitly returning the $d$ length-$n$ nullspace vectors adds $O(nd)$ time and storage. Total storage is $O(mn+nd)$ for transformed rows and output vectors.

For square $n\times n$ input, best cases such as the identity take $\Theta(n^2)$ because the XOR updates are skipped when a pivot column is already clear. The worst case is $\Theta(n^3)$. Uniformly random dense binary square matrices have expected cubic work for this elementary representation; sparse or structured inputs need their own analysis. Even the all-zero system returns a length-$n$ basis of $n$ vectors, so its output alone occupies $\Theta(n^2)$ space.

For a $W$-bit XOR basis, insertion and membership take $O(W)$ word operations, and maximum takes $\Theta(W)$. An insertion can finish immediately if its top bit finds an empty slot; dependent or zero values may scan all slots. Building from $N$ masks costs $O(NW)$ and stores $O(W)$ words. These word-operation bounds apply to the bounded masks used here; arbitrary-width big integers have costs that grow with their represented size.

For elimination, row swapping is invertible, and XORing one row into another is its own inverse. Applying these operations to the entire augmented matrix preserves exactly the set of solutions. After each pivot, completed pivot columns are identity columns; a new row operation preserves them because the new pivot row is zero there. At termination, each free assignment determines every pivot variable, unless a contradiction exists.

The nullspace construction sets a distinct free coordinate to one for each basis vector, so these vectors are independent. Any homogeneous solution is determined by its free coordinates and is the XOR combination of the corresponding basis vectors. Adding a particular solution translates this homogeneous space into the full affine solution family, establishing the count $2^{n-r}$ for consistent systems.

For the XOR basis, each reduction $x\leftarrow x\oplus B_k$ preserves the span of the old basis together with $x$. If the remainder is zero, the input was already in the span. If it has a leading bit with an empty slot, no old combination can equal it, so insertion adds one independent direction. Distinct leading bits also justify membership reduction and imply exactly $2^r$ distinct combinations.

Finally, in the maximum query, a pivot vector's highest bit is the first bit it can change. All lower-pivot vectors leave that bit unchanged. Choosing the larger current value fixes the best attainable value of that bit while preserving the already chosen higher prefix, proving the greedy maximum.

Variants, Pitfalls, and Optimizations

XOR is not OR or ordinary addition. Binary $011\oplus110=101$, whereas $011\mathbin{\lor}110=111$. OR does not cancel a shared pivot bit and can invent an unreachable value. Ordinary integer addition introduces carries and also computes a different operation. Use AND to multiply individual coefficient bits, then XOR to combine their contributions.

The right side must follow the row. Swapping or XORing only coefficients changes the affine system. Redundant coefficients can accompany either a redundant equation or a contradiction, depending on the right side. The solver's rank is coefficient rank, not augmented rank; with one right-hand-side column, an inconsistent system has augmented rank $r+1$.

A basis is not a list of original vectors or witnesses. A stored pivot can be the XOR of several inputs. To recover a subset, attach a selection mask to each vector and XOR those masks during the same reductions. To find a witness for a target from scratch, solve the system with source masks as columns. Extra provenance changes storage costs, especially for many source positions.

Representation order matters. The system solver scans columns left to right, while the packed basis scans highest numeric bits first. The sample maps the leftmost coefficient to the highest bit. Other conventions work if used consistently. The slot array is an echelon basis rather than a fully reduced canonical basis; different insertion orders may store different vectors with the same span. The descending greedy maximum needs only the distinct-highest-bit property used here.

Counts answer different questions. Rank $r$ gives $2^r$ distinct subset XORs. If $N$ indexed inputs were inserted, every reachable value has $2^{N-r}$ subset representations, including effects of duplicates and zero inputs. System solutions instead use the nullity of their coefficient matrix. Do not use any of these counts as a consistency test.

Scale the implementation with the problem. Pack augmented rows into bitsets for faster XOR, carrying the RHS bit too. Dense libraries use blocked methods such as M4RI; sparse elimination can still create fill-in. A static basis supports merging by inserting another basis's vectors, but deleting an arbitrary original value is not supported by this simple structure. Dynamic settings may need rollback, timestamps, or offline processing. A $k$-th sorted subset-XOR query requires additional ordering or reduction logic; the maximum routine alone does not provide it.

Practice Problems and Real-World Use

For small systems, enumerate every binary assignment independently and compare that set with the returned particular solution plus all nullspace combinations. Test unique, multiple, and inconsistent outcomes; include zero rows, duplicate equations with opposite right sides, and a pivot requiring a swap. For small streams, enumerate all indexed subsets and compare the distinct XOR set, maximum, and membership results.

For larger masks, test the top supported bit and boundary values explicitly. Preserve the system inputs and verify that queries leave the basis unchanged. A useful bridge test converts each coefficient row to a mask and confirms that its XOR-basis rank equals the matrix coefficient rank, while remembering that span membership and affine consistency are different queries.