Lower bounds for the bilinear complexity of associative algebras |
| |
Authors: | M Bl?ser |
| |
Affiliation: | (1) Institut für theoretische Informatik, Med. Universit?t zu Lübeck, Wallstr. 40, 23560 Lübeck, Germany, e-mail: blaeser@tcs.mu-luebeck.de , DE |
| |
Abstract: | Let R(A) denote the bilinear complexity (also called rank) of a finite dimensional associative algebra A.?We prove that if the decomposition of into simple algebras contains only noncommutative factors, that is, the division algebra is noncommutative or . In particular, -matrix multiplication requires at least essential bilinear multiplications. We also derive lower bounds of the form essential bilinear multiplications. We also derive lower bounds of the form for the algebra of upper triangular -matrices and the algebra of truncated bivariate polynomials in the indeterminates X,Y over some field k.?A class of algebras that has received wide attention in this context con-sists of those algebras A for which the Alder—Strassen Bound is sharp, i.e., R(A) = 2dim A—t is the number of maximal twosided ideals in A. These algebras are called algebras of minimal rank. We determine all semisimple algebras of minimal rank over arbitrary
fields and all algebras of minimal rank over algebraically closed fields.
Received: January 12, 2000. |
| |
Keywords: | , Associative algebras, bilinear complexity, lower bound, matrix multiplication, rank, substitution method, |
本文献已被 SpringerLink 等数据库收录! |
|