A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
Satoru Iwata, Kazuo Murota · SIAM Journal on Matrix Analysis and Applications · 1995
This paper discusses an extension of the Dulmage–Mendelsohn decomposition for a certain class of matrices whose row-set and column-set are divided into couples or singletons. A genericity assumption is imposed and an admissible transformation is defined in respect of this partition structure. Extensions of the König–Egerváry theorem and the Hall–Ore theorem are established. The latter states that the rank of such a matrix is characterized by the minimum value of a submodular function, of which the set of minimizers yields a canonical block-triangularization under the admissible transformations.