XOR Basis

Resources

Introduction

An XOR basis is a minimal set of linearly independent binary vectors that can represent any vector in a given set through XOR combinations. In computational problems, constructing an XOR basis involves iteratively adding vectors to the basis while ensuring each new vector remains independent by reducing it with existing basis vectors. This basis allows efficient representation and manipulation of binary vector spaces, enabling quick determination of linear independence and facilitating solutions to various optimization and combinatorial problems.

XOR basis involves two parts:

• Represent each given number in its base 2 form, considering it as a vector in the ${\mathbb{Z_2^d}}$ vector space, where $d$ is the maximum possible number of bits. The XOR operation on these numbers is equivalent to the addition of the corresponding vectors in the vector space ${\mathbb{Z_2^d}}$.

• Relate the answers to the queries of the second type with the basis of the vectors found in Part 1.

By constructing an XOR basis from the set of vectors, we can efficiently answer various queries about linear independence, redundancy, and other properties related to the XOR combinations of the given numbers. This basis provides a compact representation that allows for quick computation and manipulation of the vector space.

Important terms

Vector Space ${\mathbb{Z_2^d}}$

${\mathbb{Z_2}}$: ${\mathbb{Z_m}}$ is the set of remainders upon division by m. Therefore, ${\mathbb{Z_2}}$ is the set of remainders upon division by 2. Hence ${\mathbb{Z_2}}$ is simply the set $\{0, 1\}$.

${\mathbb{Z_2^d}}$: It represents the set of all binary vectors of length $d$, where each component of the vector belongs to the field ${\mathbb{Z_2}}$, which consists of two elements: 0 and 1.

Linear Span

The span of a set of vectors ${S = \{v_1, v_2,..., v_n \}}$ in a vector space $V$ consists of all vectors $x$ that can be represented as linear combination of the vectors in $S$. Mathematically, the span of $S$ is defined as:

This mean that any vector $x$ in $V$ can be expressed as a liner combination fo the vectors $v_1, v_2,...,v_n$ in $S$, where each coefficient $c_i$ is either 0 or 1. The span of $S$ represents the subspace of $V$ that is generated by the vectors in $S$, encompassing all possible combinations of those vectors. Understanding the span of a set of vectors is crucial for determining the reach or extent of the vector's influence within the vector space.

Basis

A set of vectors $B = \{v_1, v_2,....,v_n\}$ is termed the basis of a vector space $V$ if the span of $B$ covers $V$ entirely and $B$ is linearly independent. In other words, any vector in $V$ can be expressed as a linear combination of the vectors in $B$, and no vector in $B$ can be represented as a linear combination of the others. The number of vectors in $B$ , denoted as $n$, is defined as the dimension of $V$, represented by $dim(V)$. Understanding the basis and dimension of a vector space is crucial for analyzing its structure, solving linear equations, and performing transformations in various mathematical and computational contexts.

Example - Xor Closure

You are given a set of $N$ integer values. You should find the minimum number of values that you need to add to the set such that the following will hold true:

• For every two integers $A$ and $B$ in the set, their bitwise xor $A \oplus B$ is also in the set.

Solution

The solution involves constructing an XOR basis from a set of binary vectors and computing a value based on this basis. Each vector is inserted into the XOR basis by attempting to minimize it through XOR-ing with existing basis vectors, ensuring that the vector remains linearly independent. If the vector cannot be fully reduced to zero, it is added to the basis. This ensures that the basis only contains the minimal set of vectors needed to represent the space spanned by the input vectors.

Once the basis is constructed, the final result is calculated as $2^{basis.size()}- n$. Here $2^{basis.size()}$ represents the total number of distinct vectors that can be formed using the basis, including the zero vector. By subtracting $n$, the number of input vectors, we adjust for the actual number of vectors, providing insight into their linear independence and redundancy. The computed value is then printed as the output, reflecting the difference between the total possible combinations and the number of given vectors.

Copy
#include <bits/stdc++.h>
using namespace std;
#define i23 long long

vector<i23> basis;

void add(i23 x) {
	for (int i = 0; i < (int)basis.size();
	     i++) {  // reduce x using the current basis vectors
		x = min(x, x ^ basis[i]);

Example - Trees and XOR Queries Again

You are given a tree consisting of $n$ vertices. There is an integer written on each vertex; the $i$-th vertex has integer $a_i$ written on it. You have to process $q$ queries. The $i$-th query consists of three integers $x_i$, $y_i$ and $k_i$. For this query, you have to answer if it is possible to choose a set of vertices $v_1,v_2,…,v_m$ (possibly empty) such that:

• every vertex $v_j$ is on the simple path between $x_i$ and $y_i$ (endpoints can be used as well);
• $a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$, where $\oplus$ denotes the bitwise XOR operator.

Solution

To efficiently compute XOR bases on paths in a tree, we use a method involving tree rooting, Lowest Common Ancestor (LCA), and properties of XOR bases. The process begins by rooting the tree and using LCA to split any path into two vertical paths. For each vertex $v$, we maintain a list of "interesting" vertices that significantly influence the XOR base when traversing from $v$ to the root. Due to the properties of XOR bases, these lists are small, with a maximum size of 20.

The core idea is to build these lists for all vertices efficiently. For a vertex $v$, its list is derived from its parent's list. If $v$ adds a new element to the XOR base of its parent's list, $v$ is added to its list; otherwise, one element in the parent's list is replaced. This propagation ensures that the size of each list remains manageable and enables efficient construction of these lists in $\mathcal{O}(nB^2)$ time, where $B$ is the size of the XOR base, typically 20.

When answering a query, the XOR base for any path is obtained by combining the lists from the two vertical paths derived from the LCA. This merging and computation can be done in $\mathcal{O}(B^2 + \log n)$ time per query, providing an efficient solution for the problem.

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 200001, K = 20;
vector<int> arr(N), tin(N, 0), tout(N, 0), up[N];
vector<int> adj[N];
vector<vector<int>> p(N, vector<int>(K, 0));
int T = 0;

int reduce(array<int, K> &b, int x) {  // reducing x using basis vectors b

Problems

Some harder tasks: