Lemma 2.3 — determinant of a diagonal matrix plus a matrix
ProvedBipHamCount.Deterministic.lemma_2_3countingexact-algorithmsgraph-theorylinear-algebrap2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a commutative ring and any finite ordered set. Let be a square matrix on , and let be diagonal with entries . Then
All empty determinants and products are one. In particular the identity applies over , the coefficient ring required by the paper's determinant polynomial. This is the principal-minor expansion used to identify its coefficients.
Differences from the source:
- encoding: finite ordered vertex and side sets → finite types with linear orders, with Fin m as the zero-based ordered side; reason: every finite ordered set admits this relabelling; the minor factors use identical increasing orders
- generalization: the matrix identities in the paper scalar setting (also used over ℤ[x] on p.9) → the identity over every commutative ring; reason: the identity is polynomial in the matrix entries and specializes to both ℤ and ℤ[x]
Preamble
import Mathlib import Definitions.Def_BipHamCount_Deterministic_Core open scoped BigOperators
Formal statement
namespace BipHamCount.Deterministic
/-- Lemma 2.3 p.5. The coefficient ring includes ℤ[x], used on p.9.
The empty minor and empty product both equal one. -/
theorem lemma_2_3 {R K : Type*} [CommRing R] [Fintype K] [LinearOrder K]
(C : Matrix K K R) (d : K → R) :
(Matrix.diagonal d + C).det = ∑ I ∈ (Finset.univ : Finset K).powerset,
minor C I I * ∏ i ∈ Iᶜ, d i := by sorry
end BipHamCount.Deterministic
Source
Koana, Kumabe, Counting Hamiltonian Cycles in Bipartite Digraphs Deterministically in O(1.9526^n) Time, STOC 2027 submission #814 (October 2026), Lemma 2.3, p. 5. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/814.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.