New Lower Bounds for the Rank of Matrix Multiplication
Joseph M. Landsberg · SIAM Journal on Computing · 2014
The rank of the matrix multiplication operator for ${\bf n}\times{\bf n}$ matrices is one of the most studied quantities in algebraic complexity theory. I prove that the rank is at least $3{\bf n}^2-o({\bf n}^2)$. More precisely, for any integer $p\leq {\bf n} -1$ the rank is at least $(3-\frac 1{p+1}){\bf n}^2-(1+2p\binom{2p}{p-1}){\bf n}$. The previous lower bound, due to Bläser, was $\frac 52{\bf n}^2-3{\bf n}$ (the case $p=1$). The new bounds improve Bläser's bound for all ${\bf n}>84$. I also prove lower bounds for rectangular matrices that are significantly better than the previous bound.