__
TR01-060 | 23rd August 2001 00:00
__

#### Lower bounds for matrix product

**Abstract:**
We prove lower bounds on the number of product gates in bilinear

and quadratic circuits that

compute the product of two $n \times 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 \times n$ matrices over $GF(2)$ is at

least $3 n^2 - o(n^2)$.

2. We show that the number of product gates in any bilinear circuit

that computes the product of two $n \times n$ matrices over $GF(p)$ is at

least $(2.5 + \frac{1.5}{p^3 -1})n^2 -o(n^2)$.

These results improve the former results of Bshouty (89) and Blaser

(99) who proved lower bounds of $2.5 n^2 - o(n^2)$.