Constructive non-commutative rank computation is in deterministic polynomial time
From MaRDI portal
Publication:1630376
DOI10.1007/s00037-018-0165-7zbMath1402.68197arXiv1512.03531OpenAlexW2962817959MaRDI QIDQ1630376
Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam
Publication date: 10 December 2018
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.03531
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Vector and tensor algebra, theory of invariants (15A72) Actions of groups on commutative rings; invariant theory (13A50) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items (31)
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ Ideals of spaces of degenerate matrices ⋮ Information geometry of operator scaling ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ Maximum likelihood estimation for tensor normal models via castling transforms ⋮ 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 ⋮ Ranks of linear matrix pencils separate simultaneous similarity orbits ⋮ A deterministic Algorithm for Harder-Narasimhan filtrations for representations of acyclic quivers ⋮ The separating variety for matrix semi-invariants ⋮ Harder-Narasimhan filtrations and zigzag persistence ⋮ Weighted slice rank and a minimax correspondence to Strassen's spectra ⋮ Algorithms for orbit closure separation for invariants and semi-invariants of matrices ⋮ On a weighted linear matroid intersection algorithm by deg-det computation ⋮ Efficient Black-Box Identity Testing for Free Group Algebras ⋮ Wildness for tensors ⋮ A compact representation for modular semilattices and its applications ⋮ Unnamed Item ⋮ Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces ⋮ A standard form in (some) free fields: how to construct minimal linear representations ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. ⋮ 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 ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Invariant Theory and Scaling Algorithms for Maximum Likelihood Estimation ⋮ 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 ⋮ Computing valuations of the Dieudonné determinants ⋮ Polystability in positive characteristic and degree lower bounds for invariant rings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial degree bounds for matrix semi-invariants
- Vector spaces of matrices of low rank
- The eigenvalue problem \(\lambda Tx+Sx\)
- The computational complexity of some problems of linear algebra
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- Classical complexity and quantum entanglement
- Computing Cartan subalgebras of Lie algebras
- 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
- Rational identities and applications to algebra and geometry
- Polynomial bounds for rings of invariants
- A Prime Matrix Ideal Yields a Skew Field
- ON THE CONSTRUCTION OF THE FREE FIELD
- On non-commutative rank and tensor rank
- Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
- Systems of distinct representatives and linear algebra
- Derandomizing polynomial identity tests means proving circuit lower bounds
- 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
This page was built for publication: Constructive non-commutative rank computation is in deterministic polynomial time
