A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices
From MaRDI portal
Publication:5041746
DOI10.1007/978-3-030-45771-6_16zbMath1503.15001arXiv2004.10443OpenAlexW3016009702MaRDI QIDQ5041746
Publication date: 14 October 2022
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.10443
Symbolic computation and algebraic computation (68W30) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items
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
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
- Systems of distinct representatives and linear algebra
- Derandomizing polynomial identity tests means proving circuit lower bounds