Room 327

Polynomial time algorithms for the invariant theory of the left-right action.

K V Subrahmanyam

CMI

Consider the action of SL(n) x SL(n) on an m-tuple of matrices, with
a pair (A,B) sending an m-tuple (M_1,M_2,....,M_m) to (A M_1 B^t, A M_2 B^t,
...., A M_m B^t). Polynomial functions (in the entries of the m*n^2 variables of the m-tuple of matrices) which are invariant under this action, are well known. It is also known that the ring of invariants is finitely generated. However a good upper bound on the degree of the generating
polynomials needed is not known. A further question is to determine, given a m-tuple of matrices, if all invariant polynomials vanish on this m-tuple, the so called null cone for this action.

We will describe our main result, regularity under blow-ups which holds over infinite fields and large finite fields. Based on this recently, Derksen and Vishwambara showed that the invariant ring is generated in degree n^6 (over infinite fields). We indicate how a simple calculation starting with our
result yields the same n^6 bound (over infinite fields), without using the Derksen Vishwambara machinery.

We also give a polynomial time algorithm for membership in the null cone (over infinite fields and large finite fields), vastly improving on a recent result of Garg, Gurvits, Olivera and Wigderson, based on our regularity under blow ups lemma.

This is joint work with Gabor Ivanyos and Youming Qiao.