Determinant

$\det A={\sum }_{\sigma \in S_n}\mathrm{sgn}(\sigma ){\prod }_i{A}_{i,\sigma (i)}.$

The definition has $n!$ terms; Gaussian elimination computes it in $O(n^3)$.

Computing it

long long determinant(vector<vector<long long>> a, long long MOD) {
    int n = a.size();
    long long det = 1;
    for (int i = 0; i < n; i++) {
        int piv = -1;
        for (int r = i; r < n; r++) if (a[r][i]) { piv = r; break; }
        if (piv < 0) return 0;                            // singular
        if (piv != i) { swap(a[piv], a[i]); det = MOD - det; }   // row swap flips the sign
        det = det * a[i][i] % MOD;
        long long inv = powmod(a[i][i], MOD - 2, MOD);
        for (int r = i + 1; r < n; r++) {
            long long f = a[r][i] * inv % MOD;
            if (!f) continue;
            for (int c = i; c < n; c++)
                a[r][c] = (a[r][c] - f * a[i][c] % MOD + MOD) % MOD;
        }
    }
    return det;
}

Row operations and the determinant:

Operation	Effect on $\det$
Swap two rows	multiply by $-1$
Multiply a row by $c$	multiply by $c$
Add a multiple of one row to another	unchanged

Only the first two need tracking, which is why elimination works.

Properties

Property
$\det (AB)=\det A\det B$
$\det (A^T)=\det A$
$\det (A^{-1})=1/\det A$
$\det (cA)=c^n\det A$
$\det =0$ iff $A$ is singular	iff the rows are linearly dependent
$\det$ of a triangular matrix	product of the diagonal
$\det$ = product of eigenvalues
$\det$ of a block-triangular matrix	product of the blocks’ determinants

Over which ring?

Setting	Method
Modulo a prime	Gaussian elimination with inverses, $O(n^3)$
Modulo a composite	Euclidean row reduction (repeated subtraction, like gcd) — no inverses needed, $O(n^3\log )$
Exact integers	Bareiss — fraction-free, no coefficient blowup
Exact, huge	compute modulo several primes + CRT, with the Hadamard bound to know when to stop
Floating point	LU decomposition with partial pivoting
Sparse	Wiedemann, $O(n\cdot \mathrm{nnz})$

Composite modulus without inverses

for (int r = i + 1; r < n; r++)
    while (a[r][i]) {                            // Euclidean-style
        long long t = a[i][i] / a[r][i];
        for (int c = i; c < n; c++)
            a[i][c] = (a[i][c] - t * a[r][c] % MOD + MOD) % MOD;
        swap(a[i], a[r]); det = MOD - det;
    }

$O(n^3\log (\text{MOD}))$ — the standard trick when the modulus is not prime.

Hadamard’s bound

$|\det A|\le {\prod }_i\Vert {\text{row}}_i{\Vert }_2\le n^{n/2}{M}^n$ for entries bounded by $M$. Tells you how many CRT primes are needed for an exact answer.

Where determinants appear

Problem	Determinant
Count spanning trees	Matrix-Tree theorem — a Laplacian cofactor
Count Eulerian circuits	BEST theorem (an arborescence count × factorials)
Perfect matching exists (general graph)	Tutte matrix rank
Count perfect matchings in a planar graph	FKT algorithm — a Pfaffian, hence a determinant
Count perfect matchings in a bipartite graph	the permanent — p-hard, no determinant shortcut
Lattice point counting / volume	determinant of the basis
Orientation test	a $2\times 2$ or $3\times 3$ determinant
Circle through three points	a $4\times 4$ determinant
Solving $Ax=b$	Cramer’s rule ($O(n^4)$ — use elimination instead)
Lindström-Gessel-Viennot	count non-intersecting lattice paths

Lindström-Gessel-Viennot is worth flagging: the number of families of non-intersecting paths between two sets of endpoints is a determinant of the pairwise path counts. It turns several hard-looking counting problems into an $O(n^3)$ computation.

Permanent — the hard cousin

$\mathrm{perm}(A)={\sum }_{\sigma }{\prod }_i{A}_{i,\sigma (i)}$
— the determinant without signs. Computing it is #P-complete, and the signs are exactly what makes the determinant easy. Best known: Ryser’s formula, $O(2^{n}n)$, which is bitmask DP in disguise.

See also: Gaussian Elimination · Rank · Matrix-Tree Theorem