Sparsity Bound for Matrix Identities

Speaker: 

Time: 

Friday, 16 November 2018, 16:00 to 17:00

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

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!