iii. Determinants and Permanents

$\det A={\sum }_{\sigma \in S_n}\mathrm{sgn}(\sigma ){\prod }_i{A}_{i\sigma (i)},\mathrm{per}A={\sum }_{\sigma \in S_n}{\prod }_i{A}_{i\sigma (i)}.$
The definition has $n!$ terms; elimination computes the determinant in $O(n^3)$ because row operations change it predictably. The permanent drops the signs and becomes p-hard; the best general method is Ryser’s $O(2^{n}n)$. mint from Modular Arithmetic.

Row operation	Effect on $\det$
swap two rows	$\times (-1)$
multiply a row by $c$	$\times c$
add a multiple of one row to another	unchanged

Property
$\det (AB)=\det A\det B$; $\det A^{-1}=1/\det A$	multiplicative
$\det A^T=\det A$; $\det (cA)=c^n\det A$
$\det A=0$ iff the rows are linearly dependent (singular)
triangular or block-triangular	product of the diagonal entries / block determinants
$\det A=\prod {\lambda }_i$ (eigenvalues with multiplicity)	constant term of the characteristic polynomial
Hadamard: $|\det A|\le {\prod }_i\Vert {\mathrm{row}}_i{\Vert }_2\le n^{n/2}{M}^n$ for $|a_{ij}|\le M$	number of CRT primes for an exact answer

Setting	Method	Cost
modulo a prime	elimination with inverses	$O(n^3)$
modulo a composite (no inverses)	Euclid-style row reduction	$O(n^3+n^2\log m)$
exact integers	Bareiss (fraction-free) or several primes + CRT with the Hadamard bound	$O(n^3)$ operations on $O(n\log (nM))$-bit numbers
floating point	LU with partial pivoting	$O(n^3)$
sparse	Wiedemann (Sparse Matrices)	$O(n\cdot \mathrm{nnz})$

Where determinants appear
spanning trees	Matrix-Tree theorem: a Laplacian cofactor (Matrix-Tree Theorem)
Eulerian circuits	BEST theorem: arborescences $\times \prod (\mathrm{deg}-1)!$
perfect matching exists (general graph)	Tutte matrix rank (random)
perfect matchings of a planar graph	FKT: a Pfaffian, ${\mathrm{Pf}}^2=\det$
perfect matchings of a bipartite graph	the permanent (#P-hard); parity = $\det \mathrm{mod}2$
non-intersecting lattice paths	Lindström–Gessel–Viennot: a determinant of path counts
lattice volume, orientation, in-circle tests	small determinants (Geometry Primitives)
$Ax=b$	Cramer’s rule $x_i=\det A_i/\det A$: $O(n^4)$, use elimination instead

mint detMod(vector<vector<mint>> a) {                       // prime modulus, O(n^3)
    int n = sz(a); mint det = 1;
    for (int i = 0; i < n; i++) {
        int piv = -1; for (int r = i; r < n; r++) if (a[r][i] != mint(0)) { piv = r; break; }
        if (piv < 0) return 0;
        if (piv != i) swap(a[piv], a[i]), det = -det;
        det *= a[i][i]; mint inv = a[i][i].inv();
        for (int r = i + 1; r < n; r++) { mint f = a[r][i] * inv; if (f == mint(0)) continue; for (int c = i; c < n; c++) a[r][c] -= f * a[i][c]; }
    }
    return det;
}
 
ll detComposite(vector<vector<ll>> a, ll m) {              // any modulus m >= 1, entries in [0, m)
    int n = sz(a); ll det = 1 % m;
    auto mulm = [&](ll x, ll y) { return (ll)((__int128)x * y % m); };
    for (int i = 0; i < n; i++) {
        for (int r = i + 1; r < n; r++)
            while (a[r][i]) {                               // Euclid on column i: a[i][i] <- a[i][i] mod a[r][i], then swap
                ll t = a[i][i] / a[r][i];
                for (int c = i; c < n; c++) a[i][c] = ((a[i][c] - mulm(t, a[r][c])) % m + m) % m;
                swap(a[i], a[r]); det = (m - det) % m;
            }
        det = mulm(det, a[i][i]);
        if (!det) return 0;
    }
    return det;
}
 
i128 bareiss(vector<vector<i128>> a) {                       // exact integer determinant; intermediates are minors and products of two minors must fit in i128
    int n = sz(a); if (n == 0) return 1;
    i128 prev = 1; int sign = 1;
    for (int k = 0; k < n - 1; k++) {
        if (a[k][k] == 0) {
            int p = -1; for (int r = k + 1; r < n; r++) if (a[r][k] != 0) { p = r; break; }
            if (p < 0) return 0;
            swap(a[k], a[p]); sign = -sign;
        }
        for (int i = k + 1; i < n; i++) for (int j = k + 1; j < n; j++) a[i][j] = (a[i][j] * a[k][k] - a[i][k] * a[k][j]) / prev;   // exact
        prev = a[k][k];
    }
    return sign * a[n - 1][n - 1];
}
 
mint lgvGrid(const vector<pair<int, int>>& src, const vector<pair<int, int>>& dst, const Comb& cb) {   // vertex-disjoint up/right path systems src[i] -> dst[i]
    int k = sz(src); vector<vector<mint>> M(k, vector<mint>(k));
    for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) {
        int dx = dst[j].first - src[i].first, dy = dst[j].second - src[i].second;
        M[i][j] = dx < 0 || dy < 0 ? mint(0) : cb.C(dx + dy, dx);
    }
    return detMod(M);
}

Lindström–Gessel–Viennot. In a DAG, with sources $a_1..a_k$ and sinks $b_1..b_k$, $\det [e(a_i\to b_j)]$ (path counts) is the signed sum over vertex-disjoint path systems $a_i\to b_{\sigma (i)}$ of $\mathrm{sgn}\sigma$. When every disjoint system must use the identity (e.g. sources and sinks in “compatible” order on the boundary of a planar grid), the determinant counts the non-intersecting systems directly: several hard-looking counting problems become one $O(k^3)$ determinant.

Proof: elimination, multiplicativity, Hadamard, composite moduli, Bareiss, LGV

Row operations. $\det$ is multilinear and alternating in the rows (Leibniz formula): swapping two rows composes every $\sigma$ with a transposition (sign flip); scaling a row scales every term; adding $c$ times row $j$ to row $i$ adds $c\det$(matrix with two equal rows) $=0$. Elimination reaches an upper-triangular matrix, whose only non-zero Leibniz term is the diagonal. Multiplicativity: for fixed $A$, the rows of $AB$ are ${\sum }_k{A}_{ik}{\mathrm{row}}_k(B)$, so $B\mapsto \det (AB)$ is multilinear and alternating in the rows of $B$, hence equals $\det (AB)=c\det B$ with $c=\det (AI)=\det A$. Transpose: $\sigma \mapsto {\sigma }^{-1}$ preserves the sign. Singular: elimination produces a zero row iff the rows are dependent. Block triangular: a permutation with a non-zero term must map the first block of indices into itself. Hadamard: Gram–Schmidt writes $A=LQ$ with $L$ unit lower triangular and $Q$ with orthogonal rows $q_i$, $\Vert q_i\Vert \le \Vert {\mathrm{row}}_i\Vert$; $|\det A|=\prod \Vert q_i\Vert$.

Composite modulus. The inner loop is the Euclidean algorithm on the pair $(a_{ii},a_{ri})$ using only “subtract a multiple of a row” (determinant unchanged) and swaps (sign flip); since $0\le a_{ii}-t{a}_{ri}<a_{ri}$ in column $i$ no modular wrap occurs there, it terminates with $a_{ri}=0$ after $O(\log m)$ rounds, and the matrix becomes upper triangular. Bareiss. Let $M_k$ be the leading $k\times k$ minor and $g^{(k)}$ the entries after $k$ steps of ordinary elimination; by the block formula $\det \left(\begin{array}{cc}P& q\\ r& s\end{array}\right)=\det P(s-r{P}^{-1}q)$, $g_{ij}^{(k)}$ (a Schur complement entry) equals the bordered minor (rows $\mathrm{1..}k,i$, columns $\mathrm{1..}k,j$) divided by $M_k$. Put $a^{(k)}=M_k{g}^{(k)}$. Then $a_{kk}^{(k-1)}=M_k$, and the elimination step $g_{ij}^{(k)}=g_{ij}^{(k-1)}-g_{ik}^{(k-1)}{g}_{kj}^{(k-1)}/g_{kk}^{(k-1)}$ multiplied by $M_k$ becomes $a_{ij}^{(k)}=\frac{a_{kk}^{(k-1)}{a}_{ij}^{(k-1)}-a_{ik}^{(k-1)}{a}_{kj}^{(k-1)}}{M_{k-1}}$, the Bareiss recurrence with $M_{k-1}=a_{k-1,k-1}^{(k-2)}$ (prev). Every $a_{ij}^{(k)}$ is a minor of the integer matrix, so the divisions are exact and, by Hadamard, the values have $O(n\log (nM))$ bits. Row swaps apply the argument to the permuted matrix.

LGV. Expand $\det ={\sum }_{\sigma }\mathrm{sgn}\sigma {\prod }_{i}e(a_i\to b_{\sigma (i)})$ as a signed sum over path systems. For a system with an intersection, take the smallest index $i$ whose path meets another path, the first vertex $v$ on it shared with another path, and the smallest $j$ whose path passes $v$; swapping the tails of paths $i$ and $j$ after $v$ is an involution on intersecting systems (the same $i$, $v$, $j$ are chosen again) that composes $\sigma$ with a transposition, so these terms cancel in pairs. All functions were checked by brute force (Leibniz over permutations, composite moduli 12, 36, $2^{40}$, exact values against __int128 Leibniz, and enumerated disjoint path pairs and triples in small grids).

Permanent and hafnian

Quantity	Counts	Algorithm
$\mathrm{per}A$	weighted perfect matchings of a bipartite graph; permutations avoiding forbidden cells	Ryser with Gray code, $O(2^{n}n)$; mod 2 equals $\det$
$\mathrm{haf}A$ ($A$ symmetric, $n$ even)	weighted perfect matchings of a general graph	Björklund’s algorithm, $O(n^4{2}^{n/2})$ ($n=38$ in about 2 s)
values of ${⨁}_i{a}_{i\sigma (i)}$ over all $\sigma$		subset DP with bitsets, $O(2^{n}nV/64)$

The permanent is p-complete (Valiant), even for 0/1 matrices; the signs are exactly what makes the determinant easy. $\mathrm{haf}(A{)}^2=\mathrm{per}(A)$ only for special $A$.

template <class T> T permanent(const vector<vector<T>>& a) {   // Ryser, any commutative ring, n <= ~25
    int n = sz(a); if (n == 0) return T(1);
    vector<T> rowSum(n, T(0)); T total = T(0); unsigned gray = 0;
    for (unsigned k = 1; k < (1u << n); k++) {
        unsigned g = k ^ (k >> 1); int j = __builtin_ctz(g ^ gray); bool add = g >> j & 1;
        for (int i = 0; i < n; i++) rowSum[i] = add ? rowSum[i] + a[i][j] : rowSum[i] - a[i][j];
        gray = g;
        T prod = T(1); for (int i = 0; i < n; i++) prod = prod * rowSum[i];
        if (__builtin_popcount(g) % 2 == n % 2) total = total + prod; else total = total - prod;
    }
    return total;
}
 
template <class Z> Z hafnian(const vector<vector<Z>>& a) {   // symmetric, n even, diagonal ignored (Bjorklund 2012)
    int n = sz(a); assert(n % 2 == 0); int h = n / 2 + 1; using P = vector<Z>;
    auto addMul = [&](P& x, const P& p, const P& q) { for (int i = 0; i < h; i++) { if (p[i] == Z(0)) continue; for (int j = 0; j + i + 1 < h; j++) x[i + j + 1] += p[i] * q[j]; } };   // x += t p q
    auto solve = [&](auto&& self, const vector<vector<P>>& v) -> P {   // v[i][j], j < i
        P ans(h, Z(0));
        if (v.empty()) { ans[0] = 1; return ans; }
        int m = sz(v) - 2; auto V = v; V.resize(m);
        P zero = self(self, V);
        for (int i = 0; i < m; i++) for (int j = 0; j < i; j++) { addMul(V[i][j], v[m][i], v[m + 1][j]); addMul(V[i][j], v[m + 1][i], v[m][j]); }
        P one = self(self, V);
        for (int i = 0; i < h; i++) ans[i] += one[i] - zero[i];
        addMul(ans, one, v[m + 1][m]);
        return ans;
    };
    vector<vector<P>> v(n);
    for (int i = 0; i < n; i++) { v[i].resize(i); for (int j = 0; j < i; j++) v[i][j] = P(h, Z(0)), v[i][j][0] = a[i][j]; }
    return solve(solve, v).back();
}
 
template <int V> bitset<V> permutationXorValues(const vector<vector<int>>& a) {   // entries < V
    int n = sz(a); vector<bitset<V>> dp(1 << n); dp[0][0] = 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        int i = __builtin_popcount(mask); if (i == n || dp[mask].none()) continue;
        for (int j = 0; j < n; j++) if (!(mask >> j & 1)) {
            auto& to = dp[mask | 1 << j];
            for (int x = dp[mask]._Find_first(); x < V; x = dp[mask]._Find_next(x)) to[x ^ a[i][j]] = 1;
        }
    }
    return dp[(1 << n) - 1];
}

Proof: Ryser, Björklund's hafnian, XOR values

Ryser. ${\prod }_i{\sum }_{j\in S}{a}_{ij}$ sums over all functions $f:[n]\to S$; inclusion–exclusion over the set of columns $f$ misses keeps exactly the surjective $f$, which for $|S|=n$ are the permutations: $\mathrm{per}A={\sum }_S(-1{)}^{n-|S|}{\prod }_i{\sum }_{j\in S}{a}_{ij}$. The Gray code changes one column per step, updating every row sum in $O(1)$ (Inclusion–Exclusion).

Hafnian (Björklund 2012). Fix the pairing $P=\{(0,1),(2,3),\dots \}$ of the $n=2r$ vertices. For a perfect matching $M$, $M\cup P$ splits into disjoint closed alternating cycles that together visit every pair exactly once, and $M$ is recovered from them. The recursion removes the last pair $(m,m+1)$ in two ways: zero deletes it (the structure avoids the pair), one keeps it by contracting “matching edge into $m$, pair edge, matching edge out of $m+1$” into a single edge $ij$ whose polynomial degree records one more matching edge, plus the term $t{v}_{m+1,m}$ for the 2-cycle closing on the pair itself. Unfolding over all pairs, the result is ${\sum }_X(-1{)}^{r-|X|}{T}_X$, where $T_X$ is the generating polynomial (by number of matching edges, variable $t$) of collections of closed alternating walks through the pairs of $X$ only. By inclusion–exclusion over the set of pairs left untouched, the alternating sum keeps exactly the collections that touch every pair. A collection with exactly $r$ matching edges that touches all $r$ pairs touches each pair exactly once, so it is the cycle decomposition of $M\cup P$ for a perfect matching $M$ with weight ${\prod }_{e\in M}{a}_e$: the coefficient of $t^r$ (.back(), all polynomials truncated at degree $r$) is $\mathrm{haf}A$. The recursion has $2^r$ leaves, and each level does $O(n^2)$ polynomial products of length $O(n)$, giving $O(n^4{2}^{n/2})$. XOR values: the DP assigns rows in order to unused columns, so dp[mask] is the set of XORs over all partial assignments of rows $0..|mask|-1$ onto the columns in mask. All three were checked against brute force over all permutations / perfect matchings for $n\le 10$.

Related notes

• Gaussian Elimination
• Matrix-Tree Theorem (exact spanning tree counts with Bareiss)
• General Matching (Tutte matrix)