Theorem 29 — the rows of a fundamental set of circuits span the circuit matrix
ProvedWhitneyMatroid.Fano.circuitMatrix_fundamental_rows_baseLet be a real matrix, its matroid, and a circuit matrix of (one row per circuit of , the row of a circuit satisfying (14.1)). Let be a fundamental set of circuits in (§9; in particular ), and let be the corresponding rows of . Then:
- are linearly independent;
- every row of is a linear combination of ;
- hence
In the paper's notation of Theorem 29, is the given matrix and its circuit matrix. The theorem identifies the dimension of the row space of the circuit matrix with the nullity, which underlies the duality of a matrix and its circuit matrix (Theorems 30, 31) and the determinant criterion of Theorem 32.
Formalization Note The fundamental set is given by a list of row indices of , the circuit being the circuit of row . The rank is Mathlib's Matrix.rank.
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 29 (p. 527). Here `A` is Whitney's matrix `𝐌`, `M` its matroid, and `B` its
circuit matrix `𝐌′`. If the circuits `P_i = row (k i)` (`i < q`) form a fundamental set of
circuits in `M`, then the corresponding rows `B (k i)` of `B` form a base for the rows of `B`
(they are linearly independent and every row of `B` is a linear combination of them); hence the
rank of `B` is `q = n(M)`. -/
theorem circuitMatrix_fundamental_rows_base {ι : Type*} [Fintype ι] {m : ℕ} {κ : Type*}
(A : Matrix (Fin m) ι ℝ) (M : Matroid ι) (B : Matrix κ ι ℝ)
(row : κ ≃ {P : Set ι // M.IsCircuit P}) (hB : IsCircuitMatrix M A B row)
{q : ℕ} (k : Fin q → κ) (hP : IsFundamentalCircuitSet M (fun i => (row (k i) : Set ι))) :
LinearIndependent ℝ (fun i => B (k i)) ∧
(∀ k' : κ, B k' ∈ Submodule.span ℝ (Set.range fun i => B (k i))) ∧
B.rank = q := by sorry
end WhitneyMatroid.Fano
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.