A lower bound for the border rank of a bilinear map (Q1088760): Difference between revisions

Let A and M be finite-dimensional vector spaces over an algebraically closed field and \(f: A\times M\to M\) a bilinear map. Choosing bases in A and M, f can be described by its component bilinear forms \(f_ i\). In the analysis of the computational complexity of the \(f_ i\) the concepts of rank R(f) and border rank Ṟ(f) arise naturally: these are the number of nonscalar multiplications necessary and sufficient to compute or approximate, respectively, the \(f_ i\) in the (noncommuting) indeterminates. The author generalizes a theorem of Strassen to obtain lower bounds for the border rank of tensors and gives some applications.