Theorem 32 — vanishing minors of a circuit matrix and circuits avoiding a set
ProvedWhitneyMatroid.Fano.det_eq_zero_iff_circuitLet be a real matrix whose matroid has elements , and let be a circuit matrix of . Let form a strict fundamental set of circuits in with respect to , and let the first rows of be those corresponding to . Let be numbers from , numbers from , and the complement of in . Let
- be the determinant of with rows and columns ;
- be the determinant of with rows and columns .
Then
The theorem turns the combinatorics of into polynomial equations on the entries of a normalised circuit matrix; Whitney applies it in §16 to the triples , , and to show that the Fano matroid has no real matrix.
Formalization Note The elements are Fin (p + q) with : () is Fin.castAdd q (j-1) and () is Fin.natAdd p (i-1). The row of is k (i-1). The increasing lists , , are order embeddings I : Fin s ↪o Fin q, J : Fin s ↪o Fin p, I' : Fin t ↪o Fin q with and the range of I' the complement of the range of I; this avoids natural-number subtraction. The columns of are listed in the paper's order with Fin.append. Only the vanishing of and is asserted, so the order of rows and columns does not matter.
import Mathlib import Definitions.Def_WhitneyMatroid_Fano_IsMatroidOf import Definitions.Def_WhitneyMatroid_Fano_FundamentalCircuits import Definitions.Def_WhitneyMatroid_Fano_IsCircuitMatrix
namespace WhitneyMatroid.Fano
/-- Whitney, Theorem 32 (pp. 528–529). The elements are `Fin (p + q)` with `n = p + q`: Whitney's
`e_j` (`1 ≤ j ≤ n − q`) is `Fin.castAdd q (j-1)` and `e_{n−q+i}` (`1 ≤ i ≤ q`) is
`Fin.natAdd p (i-1)`. `B` (Whitney's `𝐌`) is the circuit matrix of the real matrix `A`
(Whitney's `𝐌′`), whose matroid is `M′`; the circuits `P_i = row (k i)` form a strict fundamental
set of circuits in `M′` with respect to `e_{n−q+1}, …, e_n`, and the rows `B (k i)` are "the first
`q` rows". `I` lists `i₁ < ⋯ < i_s` from `{1, …, q}`, `J` lists `j₁ < ⋯ < j_s` from
`{1, …, n − q}`, and `I'` lists the complementary `i′₁ < ⋯ < i′_{q−s}` (`t = q − s`). Then the
determinant `D` of `B` with rows `i₁, …, i_s` and columns `j₁, …, j_s` vanishes iff the
determinant `D′` with rows `1, …, q` and columns `j₁, …, j_s, n−q+i′₁, …, n−q+i′_{q−s}` vanishes,
iff some circuit of `M′` contains none of the columns `e_{j₁}, …, e_{j_s}, e_{n−q+i′₁}, …,
e_{n−q+i′_{q−s}}`. -/
theorem det_eq_zero_iff_circuit {p q m : ℕ} {κ : Type*}
(A : Matrix (Fin m) (Fin (p + q)) ℝ) (M' : Matroid (Fin (p + q)))
(B : Matrix κ (Fin (p + q)) ℝ) (row : κ ≃ {P : Set (Fin (p + q)) // M'.IsCircuit P})
(hB : IsCircuitMatrix M' A B row) (k : Fin q → κ)
(hP : IsStrictFundamentalCircuitSetWrt M' (fun i => (row (k i) : Set (Fin (p + q))))
(Fin.natAdd p))
{s t : ℕ} (hst : s + t = q) (I : Fin s ↪o Fin q) (J : Fin s ↪o Fin p) (I' : Fin t ↪o Fin q)
(hI' : ∀ i : Fin q, i ∈ Set.range I' ↔ i ∉ Set.range I) :
let D : ℝ := (Matrix.of fun a b : Fin s => B (k (I a)) (Fin.castAdd q (J b))).det
let cols : Fin (s + t) → Fin (p + q) :=
Fin.append (fun b : Fin s => Fin.castAdd q (J b)) (fun c : Fin t => Fin.natAdd p (I' c))
let D' : ℝ := (Matrix.of fun (i c : Fin q) => B (k i) (cols (Fin.cast hst.symm c))).det
(D = 0 ↔ D' = 0) ∧
(D = 0 ↔
∃ P : Set (Fin (p + q)), M'.IsCircuit P ∧ ∀ c : Fin (s + t), cols c ∉ P) := by sorry
end WhitneyMatroid.Fano
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.