Independent transversals of the mixed-matrix family are bounded by the rank
ProvedDiscreteConvex.MixedMatrices.card_le_rank_of_indep_transversaldiscrete-convex-analysislinear-algebramixed-matrices
Throughout, and are finite index sets, are fields (in Lean: Algebra K F), and for a matrix and subsets , we write for the submatrix with rows in and columns in and , for matrices over and over . A mixed matrix is with over and the nonzero entries of algebraically independent over (Murota, Ch. 12).
Let be a mixed matrix. For each column let consist of the column of (viewed over ) together with the unit vectors for those rows with . If is a linearly independent partial transversal of the family , that is for , then
Formalization Note. hA : IsMixedMatrix A Q T is the platform notion of a mixed matrix.
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MixedMatrices_IsMixedMatrix import Definitions.Def_DiscreteConvex_MixedMatrices_MatrixSubRank
Formal statement
namespace DiscreteConvex.MixedMatrices
theorem card_le_rank_of_indep_transversal {R C K F : Type*} [Fintype R] [Fintype C] [Field K]
[Field F] [Algebra K F] [DecidableEq R] [DecidableEq C]
(A : Matrix R C F) (Q : Matrix R C K) (T : Matrix R C F) (hA : IsMixedMatrix A Q T)
(J : Finset C) (v : C → R → F)
(hv : ∀ c ∈ J, v c ∈ ({fun r : R => algebraMap K F (Q r c)} ∪
(fun s : R => (Pi.single s (1 : F) : R → F)) '' {s : R | T s c ≠ 0}))
(hind : LinearIndepOn F v (J : Set C)) :
J.card ≤ A.rank := by sorry
end DiscreteConvex.MixedMatrices
Source
Auxiliary lemma for Murota, Discrete Convex Analysis, SIAM 2003, Theorem 12.9 (p. 358), using Theorem 12.7 (p. 357); the route through Rado's theorem is not the book's