The berkeDet Algorithm — detsignper.org

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

Initialize $b \leftarrow [+1]$.
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:

\operatorname{sgn}(\sigma) = (-1)^{k-1} \cdot \operatorname{sgn}(\tau)

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)$. At layer $e$, the algorithm performs $e \cdot (e-1)! = e!$ operations. Summing over all layers: $\sum_{e=1}^{n-1} e! = \Theta(n!)$.

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

Initialize $a \leftarrow [[1]]$.
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]-1], g[h[2]-1], \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 $h$ ranges over all $(n-1)!$ permutations in lexicographic order and the mapping is order-preserving, the output is in lexicographic order.

            How meryemPer differs from classical generators: The standard lexicographic generator
            (Narayana Pandita) works incrementally — each permutation is derived from the previous one
            by scanning for a pivot, swapping, and reversing a suffix. The naive version requires sorting the suffix
            at $O(n \log n)$ per step; the optimized version replaces sorting with reversal at $O(n)$ per step, but
            this is a non-trivial insight. meryemPer works compositionally — it builds the entire list
            from the previous layer via block replication and index remapping. No sorting, no reversal, no
            scanning, no in-place modification occurs at any step. The lexicographic order emerges naturally
            from the construction without requiring any optimization trick.
        

Complexity: The total number of operations is $O(n \cdot n!)$. The amortized cost per permutation is $O(n)$. At layer $b$, the algorithm generates $b!$ permutations, each of length $b$, for a cost of $O(b \cdot b!)$.

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: meryemSign runs in $\Theta(n!)$, meryemPer in $O(n \cdot n!)$, and the summation step costs $O(n \cdot n!)$. The dominant term is $O(n \cdot n!)$. This improves the standard lexicographic approach by a factor of $n$, matching SJT while preserving lexicographic order — and doing so without any sorting, reversal, or per-step scanning operations.

Structural Insight

The core observation behind meryemSign is that the sign sequence for lexicographically ordered permutations has a recursive block structure. When extending from $S_{n-1}$ to $S_n$, the blocks follow a simple alternating pattern:

\underbrace{+\mathbf{s}}_{k=1},\quad \underbrace{-\mathbf{s}}_{k=2},\quad \underbrace{+\mathbf{s}}_{k=3},\quad \underbrace{-\mathbf{s}}_{k=4},\quad \ldots

This structure makes the entire sign list computable by pure block replication with no arithmetic beyond sign flips.

Similarly, meryemPer exploits the observation that permutations of $\{1, \ldots, n\}$ with a fixed first element $f$ correspond bijectively to permutations of the remaining elements, captured by a simple index remapping using the previous layer's output. This compositional structure avoids the need for any in-place modification, scanning, or suffix manipulation.

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
# =============================================

# Define a 3x3 matrix
A = [
    [6, 1, 1],
    [4, -2, 5],
    [2, 8, 7]
]

# Step 1: See the signs for n=3
print("Signs for 3x3 matrix:")
print(meryemSign(3))
# Output: [1, -1, -1, 1, 1, -1]

# Step 2: See all permutations for n=3
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]

# Step 3: Compute the determinant
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