\documentclass[11pt,a4paper]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsmath} \usepackage{mathtools} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsthm} \usepackage{enumitem} \usepackage{booktabs} \usepackage[margin=2.5cm]{geometry} \usepackage{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}{Definition} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{observation}[theorem]{Observation} \title{berkeDet: A Dual Iterative Algorithm for Exact Determinant Computation via Block Replication and Index Mapping} \author{Berke G\"{u}lmen\textsuperscript{1} \and Meryem G\"{u}lmen\textsuperscript{1} \and \"{O}mer G\"{u}lmen\textsuperscript{1,*}} \date{26 February 2026 (Version 3: July 2026)} \begin{document} \maketitle \noindent\textsuperscript{1}Independent Researcher\\ \textsuperscript{*}Corresponding author: gulmenberkemeryem@gmail.com\\ Website: https://detsignper.org \medskip \begin{abstract} We introduce \textbf{berkeDet}, a dual iterative algorithm that evaluates the Leibniz determinant formula using two independent subroutines: \textit{meryemSign}, which produces the complete list of permutation signs in lexicographic order, and \textit{meryemPer}, which produces the corresponding permutations. Both subroutines are built exclusively from block replication and index-mapping operations, and both are \emph{compositional}: each layer of the construction is a pure function of the previous layer, so every element of a layer can be computed independently. This yields three results. \textbf{(1) Signs.} meryemSign produces all $n!$ signs in $\Theta(n!)$ total time---amortized $O(1)$ per sign with no inversion counting; in isolated measurements it outperforms per-permutation inversion counting by roughly $100\times$, merge-based parity by $350$--$400\times$, and even the strongest classical baseline (lexicographic stepping with $O(1)$ incremental parity updates) by $15$--$18\times$. \textbf{(2) Permutations.} meryemPer produces all $n!$ permutations in lexicographic order in $O(n \cdot n!)$ total time with no sorting, no reversal, and no pivot scanning; the combined algorithm matches the Steinhaus--Johnson--Trotter bound while preserving lexicographic order. \textbf{(3) Parallelism.} In the work--span model both subroutines have span $O(n)$, giving parallelism $\Theta(n!)$, whereas incremental chain generators have critical path $\Omega(n!)$ by construction. A vectorized realization confirms this empirically: it generates all permutations up to $6\times$ faster than the C-implemented \texttt{itertools} chain, produces all $479{,}001{,}600$ signs of $S_{12}$ in $0.19$ seconds, and evaluates the exact $10 \times 10$ Leibniz determinant $15\times$ faster than the fastest serial chain method. Correctness is proved by induction and verified exhaustively (element-by-element through order 10 for signs, order 9 for permutations) and numerically through order 10 against LU-based computation. \end{abstract} \medskip \noindent\textbf{Keywords:} determinant, Leibniz formula, permutation generation, lexicographic order, sign function, data parallelism \noindent\textbf{MSC2020:} 05A05, 15A15, 68W05, 68W10 \section{Introduction} The determinant is a fundamental quantity in linear algebra and appears throughout science and engineering: it characterizes invertibility, measures the volume scaling of a linear transformation, and determines orientation. For numerical work on large matrices, $O(n^3)$ methods based on LU decomposition are standard. Nevertheless, the \emph{Leibniz formula} \begin{equation}\label{eq:leibniz} \det(\mathbf{A}) \;=\; \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^{n} a_{i,\sigma(i)} \end{equation} retains an important role in exact and symbolic computation, in theoretical analysis, and in teaching, because it expresses the determinant directly as a signed sum over all $n!$ permutations. Evaluating \eqref{eq:leibniz} directly requires two ingredients: the complete sequence of permutations of $\{1, \ldots, n\}$, and the sign of each. When the permutations are required in lexicographic order, the classical toolkit imposes per-step costs at both ingredients: \begin{enumerate}[nosep] \item \emph{Permutation advancement.} The naive method of stepping to the next lexicographic permutation sorts a suffix at $O(n \log n)$ per step. The Narayana Pandita procedure (the basis of \texttt{std::next\_permutation}) avoids the sort by observing that the suffix is always in descending order, so a reversal suffices; but the procedure still scans for a pivot, scans for a successor, swaps, and reverses at every step. The reversal insight is an optimization discovered on top of the naive method, not a property of the problem itself. \item \emph{Sign computation.} The standard method computes $\operatorname{sgn}(\sigma)$ independently for each permutation by counting inversions, at $O(n^2)$ per permutation (or $O(n \log n)$ with a merge-sort variant). \end{enumerate} The total cost of the standard lexicographic Leibniz evaluation is therefore $O(n^2 \cdot n!)$. Beyond these per-step costs lies a deeper structural limitation. All classical generators---the lexicographic steppers as well as the swap-based Steinhaus--Johnson--Trotter (SJT) and Heap methods---are \emph{incremental chains}: each permutation is computed \emph{from the value of} its predecessor. A chain's critical path has length $n!$; no amount of hardware can shorten it. On vector and parallel hardware, which rewards large numbers of identical independent operations, chains cannot participate at all. This paper introduces \textbf{berkeDet}, whose two subroutines share a single design principle: \emph{build the complete list for $S_n$ from the complete list for $S_{n-1}$ by block replication and index remapping, rather than deriving each item from its predecessor}. \begin{itemize}[nosep] \item \textbf{meryemSign}$(n)$ produces all $n!$ signs in lexicographic order in $\Theta(n!)$ total time, amortized $O(1)$ per sign, using only block replication and sign flips. No inversion is ever counted. \item \textbf{meryemPer}$(n)$ produces all $n!$ permutations in lexicographic order in $O(n \cdot n!)$ total time, using only block replication and index mapping. No sorting, no reversal, and no pivot scanning occur at any step; lexicographic order emerges from the construction itself. \end{itemize} The contributions of this paper are threefold: \begin{enumerate}[nosep] \item \textbf{Elimination of per-permutation sign computation.} We prove that meryemSign is correct and runs in $\Theta(n!)$ total time (Section~\ref{sec:algorithm}), and we measure the component in isolation (Section~\ref{sec:bench-sign}): it outperforms inversion counting by roughly $100\times$, merge-based parity by $350$--$400\times$, and---decisively---the strongest classical baseline, a lexicographic stepper with $O(1)$ incremental parity updates, by $15$--$18\times$. \item \textbf{Sort-free lexicographic enumeration at the SJT bound.} The combined algorithm evaluates \eqref{eq:leibniz} in $O(n \cdot n!)$ time, matching SJT---previously the fastest complete-enumeration method---while preserving lexicographic order, which SJT does not provide (Sections~\ref{sec:algorithm}, \ref{sec:bench-serial}). \item \textbf{Inherent data parallelism.} We show that the construction is a factorial tree in which every element of a layer is a pure function of one element of the previous layer; in the work--span model both subroutines have span $O(n)$ and parallelism $\Theta(n!)$, whereas the chain strategy has critical path $\Omega(n!)$ (Section~\ref{sec:parallel}). A vectorized realization confirms the gap empirically, outperforming even the C-implemented \texttt{itertools} chain by $\approx 6\times$ and evaluating the exact vectorized determinant $15\times$ faster than the fastest serial chain method (Section~\ref{sec:bench-vector}). \end{enumerate} \section{Related Work}\label{sec:related} \subsection{Lexicographic permutation generation} The problem of listing the permutations of $\{1, \ldots, n\}$ in lexicographic order is classical. The \emph{naive} incremental method finds, in the current permutation, the rightmost position whose value can be increased, installs the next-larger available element there, and then \emph{sorts} the remaining suffix ascending; the sort costs $O(n \log n)$ per step. \emph{Narayana Pandita's algorithm} (14th century; the modern \texttt{std::next\_permutation}) improves the naive method with the observation that the suffix in question is always in strictly descending order, so the sort may be replaced by a reversal. Each step then consists of: a right-to-left scan for the pivot $i$ (the rightmost $i$ with $\sigma(i) < \sigma(i{+}1)$); a scan for the smallest suffix element exceeding $\sigma(i)$; a swap; and a suffix reversal. The per-step cost is $O(n)$ worst case, and $O(1)$ amortized over the full enumeration. The method is \emph{incremental}: each permutation is derived in place from its predecessor. \subsection{Non-lexicographic generators} The \emph{Steinhaus--Johnson--Trotter} (SJT) algorithm generates each successive permutation by a single adjacent transposition. Since one adjacent transposition changes the sign, SJT admits $O(1)$ sign tracking, which makes it the classical method of choice for Leibniz evaluation. Its enumeration order, however, is not lexicographic. \emph{Heap's algorithm} similarly produces each permutation by one swap in $O(1)$ amortized time, again in non-lexicographic order. \subsection{Sign computation} Given a single permutation, the standard sign computation counts inversions: $O(n^2)$ directly, or $O(n \log n)$ via merge sort. Applied independently to all $n!$ permutations, the sign computation alone costs $O(n^2 \cdot n!)$ or $O(n \log n \cdot n!)$. A stronger classical baseline deserves explicit mention, since we will benchmark against it. Along a Narayana Pandita enumeration, the parity change of each step can be derived from the step's own structure: the pivot swap is one transposition, and reversing a suffix of length $L$ is $\lfloor L/2 \rfloor$ transpositions, so the sign flips if and only if $1 + \lfloor L/2 \rfloor$ is odd. This yields lexicographically ordered signs at $O(1)$ update cost per step, on top of the stepping cost itself. To our knowledge this is the best sign facility available to classical lexicographic enumeration, and we adopt it as the strongest baseline in Section~\ref{sec:bench-sign}. \subsection{Position of the present work} berkeDet closes the gap in the last cell of this landscape: it attains the $O(n \cdot n!)$ total of the swap-based methods \emph{and} the lexicographic order of the classical generators, without inheriting either family's per-step machinery---no inversion counting, no pivot scanning, no swapping, no sorting, no reversal---and, unlike every method above, it is not a chain (Section~\ref{sec:parallel}). Table~\ref{tab:comparison} summarizes. \begin{table}[ht] \centering \caption{Complete-enumeration Leibniz implementations. $T_{\text{perm}}$: cost per permutation step. $T_{\text{sign}}$: cost per sign. ``Lex.'': lexicographic output order. ``Sort-free'': neither sorting nor suffix reversal. ``Parallel'': admits sublinear-span execution (Section~\ref{sec:parallel}).} \label{tab:comparison} \smallskip \begin{tabular}{@{}lcccccc@{}} \toprule \textbf{Method} & $T_{\text{perm}}$ & $T_{\text{sign}}$ & \textbf{Total} & \textbf{Lex.} & \textbf{Sort-free} & \textbf{Parallel} \\ \midrule 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\textsuperscript{$\dagger$} & No \\ Narayana + merge-sort sign & $O(n)$ & $O(n \log n)$ & $O(n \log n \cdot n!)$ & Yes & No\textsuperscript{$\dagger$} & No \\ Narayana + $O(1)$ parity flip & $O(n)$ & $O(1)$ & $O(n \cdot n!)$ & Yes & No\textsuperscript{$\dagger$} & No \\ SJT + sign flip & $O(n)$ & $O(1)$ & $O(n \cdot n!)$ & No & Yes & No \\ Heap + bookkeeping & $O(1)$ am. & $O(1)$ am. & $O(n!)$ & No & Yes & No \\ \textbf{berkeDet (this work)} & $O(n)$ am. & $O(1)$ am. & $O(n \cdot n!)$ & \textbf{Yes} & \textbf{Yes} & \textbf{Yes} \\ \bottomrule \end{tabular} \smallskip {\footnotesize\textsuperscript{$\dagger$}Suffix reversal replaces the sort but per-step pivot scanning, swapping, and reversal remain.} \end{table} \section{The berkeDet Algorithm}\label{sec:algorithm} \subsection{Notation and outline} Write $S_n$ for the symmetric group on $\{1, \ldots, n\}$ and $\operatorname{sgn}(\sigma) = (-1)^{\operatorname{inv}(\sigma)}$, where $\operatorname{inv}(\sigma)$ is the number of inversions of $\sigma$. Given an $n \times n$ matrix $\mathbf{A} = (a_{ij})$, berkeDet evaluates \eqref{eq:leibniz} in four steps: \begin{enumerate}[nosep] \item $\mathbf{s} \leftarrow \operatorname{meryemSign}(n)$ \hfill ($n!$ signs, lexicographic order) \item $\mathbf{P} \leftarrow \operatorname{meryemPer}(n)$ \hfill ($n!$ permutations, lexicographic order) \item $\operatorname{pair}(i) \leftarrow s_i \cdot \prod_{j=1}^{n} a_{j,\,P_i(j)}$ for $i = 1, \ldots, n!$ \item return $\sum_{i=1}^{n!} \operatorname{pair}(i)$ \end{enumerate} Correctness of berkeDet reduces to Theorems~\ref{thm:sign} and~\ref{thm:perm} below, which state that the two lists are correct and aligned. \subsection{meryemSign: signs by block replication} \begin{theorem}\label{thm:sign} The following procedure outputs $\big(\operatorname{sgn}(\sigma_1), \ldots, \operatorname{sgn}(\sigma_{n!})\big)$, where $\sigma_1, \ldots, \sigma_{n!}$ is the lexicographic listing of $S_n$: \begin{enumerate}[nosep] \item $b \leftarrow [+1]$. \item For $e = 1, \ldots, n-1$:\; set $c \leftarrow b$; then for $d = 0, \ldots, e-1$: append to $b$ the block $-c$ if $d$ is even, or the block $c$ if $d$ is odd. \end{enumerate} \end{theorem} \begin{proof} Induction on $n$. For $n = 1$ the output $[+1]$ is the sign of the identity. Assume the procedure is correct for $S_{n-1}$; consider layer $e = n - 1$. List $S_n$ lexicographically and group by first element: the $k$-th group ($k = 1, \ldots, n$) contains the $(n-1)!$ permutations beginning with $k$, ordered lexicographically among themselves, and the groups appear in the order $k = 1, 2, \ldots, n$. Let $\sigma = (k, \tau_1, \ldots, \tau_{n-1})$ be in group $k$, and let $\tau \in S_{n-1}$ be the standardization of $(\tau_1, \ldots, \tau_{n-1})$ (relabel the elements of $\{1,\ldots,n\} \setminus \{k\}$ order-preservingly to $\{1, \ldots, n-1\}$). Standardization preserves the relative order of every pair, hence preserves the inversion count among positions $2, \ldots, n$. The element $k$ in position 1 contributes exactly $k - 1$ additional inversions (one for each smaller element, all of which lie to its right). Therefore \[ \operatorname{sgn}(\sigma) = (-1)^{k-1}\operatorname{sgn}(\tau). \] Moreover, as $\sigma$ runs lexicographically over group $k$, the standardization $\tau$ runs lexicographically over $S_{n-1}$, because standardization is an order-preserving bijection on suffixes. So the correct sign list for $S_n$ is: the sign list of $S_{n-1}$ (group $k = 1$, factor $(-1)^0 = +1$), followed by that list multiplied by $(-1)^{k-1}$ for $k = 2, \ldots, n$. The procedure appends, after the initial list, blocks indexed $d = 0, \ldots, n-2$ corresponding to $k = d + 2$, negated when $d$ is even. Since $(-1)^{k-1} = (-1)^{d+1}$ equals $-1$ exactly when $d$ is even, the appended blocks carry the correct factors. This completes the induction. \end{proof} \begin{proposition}\label{prop:sign-complexity} meryemSign performs $\Theta(n!)$ elementary operations in total; the amortized cost per sign is $O(1)$. \end{proposition} \begin{proof} Layer $e$ appends $e$ blocks of size $(e{-}1)!$ each, i.e.\ $e!$ writes (each write a copy or a negation). The total over all layers is $\sum_{e=1}^{n-1} e!$, which is $\Theta\big((n-1)!\big)$ since the last term dominates; together with writing the final $n!$-length list once across the layers, the total work is $\Theta(n!)$. Dividing by the $n!$ outputs gives $O(1)$ amortized. \end{proof} \subsection{meryemPer: permutations by block replication and index mapping} \begin{theorem}\label{thm:perm} The following procedure outputs all $n!$ permutations of $\{1, \ldots, n\}$ in lexicographic order: \begin{enumerate}[nosep] \item $a \leftarrow [[1]]$. \item For $b = 2, \ldots, n$: let $c = [1, \ldots, b]$ and $d \leftarrow$ empty. For each $f \in c$ in increasing order: let $g = c \setminus \{f\}$ (increasing); for each $h \in a$ in order, append $[f] \circ [\,g[h_1], g[h_2], \ldots, g[h_{b-1}]\,]$ to $d$ (indices into $g$ are 1-based). Set $a \leftarrow d$. \end{enumerate} \end{theorem} \begin{proof} Induction on $n$. For $n = 1$ the output is $[[1]]$. Assume $a$ lists $S_{n-1}$ lexicographically at the start of layer $b = n$. Fix a first element $f$. The map $h \mapsto (g[h_1], \ldots, g[h_{n-1}])$ sends a permutation $h$ of positions $\{1, \ldots, n-1\}$ to the permutation of the set $g$ obtained by arranging $g$'s elements according to $h$. Because $g$ is listed increasingly, this map is a bijection from $S_{n-1}$ onto the permutations of $g$, and it is \emph{order-preserving} with respect to lexicographic order: if $h < h'$ lexicographically and they first differ at position $t$, then $h_t < h'_t$, hence $g[h_t] < g[h'_t]$ (as $g$ is increasing), so the images first differ at position $t$ in the same direction. Therefore, for fixed $f$, the appended permutations are exactly the lexicographic listing of all permutations beginning with $f$. Since $f$ runs over $1, \ldots, n$ in increasing order, and every permutation beginning with a smaller first element precedes every permutation beginning with a larger one, the full output is the lexicographic listing of $S_n$. \end{proof} \begin{remark}[Structural contrast with incremental generators]\label{rem:contrast} Classical lexicographic generators are \emph{incremental}: each permutation is produced by modifying its predecessor in place, which forces per-step pivot scans and suffix repair (sorting in the naive method; reversal in Narayana Pandita's optimization). meryemPer is \emph{compositional}: the entire layer-$b$ list is assembled from the layer-$(b{-}1)$ list by replication and index remapping. There is no predecessor to repair, hence no scan, no swap, no sort, and no reversal at any step; lexicographic order is a consequence of the order-preserving remapping (proof of Theorem~\ref{thm:perm}), not of an optimization applied to a naive procedure. Section~\ref{sec:parallel} shows this contrast is not cosmetic: it separates the two families in parallel complexity. \end{remark} \begin{proposition}\label{prop:perm-complexity} meryemPer performs $O(n \cdot n!)$ elementary operations in total; the amortized cost per permutation is $O(n)$. The space requirement is $\Theta(n \cdot n!)$. \end{proposition} \begin{proof} Layer $b$ writes $b!$ permutations of length $b$, at cost $O(b)$ each including the remapping, i.e.\ $O(b \cdot b!)$ per layer. Summing, $\sum_{b=2}^{n} b \cdot b! = O(n \cdot n!)$ since the final term dominates. Output length is $n \cdot n!$ entries, which also bounds space up to a constant (only the current and previous layers are retained). \end{proof} \begin{corollary}\label{cor:total} berkeDet evaluates the Leibniz formula in $O(n \cdot n!)$ time and $\Theta(n \cdot n!)$ space. \end{corollary} \begin{proof} Steps 1--2 cost $\Theta(n!)$ and $O(n \cdot n!)$ by Propositions~\ref{prop:sign-complexity} and~\ref{prop:perm-complexity}. Step 3 computes $n!$ products of $n$ factors: $O(n \cdot n!)$. Step 4 is $O(n!)$. \end{proof} \section{Parallel Structure}\label{sec:parallel} \subsection{The factorial tree} The construction of Theorem~\ref{thm:perm} is a layered tree. Layer 1 contains the single node $[1]$; every node of layer $b-1$ spawns exactly $b$ children in layer $b$, one per choice of first element $f$, so layer $b$ contains $b!$ nodes and the branching factor at level $b$ is $b$. The decisive property is \emph{locality of the child rule}: the child at global rank $r$ of layer $b$ is determined by two integers alone, \[ f = \left\lfloor r / (b-1)! \right\rfloor, \qquad r' = r \bmod (b-1)!, \] and equals $[f{+}1] \circ$ (the order-preserving relabeling of the layer-$(b{-}1)$ node at rank $r'$). No sibling reads another sibling's output; no shared state exists within a layer. The same holds for meryemSign, where block $k$ of layer $e$ is $(-1)^{k-1}$ times the previous list. \subsection{Work and span} We use the standard work--span model: \emph{work} $W$ is the total operation count, \emph{span} $D$ is the length of the critical path with unlimited processors, and \emph{parallelism} is $W/D$. \begin{proposition}\label{prop:span} At cell granularity, meryemPer has work $W = O(n \cdot n!)$ and span $D = O(n)$; meryemSign has work $W = \Theta(n!)$ and span $D = O(n)$. Consequently both have parallelism $\Theta(n!)$ up to a factor $n$. \end{proposition} \begin{proof} For meryemPer, cell $(r, j)$ of layer $b$ (the $j$-th entry of the rank-$r$ permutation) is a pure function of at most one cell of layer $b-1$: it equals $f$ if $j = 1$, and otherwise $g_f[\,A_{b-1}(r', j-1)\,]$, where $A_{b-1}$ is the previous layer and $f, r'$ are the integers above (computable from $r$ in $O(1)$ given $(b-1)!$). With unlimited processors, all cells of layer $b$ are computed in $O(1)$ parallel time; there are $n - 1$ layers, so $D = O(n)$. Work is Proposition~\ref{prop:perm-complexity}. For meryemSign, every entry of layer $e$ is a copy or negation of one entry of the previous list, so each layer has depth $O(1)$ and $D = O(n)$; work is Proposition~\ref{prop:sign-complexity}. \end{proof} \begin{observation}[Chains are inherently serial]\label{obs:chain} Every incremental generator discussed in Section~\ref{sec:related} computes permutation $r+1$ as a function of the \emph{value} of permutation $r$ (Narayana: pivot scan of the current array; SJT and Heap: a swap applied to the current array; the $O(1)$ parity flip: a function of the current step). Under this strategy the $n!$ outputs form a dependency chain, so the critical path is $\Omega(n!)$ regardless of processor count and regardless of implementation language. The limitation is a property of the enumeration \emph{strategy}, not of any particular code. \end{observation} \begin{remark}[Consequences] Two practical consequences follow. \emph{(i) Vector execution.} Each layer of meryemPer is realized by $b$ independent bulk gathers $g_f[A_{b-1}]$ over the whole previous layer, and each layer of meryemSign by bulk negations/copies---exactly the workload SIMD units, GPUs, and array runtimes are built for. Chains offer such hardware nothing to do. Section~\ref{sec:bench-vector} quantifies this. \emph{(ii) Rank partitioning.} Because the Leibniz sum over any lexicographic rank interval can be assigned to a worker, and Proposition~\ref{prop:span} lets each worker materialize its blocks independently, the full evaluation parallelizes across machines along rank boundaries. \end{remark} \section{Correctness Verification}\label{sec:verification} All verification described below was executed; the scripts are published on the project website. \textbf{Signs (exhaustive through order 10).} For every $n \le 10$, the output of meryemSign$(n)$ was compared element-by-element against direct inversion counting on the independently generated lexicographic listing of $S_n$; for $7 \le n \le 10$ it was additionally compared, element-by-element, against the sign sequence produced by the Narayana stepper with $O(1)$ parity updates. All comparisons matched exactly, including all $3{,}628{,}800$ signs at $n = 10$. At $n = 11$ and $n = 12$, checksums (sign sum $0$; exactly $n!/2$ positive) and $200$ random-rank spot checks per order (rank decoded via the factorial number system, sign recomputed by inversion counting) all passed. \textbf{Permutations (exhaustive through order 9).} For every $n \le 9$, the output of meryemPer$(n)$---in both its serial and vectorized realizations---was compared row-by-row against the independently generated lexicographic enumeration; all rows matched. At $n = 10$ and $n = 11$, $200$ random-rank spot checks per order (factoradic decoding of the $k$-th lexicographic permutation) all passed. \textbf{Determinants (through order 10).} For each $n \le 10$, berkeDet's exact integer output on a pseudorandom integer matrix (fixed seed) matched LU-based floating-point computation (\texttt{numpy.linalg.det}) to within $4.3 \times 10^{-15}$ relative error---i.e., to floating-point rounding; berkeDet's integer results are exact. In every benchmark of Section~\ref{sec:benchmarks}, all competing implementations were asserted to return identical values on every instance, and the vectorized determinant was asserted equal to the serial exact value at $n = 10$. \section{Benchmarks}\label{sec:benchmarks} \textbf{Environment.} All measurements: Intel Xeon @ 2.10 GHz, single core; Python 3.12.3; NumPy 2.4.4 (vectorized runs only; SIMD within one core, no GPU); median of three runs; fixed seeds. Scripts and raw outputs are published at \texttt{https://detsignper.org}. \subsection{Component isolation: sign generation}\label{sec:bench-sign} We first isolate the sign problem: \emph{produce the signs of all $n!$ permutations in lexicographic order}. The streaming baselines are handed their permutations by the C-implemented \texttt{itertools.permutations} at negligible cost, so their measured time is essentially pure sign cost; the strongest baseline (Narayana + $O(1)$ parity flip, Section~\ref{sec:related}) inseparably includes its own stepping. meryemSign touches no permutations at all. \begin{table}[ht] \centering \caption{Sign generation only (seconds, pure Python, median of 3). All sequences cross-verified as in Section~\ref{sec:verification}.} \label{tab:signbench} \smallskip \begin{tabular}{@{}rrrrr@{}} \toprule $n$ & \textbf{meryemSign} & inv-count & merge-count & Narayana + $O(1)$ flip \\ \midrule 7 & \textbf{0.0002} & 0.0095 & 0.0337 & 0.0024 \\ 8 & \textbf{0.0012} & 0.0907 & 0.2822 & 0.0189 \\ 9 & \textbf{0.0095} & 0.9802 & 3.8015 & 0.1727 \\ 10 & \textbf{0.1116} & 11.3518 & 39.0508 & 1.7376 \\ 11 & \textbf{1.2724} & -- & -- & 18.7991 \\ \bottomrule \end{tabular} \end{table} At $n = 9$--$10$, meryemSign is roughly $100\times$ faster than per-permutation inversion counting and $350$--$400\times$ faster than merge-based parity. Against the strongest classical baseline it is $18.1\times$ faster at $n = 9$, $15.6\times$ at $n = 10$, and $14.8\times$ at $n = 11$. The margin over an opponent that also pays only $O(1)$ per sign is explained by granularity: the incremental method pays interpreter and control overhead \emph{per permutation}, whereas meryemSign pays it \emph{per block}, and blocks grow factorially---each block operation is a single bulk copy or negation. The compositional structure is inherently bulk; the chain is inherently per-item. \subsection{Serial end-to-end evaluation}\label{sec:bench-serial} We next compare four complete serial Leibniz evaluations, all in pure Python, each computing the determinant of the same pseudorandom integer matrix and all asserted to agree. \begin{table}[ht] \centering \caption{Full Leibniz determinant, serial pure Python (seconds, median of 3).} \label{tab:serialbench} \smallskip \begin{tabular}{@{}rrrrr@{}} \toprule $n$ & Naive lex + inv & Narayana + inv & SJT + flip & \textbf{berkeDet} \\ \midrule 6 & 0.0013 & 0.0011 & 0.0008 & \textbf{0.0005} \\ 7 & 0.0098 & 0.0102 & 0.0061 & \textbf{0.0036} \\ 8 & 0.0849 & 0.0784 & 0.0483 & \textbf{0.0338} \\ 9 & 0.9083 & 0.8225 & 0.4820 & \textbf{0.4291} \\ 10 & -- & -- & 5.2665 & 5.7925 \\ \bottomrule \end{tabular} \end{table} At $n = 9$, berkeDet is $2.1\times$ faster than the naive lexicographic evaluation and $1.9\times$ faster than the Narayana Pandita evaluation, consistent with the removal of the per-permutation sign cost. Against SJT---the same $O(n \cdot n!)$ class---berkeDet is marginally faster through $n = 9$ and marginally slower at $n = 10$ ($5.79$ s vs.\ $5.27$ s), a crossover attributable to serial materialization: berkeDet's $\Theta(n \cdot n!)$ working set interacts with the memory hierarchy at $10!$ items, whereas SJT holds one permutation. Section~\ref{sec:bench-vector} resolves the crossover: it is a property of the serial realization, not of the algorithm---the vectorized realization runs the same instance $15\times$ faster than SJT, and SJT has no vectorized realization to answer with (Observation~\ref{obs:chain}). \subsection{Vectorized execution: the parallel structure in practice}\label{sec:bench-vector} Finally we realize Proposition~\ref{prop:span} on commodity hardware, using NumPy on a single core as a stand-in vector processor: each layer of meryemPer becomes one bulk gather $g_f[A]$ per block; each layer of meryemSign becomes bulk negations/copies into a preallocated array. As opponents we take the serial paper implementation, the Narayana chain (Python), and---the strongest chain in existence---\texttt{itertools.permutations}, which is implemented in C, streamed into an ndarray. \begin{table}[ht] \centering \caption{Generation of all $n!$ permutations, lexicographic order (seconds, median of 3). Vectorized output verified as in Section~\ref{sec:verification}.} \label{tab:vecbench} \smallskip \begin{tabular}{@{}rrrrr@{}} \toprule $n$ & meryemPer serial & Narayana chain & itertools chain (C) & \textbf{meryemPer vectorized} \\ \midrule 8 & 0.0446 & 0.0312 & 0.0085 & \textbf{0.0016} \\ 9 & 0.4980 & 0.2872 & 0.0819 & \textbf{0.0135} \\ 10 & 6.0391 & 2.9344 & 0.8601 & \textbf{0.1334} \\ 11 & -- & 34.1425 & 10.2221 & \textbf{1.7461} \\ \bottomrule \end{tabular} \end{table} At $n = 10$--$11$ the vectorized meryemPer is $\approx 45\times$ faster than its own serial form, $\approx 20$--$22\times$ faster than the Python chain, and $5.9$--$6.4\times$ faster than the \emph{C-implemented} chain. The last figure is the empirical content of Observation~\ref{obs:chain}: implementation language cannot rescue a chain, because the chain offers the vector unit no independent work; the tree consists of nothing else. Vectorized meryemSign produces all $479{,}001{,}600$ signs of $S_{12}$ in $0.1866$ seconds (and the $n = 11$ list in $0.0168$ s, $39\times$ its serial form). The fully vectorized berkeDet, in exact \texttt{int64} arithmetic, evaluates a $10 \times 10$ determinant in $0.343$ s---asserted equal to the serial exact value, and $15.4\times$ faster than serial SJT on the same instance---and an $11 \times 11$ determinant in $6.22$ s, generation included. \section{Discussion}\label{sec:discussion} \subsection{The structural insight} Both subroutines rest on one fact: \emph{the lexicographic listing of $S_n$, and its sign sequence, are block-recursive in $S_{n-1}$.} For signs, the $k$-th block is the $S_{n-1}$ sign list multiplied by $(-1)^{k-1}$---so the whole list is built by replication and alternating flips. For permutations, the $k$-th block is the $S_{n-1}$ list pushed through an order-preserving relabeling---so the whole list is built by replication and index remapping. Incremental generators cannot see this structure because they only ever look at one permutation at a time; the compositional view makes the per-step machinery (scans, swaps, sorts, reversals, inversion counts) unnecessary rather than merely cheaper, and it converts the enumeration from a chain into a tree, which is the source of the parallelism of Section~\ref{sec:parallel}. \subsection{Why lexicographic order matters} Lexicographic order is the canonical enumeration order: it supports reproducible testing and debugging; it is the order symbolic algebra systems expect; it allows an enumeration range to be split at arbitrary rank boundaries for distributed evaluation of the Leibniz sum (now backed by Proposition~\ref{prop:span}); and it is the order in which the formula is taught. SJT's speed has historically come at the cost of abandoning this order; berkeDet shows the cost is not necessary, and the vectorized results show the lexicographic method can in fact be the faster one. \subsection{Scope and the memory trade-off} Every complete-enumeration determinant method is $\Omega(n!)$ and is therefore confined to small orders, symbolic computation, and pedagogy; LU-based $O(n^3)$ methods remain the tool of choice for numerical work at scale. Within the complete-enumeration class, berkeDet attains the best known total cost achievable with lexicographic output. Its trade-off is memory: the compositional construction materializes $\Theta(n \cdot n!)$ entries (about $5.7$ GB at $n = 12$ in 8-bit storage), whereas incremental chains hold $O(n)$. The rank-locality of the tree (Section~\ref{sec:parallel}) indicates that a streaming variant emitting fixed-size rank blocks without materializing the full list is achievable, and it is the natural next step, together with GPU realizations of the layer gathers and a formal treatment of distributed rank-partitioned evaluation. \section{Conclusion} berkeDet evaluates the Leibniz determinant formula in $O(n \cdot n!)$ time with lexicographic enumeration, by replacing the per-step machinery of classical methods with two block-recursive constructions: meryemSign (all signs, amortized $O(1)$ each, no inversion counting) and meryemPer (all permutations, no sorting, reversal, or scanning). Correctness is proved by induction and verified exhaustively through order 10 (signs) and order 9 (permutations), with numerical validation through order 10. Empirically, the isolated sign component outperforms every classical alternative---including the strongest, incremental $O(1)$-parity stepping, by $15$--$18\times$; the serial end-to-end algorithm improves inversion-count-based lexicographic evaluation by about $2\times$ and matches SJT; and the compositional structure, formalized as a factorial tree with span $O(n)$ against the chains' $\Omega(n!)$ critical path, yields a vectorized realization that outruns even C-implemented chain enumeration by $\approx 6\times$ and evaluates the exact vectorized determinant $15\times$ faster than the fastest serial chain method. To our knowledge, berkeDet is the first method to combine the SJT-class total cost, lexicographic output order, and sublinear-span parallel structure in a single construction. \section*{Acknowledgments} The writing of this manuscript was assisted by AI tools for \LaTeX{} formatting, structural organization, and exposition. The mathematical content, algorithms, and proofs are the original work of the authors. \appendix \section{Reference Implementation (Serial, Python)} \begin{verbatim} def meryemSign(n: int) -> list[int]: """All n! Leibniz signs in lexicographic order; +1/-1.""" b = [1] for e in range(1, n): c = b[:] for d in range(e): f = [-x for x in c] if d % 2 == 0 else c[:] b.extend(f) return b def meryemPer(n: int) -> list[list[int]]: """All n! permutations of {1..n} in lexicographic 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: d.append([f] + [g[i - 1] for i in h]) a = d return a def berkeDet(matrix: list[list[float]]) -> float: """Exact Leibniz determinant via meryemSign + meryemPer.""" n = len(matrix) det = 0 for s, p in zip(meryemSign(n), meryemPer(n)): prod = 1 for i in range(n): prod *= matrix[i][p[i] - 1] det += s * prod return det \end{verbatim} \section{Vectorized Implementation (NumPy)} Zero-based permutations; \texttt{g[A]} is the per-block bulk gather of Section~\ref{sec:parallel}. \begin{verbatim} import numpy as np, math def meryemPer_vec(n): A = np.zeros((1, 1), dtype=np.int8) for b in range(2, n + 1): prev = A.shape[0] # (b-1)! out = np.empty((b * prev, b), dtype=np.int8) base = np.arange(b, dtype=np.int8) for f in range(b): g = np.delete(base, f) blk = slice(f * prev, (f + 1) * prev) out[blk, 0] = f out[blk, 1:] = g[A] # bulk gather A = out return A def meryemSign_vec(n): out = np.empty(math.factorial(n), dtype=np.int8) out[0] = 1; size = 1 for e in range(1, n): c = out[:size]; pos = size for d in range(e): blk = out[pos:pos + size] if d % 2 == 0: np.negative(c, out=blk) else: blk[:] = c pos += size size = pos return out def berkeDet_vec(M64, P, S): """Exact int64 Leibniz determinant (entries kept small).""" n = M64.shape[0] acc = M64[0, P[:, 0]].copy() for i in range(1, n): acc *= M64[i, P[:, i]] acc *= S return int(acc.sum(dtype=np.int64)) \end{verbatim} \end{document}