Generalized Wong sequences and their applications to Edmonds' problems

DOI10.1016/J.JCSS.2015.04.006zbMATH Open1320.68222arXiv1307.6429OpenAlexW2200115418MaRDI QIDQ2353409FDOQ2353409

Authors: Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha 

Publication date: 13 July 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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.

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

Recommendations

• Generalized Wong sequences and their applications to Edmonds' problems
• A generalization of the Wang sequence
• scientific article
• 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

zbMATH Keywords

derandomizationWong sequencesmaximum rank matrix completionEdmonds' problemsymbolic determinantal identity testing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Determinants, permanents, traces, other special matrix functions (15A15) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Matrix pencils (15A22)

Cites Work

• Title not available (Why is that?)
• The quasi-Kronecker form for matrix pencils
• Title not available (Why is that?)
• A THEOREM ON INDEPENDENCE RELATIONS
• Vector spaces of matrices of low rank
• Matrices and matroids for systems analysis
• On computing the determinant in small parallel time using a small number of processors
• Maximum rank matrix completion
• Derandomizing polynomial identity tests means proving circuit lower bounds
• The computational complexity of some problems of linear algebra
• Solution concepts for linear DAEs: a survey
• Greatest common divisors of polynomials given by straight-line programs
• The complexity of matrix completion
• The eigenvalue problem \(\lambda Tx+Sx\)
• Systems of distinct representatives and linear algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Addition to “The Quasi-Kronecker Form for Matrix Pencils
• Classical complexity and quantum entanglement
• Deterministic network coding by matrix completion
• Generalized Wong sequences and their applications to Edmonds' problems
• Singular spaces of matrices and their application in combinatorics
• On Matroid Theorems of Edmonds and Rado
• Deterministic polynomial time algorithms for matrix completion problems
• Computing Cartan subalgebras of Lie algebras
• Title not available (Why is that?)
• The linear delta-matroid parity problem
• Matroid matching via mixed skew-symmetric matrices
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• SPACES OF MATRICES OF BOUNDED RANK

Cited In (19)

• Constructive non-commutative rank computation is in deterministic polynomial time
• A deterministic Algorithm for Harder-Narasimhan filtrations for representations of acyclic quivers
• Connections between graphs and matrix spaces
• Constructive non-commutative rank computation is in deterministic polynomial time
• Operator scaling: theory and applications
• Edmonds' problem and the membership problem for orbit semigroups of quiver representations
• Generalized Wong sequences and their applications to Edmonds' problems
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• 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
• A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
• Sinkhorn-Knopp theorem for PPT states
• On rank-critical matrix spaces
• A deterministic PTAS for the commutative rank of matrix spaces
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• A generalization of the Wang sequence
• A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces

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)