Polynomial degree bounds for matrix semi-invariants

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

Authors Visu Makam, Harm Derksen

Publication date 3 April 2017

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

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

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)

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.

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

Cites work

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

Cited in

(40)

• Characteristic free description of semi-invariants of \(2 \times 2\) matrices
• Non-commutative Edmonds' problem and matrix semi-invariants
• A cost-scaling algorithm for computing the degree of determinants
• On the tensor rank of the \(3 \times 3\) permanent and determinant
• Polynomial bound for the nilpotency index of finitely generated nil algebras
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• 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
• Explicit tensors of border rank at least \(2d -2\) in \(K^d \otimes K^d \otimes K^d\) in arbitrary characteristic
• Ranks of linear matrix pencils separate simultaneous similarity orbits
• 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.
• Separating invariants of three nilpotent \(3\times 3\) matrices
• Constructive non-commutative rank computation is in deterministic polynomial time
• An exponential lower bound for the degrees of invariants of cubic forms and tensor actions
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Maximum likelihood estimation for matrix normal models via quiver representations
• Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
• Operator scaling: theory and applications
• Efficient Black-Box Identity Testing for Free Group Algebras
• Symmetries in directed Gaussian graphical models
• Invariant Theory and Scaling Algorithms for Maximum Likelihood Estimation
• The separating variety for matrix semi-invariants
• Geometry of free loci and factorization of noncommutative polynomials
• The regularity lemma is false over small fields
• scientific article; zbMATH DE number 7561740 (Why is no real title available?)
• Maximum likelihood estimation for tensor normal models via castling transforms
• A bridge between invariant theory and maximum likelihood estimation
• Determinantal hypersurfaces and representations of Coxeter groups
• Weyl's polarization theorem in positive characteristic
• scientific article; zbMATH DE number 3630952 (Why is no real title available?)
• Polystability in positive characteristic and degree lower bounds for invariant rings
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• Hilbert series and degree bounds for matrix (semi-)invariants
• Hilbert's 17th problem in free skew fields
• Matrix coefficient realization theory of noncommutative rational functions
• Polynomial matrix inequality and semidefinite representation
• On \(m\)-tuples of nilpotent \(2\times 2\) matrices over an arbitrary field
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank

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)