Prerequisites: Basic vector and matrix operations.

Elementary Row Operations and Reduced Form

There are three types of elementary row operations:

1. Scaling: Multip a row by a scalar $k$
2. Addition: Add $k$ times one row to another row
3. Swapping: Exchange two rows

Each operation corresponds to multiplying the original matrix by an elementary matrix.

Reduced form matrix: A matrix where a unit matrix appears in the upper-left corner and all other entries are zero.

Using these operations, any matrix can be transformed into its reduced form.

The process involves first making the first element of the first row equal to 1 through scaling; if impossible, swap rows. Then, use addition operations to eliminate all elements below the leading 1 in the first column. Repeat this procedure for the remaining submatrix.

Time complexity is $O(n^3)$ due to $n$ iterations over rows, each requiring $O(n)$ operations.

Gaussian Elimination

To solve a system of linear equations represented by an $n \times n$ matrix augmented with constants, we extend the coefficient matrix with an additional column for constants. Then, perform similar transformations as in reduced form calculation, applying operations to both coefficient and constant parts.

After transformation, the left side forms a triangular matrix with leading 1s, and the right side contains the solution values. If a row lacks a leading 1, check its constant term: if it's zero, there are infinitely many solutions; otherwise, no solution exists.

With minor modifications, this approach also solves XOR equation systems. The principal remains the same, but bitset optimizations reduce time complexity to $O(\frac{n^3}{\omega})$. An example problem is "Alien Centipede".

Matrix Inversion

For a matrix $A$, if there exists a matrix $B$ such that $AB = I$, then $B$ is called the inverse of $A$, denoted as $B = A^{-1}$.

As discussed earlier, elementary operations correspond to multiplication by elementary matrices. Assuming invertibility, the final result will be the identity matrix $I$.

Let ${X_i}$ denote the sequence of elementary matrices used during transformation. Then, $A\prod X_i = AA^{-1} = I$. By associativity, $\prod X_i = A^{-1}$. Typically, we augment the original matrix with an identity matrix and apply identical operations to both. When the original becomes identity, the augmented part becomes the inverse.

Linear Basis

• Linear dependence: A set of vectors $v_i$ is linearly dependent if there exist scalars $a_i$, not all zero, such that $\sum a_iv_i = 0$.
• Linear basis (basis): A maximal linearly independent subset from a vector set.
• Vector space: The set of all vectors that can be formed using the basis.

Property: If a set of $k$-dimensional vectors has a basis of size $k$, they span the entire $k$-dimensional space.

XOR Space Linear Basis

Given a set of binary numbers of length $w$, determine which values can be generated via XOR combinations?

This represents a vector set within a $w$-dimensional XOR space. As per previous property, $w$ numbers suffice to form a basis.

We can compute the basis using Gaussian elimination. Those familiar with solving XOR systems should recognize the similarity.

for(int i=1;i<=n;i++)
{
    if(!a[i][i])
    {
        int t=m+1;
        for(int j=i+1;j<=m;j++)if(a[j][i] && id[j]<id[t])t=j;
        if(t>m)return printf("Cannot Determine\n"),0;
        swap(a[t],a[i]);
        swap(id[t],id[i]);
    }
    ans=max(ans,id[i]);
    for(int j=1;j<=m;j++)if(j!=i && a[j][i])a[j]^=a[i];
}

Modify the process so that for each number, if the current bit is set, check if there's already a base at that position. If yes, XOR the number with the base and proceed. This mirrors the standard elimination algorithm.

#include<cstdio>
#define ll long long
using namespace std;
int n;
ll d[55];
int main()
{
    ll x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        for(int i=49;i>=0;i--)
            if(x&(1LL<<i))
            {
                if(!d[i]){d[i]=x;break;}
                x^=d[i];
            }
    }
    x=0;
    for(int i=49;i>=0;i--)if(d[i] && !(x&(1LL<<i)))x^=d[i];
    printf("%lld\n",x);
}

The complexity is $O(n \log V)$, where $V$ is the value range.

To query maximum value, inspect whether the current bit has a base and if XOR increases the result. Minimum value equals the smallest base. For the $k$-th largest value, perform Gaussian elimination to insure each base has exactly one bit set. Then, decide whether to include the $i$-th base based on the $i$-th bit of $k$.

Merging two linear bases requires inserting all elements of one into the other. Complexity is $O(\log^2 n)$.