Generalized Wong sequences and their applications to Edmonds' problems
From MaRDI portal
Publication:2353409
Abstract: We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the n by n matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n+1 and over the rational numbers, and the first algorithm actually solves (the non-constructive) SMR independently from the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.
Recommendations
- Generalized Wong sequences and their applications to Edmonds' problems
- A generalization of the Wang sequence
- scientific article; zbMATH DE number 1808181
- Generalized \(w\)-Euler numbers and polynomials
- On a generalized difference sequence and its applications
- On generalized Vietoris' number sequences
- On certain classes of generalized sequences
- The Prouhet-Tarry-Escott problem and generalized Thue-Morse sequences
- The congruence of Wolstenholme for generalized binomial coefficients related to Lucas sequences
- On the Wyner-Ziv problem for individual sequences
Cites work
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 3664349 (Why is no real title available?)
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 1253966 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A THEOREM ON INDEPENDENCE RELATIONS
- Addition to “The Quasi-Kronecker Form for Matrix Pencils
- Classical complexity and quantum entanglement
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- Computing Cartan subalgebras of Lie algebras
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic network coding by matrix completion
- Deterministic polynomial time algorithms for matrix completion problems
- Generalized Wong sequences and their applications to Edmonds' problems
- Greatest common divisors of polynomials given by straight-line programs
- Matrices and matroids for systems analysis
- Matroid matching via mixed skew-symmetric matrices
- Maximum rank matrix completion
- On Matroid Theorems of Edmonds and Rado
- On computing the determinant in small parallel time using a small number of processors
- SPACES OF MATRICES OF BOUNDED RANK
- Singular spaces of matrices and their application in combinatorics
- Solution concepts for linear DAEs: a survey
- Systems of distinct representatives and linear algebra
- The complexity of matrix completion
- The computational complexity of some problems of linear algebra
- The eigenvalue problem \(\lambda Tx+Sx\)
- The linear delta-matroid parity problem
- The quasi-Kronecker form for matrix pencils
- Vector spaces of matrices of low rank
Cited in
(19)- Edmonds' problem and the membership problem for orbit semigroups of quiver representations
- Sinkhorn-Knopp theorem for PPT states
- Non-commutative Edmonds' problem and matrix semi-invariants
- On the Wyner-Ziv problem for individual sequences
- Simultaneous robust subspace recovery and semi-stability of quiver representations
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- Constructive non-commutative rank computation is in deterministic polynomial time
- On rank-critical matrix spaces
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- A generalization of the Wang sequence
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- A deterministic PTAS for the commutative rank of matrix spaces
- Constructive non-commutative rank computation is in deterministic polynomial time
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- Operator scaling: theory and applications
- Generalized Wong sequences and their applications to Edmonds' problems
- A deterministic Algorithm for Harder-Narasimhan filtrations for representations of acyclic quivers
- Connections between graphs and matrix spaces
- Algebraic algorithms for fractional linear matroid parity via noncommutative rank
This page was built for publication: Generalized Wong sequences and their applications to Edmonds' problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353409)
