Matrices

Basics

$(AB{)}_{ij}={\sum }_k{A}_{ik}{B}_{kj}$. Defined when $A$ is $n\times m$ and $B$ is $m\times p$; the result is $n\times p$.

• Associative but not commutative: $AB\ne BA$ in general.
• Identity $I$ with $I_{ii}=1$.
• $(AB{)}^T=B^T{A}^T$, $(AB{)}^{-1}=B^{-1}{A}^{-1}$.

Fast multiplication in practice

using Mat = vector<vector<long long>>;
const long long MOD = 1e9 + 7;
 
Mat mul(const Mat& a, const Mat& b) {
    int n = a.size(), m = b[0].size(), K = b.size();
    Mat c(n, vector<long long>(m, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < K; k++) {
            if (!a[i][k]) continue;                    // skip zeros
            long long aik = a[i][k];
            for (int j = 0; j < m; j++)
                c[i][j] = (c[i][j] + aik * b[k][j]) % MOD;
        }
    return c;
}

The $i,k,j$ loop order is the important detail: the inner loop then walks b[k] and c[i] sequentially, so both are cache-friendly. The naive $i,j,k$ order strides down a column of b and is 3-5× slower.

Further speedups: delay the modulo (accumulate in __int128 or use unsigned long long and reduce every 18 additions), and flatten to a 1D array.

Matrix exponentiation

$A^n$ in $O(k^3\log n)$ by binary exponentiation. This is how linear recurrences, walk counting, and Markov chains get from $n$ to $10^{18}$. See Matrix Exponentiation and Matrix Exponentiation on DP.

Semirings — the underrated generalisation

Matrix multiplication works over any semiring (an addition-like and a multiplication-like operation, with distributivity). Replacing $(+,\times )$ changes what the product computes:

Semiring	$A_{ij}^n$ computes
$(+,\times )$	number of walks of length $n$ from $i$ to $j$
$(\min ,+)$	shortest path using exactly $n$ edges
$(\max ,+)$	longest path with exactly $n$ edges
$(\text{OR},\text{AND})$	reachability in exactly $n$ steps
$(\max ,\min )$	bottleneck (widest) path
$(\text{XOR},\text{AND})$	parity of walk counts

// min-plus: shortest path with exactly n edges
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);

The min-plus version with binary exponentiation solves “cheapest route using exactly $k$ flights” for $k$ up to $10^9$ in $O(V^3\log k)$ — a problem with no other reasonable approach.

Fast matrix multiplication

Algorithm	Exponent
Schoolbook	$n^3$
Strassen	$n^{2.807}$
Coppersmith-Winograd and successors	$n^{2.371}$
Lower bound	$n^2$

Strassen computes a $2\times 2$ block product with 7 multiplications instead of 8 — the same “trade multiplications for additions” idea as Karatsuba. It becomes worthwhile around $n\ge 500$ and is numerically less stable. The sub-2.8 algorithms are galactic.

For boolean matrices, a bitset gives $O(n^3/64)$ with a tiny constant — better than Strassen for every practical size. See Bitset Optimization.

What matrices compute

Task	Method	Cost
Solve $Ax=b$	Gaussian elimination	$O(n^3)$
Determinant	Gaussian elimination	$O(n^3)$
Exact integer determinant	Bareiss	$O(n^3)$
Rank	row reduce, count pivots	$O(n^3)$
Inverse	Gauss-Jordan on $[A\mid I]$	$O(n^3)$
Characteristic polynomial	Faddeev-LeVerrier or Hessenberg	$O(n^4)$ / $O(n^3)$
$A^n$	binary exponentiation	$O(n^3\log k)$
Sparse system	Wiedemann / Lanczos	$O(n\cdot \mathrm{nnz})$
Count spanning trees	Matrix-Tree	$O(n^3)$
Perfect matching exists	Tutte matrix + rank	$O(n^3)$ randomized

Working modulo a prime

Everything above works over ${\mathbb{F}}_p$: replace division by multiplication with the modular inverse. Over a composite modulus, division may be impossible — use a Euclidean-style row reduction (repeatedly subtract multiples, as in the gcd algorithm) instead of pivoting by inverses.

See also: Matrix Exponentiation · Determinant · Gaussian Elimination