Linear Basis

Recalling the concept of basis vectors from high-school solid geometry, we can find a set of basis vectors $\boldsymbol{i}$, $\boldsymbol{j}$, and $\boldsymbol{k}$ in three-dimensional Euclidean space, after which any vector in the space can be represented by these basis vectors. In other words, we can describe an infinite three-dimensional space using finitely many basis vectors, which is enough to demonstrate the importance of basis vectors.

Three-dimensional Euclidean space is a special linear space, and its basis vectors are generalized to linear bases in linear spaces.

Applications of linear bases in OI usually involve only two kinds of linear spaces: the $n$-dimensional real linear space $\mathbf{R}^n$ and the $n$-dimensional linear space $\mathbf{Z}_2^n$ over the Boolean domain. We will introduce them in detail in the Applications section. If you are unfamiliar with linear algebra, we recommend starting with the Applications section.

The following discussion introduces linear bases from the perspective of general linear spaces and gives their common properties.

Prerequisite: Linear spaces.

A linear basis is a basis of a linear space and an important tool for studying linear spaces.

Definition

An inclusion-maximal linearly independent set in a linear space $V$ is called a Hamel basis or linear basis of $V$, abbreviated as a basis.

The basis of the linear space $\{\theta\}$ is defined to be the empty set.

It can be proved that every linear space has a linear basis¹. We define the dimension of a linear space $V$ as the number of elements (or the cardinality) of a linear basis, denoted by $\dim V$.

Properties

1. For a finite-dimensional linear space $V$ of dimension $n$:

   1. In $V$, any collection of $n+1$ vectors is linearly dependent.

   2. In $V$, any $n$ linearly independent vectors form a basis of $V$.

   3. If every vector in $V$ can be expressed linearly by the vector group $a_1,a_2,\dots,a_n$, then it is a basis of $V$.

      ???+ note "Proof" In $V$, take any basis $b_1,b_2,\dots,b_n$. By the given condition, the vector group $b_1,b_2,\dots,b_n$ can be expressed linearly by $a_1,a_2,\dots,a_n$, so

      $$
      n=\operatorname{rank}\{b_1,b_2,\dots,b_n\}\leq\operatorname{rank}\{a_1,a_2,\dots,a_n\}\leq n
      $$
      
      Therefore, $\operatorname{rank}\{a_1,a_2,\dots,a_n\}=n$.
      

   4. In $V$, any linearly independent vector group $a_1,a_2,\dots,a_m$ can be made into a basis of $V$ by inserting some vectors.

2. (The subspace dimension formula.) Let $V_1,V_2$ be finite-dimensional linear spaces over $\Bbb{P}$, and suppose that $V_1+V_2$ and $V_1\cap V_2$ are also finite-dimensional. Then $\dim V_1+\dim V_2=\dim(V_1+V_2)+\dim(V_1\cap V_2)$.

   ???+ note "Proof" Let $\dim V_1=n_1$, $\dim V_2=n_2$, and $\dim(V_1\cap V_2)=m$.

   Take a basis of $V_1\cap V_2$, denoted by $a_1,a_2,\dots,a_m$, and extend it to bases of $V_1$ and $V_2$, respectively: $a_1,a_2,\dots,a_m,b_1,b_2,\dots,b_{n_1-m}$ and $a_1,a_2,\dots,a_m,c_1,c_2,\dots,c_{n_2-m}$.
   
   It remains only to prove that the vector group $a_1,a_2,\dots,a_m,b_1,b_2,\dots,b_{n_1-m},c_1,c_2,\dots,c_{n_2-m}$ is linearly independent.
   
   Let $\sum_{i=1}^m r_ia_i+\sum_{i=1}^{n_1-m} s_ib_i+\sum_{i=1}^{n_2-m} t_ic_i=\theta$.
   
   Then $\sum_{i=1}^{n_2-m} t_ic_i=-\sum_{i=1}^m r_ia_i-\sum_{i=1}^{n_1-m} s_ib_i$.
   
   The left side lies in $V_2$ and the right side lies in $V_1$, so both sides lie in $V_1\cap V_2$. Therefore, $\sum_{i=1}^{n_2-m} t_ic_i=\sum_{i=1}^m k_ia_i$.
   
   Hence $t_1=t_2=\dots=t_{n_2-m}=k_1=k_2=\dots=k_m=0$, and consequently $r_1=r_2=\dots=r_m=s_1=s_2=\dots=s_{n_1-m}=t_1=t_2=\dots=t_{n_2-m}=0$.
   

3. Let $V_1,V_2$ be finite-dimensional linear spaces over $\Bbb{P}$, and suppose that $V_1+V_2$ and $V_1\cap V_2$ are also finite-dimensional. The following statements are equivalent:

   1. $V_1+V_2=V_1\oplus V_2$.

   2. $\dim V_1+\dim V_2=\dim(V_1+V_2)$.

   3. If $a_1,a_2,\dots,a_n$ is a basis of $V_1$ and $b_1,b_2,\dots,b_m$ is a basis of $V_2$, then $a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_m$ is a basis of $V_1+V_2$.

   ???+ note "Note" Statements 1 and 3 can be generalized to infinite-dimensional linear spaces.

Examples

Consider bases of $\Bbb{R}^2$.

1. As shown in the figure:

   

   $u,v$ form a basis.

2. As shown in the figure:

   

   $u,v$ form a basis.

3. As shown in the figure:

   

   $u,v$ do not form a basis because $u=-v$.

4. As shown in the figure:

   

   $u,v,w$ do not form a basis because $u+4v+6w=\theta$.

Orthogonal Bases and Orthonormal Bases

If a linear space $V$ has a basis $B$ satisfying $\forall b,b'\in B,~(b,b')\ne 0\iff b=b'$ (that is, its elements are pairwise orthogonal), then this basis is called an orthogonal basis.

If a linear space $V$ has an orthogonal basis $B$ that also satisfies $\forall b\in B,~|b|=\sqrt{(b,b)}=1$, this basis is called an orthonormal basis.

The basis of any finite-dimensional linear space $V$ can be transformed into an orthogonal basis through Schmidt orthogonalization.

Applications

Based on the preceding discussion, linear bases can be used to:

1. Find the rank of a given vector group;
2. Find a maximal linearly independent set (or a basis of its span) for a given vector group;
3. Insert some vectors into a given vector group and find a maximal linearly independent set (or a basis of its span) in the resulting vector group;
4. Determine whether a vector can be expressed linearly by a maximal linearly independent set (or basis) that has been found;
5. Find special elements in the span of a maximal linearly independent set (or basis) that has been found, such as the maximum or minimum element.

In OI, a linear basis of the $n$-dimensional real linear space $\mathbf{R}^n$ is generally called a real linear basis, while a linear basis of the $n$-dimensional Boolean-domain linear space $\mathbf{Z}_2^n$ is called an XOR linear basis.

Taking an XOR linear basis as an example, for a given set of Boolean sequences $X=\{x_1,\dots,x_m\}$, we can construct an XOR linear basis $B=\{b_1,\dots,b_n\}$ with the following properties:

1. The XOR sum of any nonempty subset of $B$ is not $0$;
2. For $X$, any element $x$ can be obtained by taking some elements from $B$ whose XOR sum is $x$;
3. For any set $B'$ satisfying the preceding two conditions, the number of its elements is no smaller than the number of elements in $B$.

An XOR linear basis can be used to:

1. Determine whether a number can be represented as the XOR sum of a subset of a given set of numbers;
2. Count the ways to represent a number as the XOR sum of a subset of a given set of numbers;
3. Find the maximum, minimum, $k$-th largest, or $k$-th smallest XOR sum of a subset of a given set of numbers;
4. Find the rank of a number among the XOR sums of subsets of a given set of numbers.

Construction

Since XOR linear bases and real linear bases have no essential difference, we use XOR linear bases as the example below; the code for a real linear basis only requires minor modifications.

Greedy Method

Convert each number $p$ in the original set to binary and scan from the highest bit to the lowest. If bit $x$ is $1$ and $a_x$ does not exist, set $a_x \leftarrow p$ and end the scan; if it exists, set $p\leftarrow p~\text{xor}~a_x$.

To query the maximum value of $\text{xor}$ over any number of elements from the original set, scan the linear basis from the highest bit to the lowest. If applying the current $\text{xor}$ operation to $a_x$ makes the answer larger, XOR the answer with $a_x$.

Why does this work? When scanning from high to low bits, if we have reached bit $i$, we can ensure that bit $i$ of the answer is $1$, and no later operation can change bit $i$.

The minimum value of $\text{xor}$ over any number of elements from the original set is simply the smallest element in the linear-basis set.

To query whether a number can be obtained by XOR, proceed similarly to insertion: if the number $p$ left at the end of insertion has been XORed to $0$, it can be obtained.

#include <algorithm>
#include <iostream>
using ull = unsigned long long;

ull p[64];

void insert(ull x) {
  for (int i = 63; ~i; --i) {
    if (!(x >> i))  // Bit i of x is 0
      continue;
    if (!p[i]) {
      p[i] = x;
      break;
    }
    x ^= p[i];
  }
}

using std::cin;
using std::cout;

int main() {
  int n;
  cin >> n;
  ull a;
  for (int i = 1; i <= n; ++i) {
    cin >> a;
    insert(a);
  }
  ull ans = 0;
  for (int i = 63; ~i; --i) {
    ans = std::max(ans, ans ^ p[i]);
  }
  cout << ans << '\n';
  return 0;
}

Gaussian Elimination

Gaussian elimination constructs a linear basis from the perspective of a system of linear equations; its correctness is clear.

#include <iostream>
using ull = unsigned long long;
constexpr int MAXN = 1e5 + 5;

ull deg(ull num, int deg) { return num & (1ull << deg); }

ull a[MAXN];
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int row = 1;
  for (int col = 63; ~col && row <= n; --col) {
    for (int i = row; i <= n; ++i) {
      if (deg(a[i], col)) {
        std::swap(a[row], a[i]);
        break;
      }
    }
    if (!deg(a[row], col)) continue;
    for (int i = 1; i <= n; ++i) {
      if (i == row) continue;
      if (deg(a[i], col)) {
        a[i] ^= a[row];
      }
    }
    ++row;
  }
  ull ans = 0;
  for (int i = 1; i < row; ++i) {
    ans ^= a[i];
  }
  cout << ans << '\n';
  return 0;
}

Properties

The linear basis constructed by the greedy method has the following properties:

• No subset of the linear basis has XOR sum $0$.
• The highest set bit of each number in the linear basis is different.

The linear basis constructed by Gaussian elimination satisfies the following property:

• The matrix after Gaussian elimination is a row-reduced echelon matrix.

  This property includes the two properties satisfied by the linear basis constructed by the greedy method.

  If you do not understand why this property holds, you can read Gaussian elimination.

Here is an example:

5
633 211 169 841 1008

Binary representations:

1001111001
0011010011
0010101001
1101001001
1111110000

Linear basis generated by the greedy method:

1001111001
0100110000
0011010011
0001111010
0000000000
0000010000
0000000000
0000000000
0000000000
0000000000

Linear basis generated by Gaussian elimination:

1000000011
0100100000
0010101001
0001101010
0000010000
0000000000
0000000000
0000000000
0000000000
0000000000

This is a very useful property that makes many problems easier to solve. For example, given some numbers, if we want the maximum XOR of a subset and construct the linear basis greedily, we need to perform another greedy pass: if the current bit of ans is 0, XORing it will improve the answer; if the current bit is 1, it will not. After constructing the basis by Gaussian elimination, we can simply XOR all basis elements and output the result.

For other classic problems, such as querying whether a number can be obtained by XOR or finding the $k$-th largest XOR value, the basis obtained by Gaussian elimination is also more convenient.

Time Complexity

Let the vector length be $n$ and the total number of vectors be $m$. The time complexity is $O(nm)$. The constant factor of Gaussian elimination is slightly larger.

For a real linear basis, the time complexity is $O(n^2m)$.

Merging Linear Bases

Merging linear bases only requires brute force: insert every vector from one linear basis into the other. The time complexity of one merge is $O(n^2)$ for an XOR linear basis or $O(n^3)$ for a real linear basis.

Intersecting Linear Bases

Strictly speaking, intersecting linear bases means finding a linear basis of the intersection of the two linear spaces that they span. This section presents two algorithms. For both algorithms, the time complexity of one intersection is $O(n^2)$ for an XOR linear basis or $O(n^3)$ for a real linear basis.

Naive Algorithm

Let the two linear bases to be intersected be $\alpha$ and $\beta$. The intersection algorithm only needs the following adjustments to the brute-force linear-basis merge algorithm (using an XOR linear basis as an example):

• Using the linear basis $\beta$, try to insert its vector $\beta_j$ into $\alpha$ using the greedy method, and initialize the intersection basis $\gamma$ as the empty set;
• During insertion, record the contribution of elements from the linear basis $\beta$ to the vector being inserted. Specifically, maintain a new vector $b$, initialized to $\beta_j$; if the vector being inserted is XORed with the vector at position $x$ in the linear basis, XOR the contribution $b$ with the contribution recorded at position $x$, namely $b_x$;
• If insertion succeeds and at position $x$ the vector $\beta_j'$ is inserted, set the recorded value at position $x$, namely $b_x$, to the contribution that produced $\beta_j'$ from elements of $\beta$, namely $b$;
• If insertion fails, insert the contribution of the elements of $\beta$, recorded as $b$, into $\gamma$.

The resulting linear basis $\gamma$ is the desired intersection; the algorithm also computes the union of the two linear bases.

The template-problem code is as follows:

#include <array>
#include <iostream>

class LinearBasis {
  static constexpr int K = 30;
  std::array<int, K> a;

  // Size of basis.
  int size() const {
    int res = 0;
    for (auto x : a) {
      if (x) {
        ++res;
      }
    }
    return res;
  }

 public:
  LinearBasis() : a{} {}

  // Insert vector x.
  void insert(int x) {
    for (int k = K - 1; ~k && x; --k) {
      if ((x >> k) & 1) {
        if (!a[k]) {
          a[k] = x;
        }
        x ^= a[k];
      }
    }
  }

  // Return a basis for *THIS intersecting RHS.
  LinearBasis intersect(const LinearBasis& rhs) const {
    LinearBasis res;
    std::array<int, K> c = a, b_parts = {};
    for (int i = K - 1; ~i; --i) {
      int x = rhs.a[i], b_part = x;
      for (int k = i; ~k && x; --k) {
        if ((x >> k) & 1) {
          if (!c[k]) {
            c[k] = x;
            b_parts[k] = b_part;
          }
          x ^= c[k];
          b_part ^= b_parts[k];
        }
      }
      res.insert(b_part);
    }
    return res;
  }

  // Output.
  void print() const {
    std::cout << size();
    for (auto x : a) {
      if (x) {
        std::cout << ' ' << x;
      }
    }
    std::cout << '\n';
  }
};

int main() {
  int t;
  std::cin >> t;
  for (; t; --t) {
    LinearBasis a, b;
    int n;
    std::cin >> n;
    for (; n; --n) {
      int x;
      std::cin >> x;
      a.insert(x);
    }
    int m;
    std::cin >> m;
    for (; m; --m) {
      int x;
      std::cin >> x;
      b.insert(x);
    }
    a.intersect(b).print();
  }
  return 0;
}

Zassenhaus Algorithm

Another equivalent approach is the Zassenhaus algorithm, which can also compute the union and intersection of two linear bases simultaneously. Its complexity is exactly the same as above.

The steps are as follows:

• Initialize an empty linear basis of vector length $2n$, denoted $\gamma$, whose vectors have the form $(a,b)$ with both $a$ and $b$ of length $n$;
• From $\alpha$, insert each element $\alpha_i$ in the form $(\alpha_i,\alpha_i)$ into $\gamma$;
• From $\beta$, insert each element $\beta_j$ in the form $(\beta_j,0)$ into $\gamma$;
• In the final linear basis $\gamma$, among all nonzero elements $(c_k,d_k)$, the $c_k$ components of those with nonzero $c_k$ form a linear basis of the union of $\alpha$ and $\beta$, while, for those with zero $c_k$, the components $d_k$ form a linear basis of the intersection of $\alpha$ and $\beta$.

The method used to construct the linear basis can be the greedy method or Gaussian elimination, as long as the linear basis in $\gamma$ forms a row-echelon matrix.

Comparing the elimination steps in the Zassenhaus algorithm with those in the preceding naive algorithm, it is easy to see that the greedy Zassenhaus algorithm is equivalent to the naive algorithm that maintains the contributions of elements in $\alpha$. If we instead insert all $(\alpha_i,0)$ first and then all $(\beta_j,\beta_j)$, the greedy Zassenhaus algorithm is equivalent to the naive algorithm that maintains the contributions of elements in $\beta$. By the equivalence of the elimination steps, the Zassenhaus algorithm is also correct.

In addition, an independent and more general algebraic proof can be given:

The template-problem code is as follows:

#include <iostream>
#include <vector>

class LinearBasis {
  int K;
  std::vector<long long> a;

 public:
  LinearBasis(int K) : K(K), a(K) {}

  // Insert vector x.
  void insert(long long x) {
    for (int k = K - 1; ~k && x; --k) {
      if ((x >> k) & 1) {
        if (!a[k]) {
          a[k] = x;
        }
        x ^= a[k];
      }
    }
  }

  // Output those not exceeding 2^k.
  void print(int k) const {
    int sz = 0;
    for (int i = 0; i < k; ++i) {
      if (a[i]) {
        ++sz;
      }
    }
    std::cout << sz;
    for (int i = 0; i < k; ++i) {
      if (a[i]) {
        std::cout << ' ' << a[i];
      }
    }
    std::cout << '\n';
  }
};

int main() {
  constexpr int K = 30;
  int t;
  std::cin >> t;
  for (; t; --t) {
    LinearBasis c(K << 1);
    int n;
    std::cin >> n;
    for (; n; --n) {
      int x;
      std::cin >> x;
      c.insert(((long long)x << K) | x);
    }
    int m;
    std::cin >> m;
    for (; m; --m) {
      int x;
      std::cin >> x;
      c.insert((long long)x << K);
    }
    c.print(K);
  }
  return 0;
}

Note that when outputting, we only need to consider vectors whose first $n$ bits are all zero.

Extension: Prefix Linear Basis

This section discusses only XOR linear bases and assumes that a single vector can be stored in $O(1)$ space and that each individual operation always has $O(1)$ complexity.

For repeated queries of the maximum XOR on intervals, a common approach is to combine a cat tree with a linear basis, with time complexity $O(nm\log m+n^2q)$, where $n$ is the vector length, $m$ is the sequence length, and $q$ is the number of queries. Another feasible approach uses a prefix linear basis (also called a timestamp linear basis), reducing the complexity to $O(n(m+q))$.

A prefix linear basis maintains, for every prefix of a sequence, the linear bases of all suffixes of that prefix, thereby supporting queries for the linear basis of every interval. Observe that for a prefix $[1,i]$, the linear bases of all its suffixes $[j,i]$ are nested: the linear basis of $[j,i]$ always contains that of $[j+1,i]$. Thus, there are at most $n$ distinct linear bases among these suffixes, and they can always be obtained by gradually adding new vectors to the empty set, from the suffix $[i,i]$ through all suffixes up to $[1,i]$. By this monotonicity, it is enough to mark each added vector $v$ with the largest index $t$ at which it appears. Then all suffix linear bases can be stored in $O(n)$ space. When querying the linear basis of interval $[j,i]$, we only need to retain, in the prefix linear basis at $i$, the vectors whose marks satisfy $t\ge j$.

For each vector $v$, call its mark $t$ its timestamp. A vector $v$ in the linear basis can always be represented as the XOR sum of some elements of the original sequence, for example $v_{i_1}\oplus v_{i_2}\oplus\cdots\oplus v_{i_k}$. Among all such possible representations, the maximum of the minimum indices is $t$, namely

This expression merely writes the description in the preceding paragraph in formal language. It suggests that, to maintain the timestamp of each vector $v$ in the linear basis, we only need to greedily replace old vectors with the newest possible vectors.

When constructing a linear basis using the greedy method described above, the prefix linear basis makes the following adjustments during construction:

• For every vector $a_x$ retained in the linear basis, store a timestamp $t_x$, initially setting all of them to $0$;
• To add the $i$-th vector $v$ in the sequence, still scan from the highest bit to the lowest, but also record the current time $i$;
• If $v$ has bit $x$ set, compare the timestamp of the existing vector $a_x$ in the linear basis, $t_x$, with the current time $i$:
  • If $i>t_x$, that is, the vector being added is newer, set $a_x$ to $v$, update its timestamp to $i$, and continue the insertion using the old $a_x$ XORed with $v$, namely $a_x\oplus v$, with the old recorded time $t_x$;
  • If $i<t_x$, that is, the vector being added is older, do not update $a_x$ or $t_x$; continue the insertion after XORing $v$ with $a_x$.

In other words, if the current bit can be represented by a newer vector, use the newer vector directly; otherwise retain the original vector. When updating the vector at position $x$, do not store the XOR result $a_x\oplus v$ at position $x$, because the timestamp of $a_x\oplus v$ is $\min\{t(a_x)=t(v)\}=t(a_x)$, which is smaller than the timestamp of the added vector $v$, namely $t(v)$. For the same reason, upward updates during construction by Gaussian elimination may break the timestamp property, so Gaussian elimination is no longer suitable for constructing a prefix linear basis.

The template-problem code is as follows:

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <vector>

class LinearBasis {
  static constexpr int K = 20;
  std::array<int, K> a, t;

 public:
  LinearBasis() : a{}, t{} {}

  // Insert vector x at time i.
  void insert(int x, int i) {
    for (int k = K - 1; ~k && x; --k) {
      if (((x >> k) & 1)) {
        if (i > t[k]) {
          std::swap(a[k], x);
          std::swap(t[k], i);
        }
        x ^= a[k];
      }
    }
  }

  // Find max xor of subsets of elements from time i till now.
  int query(int i) const {
    int res = 0;
    for (int k = K - 1; ~k; --k) {
      if (t[k] >= i && (res ^ a[k]) > res) {
        res ^= a[k];
      }
    }
    return res;
  }
};

int main() {
  int n;
  std::cin >> n;
  std::vector<int> c(n + 1);
  for (int i = 1; i <= n; ++i) std::cin >> c[i];
  int q;
  std::cin >> q;
  std::vector<std::array<int, 2>> qu(q);
  for (auto& v : qu) std::cin >> v[0] >> v[1];
  std::vector<int> ids(q);
  std::iota(ids.begin(), ids.end(), 0);
  std::sort(ids.begin(), ids.end(),
            [&](int l, int r) -> bool { return qu[l][1] < qu[r][1]; });
  LinearBasis lb;
  std::vector<int> res(q);
  for (int i = 1, j = 0; i <= n; ++i) {
    lb.insert(c[i], i);
    for (; j < q && qu[ids[j]][1] == i; ++j) {
      res[ids[j]] = lb.query(qu[ids[j]][0]);
    }
  }
  for (int x : res) std::cout << x << '\n';
  return 0;
}

If online queries are required, we can store the prefix linear basis at every prefix using $O(mn)$ space and then answer queries; this can be viewed as a persistent linear basis. If we need properties of the linear basis obtained by Gaussian elimination, they can be handled separately during queries.

Exercises

• Luogu P3812 (Template) Linear Basis
• Acwing 3164. Linear Basis
• SGU 275 to xor or not xor
• HDU 3949 XOR
• HDU 6579 Operation
• Luogu P4151 [WC2011] Maximum XOR-Sum Path
• Library Checker - Intersection of $\mathbf F_2$ vector spaces
• AtCoder Grand Contest 045 A - Xor Battle
• Codeforces 1100F Ivan and Burgers
• Luogu P3292 [SCOI2016] Lucky Number

References and Notes

1. Qiu Weisheng, Advanced Algebra (Volume II). Tsinghua University Press.
2. Basis (linear algebra) - Wikipedia
3. Vector Basis -- from Wolfram MathWorld
4. Zassenhaus algorithm - Wikipedia