Matrix invariants and algebraic complexity theory

Matrix invariants and algebraic complexity theory - Harm Derksen

Harm Derksen
University of Michigan
October 17, 2016
The determinant of an $n\times n$ matrix is an invariant polynomial of degree $n$ that is invariant under left and right multiplication with matrices in ${\rm SL}_n$. It generates in the sense that every other invariant polynomial is a polynomial expression in the determinant. In this talk we consider the simultaneous left and right action of ${\rm SL}_n$ on $m$-tuples of $n\times n$ matrices. I will explain a joint result with Visu Makam that shows that invariants of degree $\leq n^6$ are sufficient to generate all polynomial invariants. I will also explain how these results have applications in Algebraic Complexity Theory, such as a deterministic polynomial time algorithm for non-commutative rational identity testing.