The rank of a submatrix is at most its number of nonzero rows
ProvedDiscreteConvex.MixedMatrices.matrixSubRank_le_gammaFundiscrete-convex-analysislinear-algebramixed-matrices
Let be finite index sets and an matrix over a field , with the submatrix with rows in and columns in . For index sets ,
where is the number of nonzero rows of .
Formalization Note. MatrixSubRank and GammaFun are the platform definitions of and .
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MixedMatrices_MatrixSubRank import Definitions.Def_DiscreteConvex_MixedMatrices_GammaFun
Formal statement
namespace DiscreteConvex.MixedMatrices
theorem matrixSubRank_le_gammaFun {R C F : Type*} [Fintype R] [Fintype C] [Field F]
(T : Matrix R C F) (I : Finset R) (J : Finset C) :
MatrixSubRank T I J ≤ GammaFun T I J := by sorry
end DiscreteConvex.MixedMatrices
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, Chapter 12 (mixed matrices), p. 357 (the function gamma); elementary lemma used in formalising Theorem 12.8; not stated in the book