Lemma 6.7 — for an oriented tree
ProvedInfoLossLAR.WorstCase.lemma_6_7determinantgraph-theoryincidence-matrixp2o-gran-per-chapterp2o-plan-bookp2o-v1
For every oriented tree on vertices with signed incidence matrix and every integer column ,
Differences from the source:
- encoding: the columns of in the paper's order → in an arbitrary order given by a bijection from (edges one extra column) to ; reason: does not depend on the column order, and the paper does not fix one
Preamble
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_FixedT set_option autoImplicit false
Formal statement
namespace InfoLossLAR.WorstCase
/-- Lemma 6.7 (Determinant of an extended tree incidence matrix), p. 28: for every oriented
tree `𝒯` on the `d` vertices `Fin d` and every `v ∈ ℤ^d`, `|det[D_𝒯 | v]| = |1ᵀv|`. The `d`
columns (the `d − 1` edge columns and `v`) are put in an arbitrary order `σ`; the absolute value
of the determinant does not depend on it. -/
theorem lemma_6_7 (d : ℕ) (𝒯 : OrientedTree d) (v : Fin d → ℤ)
(σ : 𝒯.G.edgeSet ⊕ Unit ≃ Fin d) :
|((𝒯.extended v).submatrix id σ.symm).det| = |∑ i, v i| := by sorry
end InfoLossLAR.WorstCase
Source
Chen Qian, Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices, arXiv:2611.05136 (held version, sha256 2ebdfbf3…), p. 28, Lemma 6.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.