Linear Algebra

"Matrix operations, Gaussian elimination, determinant, rank, eigenvalues, linear transformations."

Deep Dive Tutorial

Matrix exponentiation is a single powerful trick: if a system's next state is a linear function of its current state, you can represent that function as a matrix and compute the nth state in O(k³ log n) instead of O(kn). This unlocks Fibonacci in log n, counts paths of length n in a graph, and accelerates any DP with a fixed transition.

Core Idea — State × Transition Matrix

key

Pattern recognition:
- "Find f(n) where f(n) = a·f(n-1) + b·f(n-2) + ..." → matrix exponentiation
- "Count paths of length exactly k in a graph" → raise adjacency matrix to kth power
- "DP transition is the same at every step" → encode in a matrix

Key formula: If state_n = M × state_{n-1}, then state_n = M^n × state_0

Matrix multiply + fast power — O(k³ log n)

const MOD = 1_000_000_007n;

function matMul(A, B) {
    const n = A.length, m = B[0].length, k = B.length;
    const C = Array.from({length: n}, () => new Array(m).fill(0n));
    for (let i = 0; i < n; i++)
        for (let j = 0; j < m; j++)
            for (let p = 0; p < k; p++)
                C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD;
    return C;
}

function matPow(M, n) {
    let result = M.map((r, i) => r.map((_, j) => i === j ? 1n : 0n)); // identity
    while (n > 0n) {
        if (n & 1n) result = matMul(result, M);
        M = matMul(M, M);
        n >>= 1n;
    }
    return result;
}

// Fibonacci in O(log n)
// [F(n+1)]   [1 1]^n   [1]
// [F(n)  ] = [1 0]   × [0]
function fibonacci(n) {
    if (n <= 1) return n;
    const M = [[1n, 1n], [1n, 0n]];
    const R = matPow(M, BigInt(n - 1));
    return R[0][0]; // F(n)
}

Building the Transition Matrix

lightbulb

Recipe for any linear recurrence f(n) = c1·f(n-1) + c2·f(n-2) + ... + ck·f(n-k):

State vector: [f(n), f(n-1), ..., f(n-k+1)]

Transition matrix (k×k):
``


[c1  c2  c3 ... ck ]
[1   0   0  ... 0  ]
[0   1   0  ... 0  ]
...                 
[0   0  ... 1   0  ]

``

For "count paths of length n in graph": raise adjacency matrix to nth power. Entry [i][j] = number of paths from i to j of length n.

Count paths of length exactly k in a graph

// adj[i][j] = 1 if edge exists
// After matPow(adj, k): result[i][j] = paths from i to j of length k
function countPaths(n, edges, k, src, dst) {
    const adj = Array.from({length: n}, () => new Array(n).fill(0n));
    for (const [u, v] of edges) {
        adj[u][v] = 1n;
        adj[v][u] = 1n; // undirected
    }
    const R = matPow(adj, BigInt(k));
    return R[src][dst];
}

Gaussian Elimination

lightbulb

Gaussian elimination solves Ax = b or finds matrix rank. Over GF(2) (bits), it solves systems of XOR equations — used for XOR basis / linear independence problems.

Time: O(n² × cols/64) with bitset optimization.

XOR basis — linear independence over GF(2)

// Insert numbers into XOR basis
// Basis can represent any XOR of inserted numbers
function buildXorBasis(nums) {
    const basis = new Array(30).fill(0);
    for (const x of nums) {
        let cur = x;
        for (let i = 29; i >= 0; i--) {
            if (!(cur >> i & 1)) continue;
            if (!basis[i]) { basis[i] = cur; break; }
            cur ^= basis[i];
        }
    }
    return basis;
}

// Max XOR of any subset
function maxXor(nums) {
    const basis = buildXorBasis(nums);
    let res = 0;
    for (let i = 29; i >= 0; i--)
        res = Math.max(res, res ^ basis[i]);
    return res;
}

// Check if x can be formed by XOR of subset
function canForm(basis, x) {
    for (let i = 29; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!basis[i]) return false;
        x ^= basis[i];
    }
    return x === 0;
}