Non-commutative Edmonds' problem and matrix semi-invariants

DOI10.1007/s00037-016-0143-xzbMath1421.13002arXiv1508.00690OpenAlexW2962789909MaRDI QIDQ2410690

K. V. Subrahmanyam, Youming Qiao, Gábor Ivanyos

Publication date: 18 October 2017

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

semi-invariants of quiversWong sequencescyclic division algebrasEdmonds' problemnon-commutative ranksymbolic determinant identity test

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Vector and tensor algebra, theory of invariants (15A72) Commutativity of matrices (15A27) Actions of groups on commutative rings; invariant theory (13A50) Finite-dimensional division rings (16K20)

Related Items

Derandomization and absolute reconstruction for sums of powers of linear forms ⋮ A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ Constructive non-commutative rank computation is in deterministic polynomial time ⋮ Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. ⋮ Information geometry of operator scaling ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory ⋮ The \(G\)-stable rank for tensors and the cap set problem ⋮ Polynomial bound for the nilpotency index of finitely generated nil algebras ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ An exponential lower bound for the degrees of invariants of cubic forms and tensor actions ⋮ Maximum likelihood estimation for tensor normal models via castling transforms ⋮ On rank-critical matrix spaces ⋮ Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces ⋮ Connections between graphs and matrix spaces ⋮ 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 ⋮ Algorithms for orbit closure separation for invariants and semi-invariants of matrices ⋮ Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing ⋮ Wildness for tensors ⋮ Polynomial degree bounds for matrix semi-invariants ⋮ Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces ⋮ Characteristic free description of semi-invariants of \(2 \times 2\) matrices ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ The regularity lemma is false over small fields ⋮ Operator scaling: theory and applications ⋮ A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ Weyl's polarization theorem in positive characteristic ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Maximum Likelihood Estimation for Matrix Normal Models via Quiver Representations ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices ⋮ Hilbert series and degree bounds for matrix (semi-)invariants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial degree bounds for matrix semi-invariants
• A geometric approach to the Kronecker problem. I: The two row case.
• Testing isomorphism of modules.
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Vector spaces of matrices of low rank
• Invariants of several matrices
• The eigenvalue problem \(\lambda Tx+Sx\)
• The invariant theory of \(n\times n\) matrices
• Maximum rank matrix completion
• The computational complexity of some problems of linear algebra
• Finding the radical of an algebra of linear transformations
• The linear delta-matroid parity problem
• An algebraic matching algorithm
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Rings of matrix invariants in positive characteristic
• Classical complexity and quantum entanglement
• Computing Cartan subalgebras of Lie algebras
• Defining relation for semi-invariants of three by three matrix triples
• Poincaré series of semi-invariants of \(2\times 2\) matrices
• Generalized Wong sequences and their applications to Edmonds' problems
• Non-commutative Edmonds' problem and matrix semi-invariants
• The Hilbert null-cone on tuples of matrices and bilinear forms
• Matroid matching via mixed skew-symmetric matrices
• Rational identities and applications to algebra and geometry
• Polynomial bounds for rings of invariants
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• On P vs. NP and geometric complexity theory
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• A note on certain Kronecker coefficients
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• THE CONSTRUCTIVE THEORY OF INVARIANTS
• Singular spaces of matrices and their application in combinatorics
• The word problem for free fields: a correction and an addendum
• TRACE IDENTITIES OF FULL MATRIX ALGEBRAS OVER A FIELD OF CHARACTERISTIC ZERO
• A Prime Matrix Ideal Yields a Skew Field
• Relative invariants of 3 × 3 matrix triples^∗
• ON THE CONSTRUCTION OF THE FREE FIELD
• Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.
• Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
• The word problem for free fields
• Invariant functions on matrices
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• Systems of distinct representatives and linear algebra
• The Factorization of Linear Graphs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Matrices and matroids for systems analysis
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Semi-invariants of quivers as determinants
• Semi-invariants of quivers for arbitrary dimension vectors