Lower bounds for matrix product

We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n × n matrices over finite fields. In particular we obtain the following results: 1. We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two n × n matrices over GF(2) is at least 3n² o(n²). 2. We show that the number of product gates in any bilinear circuit that computes the product of two n × n matrices over GF(p) is at least (2.5 + 1.5/p³-1)n² - o(n²). These results improve the former results of N.H. Bshouty (1997) and M. Blaser (1999) who proved lower bounds of 2.5n² o(n²).