We prove a lower bound of 5/2n~2 - 3n for the multiplicative complexity of n * 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 5/2 dim A - 3(n_1 + … + n_t) if the decomposition of A approx= A_1 * … * A_t into simple algebras A_τ approx= D_τ~(n_τ * n_τ) contains only noncommutative factors, that is, the division algebra D_τ is noncommutative or n_τ ≥ 2.
展开▼
