We prove a lower bound of 5/2n{sup}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 dimA－3(n{sub}1+…+n{sub}t) if the decomposition of A ≌ A{sub}1×…×A{sub}t into simple algebras A{sub}τ≌ D{sub}τ{sup}(n{sub}τ×n{sub}τ) contains only noncommutative factors, that is, the division algebra D{sub}τ is noncommutative or n{sub}τ≥2.
展开▼
