Problem 903: Matrix Permanent Modulo a Prime

Mathematical Analysis

Definition of the Permanent

The permanent of an $n \times n$ matrix $A$ is:

Unlike the determinant, the permanent uses no sign factor. It is #P-complete to compute in general (Valiant, 1979), but Ryser’s formula reduces the cost to $O(2^n \cdot n)$.

Structure of the Multiplication Table Matrix

The matrix $A_{ij} = (ij) \bmod n$ is the multiplication table of $\mathbb{Z}/n\mathbb{Z}$ restricted to $\{1, \ldots, n\}$. Key properties:

Observation 1. Row $i$ has $A_{i,j} = (ij) \bmod n$. If $\gcd(i, n) = d > 1$, then every entry in row $i$ is divisible by $d$, and specifically $A_{i,j} \in \{0, d, 2d, \ldots, n-d\}$.

Observation 2 (Zero Row). When $i = n$, $A_{n,j} = (nj) \bmod n = 0$ for all $j$. Row $n$ is entirely zero.

Theorem. For any $n \ge 2$, $\text{perm}(A) = 0$ where $A_{ij} = (ij) \bmod n$.

Proof. Row $n$ consists entirely of zeros: $A_{n,j} = nj \bmod n = 0$ for all $j \in \{1, \ldots, n\}$. Every term in the permanent sum (1) includes the factor $A_{n,\sigma(n)} = 0$. Therefore $\text{perm}(A) = 0$. $\square$

This is a structurally trivial result once the zero row is identified, but the problem illustrates how algebraic structure (the annihilator $n \equiv 0$ in $\mathbb{Z}/n\mathbb{Z}$) interacts with combinatorial quantities.

Ryser’s Formula

For general matrices, Ryser’s formula provides an inclusion-exclusion computation:

Derivation. Start from the identity:

Using inclusion-exclusion to remove the bijection constraint yields (2). The key is that $\prod_{i=1}^n \sum_{j \in S} A_{ij}$ counts all functions $f: [n] \to S$ weighted by $\prod A_{i,f(i)}$, and inclusion-exclusion extracts the bijections.

Permanents of Modified Multiplication Tables

If we instead use $A_{ij} = (ij) \bmod n$ with $i, j \in \{0, 1, \ldots, n-1\}$, the situation is identical (row 0 is all zeros). For the non-trivial variant with $i, j \in \{1, \ldots, n-1\}$ (an $(n-1) \times (n-1)$ matrix), the permanent is non-zero when $n$ is prime (since $\mathbb{Z}/p\mathbb{Z}^*$ has no zero divisors).

Proposition. For prime $p$, the $(p-1) \times (p-1)$ matrix $B_{ij} = (ij) \bmod p$ for $i, j \in \{1, \ldots, p-1\}$ has $\text{perm}(B) \ne 0$.

Proof sketch. When $p$ is prime, each row of $B$ is a permutation of $\{1, \ldots, p-1\}$ (since multiplication by a unit is a bijection on $\mathbb{Z}/p\mathbb{Z}^*$). By the van der Waerden conjecture (proven by Egorychev and Falikman, 1981), the permanent of a doubly stochastic matrix is positive. While $B$ is not doubly stochastic, its row-permutation structure guarantees the identity permutation contributes $\prod_{i=1}^{p-1} (i^2 \bmod p) \ne 0$. $\square$

Concrete Verification

The matrix $A$ for $n = 12$ (entries $(ij) \bmod 12$):

Row 12 is all zeros, confirming $\text{perm}(A) = 0$.

Permanent Values for Smaller $n$

For all $n \ge 1$, the $n \times n$ multiplication-table matrix with 1-indexed rows/columns always has $A_{n,j} = 0$ for all $j$.

Complexity Analysis

• Structural argument: $O(n)$ to verify row $n$ is zero.
• Ryser’s formula (if needed): $O(2^n \cdot n)$ time, $O(n)$ space.
• Brute-force permanent: $O(n! \cdot n)$ time — infeasible for large $n$ but fine for $n = 12$ ($12! \approx 4.8 \times 10^8$).

Answer

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

/*
 * Problem 903: Matrix Permanent Modulo a Prime
 *
 * A[i][j] = (i*j) mod n for i,j in {1,...,n}, n = 12.
 * Find perm(A) mod 10^9+7.
 *
 * Key insight: Row n has A[n][j] = (n*j) mod n = 0 for all j.
 * A matrix with a zero row has permanent = 0.
 *
 * Two methods:
 *   1. Zero-row detection (O(n) check)
 *   2. Ryser's formula (O(2^n * n) general computation)
 */

const long long MOD = 1e9 + 7;

/*
 * Method 1: Check for zero row
 * If any row i has A[i][j] = 0 for all j, perm = 0.
 * For the multiplication table mod n, row n always satisfies this.
 */
bool has_zero_row(int n) {
    for (int i = 1; i <= n; i++) {
        bool all_zero = true;
        for (int j = 1; j <= n; j++) {
            if ((i * j) % n != 0) {
                all_zero = false;
                break;
            }
        }
        if (all_zero) return true;
    }
    return false;
}

/*
 * Method 2: Ryser's formula
 * perm(A) = (-1)^n * sum_{S} (-1)^|S| * prod_i (sum_{j in S} A[i][j])
 *
 * O(2^n * n) time.  For n=12, 2^12 * 12 = 49152 operations.
 */
long long permanent_ryser(vector<vector<int>>& A) {
    int n = A.size();
    long long result = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        int bits = __builtin_popcount(mask);

        // Product of row sums for columns in mask
        long long prod = 1;
        bool zero = false;
        for (int i = 0; i < n && !zero; i++) {
            long long row_sum = 0;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j))
                    row_sum += A[i][j];
            }
            if (row_sum == 0) { zero = true; break; }
            prod *= row_sum;
        }
        if (zero) continue;

        long long sign = ((n - bits) % 2 == 0) ? 1 : -1;
        result += sign * prod;
    }

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

int main() {
    int n = 12;

    // Method 1: structural
    if (has_zero_row(n)) {
        cout << 0 << endl;
    }

    // Method 2: Ryser verification
    vector<vector<int>> A(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            A[i][j] = ((i + 1) * (j + 1)) % n;

    long long perm = permanent_ryser(A);
    assert(perm == 0);

    // Verify for small n: all should be 0
    for (int nn = 2; nn <= 8; nn++) {
        vector<vector<int>> M(nn, vector<int>(nn));
        for (int i = 0; i < nn; i++)
            for (int j = 0; j < nn; j++)
                M[i][j] = ((i + 1) * (j + 1)) % nn;
        assert(permanent_ryser(M) == 0);
    }

    cout << 0 << endl;
    return 0;
}

"""
Problem 903: Matrix Permanent Modulo a Prime

Let A be the n x n matrix with A[i,j] = (i*j) mod n, i,j in {1,...,n}.
Find perm(A) mod 10^9+7 for n = 12.

Key insight: Row n has A[n,j] = (n*j) mod n = 0 for all j, so perm(A) = 0.

Methods:
    1. Structural argument (zero row detection)
    2. Ryser's formula (general permanent computation)
    3. Brute-force via itertools.permutations (small n verification)
"""

from itertools import permutations
from math import gcd

MOD = 10**9 + 7

def solve_structural(n: int):
    """Detect if any row is all zeros => perm = 0."""
    for i in range(1, n + 1):
        if all((i * j) % n == 0 for j in range(1, n + 1)):
            return 0  # Row i is all zeros
    return None  # No zero row found; need computation

def permanent_ryser(A: list, mod: int = 0):
    """Compute permanent using Ryser's inclusion-exclusion formula.

    perm(A) = (-1)^n * sum_{S subset [n]} (-1)^|S| * prod_{i} sum_{j in S} A[i][j]
    Complexity: O(2^n * n).
    """
    n = len(A)
    result = 0
    for mask in range(1, 1 << n):
        bits = bin(mask).count("1")
        # Compute product of row sums restricted to columns in mask
        prod = 1
        for i in range(n):
            row_sum = 0
            for j in range(n):
                if mask & (1 << j):
                    row_sum += A[i][j]
            prod *= row_sum
            if prod == 0:
                break  # Early termination
        sign = (-1) ** (n - bits)
        result += sign * prod
    result *= (-1) ** n
    return result % mod if mod else result

def permanent_brute(A: list):
    """Compute permanent by definition: sum over all permutations."""
    n = len(A)
    total = 0
    for sigma in permutations(range(n)):
        prod = 1
        for i in range(n):
            prod *= A[i][sigma[i]]
            if prod == 0:
                break
        total += prod
    return total

# Build matrix and solve
N = 12
A = [[(i * j) % N for j in range(1, N + 1)] for i in range(1, N + 1)]

ans_structural = solve_structural(N)
assert ans_structural == 0, "Structural method failed"

ans_ryser = permanent_ryser(A) % MOD

for test_n in [3, 4, 5, 6, 7]:
    M = [[(i * j) % test_n for j in range(1, test_n + 1)] for i in range(1, test_n + 1)]
    p_ryser = permanent_ryser(M)
    p_brute = permanent_brute(M)
    assert p_ryser == p_brute, f"n={test_n}: Ryser={p_ryser}, brute={p_brute}"
    assert p_ryser == 0, f"n={test_n}: permanent should be 0, got {p_ryser}"

assert ans_ryser == 0

print(0)

# Permanents of the reduced matrix (i,j in {1..n-1}) for prime n
def permanent_reduced(n: int):
    """Permanent of the (n-1)x(n-1) matrix B[i,j] = (i*j) mod n, i,j in {1..n-1}."""
    B = [[(i * j) % n for j in range(1, n)] for i in range(1, n)]
    return permanent_ryser(B)