Computing DM-decomposition of a partitioned matrix with rank-1 blocks

DOI10.1016/J.LAA.2018.02.008MaRDI QIDQ1747895zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai

Publication date 27 April 2018

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01934

zbMATH Keywords

Dulmage-Mendelsohn decompositionmatroidmodular latticepartitioned matrixsubmodular function

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Canonical forms, reductions, classification (15A21) Spectral operators, decomposable operators, well-bounded operators, etc. (47B40) Analysis of algorithms and problem complexity (68Q25)

Abstract: In this paper, we develop a polynomial time algorithm to compute a Dulmage-Mendelsohn-type decomposition of a matrix partitioned into submatrices of rank at most $1$.

Cites work

• A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
• Admissible Mappings between Dependence Spaces
• Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
• Combinatorial Canonical Form of Layered Mixed Matrices and Its Application to Block-Triangularization of Systems of Linear/Nonlinear Equations
• Coverings of Bipartite Graphs
• scientific article; zbMATH DE number 3149610 (Why is no real title available?)
• Matching theory
• Matrices and matroids for systems analysis
• On the complexity of submodular function minimisation on diamonds
• Singular spaces of matrices and their application in combinatorics
• The power of linear programming for general-valued CSPs

Cited in

(4)

• A compact representation for modular semilattices and its applications
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings

This page was built for publication: Computing DM-decomposition of a partitioned matrix with rank-1 blocks

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