Division-free signed matching-sum Pfaffian
DefinitionDetSupportRank_DeterminantSupport_Supplement_Pfaffianalgebracombinatoricsdeterminantsupportp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For an even-order matrix , take all partitions of the ordered indices into pairs. Orient each pair increasingly, order the pairs by first endpoint, and let be the resulting concatenated permutation. Define
Canonical permutations encode these pair partitions exactly once. No factorial or power of two is inverted. The empty Pfaffian is one, and odd-order inputs are assigned zero, as their perfect-matching set is empty. The source applies this construction to alternating matrices. The same definition works over a field and its formal polynomial ring.
Definition code
import Mathlib
noncomputable section
open scoped BigOperators
namespace DetSupportRank.DeterminantSupport.Supplement
/-- Canonical ordered pair partitions, represented without multiplicity by permutations.
Pairs occupy positions (0,1),(2,3),...; their first endpoints increase. Formula (3), p.9. -/
def IsMatchingPermutation {n : ℕ} (σ : Equiv.Perm (Fin n)) : Prop :=
(∀ (i : Fin n), i.val % 2 = 0 → ∀ h : i.val + 1 < n,
σ i < σ ⟨i.val + 1, h⟩) ∧
(∀ (i j : Fin n), i.val % 2 = 0 → j.val % 2 = 0 → i < j → σ i < σ j)
/-- Division-free signed matching sum (3). Empty Pfaffian is 1; odd order is 0. -/
def pfaffian {R : Type*} [CommRing R] {n : ℕ}
(A : Matrix (Fin n) (Fin n) R) : R := by
classical
exact if Even n then
∑ σ ∈ Finset.univ.filter IsMatchingPermutation,
(((Equiv.Perm.sign σ : ℤˣ) : ℤ) : R) *
∏ i ∈ Finset.univ.filter (fun i : Fin n => i.val % 2 = 0),
if h : i.val + 1 < n then A (σ i) (σ ⟨i.val + 1, h⟩) else 0
else 0
end DetSupportRank.DeterminantSupport.Supplement
Source
Neil Krishnan, Guy Moshkovitz, Optimal partition rank bounds for the determinant and other multilinear polynomials, STOC 2027 submission #631 (October 2026), §4.1, equation (3) and empty-matrix convention, p. 9 (PDF p. 9); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/631.pdf