A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices

DOI10.1137/S0895479893255901zbMATH Open0829.15008MaRDI QIDQ4842560FDOQ4842560

Authors: Satoru Iwata, Kazuo Murota 

Publication date: 24 January 1996

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Recommendations

• Combinatorial Analysis of Singular Matrix Pencils
• Nonbipartite Dulmage-Mendelsohn decomposition for Berge duality
• Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
• Fully indecomposable and nearly decomposable matrices in Ω(r,s)
• A generalization of a theorem of König

zbMATH Keywords

matrix decompositionDulmage-Mendelsohn decompositionHall-Ore theoremKönig- Egerváry theorem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Canonical forms, reductions, classification (15A21)

Cited In (13)

• Minimal Gerschgorin sets for partitioned matrices. III: Sharpness of boundaries and monotonicity as a function of the partition
• Computing DM-decomposition of a partitioned matrix with rank-1 blocks
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Signed ring families and signed posets
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• A cost-scaling algorithm for computing the degree of determinants
• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices
• A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
• On the complexity of submodular function minimisation on diamonds
• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices

This page was built for publication: A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4842560)