Matrix invariants and algebraic complexity theory

Computer Science/Discrete Mathematics Seminar I
Topic:Matrix invariants and algebraic complexity theory
Speaker:Harm Derksen
Affiliation:University of Michigan
Date:Monday, October 17
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2016/1017-HarmDerksen

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.