Polynomial degree bounds for matrix semi-invariants

DOI10.1016/J.AIM.2017.01.018zbMATH Open1361.15033arXiv1512.03393OpenAlexW2962745033MaRDI QIDQ520358FDOQ520358

Visu Makam, Harm Derksen

Publication date: 3 April 2017

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: We study the left-right action of $operatorname{SL}_{n}imesoperatorname{SL}_n$ on $m$-tuples of $nimesn$ matrices with entries in an infinite field $K$. We show that invariants of degree $n^2-n$ define the null cone. Consequently, invariants of degree $leq{n}^6$ generate the ring of invariants if $operatornamechar(K)=0$. We also prove that for $mgg0$, invariants of degree at least $nlfloorsqrtn+1floor$ are required to define the null cone. We generalize our results to matrix invariants of $m$-tuples of $pimesq$ matrices, and to rings of semi-invariants for quivers. For the proofs, we use new techniques such as the regularity lemma by Ivanyos, Qiao and Subrahmanyam, and the concavity property of the tensor blow-ups of matrix spaces. We will discuss several applications to algebraic complexity theory, such as a deterministic polynomial time algorithm for non-commutative rational identity testing, and the existence of small division-free formulas for non-commutative polynomials.

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

Recommendations

• Hilbert series and degree bounds for matrix (semi-)invariants
• scientific article; zbMATH DE number 4051826
• Non-commutative Edmonds' problem and matrix semi-invariants
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Polynomial bounds for rings of invariants

zbMATH Keywords

invariantsalgebraic complexity theorydegree boundsinvariant theorymatricesquiver representationssemi-invariantsnull conesemi-invariants of quivers

Mathematics Subject Classification ID

Vector and tensor algebra, theory of invariants (15A72)

Cites Work

• Computational invariant theory
• MODULI OF REPRESENTATIONS OF FINITE DIMENSIONAL ALGEBRAS
• Poincaré series of semi-invariants of \(2\times 2\) matrices
• Non-commutative Edmonds' problem and matrix semi-invariants
• Relative invariants of 3 × 3 matrix triples^∗
• Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
• Semi-invariants of quivers as determinants
• Semi-invariants of quivers for arbitrary dimension vectors
• Title not available (Why is that?)
• The invariant theory of \(n\times n\) matrices
• TRACE IDENTITIES OF FULL MATRIX ALGEBRAS OVER A FIELD OF CHARACTERISTIC ZERO
• Minimal Identities for Algebras
• Invariants of a group in an affine ring
• Invariants of several matrices
• Polynomial bounds for rings of invariants
• Rings of matrix invariants in positive characteristic
• Invariant functions on matrices
• Reductive groups are geometrically reductive
• Classical complexity and quantum entanglement
• Non-commutative arithmetic circuits with division
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE CONSTRUCTIVE THEORY OF INVARIANTS
• Title not available (Why is that?)

Cited In (39)

• A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.
• Determinantal hypersurfaces and representations of Coxeter groups
• The separating variety for matrix semi-invariants
• Polystability in positive characteristic and degree lower bounds for invariant rings
• An exponential lower bound for the degrees of invariants of cubic forms and tensor actions
• Polynomial matrix inequality and semidefinite representation
• Efficient Black-Box Identity Testing for Free Group Algebras
• Separating invariants of three nilpotent \(3\times 3\) matrices
• Invariant Theory and Scaling Algorithms for Maximum Likelihood Estimation
• Maximum Likelihood Estimation for Matrix Normal Models via Quiver Representations
• Characteristic free description of semi-invariants of \(2 \times 2\) matrices
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Explicit tensors of border rank at least 2d−2 in K^d ⊗ K^d ⊗ K^d in arbitrary characteristic
• Constructive non-commutative rank computation is in deterministic polynomial time
• Operator scaling: theory and applications
• Geometry of free loci and factorization of noncommutative polynomials
• Maximum likelihood estimation for tensor normal models via castling transforms
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Polynomial bound for the nilpotency index of finitely generated nil algebras
• From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
• Symmetries in directed Gaussian graphical models
• Non-commutative Edmonds' problem and matrix semi-invariants
• A cost-scaling algorithm for computing the degree of determinants
• Matrix coefficient realization theory of noncommutative rational functions
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Title not available (Why is that?)
• A bridge between invariant theory and maximum likelihood estimation
• Title not available (Why is that?)
• On the tensor rank of $3\times 3$ permanent and determinant
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.
• Ranks of linear matrix pencils separate simultaneous similarity orbits
• Weyl's polarization theorem in positive characteristic
• On \(m\)-tuples of nilpotent \(2\times 2\) matrices over an arbitrary field
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
• Hilbert’s 17th problem in free skew fields
• The regularity lemma is false over small fields

This page was built for publication: Polynomial degree bounds for matrix semi-invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520358)