Research Paper — Version 3

berkeDet: A Dual Iterative Algorithm for Exact Determinant Computation via Block Replication and Index Mapping

A new approach to the Leibniz formula: $O(n \cdot n!)$ complexity, lexicographic order, no sorting or per-permutation sign computation — and a compositional structure that is inherently parallel (span $O(n)$, against the chains' $\Omega(n!)$ critical path).

Berke Gülmen  ·  Meryem Gülmen  ·  Ömer Gülmen
Authors Berke Gülmen, Meryem Gülmen, Ömer Gülmen
Version 3 12 July 2026 (first version: 26 February 2026)
Keywords Leibniz Formula, Determinant, Permutation, Lexicographic Order, Data Parallelism
Complexity $O(n \cdot n!)$ total — span $O(n)$, parallelism $\Theta(n!)$

The Problem

The Leibniz formula expresses the determinant of a square matrix as a sum over all $n!$ permutations:

$$\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}$$

To compute this directly, you need two things: all $n!$ permutations of $\{1, 2, \ldots, n\}$ in order, and the sign ($+1$ or $-1$) of each one.

The classical way to do this has three limitations:

  1. Generating the next permutation — the naive lexicographic method requires sorting a suffix at each step ($O(n \log n)$ per permutation). The Narayana Pandita optimization replaces sorting with a suffix reversal, but still scans for a pivot, swaps, and reverses at every step.
  2. Computing the sign — the standard method counts inversions at $O(n^2)$ per permutation; over all $n!$ permutations, $O(n^2 \cdot n!)$.
  3. Serial by construction — every classical generator (naive, Narayana, SJT, Heap) computes permutation $r{+}1$ from the value of permutation $r$. That is a dependency chain with critical path $\Omega(n!)$: no processor count and no implementation language can shorten it, and vector hardware is given nothing to do.

Our Solution

berkeDet removes all three limitations with two subroutines built purely from block replication and index mapping — no sorting, no reversal, no scanning, no inversion counting at any step:

meryemSign generates all $n!$ signs in $\Theta(n!)$ total time — an amortized cost of $O(1)$ per sign. It exploits the recursive block structure of the sign sequence: when extending from $S_{n-1}$ to $S_n$, the signs 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$$
where $\mathbf{s}$ is the sign list for $S_{n-1}$. Isolated measurements: ~100× faster than inversion counting, 350–400× faster than merge-based parity, and 15–18× faster than the strongest classical baseline (Narayana stepping with $O(1)$ incremental parity updates).
meryemPer generates all $n!$ permutations in lexicographic order in $O(n \cdot n!)$ total time. It builds the complete list layer by layer: for each possible first element, it remaps the previous layer's permutations onto the remaining elements. No sorting, no reversal, no pivot scanning appears at any step — the lexicographic order emerges naturally from the construction.
The factorial tree (parallel structure). Every element of a layer is a pure function of one element of the previous layer — siblings never wait for each other. In the work–span model both subroutines have span $O(n)$ and parallelism $\Theta(n!)$. Measured on a single core with vectorized (NumPy) realizations: meryemPer generates all permutations $\approx 6\times$ faster than the C-implemented itertools chain; all 479,001,600 signs of $S_{12}$ in 0.19 seconds; and the exact vectorized $10 \times 10$ determinant runs 15× faster than SJT, the fastest serial chain method.

Why It Matters

The classical lexicographic approach costs $O(n^2 \cdot n!)$ total. berkeDet costs $O(n \cdot n!)$ — a factor of $n$ faster — matching the Steinhaus–Johnson–Trotter algorithm, the fastest non-lexicographic method, while keeping lexicographic order. And unlike every classical method, its structure is a tree rather than a chain, so it alone can exploit vector and parallel hardware.

berkeDet is the first method to combine the SJT-class total cost, lexicographic output order, and sublinear-span parallel structure in a single construction.

Comparison with Existing Methods

Method Tperm Tsign Total Lex. Sort-free Parallel
Naive lex. + inversion count $O(n \log n)$ $O(n^2)$ $O(n^2 \cdot n!)$ Yes No No
Narayana + inversion count $O(n)$ $O(n^2)$ $O(n^2 \cdot n!)$ Yes No* No
Narayana + merge-sort sign $O(n)$ $O(n \log n)$ $O(n \log n \cdot n!)$ Yes No* No
Narayana + $O(1)$ parity flip $O(n)$ $O(1)$ $O(n \cdot n!)$ Yes No* No
SJT + sign flip $O(n)$ $O(1)$ $O(n \cdot n!)$ No Yes No
Heap + bookkeeping $O(1)$ amort. $O(1)$ amort. $O(n!)$ No Yes No
berkeDet (this work) $O(n)$ amort. $O(1)$ amort. $O(n \cdot n!)$ Yes Yes Yes

*Narayana Pandita replaces sorting with suffix reversal — a non-trivial optimization that still requires per-step pivot scanning, swapping, and reversal.

Abstract (Version 3)

We introduce berkeDet, a dual iterative algorithm that evaluates the Leibniz determinant formula using two independent subroutines built exclusively from block replication and index-mapping operations. Both are compositional: each layer is a pure function of the previous layer, so every element of a layer can be computed independently. This yields three results. (1) Signs: meryemSign produces all $n!$ signs in $\Theta(n!)$ total time — amortized $O(1)$ per sign, no inversion counting; isolated measurements show ~100× over inversion counting, 350–400× over merge parity, and 15–18× over the strongest classical baseline. (2) Permutations: meryemPer produces all $n!$ permutations in lexicographic order in $O(n \cdot n!)$ with no sorting, reversal, or scanning, matching the SJT bound while preserving lexicographic order. (3) Parallelism: both subroutines have span $O(n)$ (parallelism $\Theta(n!)$) while chain generators have critical path $\Omega(n!)$; vectorized realizations confirm it empirically. Correctness is proved by induction, verified exhaustively through order 10 (signs) and order 9 (permutations), and validated numerically through order 10. Full details in the Version 3 paper (DOI: 10.5281/zenodo.21326563).

Scope and Applicability

Like all Leibniz-based methods, berkeDet has factorial time complexity and is intended for exact determinant computation of small to moderate matrices, symbolic algebra, and educational contexts — not as a replacement for $O(n^3)$ numerical methods such as LU decomposition. The contribution is the most efficient known implementation of the Leibniz formula in lexicographic order — without sorting, reversal, or per-permutation sign computation — and the only one whose structure admits vector and parallel execution.

Lexicographic order supports reproducible testing, canonical ordering in symbolic algebra, teaching, and rank-partitioned distributed evaluation of the Leibniz sum — now backed by the span-$O(n)$ analysis.

Verification

Signs verified element-by-element through order 10 (all 3,628,800 at $n = 10$, three independent ways); permutations verified row-by-row through order 9, with random-rank spot checks beyond; determinants exact against numpy.linalg.det through order 10. All scripts are on the Resources page.

View the Algorithm →     View Resources →     View Timeline →

♥ Support This Research ♥