A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices

DOI10.1007/s10107-021-01676-5zbMath1504.90125OpenAlexW3020014329MaRDI QIDQ2089763

Hiroshi Hirai, Yuni Iwamasa

Publication date: 24 October 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-021-01676-5

zbMATH Keywords

Edmonds' problemgeneric partitioned matrixmaximum rank completion problemnon-commutative Edmonds' problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Related Items (2)

Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ 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

Cites Work

• Unnamed Item
• On the complexity of submodular function minimisation on diamonds
• The computational complexity of some problems of linear algebra
• Constructive non-commutative rank computation is in deterministic polynomial time
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Operator scaling: theory and applications
• Generalized Wong sequences and their applications to Edmonds' problems
• Non-commutative Edmonds' problem and matrix semi-invariants
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Singular spaces of matrices and their application in combinatorics
• Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
• A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Systems of distinct representatives and linear algebra
• The Factorization of Linear Graphs
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices