XOR Basis

Table of contents

Introduction

The xor basis is a technique for problems about the xor sum of subarrays (contiguous or not) of an array of integers, or about appending elements to an array while answering queries.

The technique splits into two main parts:

• Represent the integers in base 2 and view each element as a vector in the vector space $\mathbb{Z}_2^d$, where $d$ is the number of bits needed to represent them. Xor between elements then equals addition between the corresponding vectors in $\mathbb{Z}_2^d$.
• Relate what a query asks to the basis of the vector space built above.

Some concepts

Vector space

A set $V \ne \varnothing$ is a vector space if $V$ carries two operations: addition and multiplication by a scalar. The elements of $V$ are called vectors.

• $V$ is closed: $\forall x, y \in V \Longrightarrow x + y \in V$ and $\forall x \in V \Longrightarrow kx \in V$, where $k$ is a scalar.
• Addition is associative and commutative.
• Multiplication by a scalar is associative and distributive.
• $V$ contains an element $O$ called the zero vector (not to be confused with the number $0$).

Some special vector spaces:

• The coordinate space $\mathbb{R}^n = \{(x_1, x_2, \ldots, x_n)\}$.
• The vector space $M_{n \times m}$ of $n \times m$ matrices.
• The vector space $P_n(x)$ of polynomials of degree at most $n$.
• The vector space $F$ of functions.
• …

Linear independence and dependence

A set of vectors $\{v_1, v_2, \ldots, v_n\}$ is linearly independent if the equation

has only the trivial solution $x_1 = x_2 = \ldots = x_n = 0$.

Conversely, if there exist $x_1, x_2, \ldots, x_n$ not all zero with

the set is linearly dependent.

The vector space $\mathbb{Z}_2^d$

$\mathbb{Z}_2$: $\mathbb{Z}_m$ is the set of residues when dividing by $m$, and the operations on $\mathbb{Z}_m$ also divide by $m$. So $\mathbb{Z}_2$ is the set of residues when dividing by $2$, hence $\mathbb{Z}_2 = \{0, 1\}$.

$\mathbb{Z}_2^d$: a $d$-dimensional vector space containing every vector with $d$ coordinates, each coordinate an element of $\mathbb{Z}_2$.

• For two vectors $x, y \in \mathbb{Z}_2^d$, define $x + y$ as $x \oplus y$ ($\oplus$ is bitwise xor). Note that $x + y \in \mathbb{Z}_2^d$ must hold. Concretely:

  		$\oplus$	Sum	Sum mod 2
  0	0	0	0	0
  0	1	1	1	1
  1	0	1	1	1
  1	1	0	2	0

• For $c \in \mathbb{Z}_2$, write $cx = \underbrace{x + x + \ldots + x}_{c \text{ times }x}$. Then $cx = 0$ if $c$ is even and $cx = x$ if $c$ is odd.

From here on we only care about the vector space $\mathbb{Z}_2^d$. Every computation is taken modulo 2, and we treat $\oplus$ (bitwise xor) as the $+$ of $\mathbb{Z}_2^d$.

Linear span

A vector space $V$ is spanned by a set of vectors $S = \{v_1, v_2, \ldots, v_n\}$ if it contains every vector $x$ expressible as a linear combination of the vectors in $S$. $\text{span}(S) = \left\{\sum_{i = 1}^n c_i v_i \, \middle| \, v_i \in S, c_i \in \{0, 1\} \right\}$ Then we say $V$ is spanned by $S$, $V$ is generated by $S$, or $S$ generates $V$. Note: since we only work in $\mathbb{Z}_2^d$, each coefficient $c_i$ is also a binary value. So in the combination above each $v_i$ has exactly two states: present or absent. Example: find span$(\{2, 5\})$, span$(\{2, 5, 7\})$ and span$(\{\})$?

• Since $2 \oplus 5 = 7$:

Some important properties:

• If $v_{n + 1} \in \text{span}(\{v_1, v_2, \ldots, v_n\})$ then:

  $$\text{span}(\{v_1, v_2, \ldots, v_n, v_{n + 1}\}) = \text{span}(\{v_1, v_2, \ldots, v_n\})$$

• $\text{span}(\{v_1 + v_3, v_2, \ldots, v_n\}) = \text{span}(\{v_1, v_2, \ldots, v_n\})$

Basis

A set of vectors $B = \{v_1, v_2, \ldots, v_n\}$ is a basis of a vector space $V$ if span$(B) = V$ and $B$ is linearly independent. Then $n$ is the dimension of $V$, written $\text{dim}(V)$.

Example: consider the vector space $V = \{0, 2, 5, 7\}$. $\{2, 5\}$ is a basis of $V$, but $\{2, 5, 7\}$ is not, because it is linearly dependent: $2 \oplus 5 \oplus 7 = 0$. Naturally $\{2, 7\}$ and $\{5, 7\}$ are also bases of $V$.

Note: the number of distinct elements in a vector space $V$ spanned by a basis $B = \{v_1, v_2, \ldots, v_n\}$ is $|V| = 2^n$.

Matrices

Row space and column space

Consider an $n \times m$ matrix $M$ ($n$ rows and $m$ columns):

• Splitting $M$ into row vectors gives: $row_i = [v_{i, 1}, v_{i, 2}, \ldots, v_{i, m}]$
• Splitting $M$ into column vectors gives: $col_i = [v_{1, i}, v_{2, i}, \ldots, v_{n, i}]$
• The row space and column space of $M$ are then:

Rank of a matrix

One can prove that dim$(RS(M)) =$ dim$(CS(M))$; this common value is written dim$(M)$ and is known as the rank of $M$, written rank$(M)$. (See the proof here)

Null space

To follow this part you need to be comfortable with matrix multiplication.

The null space of a matrix $M$, written null$(M)$, is the set of vectors $x \in \mathbb{R}^m$ (written as columns) with:

Suppose:

Then $(x_1, x_2, \ldots, x_m)$ solves the system:

In particular: if the $n \times m$ matrix $M$ consists of $m$ vectors $v \in \mathbb{Z}_2^n$ and $x \in \mathbb{Z}_2^m$ (the vectors $v$ and $x$ written as columns):

then:

Note that the null space is itself a vector space:

Nullity

The nullity of a matrix $M$ is the dimension of its null space:

Rank-nullity theorem

For an $n \times m$ matrix $M$:

The proof is involved and needs several more concepts, so you can consult this one.