What is the minimum number of multiplications for $2\times 3$ and $3\times 2$ multiplication?

Question

Strassen demonstrated a seven multiplication algorithm for $2\times 2$ matrix multiplication and Winograd showed its optimality.

Let $A$ be $2\times k$ and $B$ be $k\times 2$.

What is the minimum number of multiplications needed for the product $AB$ at any fixed $k\geq3$? Is there a reference?

Answer 1

A recent paper with relevant results is New lower bounds for matrix multiplication and the 3x3 determinant by Austin Conner, Alicia Harper, J.M. Landsberg, https://arxiv.org/abs/1911.07981. A fairly comprehensive book is Tensors: Geometry and Applications by J.M. Landsberg, https://bookstore.ams.org/gsm-128/. The author has made the first few chapters available for free, https://www.math.tamu.edu/~joseph.landsberg/Tbookintro.pdf. The book is from 2012, so it no longer represents the cutting edge of current work, but it has background and develops an introduction to the subject.

The rest of this answer will be some super-basic, very elementary explanation, I hope it is not too low-level for MathOverflow.

The "number of multiplications" is interpreted as the rank of a tensor. However most of the results (including results from Conner-Harper-Landsberg) are about border rank, instead of rank. It's not completely clear to me what exactly border rank represents, in concrete terms. Supposedly border rank is what matters for "practical" computations, but then it's not clear whether these matrix multiplication algorithms are "practical". So the results here aren't directly about the number of multiplications needed to multiply matrices; they are instead something like the number of multiplications for a sufficiently good approximation, which is theoretically good enough for all practical purposes, for an algorithm that's only of theoretical interest.

If someone else answers with some information about actual tensor rank of matrix multiplication tensors, that will probably be more relevant to the question.

With that out of the way, what are the results about border rank of these matrix multiplication tensors?

In short, multiplication of $2 \times k$ with $k \times 2$ matrices is represented by a tensor of border rank at least $3k$ (result of Landsberg-Ottaviani) and at most $3k+1$, for $k \leq 7$ (result of Smirnov). The Strassen $2 \times 2$ matrix multiplication is $k=2$, and it has border rank $7$. Conner-Harper-Landsberg show that for $k=3$, multiplication of $2 \times 3$ with $3 \times 2$ is represented by a tensor of border rank $10$. They conjecture ("we expect") that equality (border rank equal to $3k+1$) holds for all $k$.

To read this paper, or the Landsberg book, or any other papers in this field, one must deal with certain notation for tensors representing matrix multiplication. Here is my attempt at an explanation of this. Let us fix dimensions $a,b,c \geq 0$ and suppose we are interested in multiplying $a \times b$ with $b \times c$ matrices. This is a bilinear map $$\operatorname{Mat}_F(a,b) \otimes \operatorname{Mat}_F(b,c) \to \operatorname{Mat}_F(a,c)$$ (I'm writing $\operatorname{Mat}_F(a,b)$ for the space of $a \times b$ matrices over a field $F$) or in other words $$F^{a \times b} \otimes F^{b \times c} \to F^{a \times c},$$ hopefully the notation there is clear enough. As a bilinear map this corresponds to a tensor in $$ (F^{a \times b})^* \otimes (F^{b \times c})^* \otimes F^{a \times c} .$$ Recall that matrices are linear maps, so $F^{a \times b} \cong (F^a)^* \otimes F^b$, and similarly for the other factors. The above tensor product factors as: $$ (F^a \otimes F^{b*}) \otimes (F^b \otimes F^{c*}) \otimes (F^c \otimes F^{a*}) $$ (up to isomorphisms like $(V^* \otimes W)^* \equiv V \otimes W^*$, commutativity of tensor product, etc).

The tensor representing this matrix multiplication is denoted $M_{\langle \text{something} \rangle}$, where the question is, in what order should we list the dimensions $a,b,c$. It seems sensible to write $M_{\langle a,b,c \rangle}$, listing them in the same order as they are encountered in the matrix multiplication, $a \times b$ times $b \times c$. For some reason Conner-Harper-Landsberg have it $M_{\langle b,a,c \rangle}$ (also they use $\mathbf{l},\mathbf{n},\mathbf{m}$ instead of $a,b,c$), I don't know the reason for that choice. In the end, though, it doesn't matter: all the tensors are equal, $$ M_{\langle a,b,c \rangle} = M_{\langle a,c,b \rangle} = M_{\langle b,c,a \rangle} = \dotsb $$

To see why this is, perhaps it's helpful to recast the problem. Instead of a map that takes matrices $A$ and $B$ and tries to find the product $AB$, consider a map that takes three matrices $A,B,C$ and returns "the coefficient of $C$ in $AB$", or more precisely the inner product of $AB$ with $C$, where inner product just means the naive dot product on entries of the matrices, which we can do since $AB$ and $C$ have the same shape. But this dot product is a trace, $\operatorname{tr}(ABC^t)$. (In general if $M,N$ are matrices of the same shape, say both $a \times b$, the dot product $\sum_{i=1}^a \sum_{j=1}^b m_{ij}n_{ij} = \operatorname{tr}(MN^t)$, by straightforward calculation.) So, $M_{\langle a,b,c \rangle}$ corresponds to the trilinear map $(A,B,C) \mapsto \operatorname{tr}(ABC^t)$.

Well, by properties of trace, $$ \operatorname{tr}(ABC^t) = \operatorname{tr}(BC^tA) $$ and this translates into $M_{\langle a,b,c \rangle} = M_{\langle b,c,a \rangle}$, equivalence of multiplying $a\times b$ times $b \times c$, with multiplying $b \times c$ times $c \times a$. (There is some fiddling because we use $c \times a$ matrix $C^t$ instead of $a \times c$ matrix $C$, and likewise $b \times a$ matrix $A^t$ instead of $a \times b$ matrix $A$.) Likewise, by transposition, $$ \operatorname{tr}(ABC^t) = \operatorname{tr}(CB^tA^t) $$ which translates into $M_{\langle a,b,c \rangle} = M_{\langle c,b,a \rangle}$. Using these we can get all the permutations of $a,b,c$.

I am writing literal equality of tensors because they are all tensors in "the same" space $$ F^a \otimes F^{b*} \otimes F^b \otimes F^{c*} \otimes F^c \otimes F^{a*} , $$ well, "the same" space up to commutativity and associativity of tensor products.

With all of this, the original question is about multiplication of $2 \times k$ by $k \times 2$ matrices. I personally would have chosen to denote the tensor for this as $M_{\langle 2,k,2\rangle}$, for whatever reason it seems instead to be denoted $M_{\langle k,2,2\rangle}$, but in the end it doesn't matter, they are all the same, and all the same as $M_{\langle 2,2,k\rangle}$. And this tensor has border rank at least $3k$, conjecturally at most $3k+1$.

Finally to list out a few explicit identifications:

• $(2 \times k) \times (k \times 2)$ is $M_{\langle 2,k,2 \rangle}$
• $(2 \times 2) \times (2 \times k)$ is $M_{\langle 2,2,k \rangle}$
• $(k \times 2) \times (2 \times 2)$ is $M_{\langle k,2,2 \rangle}$

The above are all "the same" (up to commutativity and associativity of tensor products). In contrast,

• $(k \times 2) \times (2 \times k)$ is $M_{\langle k,2,k \rangle}$
• $(2 \times k) \times (k \times k)$ is $M_{\langle 2,k,k \rangle}$

and so on. The Conner-Harper-Landsberg paper discusses both of these (among many other cases). The multiplication in this MathOverflow question is $M_{\langle 2,2,k \rangle}$.