Computer Science/Discrete Mathematics Seminar I

Matrix invariants and algebraic complexity theory

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.

Date & Time

October 17, 2016 | 11:15am – 12:15pm

Location

S-101

Speakers

Harm Derksen

Affiliation

University of Michigan