Linear Basis / XOR Basis

A basis is a maximal linearly independent subset — it spans the same space with the fewest vectors. Over ${\mathbb{F}}_2$ this is the XOR basis, one of the most reused structures in competitive programming; see XOR / Linear Basis for the implementation and applications.

This page covers the general picture.

The general construction

Maintain vectors in reduced row echelon form: each basis vector has a distinct pivot coordinate, and that coordinate is zero in all the others. Inserting a new vector means repeatedly eliminating its leading coordinate against the existing basis; if anything survives, it becomes a new basis vector.

// over a prime field F_p, vectors of dimension d
vector<vector<long long>> basis(d);              // basis[i] has pivot at coordinate i
bool insert(vector<long long> v) {
    for (int i = 0; i < d; i++) {
        if (!v[i]) continue;
        if (basis[i].empty()) {
            long long inv = powmod(v[i], MOD - 2, MOD);
            for (auto& x : v) x = x * inv % MOD;  // normalise the pivot to 1
            basis[i] = v;
            return true;
        }
        long long f = v[i];
        for (int j = 0; j < d; j++)
            v[j] = (v[j] - f * basis[i][j]) % MOD;
    }
    return false;                                 // v was already in the span
}

$O(d^2)$ per insertion, $O(n{d}^2)$ to build.

What a basis tells you

Question	Answer
Dimension of the span	number of basis vectors ($=$ rank)
Is $v$ in the span?	reduce it against the basis; is the result zero
Size of the span (over ${\mathbb{F}}_q$)	$q^{\mathrm{rank}}$
How many input subsets give a specific element	$q^{n-\mathrm{rank}}$
Are the inputs independent?	rank $=$ count
Extremal element of the span	greedy over the basis (over ${\mathbb{F}}_2$: maximum XOR)

The ${\mathbb{F}}_2$ specialisation

Over ${\mathbb{F}}_2$, a vector is an integer, addition is XOR, and there is no scaling. The basis collapses to an array of at most 60 integers, insertion is $O(60)$, and everything becomes bit operations. That efficiency is why it is so widely used.

Over ${\mathbb{F}}_2$	Meaning
Maximum element of the span	greedy from the top bit
$|\mathrm{span}|$	$2^{\mathrm{rank}}$
$k$-th smallest in the span	read $k$‘s bits after full reduction
Merge two bases	insert one into the other, $O(60^2)$

Where it appears

Problem	Field
Maximum XOR of a subset	${\mathbb{F}}_2$
Number of distinct subset XORs	${\mathbb{F}}_2$
XOR of paths in a graph (cycle space)	${\mathbb{F}}_2$
Lights Out / toggle puzzles	${\mathbb{F}}_2$
Solving a modular linear system	${\mathbb{F}}_p$
Counting solutions of linear constraints	${\mathbb{F}}_p$
Independence of vectors / matroid rank	any
Detecting linear dependence in a sequence	any

The matroid connection

The independent subsets of a set of vectors form a linear matroid. That is exactly why the greedy algorithm works: to find the maximum-weight independent set, sort by weight and insert greedily.

This is the same reason Kruskal’s algorithm is correct — spanning forests form a graphic matroid. Recognising a problem as “maximum weight independent set in a matroid” tells you immediately that greedy is optimal.

Example. “Choose a subset of maximum total weight whose XOR-span dimension is as large as possible” → sort by weight descending, insert into the basis greedily, keep whatever expands the span.

Merging and range queries

Bases merge in $O(d^2)$, which makes them compatible with:

• segment trees over ranges — “basis of $a[l..r]$” in $O(\log n\cdot d^2)$;
• small-to-large merging on trees;
• binary lifting — “basis along a tree path”;
• prefix bases with timestamps — $O(d)$ per range query, the technique described in XOR Basis.

See also: XOR / Linear Basis · Rank · Gaussian Elimination