The berkeDet Algorithm

Overview

berkeDet computes the determinant of an $n \times n$ matrix via the Leibniz formula by decomposing the problem into two independent subroutines, each based on block replication and index mapping:

• meryemSign$(n)$: generates the complete list of $n!$ Leibniz signs in lexicographic order using iterated block replication with sign flips, in $\Theta(n!)$ total time.
• meryemPer$(n)$: generates all $n!$ permutations of $\{1, \ldots, n\}$ in lexicographic order via layer-wise block replication and index mapping, in $O(n \cdot n!)$ total time — without any sorting, reversal, or pivot scanning.

meryemSign: Sign Generation by Block Replication

The sign of a permutation $\sigma$ is defined as $\operatorname{sgn}(\sigma) = (-1)^m$, where $m$ is the number of inversions — pairs $(i,j)$ with $i < j$ but $\sigma(i) > \sigma(j)$.

Traditionally, computing $\operatorname{sgn}(\sigma)$ requires $O(n^2)$ per permutation via inversion counting. meryemSign eliminates this entirely by exploiting a recursive block structure.

The Algorithm

1. Initialize $b \leftarrow [+1]$.
2. For $e = 1, 2, \ldots, n-1$:
   1. Set $c \leftarrow b$ (replicate the current list).
   2. For $d = 0, 1, \ldots, e-1$:
      • If $d$ is even, let $f \leftarrow -c$ (negate every element of the replica).
      • If $d$ is odd, let $f \leftarrow c$ (keep the replica unchanged).
      • Append $f$ to $b$.

After completion, $b$ contains $n!$ entries, and $b[i] = \operatorname{sgn}(\sigma_i)$ where $\sigma_i$ is the $i$-th permutation in lexicographic order.

Why It Works

Consider the permutations of $\{1, \ldots, n\}$ grouped by their first element $k$. If $\sigma = (k, \tau_1, \tau_2, \ldots, \tau_{n-1})$, then moving $k$ to the first position from its natural position requires $k-1$ adjacent transpositions, so:

The algorithm starts with the block for $k=1$ (unchanged, since $(-1)^0 = +1$), then appends blocks for $k = 2, 3, \ldots, n$. Block $d$ corresponds to $k = d+2$, and the sign factor $(-1)^{k-1} = (-1)^{d+1}$ matches the rule: negate when $d$ is even, replicate unchanged when $d$ is odd.

Complexity: The total number of operations is $\Theta(n!)$. The amortized cost per sign is $O(1)$. Measured, isolated: ~100× faster than inversion counting, 350–400× faster than merge-based parity, 15–18× faster than the strongest classical baseline (Narayana stepping with $O(1)$ parity updates). Verified element-by-element through order 10.

Python Implementation

def meryemSign(n: int) -> list[int]:
    """Generate signs for all n! permutations in lex order.
    Returns list of +1 and -1 values."""
    b = [1]  # start with +1
    for e in range(1, n):
        c = b[:]
        for d in range(e):
            if d % 2 == 0:
                f = [-x for x in c]
            else:
                f = c[:]
            b.extend(f)
    return b

meryemPer: Permutation Generation by Block Replication and Index Mapping

meryemPer generates all $n!$ permutations of $\{1, \ldots, n\}$ in lexicographic order using a layer-wise construction. At each layer, it builds permutations of $\{1, \ldots, b\}$ from the permutations of $\{1, \ldots, b-1\}$ via block replication and index remapping.

The Algorithm

1. Initialize $a \leftarrow [[1]]$.
2. For each layer $b = 2, 3, \ldots, n$:
   1. Let $c = [1, 2, \ldots, b]$.
   2. Initialize $d \leftarrow$ empty list.
   3. For each $f \in c$ (in increasing order):
      • Form $g = c \setminus \{f\}$ (remaining elements in order).
      • For each permutation $h \in a$: compute $j = [g[h_1], g[h_2], \ldots]$ and append $[f] \circ j$ to $d$.
   4. Set $a \leftarrow d$.

Why It Works

Permutations of $\{1, \ldots, n\}$ with a fixed first element $f$ correspond bijectively to permutations of the remaining elements. The index-mapping step applies the permutation pattern $h$ (from the previous layer) to the concrete remaining elements $g$. Since $g$ is increasing, the map is order-preserving, so lexicographic order is preserved within each block; since $f$ increases, the full output is lexicographic.

Complexity: $O(n \cdot n!)$ total; amortized $O(n)$ per permutation.

Python Implementation

def meryemPer(n: int) -> list[list[int]]:
    """Generate all n! permutations of {1,...,n} in lex order.
    No sorting, reversal, or pivot scanning at any step."""
    a = [[1]]
    for b in range(2, n + 1):
        c = list(range(1, b + 1))
        d = []
        for f in c:
            g = [e for e in c if e != f]
            for h in a:
                j = [g[i - 1] for i in h]
                d.append([f] + j)
        a = d
    return a

berkeDet: Combined Determinant Computation

With both subroutines in hand, berkeDet simply combines them:

Python Implementation

def berkeDet(matrix: list[list[float]]) -> float:
    """Compute determinant via Leibniz formula using
    meryemSign and meryemPer."""
    n = len(matrix)
    signs = meryemSign(n)
    perms = meryemPer(n)
    det = 0
    for sign, perm in zip(signs, perms):
        product = 1
        for i in range(n):
            product *= matrix[i][perm[i] - 1]
        det += sign * product
    return det

Combined Complexity: $O(n \cdot n!)$ time — a factor of $n$ better than the classical lexicographic approach, matching SJT while preserving lexicographic order, with no sorting, reversal, or per-step scanning anywhere.

Parallel Structure: the Factorial Tree

The layer-by-layer construction is a tree: layer 1 holds the single node $[1]$, and every node of layer $b-1$ spawns exactly $b$ children in layer $b$ (one per first element $f$), so layer $b$ has $b!$ nodes. The decisive property is locality: the child at global rank $r$ of layer $b$ depends on two integers only — $f = \lfloor r/(b-1)! \rfloor$ and $r' = r \bmod (b-1)!$ — and on the single layer-$(b-1)$ node at rank $r'$. Siblings never read each other.

Measured on a single core with NumPy as the vector-processor stand-in (each layer = one bulk gather $g_f[A]$ per block): vectorized meryemPer generates all permutations $\approx 6\times$ faster than the C-implemented itertools chain at $n = 10$–$11$; vectorized meryemSign emits all 479,001,600 signs of $S_{12}$ in 0.19 s; and the fully vectorized berkeDet evaluates the exact $10 \times 10$ determinant in 0.343 s — $15\times$ faster than serial SJT on the same instance. Vectorized reference code is in Appendix B of the paper and in the downloadable scripts on the Resources page.

Try It Yourself (Python)

You don't need to be a mathematician to try berkeDet. Copy the code below, paste it into any Python environment (such as online-python.com), and run it. The code is beginner-friendly with comments explaining each step.

Complete Example with Comments

# =============================================
#  berkeDet — Complete Beginner-Friendly Code
# =============================================

def meryemSign(n):
    """
    Generate signs (+1 or -1) for all n! permutations
    in lexicographic order.

    How it works:
    - Start with [+1]
    - For each new layer, replicate the existing signs
      and append flipped/unflipped copies
    - The pattern: flip, keep, flip, keep, ...

    Example for n=3:
    Layer 0: [+]
    Layer 1: [+] + [-]         = [+, -]
    Layer 2: [+, -] + [-, +] + [+, -] = [+, -, -, +, +, -]
    """
    b = [1]  # start with +1
    for e in range(1, n):
        c = b[:]  # replicate current list
        for d in range(e):
            if d % 2 == 0:
                f = [-x for x in c]  # flip all signs
            else:
                f = c[:]             # keep signs as-is
            b.extend(f)              # append to list
    return b


def meryemPer(n):
    """
    Generate all n! permutations of {1, 2, ..., n}
    in lexicographic (dictionary) order.

    How it works:
    - Start with [[1]]
    - For each new layer, try each number as the first element
    - Fill the rest using previous layer's patterns
    - NO sorting, NO reversal, NO scanning needed!

    Example for n=3:
    Layer 1: [[1]]
    Layer 2: [[1,2], [2,1]]
    Layer 3: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
    """
    a = [[1]]
    for b in range(2, n + 1):
        c = list(range(1, b + 1))  # [1, 2, ..., b]
        d = []
        for f in c:                # try each as first element
            g = [e for e in c if e != f]  # remaining elements
            for h in a:            # use previous patterns
                j = [g[i - 1] for i in h]  # map indices
                d.append([f] + j)
        a = d
    return a


def berkeDet(matrix):
    """
    Compute the determinant of a square matrix using
    the Leibniz formula with meryemSign and meryemPer.

    Input: a list of lists, e.g. [[1,2],[3,4]]
    Output: the determinant (a number)
    """
    n = len(matrix)
    signs = meryemSign(n)
    perms = meryemPer(n)
    det = 0
    for sign, perm in zip(signs, perms):
        product = 1
        for i in range(n):
            product *= matrix[i][perm[i] - 1]
        det += sign * product
    return det


# =============================================
#  EXAMPLE: Try berkeDet on a 3x3 matrix
# =============================================

A = [
    [6, 1, 1],
    [4, -2, 5],
    [2, 8, 7]
]

print("Signs for 3x3 matrix:")
print(meryemSign(3))
# Output: [1, -1, -1, 1, 1, -1]

print("\nPermutations for 3x3 matrix:")
for p in meryemPer(3):
    print(p)
# Output: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

result = berkeDet(A)
print(f"\nDeterminant of A = {result}")
# Output: Determinant of A = -306


# =============================================
#  VERIFY: Compare with a simple 2x2 matrix
# =============================================

B = [
    [3, 8],
    [4, 6]
]

print(f"\nDeterminant of B = {berkeDet(B)}")
# Output: Determinant of B = -14
# Check: 3*6 - 8*4 = 18 - 32 = -14


# =============================================
#  TRY YOUR OWN: Change the matrix below!
# =============================================

C = [
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]
]

print(f"\nDeterminant of identity matrix = {berkeDet(C)}")
# Output: Determinant of identity matrix = 1