Rank and Linear Systems

The rank of a matrix is the number of linearly independent rows (equivalently, columns). Computed by row reduction in $O(n^{2}m)$.

Computing the rank

int rank(vector<vector<long long>> a, long long MOD) {
    int n = a.size(), m = a[0].size(), rk = 0;
    for (int col = 0; col < m && rk < n; col++) {
        int piv = -1;
        for (int r = rk; r < n; r++) if (a[r][col]) { piv = r; break; }
        if (piv < 0) continue;                            // free column
        swap(a[rk], a[piv]);
        long long inv = powmod(a[rk][col], MOD - 2, MOD);
        for (int c = col; c < m; c++) a[rk][c] = a[rk][c] * inv % MOD;
        for (int r = 0; r < n; r++) {
            if (r == rk || !a[r][col]) continue;
            long long f = a[r][col];
            for (int c = col; c < m; c++)
                a[r][c] = (a[r][c] - f * a[rk][c] % MOD + MOD) % MOD;
        }
        rk++;
    }
    return rk;
}

Solving $Ax=b$ — the three cases

Row-reduce the augmented matrix $[A\mid b]$. Then:

Condition	Solutions
$\mathrm{rank}(A)<\mathrm{rank}([A\mid b])$	none (an inconsistent row $0=c$ with $c\ne 0$)
$\mathrm{rank}(A)=\mathrm{rank}([A\mid b])=m$ (number of unknowns)	unique
$\mathrm{rank}(A)=\mathrm{rank}([A\mid b])<m$	infinitely many — $m-\mathrm{rank}$ free variables

Over ${\mathbb{F}}_p$ the third case gives exactly $p^{m-\mathrm{rank}}$ solutions — a count, not “infinitely many”. That count is what most contest problems actually ask for.

Over ${\mathbb{F}}_2$ — the common case

XOR systems are ${\mathbb{F}}_2$ linear systems, and the whole computation becomes bitwise:

int rankF2(vector<uint64_t> a) {                  // each row is a bitmask
    int n = a.size(), rk = 0;
    for (int col = 63; col >= 0 && rk < n; col--) {
        int piv = -1;
        for (int r = rk; r < n; r++) if (a[r] >> col & 1) { piv = r; break; }
        if (piv < 0) continue;
        swap(a[rk], a[piv]);
        for (int r = 0; r < n; r++)
            if (r != rk && (a[r] >> col & 1)) a[r] ^= a[rk];
        rk++;
    }
    return rk;
}

$O(n^2)$ with 64-bit rows, or $O(n^{2}m/64)$ with bitset rows for wider systems. This is the XOR basis construction, viewed as Gaussian elimination.

Where rank answers the question

Problem	Rank interpretation
Number of distinct subset XORs	$2^{\mathrm{rank}}$
Number of subsets with a given XOR	$2^{n-\mathrm{rank}}$ (or 0)
Solve a system of XOR equations (light switches, Lights Out)	${\mathbb{F}}_2$ elimination
Does a perfect matching exist?	rank of the Tutte matrix $=n$
Maximum matching size	half the Tutte matrix rank
Dimension of a vector space	rank of a spanning set
Number of independent constraints	rank
Linear independence of vectors	rank $=$ count
Count solutions of a modular linear system	$p^{m-\mathrm{rank}}$
Minimum generators of a group $({\mathbb{Z}}_2{)}^k$	rank

The Lights Out pattern

A grid of lights; pressing one toggles it and its neighbours; make everything off. Each cell is an ${\mathbb{F}}_2$ variable, each light gives one equation. Solve with ${\mathbb{F}}_2$ Gaussian elimination:

• rank $=n$ → unique solution;
• rank $<n$ → $2^{n-\mathrm{rank}}$ solutions; enumerate the free variables to find the one with the fewest presses;
• inconsistent → impossible.

This models a large family of “toggle” puzzles.

Numerical rank

Over the reals, “is this entry zero” is meaningless in floating point. Use the singular value decomposition and count singular values above a tolerance. In competitive programming, work over ${\mathbb{F}}_p$ instead — exact and unambiguous.

Sparse systems

For huge sparse matrices, elimination causes fill-in and destroys sparsity. Use Wiedemann or Lanczos, which only ever compute matrix-vector products: $O(n\cdot \mathrm{nnz})$ time, $O(n)$ space.

See also: Gaussian Elimination · Linear Basis · Determinant