2015/12/10 by Derksen, Harm, Makam, Visu · 1 citation
#13A50 (Primary) #14L24 #16G20 (Secondary) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Representation Theory (math.RT)
paper · doi:10.48550/arxiv.1512.03393
We study the left-right action of SLn × SLn on m-tuples of n × n matrices with entries in an infinite field K. We show that invariants of degree n2- n define the null cone. Consequently, invariants of degree ≤ n6 generate the ring of invariants if char(K)=0. We also prove that for m ≫ 0, invariants of degree at least n\lfloor √(n+1)\rfloor are required to define the null cone. We generalize our results to matrix invariants of m-tuples of p× q 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.