A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
- 1 July 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 16 (3) , 719-734
- https://doi.org/10.1137/s0895479893255901
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- König's theorem and bimatroidsLinear Algebra and its Applications, 1994
- Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence TransformationsSIAM Journal on Matrix Analysis and Applications, 1994
- Mixed Matrices: Irreducibility and DecompositionPublished by Springer Nature ,1993
- Combinatorial Matrix TheoryPublished by Cambridge University Press (CUP) ,1991
- Systems Analysis by Graphs and MatroidsPublished by Springer Nature ,1987
- Combinatorial Canonical Form of Layered Mixed Matrices and Its Application to Block-Triangularization of Systems of Linear/Nonlinear EquationsSIAM Journal on Algebraic Discrete Methods, 1987
- A determinantal version of the frobenius-könig theoremLinear and Multilinear Algebra, 1984
- Structural Theory for the Combinatorial Systems Characterized by Submodular FunctionsPublished by Elsevier ,1984
- Combinatorial TheoryPublished by Springer Nature ,1979