New lower bounds for the rank of matrix multiplication

Introduction

If $T$ is a tensor of border rank $r$, where the approximating curve of rank $r$ tensors limits in such a way that $q$ derivatives of the curve are used, then the rank of $T$ is at most $(2q-1)r$, see [3, Prop. 15.26]. In they give explicit, but very large upper bounds on the order of approximation $h$ needed to write a tensor of border rank $r$ as lying in the $h$-jet of a curve of tensors of rank $r$.

The language of tensors will be used throughout. In §2 the language of tensors is introduced and previous work of Bläser and others is rephrased in a language suitable for generalizations. In §3 I describe the equations of and give a very easy proof of a slightly weaker result than Theorem 1.1. In §4 I express the equations in coordinates and prove Theorem 1.1. I work over the complex numbers throughout.

I thank the anonymous referee for useful suggestions and C. Ikenmeyer for help with the exposition.

Ranks and border ranks of tensors

The following proposition is a rephrasing of part of the proof in :

As stated, the proposition is useless, as the degrees of polynomials vanishing on on all tensors of border rank at most $r$ are greater than $r$. (A general tensor of border rank $r$ also has rank $r$.) However the conclusion still holds if one can find, for a given tensor $T$, a polynomial, or collection of polynomials on smaller spaces, such that the nonvanishing of $P$ on $T$ is equivalent to the non-vanishing of the new polynomials. Then one substitutes the smaller degree into the statement to obtain the nontrivial lower bound.

To prove the Proposition, we need a standard Lemma, also used in , which appears in this form in [4, Lemma 11.5.0.2]:

The lemma follows by simply choosing a monomial that appears in $P$, as it can involve at most $d$ basis vectors.

Let $A$ be given a basis. Given a homogeneous polynomial of degree $d$ on the Grassmannian $G(k,A)$, there exists at least $dk$ basis vectors such that, denoting their (at most) $dk$-dimensional span by $A^{\prime}$, $P$ restricted to $G(k,A^{\prime})$ is not identically zero.

Consider the map $f:A^{\times k}\rightarrow G(k,A)$ given by $(a_{1},\ldots,a_{k})\mapsto[a_{1}\wedge\cdots\wedge a_{k}]$. Then $f$ is surjective. Take the polynomial $P$ and pull it back by $f$. (The pullback $f^{*}(P)$ is defined by $f^{*}(P)(a_{1},\ldots,a_{k}):=P(f(a_{1},\ldots,a_{k}))$.) The pullback is of degree $d$ in each copy of $A$. (I.e., fixing $k-1$ parameters, it becomes a degree $d$ polynomial in the $k$-th.) Now simply apply Lemma 2.2 $k$ times to see that the pulled back polynomial is not identically zero restricted to $A^{\prime}$, and thus $P$ restricted to $G(k,A^{\prime})$ is not identically zero. ∎

Matrix multiplication and its rank

The equations of [5] in coordinates

so the corresponding matrix for $T_{A}^{\wedge 1}$ is the block matrix

Now assume $X_{0}$ is invertible and change bases such that it is the identity matrix. Recall the formula for block matrices

I now phrase the equations of in coordinates. Let $\operatorname{dim}A=2p+1$. Write $T=a_{0}{\mathord{\otimes}}X_{0}+\cdots+a_{2p}{\mathord{\otimes}}X_{2p}$. The expression of (1) in bases is as follows: write $a_{I}:=a_{i_{1}}\wedge\cdots\wedge a_{i_{p}}$ for $\Lambda^{p}A$, require that the first $\binom{2p}{p-1}$ basis vectors have $i_{1}=0$, that the second $\binom{2p}{p}$ do not, and call these multi-indices $0J$ and $K$. Order the bases of $\Lambda^{p+1}A$ such that the first $\binom{2p}{p+1}$ multi-indices do not have , and the second $\binom{2p}{p}$ do, and furthermore that the second set of indices is ordered the same way as $K$, only we write $0K$ since a zero index is included. Then the resulting matrix is of the form

References