Theorem 37 — every (C*)-matroid is the matroid of a matrix mod 2, uniquely given the base columns
ProvedWhitneyMatroid.Binary.exists_unique_binary_representationLet be any matroid satisfying Postulate (C*). Suppose , so consists of the elements , and that is a base of . Let be any matrix of integers (mod 2), with any number of rows, having columns which are independent (mod 2). Then columns can be adjoined in a unique manner to , forming a matrix
of which the corresponding matroid is .
Together with the appendix result that the matroid of any matrix mod 2 satisfies (C*), this characterizes the matroids corresponding to matrices of integers mod 2 (the binary matroids) as exactly those satisfying (C*), and shows that a representation is fixed once the columns of one base are chosen.
Formalization Note Elements are Fin (r + q) with and , so the base is the range of Fin.castAdd q; the ground set of M is all of Fin (r + q) (that is ). The matrices are Matrix (Fin m) (Fin r) (ZMod 2) and Matrix (Fin m) (Fin (r + q)) (ZMod 2); "adjoined to " means the first columns of are those of , and "the corresponding matroid is " is IsMatroidOf M A (same independent sets). Uniqueness is of the whole matrix under these two conditions. Independence of the columns of is linear independence over ZMod 2 of its transpose's rows.
import Mathlib import Definitions.Def_WhitneyMatroid_Binary_Cycles import Definitions.Def_WhitneyMatroid_Binary_IsMatroidOf
namespace WhitneyMatroid.Binary
/-- Theorem 37 (Appendix, p. 533). Let `M` be any matroid satisfying (C*). Suppose `ρ(M) = n`
(the elements are `e₁, …, eₙ`, here `Fin (r + q)` with `e_k ↦ k - 1`, all of them in `M`), and
`e₁ + ⋯ + e_{n-q}` is a base. Then if `A₁` is any matrix of integers (mod 2) with `n - q = r`
columns which are independent (mod 2), columns `C_{n-q+1}, …, Cₙ` can be adjoined in a unique
manner to `A₁`, forming a matrix `A` of which the corresponding matroid is `M`. -/
theorem exists_unique_binary_representation {r q m : ℕ} (M : Matroid (Fin (r + q)))
(hE : M.E = Set.univ) (hC : SatisfiesCStar {C | M.IsCircuit C})
(hB : M.IsBase (Set.range (Fin.castAdd q : Fin r → Fin (r + q))))
(A₁ : Matrix (Fin m) (Fin r) (ZMod 2))
(hA₁ : LinearIndependent (ZMod 2) A₁.transpose) :
∃! A : Matrix (Fin m) (Fin (r + q)) (ZMod 2),
(∀ i : Fin m, ∀ j : Fin r, A i (Fin.castAdd q j) = A₁ i j) ∧ IsMatroidOf M A := by sorry
end WhitneyMatroid.Binary
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.