A note on border rank (Q794161): Difference between revisions

Approximative bilinear algorithms play an important role in the investigation of the complexity of matrix multiplication. In this paper the lower bound \(rk<n,n,n>\geq(3/2)n^ 2+n/2-1\) for the border rank \((=\) approximative bilinear complexity) of the structural tensor \(<n,n,n>\) of \(n\times n\) matrix multiplication is given. This result is based on a description of the algebraic variety \(X_ r=\{t:rk t\leq r\}\) of tensors of border rank \(\leq r\) by a certain existential condition. As another application of the given description of \(X_ r\) it can be shown that larger matrix multiplications always have larger approximative bilinear complexity, i.e., \(rk<n_ 1,n_ 2,n_ 3><rk<n_ 1,n_ 2,n_ 3+1>.\)