Permanent of a Matrix

June 2026 · 25 min read

Permanent vs Determinant

Given an n × n matrix A, its permanent is defined as:

perm(A) = Σ_{σ ∈ S_n} Π_{i=1}^{n} a_{i, σ(i)}

Compare this with the determinant:

det(A) = Σ_{σ ∈ S_n} sgn(σ) ⋅ Π_{i=1}^{n} a_{i, σ(i)}

The only difference is the sign factor sgn(σ). The determinant alternates signs based on whether the permutation is even or odd; the permanent simply sums every product without any sign. This tiny difference has enormous computational consequences.

Let’s see a concrete 3×3 example. Consider:

    | 1  2  3 |
A = | 4  5  6 |
    | 7  8  9 |

det(A) = 1(5⋅9 - 6⋅8) - 2(4⋅9 - 6⋅7) + 3(4⋅8 - 5⋅7)
       = 1(-3) - 2(-6) + 3(-3) = -3 + 12 - 9 = 0

perm(A) = 1⋅5⋅9 + 1⋅6⋅8 + 2⋅4⋅9 + 2⋅6⋅7 + 3⋅4⋅8 + 3⋅5⋅7
        = 45 + 48 + 72 + 84 + 96 + 105 = 450

Notice: the determinant vanishes (the matrix is singular), yet the permanent is a large positive number. The two quantities carry fundamentally different information.

This hardness result is one of the most striking in complexity theory. The determinant lives in P (even in NC, meaning it is efficiently parallelizable), while the permanent — differing by only a sign — is #P-complete. This is sometimes called the “permanent vs determinant” problem and remains a central open question in algebraic complexity.

For competitive programming, this means we must rely on exponential-time algorithms. Fortunately, Ryser’s formula gives us an efficient O(2ⁿ ⋅ n) method that works well for n ≤ 20.

Ryser’s Formula

The fastest known general algorithm for computing the permanent is Ryser’s formula (1963). It expresses the permanent as a sum over all subsets of columns:

perm(A) = (-1)^n Σ_{S ⊆ [n]} (-1)^{|S|} Π_{i=1}^{n} (Σ_{j ∈ S} a_{ij})

Here [n] = {1, 2, …, n} and the sum ranges over all 2ⁿ subsets of columns. For each subset S, we compute the product of row sums restricted to columns in S.

Derivation via Inclusion-Exclusion

The key insight is to view the permanent as a sum over all functions f: [n] → [n] (not just bijections), then subtract the overcounting using inclusion-exclusion.

Consider expanding the product:

Π_{i=1}^{n} (Σ_{j=1}^{n} a_{ij}) = Σ_{f: [n] → [n]} Π_{i=1}^{n} a_{i, f(i)}

This sums over all nⁿ functions from rows to columns. The permanent only wants bijections (permutations). We use inclusion-exclusion to enforce that every column is hit at least once.

Define A_j = “column j is not used by f.” We want to count functions avoiding all A_j, i.e., functions that use every column:

perm(A) = |complement of (A_1 ∪ A_2 ∪ … ∪ A_n)|
        = Σ_{S ⊆ [n]} (-1)^{|S|} ⋅ (functions avoiding columns in S)
        = Σ_{S ⊆ [n]} (-1)^{n - |S|} ⋅ Π_{i=1}^{n} (Σ_{j ∈ S} a_{ij})

Reindexing by the complement of S gives us Ryser’s formula. The factor (-1)n at the front accounts for the sign convention.

Step-by-Step Example (2×2)

Let’s verify with a 2×2 matrix:

A = | a  b |
    | c  d |

perm(A) = a⋅d + b⋅c   (by definition: two permutations of {1,2})

Ryser: (-1)^2 Σ_{S ⊆ {1,2}} (-1)^{|S|} Π_{i=1}^{2} (row_i sum over S)

S = {}:    (-1)^0 ⋅ 0 ⋅ 0 = 0
S = {1}:   (-1)^1 ⋅ a ⋅ c = -ac
S = {2}:   (-1)^1 ⋅ b ⋅ d = -bd
S = {1,2}: (-1)^2 ⋅ (a+b)(c+d) = ac + ad + bc + bd

Total = 0 - ac - bd + ac + ad + bc + bd = ad + bc  ✓

Bitmask DP Implementation

In competitive programming, we implement the permanent using bitmask DP over columns. The idea is to process rows one by one and track which columns have been “assigned” so far using a bitmask.

DP Formulation

Let dp[mask] = number of ways to assign columns (encoded in mask) to the first popcount(mask) rows such that each row gets a distinct column. Then:

dp[0] = 1
dp[mask] = Σ_{j ∈ mask} a[popcount(mask)-1][j] ⋅ dp[mask ^ (1 << j)]

Answer = dp[(1 << n) - 1]

This directly counts perfect matchings: at each step, we pick which column to match to the current row.

C++ Implementation: Bitmask DP

#include <bits/stdc++.h>
using namespace std;

// Compute permanent of an n x n matrix using bitmask DP.
// O(2^n * n) time, O(2^n) space.
// Works for n <= 20 within typical contest limits.
long long permanent_bitmask(vector<vector<long long>>& a, int n) {
    vector<long long> dp(1 << n, 0);
    dp[0] = 1;

    for (int mask = 1; mask < (1 << n); mask++) {
        int row = __builtin_popcount(mask) - 1;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                dp[mask] += a[row][j] * dp[mask ^ (1 << j)];
            }
        }
    }
    return dp[(1 << n) - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<long long>> a(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    cout << permanent_bitmask(a, n) << "\n";
    return 0;
}

This bitmask DP is the most intuitive approach and directly models the assignment/matching interpretation. Each state dp[mask] represents a partial matching of the first popcount(mask) rows to the columns indicated by mask.

C++ Implementation: Ryser’s Formula

Ryser’s formula is often faster in practice because it avoids the overhead of the DP transitions and has better cache behavior:

#include <bits/stdc++.h>
using namespace std;

// Compute permanent using Ryser's formula.
// O(2^n * n) time, O(n) space.
long long permanent_ryser(vector<vector<long long>>& a, int n) {
    long long result = 0;

    // Iterate over all non-empty subsets S of [n]
    for (int S = 1; S < (1 << n); S++) {
        long long prod = 1;
        for (int i = 0; i < n; i++) {
            long long row_sum = 0;
            for (int j = 0; j < n; j++) {
                if (S & (1 << j)) {
                    row_sum += a[i][j];
                }
            }
            prod *= row_sum;
        }

        int bits = __builtin_popcount(S);
        if ((n - bits) % 2 == 0)
            result += prod;
        else
            result -= prod;
    }

    // Multiply by (-1)^n
    if (n % 2 == 1)
        result = -result;

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<long long>> a(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    cout << permanent_ryser(a, n) << "\n";
    return 0;
}

A key advantage of Ryser’s formula is that it uses only O(n) auxiliary space (versus O(2ⁿ) for the bitmask DP), which matters when n is close to 20.

Gray Code Optimization

We can speed up Ryser’s formula by enumerating subsets in Gray code order, so that consecutive subsets differ by exactly one element. Instead of recomputing all row sums from scratch for each subset, we incrementally update them by adding or subtracting one column:

With Gray code enumeration, the per-subset update cost drops from O(n) (recomputing row sums) to O(1) for the update step, though we still need O(n) to compute the product. Total: still O(2ⁿ ⋅ n), but the constant factor is significantly better.

Permanent and Perfect Matchings

The most important combinatorial interpretation of the permanent is through bipartite graph matchings.

This follows directly from the definition. Each permutation σ ∈ S_n corresponds to a potential matching {(u₁, v_σ(1)), …, (u_n, v_σ(n))}. The product Π a_i,σ(i) is 1 if and only if all edges in this matching exist, and 0 otherwise. So the sum over all permutations counts exactly the perfect matchings.

Weighted Matchings

If the matrix entries are weights rather than 0/1 values, then perm(A) computes the sum of weights of all perfect matchings, where the weight of a matching is the product of its edge weights. This generalizes the counting interpretation.

Connection to the Assignment Problem

The assignment problem asks for the minimum-weight perfect matching in a bipartite graph. While it can be solved in O(n³) by the Hungarian algorithm, counting all perfect matchings (or summing all matching weights) is #P-hard, which is why we need exponential algorithms.

Hall’s Marriage Theorem

Hall’s theorem gives a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph: for every subset S of the left vertices, the neighborhood N(S) satisfies |N(S)| ≥ |S|.

The permanent provides a quantitative strengthening: not just whether a perfect matching exists, but how many. A celebrated result by van der Waerden (proved by Egorychev and Falikman in 1981) gives a lower bound on the permanent of a doubly stochastic matrix:

Inclusion-Exclusion Perspective

Let’s re-derive Ryser’s formula from scratch using a pure inclusion-exclusion argument, to build intuition for why it works.

The Overcounting Approach

We want to count the number of permutation matrices “contained” in A (i.e., supported on its nonzero entries). Start by overcounting: consider all generalized assignments f: [n] → [n] (not necessarily injective).

For each row i, independently choose any column j with a_ij ≠ 0. The total number of such assignments is:

T = Π_{i=1}^{n} r_i   where r_i = Σ_{j=1}^{n} a_{ij} (row sum)

This overcounts because multiple rows may choose the same column. We need to subtract assignments that miss at least one column.

Applying Inclusion-Exclusion

Let B_j = set of assignments that do not use column j. The permanent equals the number of assignments that avoid all B_j:

perm(A) = |T \ (B_1 ∪ B_2 ∪ … ∪ B_n)|

By inclusion-exclusion:

perm(A) = Σ_{k=0}^{n} (-1)^k Σ_{|T|=k} |B_{t_1} ∩ B_{t_2} ∩ … ∩ B_{t_k}|

The intersection B_{t_1} ∩ … ∩ B_{t_k} consists of assignments that avoid columns t₁, …, t_k. For such assignments, each row i picks from the remaining columns, so:

|B_{t_1} ∩ … ∩ B_{t_k}| = Π_{i=1}^{n} (Σ_{j ∉ {t_1,...,t_k}} a_{ij})

Substituting into the inclusion-exclusion sum and reindexing by the complement set S = [n] \ {t₁, …, t_k} (the columns we do include):

perm(A) = Σ_{S ⊆ [n]} (-1)^{n-|S|} Π_{i=1}^{n} (Σ_{j ∈ S} a_{ij})
        = (-1)^n Σ_{S ⊆ [n]} (-1)^{|S|} Π_{i=1}^{n} (Σ_{j ∈ S} a_{ij})

This is exactly Ryser’s formula. ■

Why This Matters in CP

The inclusion-exclusion viewpoint shows that the permanent is a special case of a general pattern: count unrestricted objects, then subtract those violating constraints. Many CP problems follow this template:

• Derangements: perm of (J - I), where J is the all-ones matrix and I is identity.
• Latin rectangles: count row assignments with no column repetition.
• SDR counting: given sets S₁, …, S_n, count distinct representative systems.

Whenever you see “count bijections with constraints,” think permanent.

CP Applications

1. Counting Perfect Matchings in Bipartite Graphs

The most direct application. Given a bipartite graph with n ≤ 20 on each side, build the adjacency matrix and compute the permanent.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

// Permanent modulo a prime using Ryser's formula.
// Handles n <= 20 comfortably.
long long permanent_mod(vector<vector<int>>& a, int n, int mod) {
    long long result = 0;

    for (int S = 1; S < (1 << n); S++) {
        long long prod = 1;
        for (int i = 0; i < n; i++) {
            long long row_sum = 0;
            for (int j = 0; j < n; j++) {
                if (S & (1 << j)) {
                    row_sum = (row_sum + a[i][j]) % mod;
                }
            }
            prod = prod % mod * (row_sum % mod) % mod;
        }

        int bits = __builtin_popcount(S);
        if ((n - bits) % 2 == 0)
            result = (result + prod) % mod;
        else
            result = (result - prod + mod) % mod;
    }

    if (n % 2 == 1)
        result = (mod - result) % mod;

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1;
    }

    cout << permanent_mod(adj, n, MOD) << "\n";
    return 0;
}

2. Counting Latin Squares

A Latin square of order n is an n × n grid filled with n different symbols such that each symbol occurs exactly once in each row and column. We can build a Latin square row by row: after placing the first k rows, the allowed positions in row k+1 form a 0/1 matrix, and the number of valid completions of that row is a permanent.

The total number of Latin squares can be computed by multiplying permanents across rows, though the matrix changes after each row is fixed. For small n, this gives an exact count.

3. System of Distinct Representatives (SDR)

Given sets S₁, S₂, …, S_n over a universe of size n, an SDR is a selection of distinct elements x₁ ∈ S₁, x₂ ∈ S₂, …, x_n ∈ S_n. The number of SDRs equals perm(A) where a_ij = 1 iff element j is in set S_i.

4. Common Contest Patterns

Look for the permanent in problems that ask:

• “How many ways to assign n workers to n tasks?” (with eligibility constraints)
• “Count permutations σ where σ(i) ∈ S_i for given sets S_i.”
• “Number of perfect matchings in a bipartite graph” with n ≤ 20.
• “Count n × n binary matrices with prescribed row and column sums.”

5. Problem References

Optimizations

Glynn’s Formula (2010)

Glynn’s formula provides an alternative to Ryser that avoids the alternating signs, using ±1 vectors instead of subset sums:

perm(A) = (1 / 2^{n-1}) Σ_{\varepsilon} (Π_{j=1}^{n} &varepsilon_j) ⋅ Π_{i=1}^{n} (Σ_{j=1}^{n} &varepsilon_j ⋅ a_{ij})

where the sum is over all vectors ϵ ∈ {+1, -1}ⁿ with ϵ₁ = +1 (we fix one coordinate to avoid double-counting).

Advantages of Glynn’s formula:

• No cancellation issues: useful when working in characteristic 2 (e.g., GF(2) or mod 2).
• Better numerical stability for floating-point computation.
• Same asymptotic complexity: O(2^n-1 ⋅ n), but with a constant-factor improvement (half as many terms).

Parallel / SIMD Computation

Since each subset’s contribution in Ryser’s formula is independent, the computation is embarrassingly parallel. Practical speedups:

• Split subset enumeration across threads (each thread handles a range of masks).
• Use SIMD instructions to compute multiple row sums simultaneously.
• On modern CPUs, 128-bit or 256-bit vector instructions can process 2–4 row sums in parallel.

Modular Permanent

When computing perm(A) mod p for a prime p, all arithmetic is done in Z_p. Key considerations:

• Replace multiplications and additions with modular versions.
• Be careful with the (-1)ⁿ and (-1)^|S| signs — represent -1 as (p-1) mod p.
• If the modulus is 2, every term in Ryser’s formula collapses: perm(A) mod 2 = det(A) mod 2. This is because over GF(2), the sign of a permutation is 1 (since -1 = 1 in GF(2)), so the permanent and determinant coincide. Determinant mod 2 can be computed in O(n³)!

Sparse Matrix Optimization

If the matrix A is sparse (many zeros), the bitmask DP can be sped up. For each row, only iterate over columns where a_ij ≠ 0. If each row has at most d nonzero entries, the DP transition cost drops from O(n) to O(d) per state.

For very sparse bipartite graphs (small degree), this can be a significant improvement, though the number of DP states remains 2ⁿ.

Comparison of Methods

Summary

The permanent of a matrix is a deceptively simple quantity — identical to the determinant except for a missing sign — yet it is fundamentally harder to compute. Here are the key takeaways:

• Definition: perm(A) = Σ_σ Π a_i,σ(i) (no sign factor, unlike the determinant).
• Complexity: Computing the permanent is #P-complete, even for 0/1 matrices. No polynomial-time algorithm is known.
• Ryser’s formula: The practical algorithm for CP — runs in O(2ⁿ ⋅ n) time and O(n) space. Derived from inclusion-exclusion on column usage.
• Bitmask DP: An alternative O(2ⁿ ⋅ n) approach that directly models the matching process. Uses O(2ⁿ) space but is often easier to understand.
• Matchings: perm(A) counts perfect matchings in the bipartite graph with biadjacency matrix A. This is the primary combinatorial application.
• Contest usage: Look for permanent when n ≤ 20 and the problem asks to count assignments, matchings, or restricted permutations.
• Mod 2 shortcut: perm(A) ≡ det(A) (mod 2), computable in O(n³).
• Glynn’s formula: An alternative with half the terms, useful in special fields.