Appendix, p. 532 — the matroid of a matrix mod 2 satisfies (C*), and the two notions of cycle agree
ProvedWhitneyMatroid.Binary.matrix_matroid_satisfies_cStarbinary-matroidslinear-algebramatroidsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an matrix of integers mod 2 with columns , and let be the set of elements corresponding to the columns, a set of elements being independent (equivalently, a circuit) in exactly when the corresponding columns are independent (a circuit) mod 2. Then:
- is a matroid;
- satisfies Postulate (C*);
- the definitions of cycle in and in agree: a set of elements is a cycle of (a sum mod 2 of circuits) if and only if there are coefficients (integers mod 2) with
This is the easy direction of Whitney's characterization: every matroid of a matrix mod 2 satisfies (C*). Theorem 37 is the converse.
Formalization Note Item 1 is the existence of a Mathlib matroid M on Fin n with IsMatroidOf M A; items 2 and 3 are asserted for every such M (there is only one). The linear combination is A.mulVec x = 0 for x : Fin n → ZMod 2.
Preamble
import Mathlib import Definitions.Def_WhitneyMatroid_Binary_Cycles import Definitions.Def_WhitneyMatroid_Binary_IsMatroidOf
Formal statement
namespace WhitneyMatroid.Binary
/-- Appendix, p. 532. Let `A` be an `m × n` matrix of integers mod 2 with columns `C₁, …, Cₙ`,
and let `M` be the set of elements `e₁, …, eₙ` (`Fin n`) corresponding to the columns, with the
independent (equivalently, circuit) sets of the columns as its independent (circuit) sets. Then
`M` is a matroid satisfying (C*), and the definitions of cycle in `M` and in `A` agree: a set `Q`
of elements is a cycle of `M` (a sum mod 2 of circuits) iff `Q` is the set of columns with
coefficient `1` in a linear combination `Σ αᵢ Cᵢ ≡ 0 (mod 2)`. -/
theorem matrix_matroid_satisfies_cStar {m n : ℕ} (A : Matrix (Fin m) (Fin n) (ZMod 2)) :
(∃ M : Matroid (Fin n), IsMatroidOf M A) ∧
∀ M : Matroid (Fin n), IsMatroidOf M A →
SatisfiesCStar {C | M.IsCircuit C} ∧
∀ Q : Set (Fin n), IsCycleOf {C | M.IsCircuit C} Q ↔
∃ x : Fin n → ZMod 2, A.mulVec x = 0 ∧ Q = {j | x j ≠ 0} := by sorry
end WhitneyMatroid.Binary
Source
Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), p. 532, Appendix (unnumbered: 'We shall show that M is a matroid satisfying (C*) and the definitions of cycle in M and 𝐌 agree')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.