Weak duality for the rank of a mixed matrix
ProvedDiscreteConvex.MixedMatrices.rank_le_matrixSubRank_adddiscrete-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 fields and entrywise, with over and over . Then for all , ,
This is the easy (weak duality) inequality behind the min-formulas for the rank of a mixed matrix. No independence of the entries of is needed.
Formalization Note. The hypothesis is only the entrywise decomposition A i j = algebraMap K F (Q i j) + T i j.
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MixedMatrices_MatrixSubRank
Formal statement
namespace DiscreteConvex.MixedMatrices
theorem rank_le_matrixSubRank_add {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 : ∀ i j, A i j = algebraMap K F (Q i j) + T i j) (I : Finset R) (J : Finset C) :
A.rank ≤ MatrixSubRank Q I J + MatrixSubRank T I J + Iᶜ.card + Jᶜ.card := by sorry
end DiscreteConvex.MixedMatrices
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, Chapter 12 (mixed matrices), Theorem 12.8 (p. 358): the inequality rank A <= the minima in Eqs. (12.10)-(12.12) (weak duality)