§2.6, p.19 (Preserving the representation) — the exchange (AR) keeps the auxiliary matrix invertible
ProvedAffDisp4n.exchange_matrix_invertibleaffine-disperserscircuit-complexitycircuit-lower-boundsgate-eliminationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be invertible, let , and let be an index with . Then the matrix obtained from by replacing its -th column with is invertible:
In the exchange (AR), is the column of the parameter in and is the column of the auxiliary variable . The hypothesis says that depends on . The lemma keeps the fairness condition after the exchange.
Differences from the source:
- generalization: ν = Nₓ, the column of the parameter x in the parameter matrix N → an arbitrary vector ν ∈ 𝔽₂ʳ; reason: the argument (A′ = AB, det B = tⱼ) uses nothing about ν except (A⁻¹ν)ⱼ = 1; taking ν = Nₓ gives the paper's statement
Preamble
import Mathlib
Formal statement
namespace AffDisp4n
/-- **The auxiliary matrix stays invertible under the exchange (AR)** (Mishra–Santhanam, *An Explicit 4n−O(log(n)) Size Lower Bound against General Boolean Circuits*, STOC 2027 submission (manuscript sha256 6bc3ff9d…), §2.6 "Preserving the
representation", p.19): "let j be the column index of Q, let Nₓ be the column of x in N, and let
t = A⁻¹Nₓ … Since A′ is obtained from A by replacing its jth column with Nₓ, we have A′ = AB, where B is
the identity matrix with its jth column replaced by t. As det B = tⱼ = 1, the matrix A′ is invertible."
Over `𝔽₂`: if `A` is invertible and `(A⁻¹ ν)ⱼ = 1`, then `A` with its `j`th column replaced by `ν` is
invertible. -/
theorem exchange_matrix_invertible {r : ℕ} (A : Matrix (Fin r) (Fin r) (ZMod 2)) (hA : IsUnit A.det)
(ν : Fin r → ZMod 2) (j : Fin r) (hj : (A⁻¹.mulVec ν) j = 1) :
IsUnit (A.updateCol j ν).det := by sorry
end AffDisp4n
Source
Mishra, Santhanam, An Explicit 4n−O(log(n)) Size Lower Bound against General Boolean Circuits, STOC 2027 submission (manuscript sha256 6bc3ff9d…fd96), §2.6, p.19, paragraph "Preserving the representation"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.