A 5/2n~2-Lower Bound for the Multiplicative Complexity of n x n-Matrix Multiplication

摘要

We prove a lower bound of 5/2n~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 of the multiplication in A is bounded from below by f dim A - 3(n_1 + ... + n_t) if the decomposition of A ≈ A_1 x ... x A_t into simple algebras A_T ≈ D_T~(n_T) X n_T contains only noncommutative factors, that is, the division algebra D_T is noncommu-tative or n_T ≥ 2.