Dense and sparse alternating matrices and aligned subsets
DefinitionDetSupportRank_DeterminantSupport_Supplement_SpecialMatricesalgebracombinatoricsdeterminantsupportp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let have zero diagonal, entries one above the diagonal, and minus one below. Let be the direct sum of adjacent blocks when is even. A subset is aligned precisely when it is a union of whole adjacent blocks:
These are explicit matrices and subsets, without assuming their Pfaffian values. At order zero both matrices and the aligned empty union are included. A total odd-order sparse matrix has an unused zero last row and column; all statements about the whole matrix assume even order.
Definition code
import Mathlib
noncomputable section
open scoped BigOperators
namespace DetSupportRank.DeterminantSupport.Supplement
/-- Dense alternating matrix K_n on p.11. -/
def denseK (R : Type*) [Zero R] [One R] [Neg R] (n : ℕ) : Matrix (Fin n) (Fin n) R :=
fun i j => if i < j then 1 else if j < i then -1 else 0
/-- Sparse alternating matrix L_n on p.12. Adjacent pairs are (0,1),(2,3),... . -/
def sparseL (R : Type*) [Zero R] [One R] [Neg R] (n : ℕ) : Matrix (Fin n) (Fin n) R :=
fun i j => if i.val / 2 = j.val / 2 then denseK R n i j else 0
/-- One complete adjacent column block, with b ranging from 0 to n/2-1. -/
def adjacentBlock {n : ℕ} (b : Fin (n / 2)) : Finset (Fin n) :=
Finset.univ.filter (fun j => j.val = 2 * b.val ∨ j.val = 2 * b.val + 1)
/-- A subset is a union of complete adjacent blocks, p.12. -/
def IsAligned {n : ℕ} (J : Finset (Fin n)) : Prop :=
∃ B : Finset (Fin (n / 2)), J = B.biUnion adjacentBlock
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.2, dense matrix K_n and sparse matrix L_n, p. 11–12 (PDF p. 11–12); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/631.pdf