Theorem 2.14 (Cauchy–Binet)
ProvedRSSubspaceDesign.theorem_2_14coding-theoryfinite-fieldslist-decodingp2o-gran-per-chapterp2o-plan-paperp2o-v1reed-solomon-codessubspace-designs
Let be a field and . For and ,
where the submatrices use the indicated rows and columns in increasing order.
In the proof of Proposition 4.3 this expresses the determinant of a change of basis as a -combination of the maximal minors of a fixed polynomial matrix.
Differences from the source:
- encoding: index sets [e], [t] and the sum over S ⊆ [e] with |S| = t, rows and columns in increasing order → Fin e, Fin t; the sum over the subtype {S // S.card = t}, S listed by its increasing enumeration orderEmbOfFin; reason: Lean convention; same matrices and index set
Preamble
import Mathlib
Formal statement
namespace RSSubspaceDesign
/-- **Theorem 2.14 (Cauchy–Binet).** Alrabiah–Goyal–Guruswami, *Explicit Reed-Solomon Subspace
Designs: Optimal List and Line Decoding*, arXiv:2610.36215 (held version, sha256
cf26424b…f36206), Theorem 2.14, p.13.
Let `E` be a field and `1 ≤ t ≤ e`. For `B ∈ E^{t×e}` and `D ∈ E^{e×t}`,
`det(BD) = ∑_{S ⊆ [e], |S| = t} det B_{[t],S} · det D_{S,[t]}`, the submatrices using the indicated
rows and columns in increasing order.
**Formalization Note.** Indices are `Fin t`, `Fin e`. The sum runs over the subtype of `t`-element
subsets `S`, and `S.orderEmbOfFin` lists `S` in increasing order. -/
theorem theorem_2_14 {E : Type*} [Field E] {t e : ℕ} (ht : 1 ≤ t) (hte : t ≤ e)
(B : Matrix (Fin t) (Fin e) E) (D : Matrix (Fin e) (Fin t) E) :
(B * D).det = ∑ S : {S : Finset (Fin e) // S.card = t},
(B.submatrix id (S.1.orderEmbOfFin S.2)).det * (D.submatrix (S.1.orderEmbOfFin S.2) id).det := by sorry
end RSSubspaceDesign
Source
O. Alrabiah, R. Goyal, V. Guruswami, Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding, arXiv:2610.36215 (held version, sha256 cf26424b…), Theorem 2.14, p.13 (PDF p.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.