Beyond the Alder-Strassen bound

We prove a lower bound of 5/2 n(2) - 3n for the multiplicative complexity of n x n-matrix multiplication over arbitrary fields. More general, we show that for any finite dimensional semisimple algebra A with unity, the multiplicative complexity C (A) of the multiplication in A is bounded from below by 5/2 dim A - 3(n(1) + ... + n(t)) if the decomposition of A congruent to A(1) x ... x A(t) into simple algebras A(tau) congruent to D-tau(tau)tau(n)xn contains only noncommutative factors, that is, the division algebra D-tau is noncommutative or ntau greater than or equal to 2. We also deal with the complexity of multiplication in algebras with nonzero radical. We present an example that shows that our methods in the semisimple case cannot be applied directly to this problem. We exhibit lower bound techniques for C (A) that yield bounds still significantly above the Alder-Strassen bound. The main application is the lower bound C (T-n (k)) greater than or equal to (2 1/8 - o(1)) dim T-n (k) for the multiplicative complexity of multiplication in the algebra Tn (k) of upper triangular n x n-matrices. (C) 2004 Elsevier B.V. All rights reserved.