School of Technology and Computer Science Seminars

Sparsity Bound for Matrix Identities

by Anamay Tengse (STCS, TIFR)

Friday, November 16, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
Abstract: A polynomial $f(x_1,\ldots,x_n)$ is said to be an identity for $m \times m$ matrices if $f(M_1,\ldots,M_n) = 0$ for all choices of $m \times m$ matrices for $M_i$s. It was shown by Levitzki in 1950 that any identity for $m \times m$ matrices has to have a degree of at least $2m$. The \emph{Amitsur-Levitzki theorem} then provided an identity of degree $2m$ for $m \times m$ matrices for all $m$.

In this talk, we will see a bound on the number of monomials (sparsity) of an identity for $m \times m$ matrices, due to Arvind, Joglekar, Mukhopadhyay and Raja (STOC 2017). They showed that if $f$ is a polynomial with $t$ monomials, then it cannot be an identity for $m \times m$ matrices, whenever $m > \log_2{t}$.

P.S. : It is worth mentioning that the proof involves an elegant use of nondeterministic automata!
Organised by Sayantan Chakraborty