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.