Rank of a mixed matrix: a tight pair of index sets
ProvedDiscreteConvex.MixedMatrices.exists_tight_pairdiscrete-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. Then there are and with and
Equivalently, for some pair with . This is the existence statement of Murota's Theorem 12.9 (König-Egerváry theorem for mixed matrices) in complement form; together with weak duality it gives .
Formalization Note. MatrixSubRank T I J = 0 expresses , equivalently .
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MixedMatrices_IsMixedMatrix import Definitions.Def_DiscreteConvex_MixedMatrices_MatrixSubRank
Formal statement
namespace DiscreteConvex.MixedMatrices
theorem exists_tight_pair {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) :
∃ (I : Finset R) (J : Finset C), MatrixSubRank T I J = 0 ∧
MatrixSubRank Q I J + Iᶜ.card + Jᶜ.card = A.rank := by sorry
end DiscreteConvex.MixedMatrices
Source
Murota, Discrete Convex Analysis, SIAM 2003, Theorem 12.9 (p. 358), restated in complement form; proved here via Rado's theorem, a route different from the book's