# Flip Graphs for Matrix Multiplication

Manuel Kauers ∗ and  Jakob Moosbauer † Manuel Kauers, Institute for Algebra,
J. Kepler University Linz, Austria<EMAIL_ADDRESS>Jakob Moosbauer,
Institute for Algebra, J. Kepler University Linz, Austria
<EMAIL_ADDRESS>
###### Abstract.

We introduce a new method for discovering matrix multiplication schemes based
on random walks in a certain graph, which we call the flip graph. Using this
method, we were able to reduce the number of multiplications for the matrix
formats $(4,4,5)$ and $(5,5,5)$, both in characteristic two and for arbitrary
ground fields.

###### Key words and phrases:

Bilinear complexity; Strassen’s algorithm; Tensor rank

∗ Supported by the Austrian FWF grants P31571-N32 and I6130-N

† Supported by the Land Oberösterreich through the LIT-AI Lab

##  1\. Introduction

Nobody knows the computational cost of computing the product of two matrices.
Strassen’s discovery [17] that two $2\times 2$-matrices can be multiplied with
only 7 multiplications in the ground field launched intensive research on the
complexity of matrix multiplication during the past decades. One branch of
this research aims at finding upper (or possibly also lower) bounds on the
matrix multiplication exponent $\omega$. The current world record
$\omega<2.37188$ is held by Duan, Wu and Zhou [7] and only slightly improves
the previous record $\omega<2.37286$ by Alman and Williams [1]. These results
concern asymptotically large matrix sizes.

Another branch of research on matrix multiplication algorithms concerns
specific small matrix sizes. For $2\times 2$ matrices, it is known that there
is no way to do the job with only 6 multiplications [19], and that Strassen’s
algorithm is essentially the only way to do it with 7 [6]. Also for
multiplying a $2\times 2$ matrix with a $2\times p$ matrix and for multiplying
a $2\times 3$ matrix with a $3\times 3$ matrix, optimal algorithms are known
[11]. For all other formats, the known upper and lower bounds do not match.
For example, for the case $3\times 3$ times $3\times 3$, the best known upper
bound is 23 [14] and the best known lower bound is 19 [2] unless we impose
restrictions on the ground domain such as commutativity.

An upper bound for a specific matrix format can be obtained by stating an
explicit matrix multiplication scheme with as few multiplications as possible.
Such schemes can be discovered by various techniques, including hand
calculation [17, 14], numerical methods [16, 15], SAT solving [5, 10, 9], or
machine learning [8]. The latter approach, due to Fawzi et al., has received a
lot of attention, even in the general public, because it led to an unexpected
improvement of the upper bound for multiplying two $4\times 4$ matrices from
49 to 47 multiplications in characteristic two. They also reduced the bound
for multiplying two $5\times 5$ matrices from 98 to 96 in characteristic two,
and found improvements for some formats involving rectangular matrices.

In our quick response [12] to the paper of Fazwi et al., we announced that we
can find further schemes for $4\times 4$ matrices using 47 multiplications in
characteristic two, and that we can reduce the number of multiplications
required for $5\times 5$ matrices in characteristic two to 95. In the present
paper, we introduce the method by which we found these schemes.

We define a graph whose vertices are correct matrix multiplication schemes and
where there is an edge from one scheme to another if the second can be
obtained from the first by some kind of transformation. We consider two
transformations. One is called a flip and turns a given scheme to a different
one with the same number of multiplications, and the other is called a
reduction and turns a given scheme to one with a smaller number of
multiplications. The precise construction of this flip graph is given in Sect.
3. In Sect. 4, we illustrate (parts of) the flip graph for $2\times 2$ and
$3\times 3$ matrices.

In order to find better upper bounds for a specific format, we start from a
known scheme, e.g., the standard algorithm, and perform a random walk in the
flip graph. Although reduction edges are much more rare than flip edges, it
turned out that there are enough of them to reach interesting schemes with a
reasonable amount of computation time. In particular, we were able to match
the best known algorithms for all multiplication formats $n\times m$ times
$m\times p$ with $n,m,p\leq 5$, and found better bounds in four cases. These
results are reported in Sect. 5.

##  2\. Matrix Multiplication

Let $K$ be a field, let $R$ be a $K$-Algebra and let $\mathbf{A}\in R^{n\times
m}$, $\mathbf{B}\in R^{m\times p}$. Recall that the computation of the matrix
product $\mathbf{C}=\mathbf{A}\mathbf{B}$ by a Strassen-like algorithm
proceeds in two stages. In the first stage we compute certain products
$m_{1},\ldots,m_{r}$ of linear combinations of entries of $\mathbf{A}$ and
linear combinations of entries of $\mathbf{B}$. In the second stage the
entries of $\mathbf{C}$ are obtained as linear combinations of the $m_{i}$. An
algorithm of this form is called a bilinear algorithm [4].

For example, in the case $n=m=p=2$, if we let

$\mathbf{A}=\begin{pmatrix}a_{1,1}&a_{1,2}\\\ a_{2,1}&a_{2,2}\\\
\end{pmatrix},\quad\mathbf{B}=\begin{pmatrix}b_{1,1}&b_{1,2}\\\
b_{2,1}&b_{2,2}\end{pmatrix}\quad\text{and}\quad\mathbf{C}=\begin{pmatrix}c_{1,1}&c_{1,2}\\\
c_{2,1}&c_{2,2}\end{pmatrix},$

then Strassen’s algorithm computes $\mathbf{C}$ in the following way:

$\displaystyle m_{1}$ $\displaystyle=(a_{1,1}+a_{2,2})(b_{1,1}+b_{2,2})$
$\displaystyle\quad\smash{\raisebox{-76.79993pt}{\rule{0.4pt}{84.0pt}}}\quad
c_{1,1}$ $\displaystyle=m_{1}+m_{4}-m_{5}+m_{7}$ $\displaystyle m_{2}$
$\displaystyle=(a_{2,1}+a_{2,2})(b_{1,1})$ $\displaystyle c_{1,2}$
$\displaystyle=m_{3}+m_{5}$ $\displaystyle m_{3}$
$\displaystyle=(a_{1,1})(b_{1,2}-b_{2,2})$ $\displaystyle c_{2,1}$
$\displaystyle=m_{2}+m_{4}$ $\displaystyle m_{4}$
$\displaystyle=(a_{2,2})(b_{2,1}-b_{1,1})$ $\displaystyle c_{2,2}$
$\displaystyle=m_{1}-m_{2}+m_{3}+m_{6}.$ $\displaystyle m_{5}$
$\displaystyle=(a_{1,1}+a_{1,2})(b_{2,2})$ $\displaystyle m_{6}$
$\displaystyle=(a_{2,1}-a_{1,1})(b_{1,1}+b_{1,2})$ $\displaystyle m_{7}$
$\displaystyle=(a_{1,2}-a_{2,2})(b_{2,1}+b_{2,2})$

It is common and convenient to express matrix multiplication in the language
of tensors. For $2\times 2$ matrices, the matrix multiplication tensor is

$\mathcal{M}_{2,2,2}=\sum_{i,j,k=1}^{2}E_{i,j}\otimes E_{j,k}\otimes
E_{k,i}\in K^{2\times 2}\otimes K^{2\times 2}\otimes K^{2\times 2},$

where $E_{u,v}$ refers to the matrix having a $1$ at position $(u,v)$ and
zeros elsewhere. Strassen’s algorithm is based on the observation that this
tensor can also be written as the sum of only seven tensors of the form
$A\otimes B\otimes\varGamma$. Indeed, we have

$\displaystyle\mathcal{M}_{2,2,2}$
$\displaystyle=(a_{1,1}+a_{2,2})\otimes(b_{1,1}+b_{2,2})\otimes(c_{1,1}+c_{2,2})$
$\displaystyle+(a_{2,1}+a_{2,2})\otimes(b_{1,1})\otimes(c_{1,2}-c_{2,2})$
$\displaystyle+(a_{1,1})\otimes(b_{1,2}-b_{2,2})\otimes(c_{2,1}+c_{2,2})$
$\displaystyle+(a_{2,2})\otimes(b_{2,1}-b_{1,1})\otimes(c_{1,1}+c_{1,2})$
$\displaystyle+(a_{1,1}+a_{1,2})\otimes(b_{2,2})\otimes(c_{2,1}-c_{1,1})$
$\displaystyle+(a_{2,1}-a_{1,1})\otimes(b_{1,1}+b_{1,2})\otimes(c_{2,2})$
$\displaystyle+(a_{1,2}-a_{2,2})\otimes(b_{2,1}+b_{2,2})\otimes(c_{1,1}),$

where for better readability we write $a_{i,j},b_{i,j},c_{i,j}$ instead of
$E_{i,j}$. Readers not comfortable with tensor products are welcome to
understand $a_{i,j},b_{i,j},c_{i,j}$ as polynomial variables and $\otimes$ as
multiplication. Note that each row in the expression above corresponds to one
of the $m_{i}$’s from before. The first two factors encode their definitions
and the third how they enter into the $c_{j,i}$. Note also that the indices in
the third factor are swapped in order to be consistent with the matrix
multiplication literature, where this version is preferred because it makes
certain equations more symmetric.

The general definition is as follows.

######  Definition 1.

Let $n,m,p\in\mathbb{N}$. The matrix multiplication tensor of the format
$(n,m,p)$ is defined as

$\mathcal{M}_{n,m,p}=\sum_{i,j,k=1}^{n,m,p}a_{i,j}\otimes b_{j,k}\otimes
c_{k,i}\in K^{n\times m}\otimes K^{m\times p}\otimes K^{p\times n},$

where $a_{u,v},b_{u,v},c_{u,v}$ refer to matrices of the respective format
having a $1$ at position $(u,v)$ and zeros in all other positions.

Rank-one tensors are non-zero tensors that can be written as $A\otimes
B\otimes\varGamma$ for certain matrices $A\in K^{n\times m}$, $B\in K^{m\times
p}$, $\varGamma\in K^{p\times m}$. The rank of a tensor $\mathcal{T}$ is the
smallest number $r$ such that $\mathcal{T}$ can be written as a sum of $r$
rank-one tensors.

An $(n,m,p)$-matrix multiplication scheme is a finite set $S$ of rank-one
tensors whose sum is $\mathcal{M}_{n,m,p}$. We call $|S|$ the rank of the
scheme.

The sum of $k$ linearly independent rank-one tensors need not necessarily have
tensor rank $k$. Strassen’s discovery amounts precisely to the observation
that $\mathcal{M}_{2,2,2}$, which is defined as a sum of 8 linearly
independent rank-one tensors, has only rank 7. A more simple example is the
equation

$\displaystyle a_{1,1}\otimes b_{1,1}\otimes c_{1,1}\ +\ a_{1,1}\otimes
b_{1,2}\otimes c_{3,1}\ +\ a_{1,1}\otimes(b_{1,1}+b_{1,2})\otimes c_{2,2}$
$\displaystyle=a_{1,1}\otimes b_{1,1}\otimes(c_{1,1}+c_{2,2})\ +\
a_{1,1}\otimes b_{1,2}\otimes(c_{3,1}+c_{2,2}).$

If a matrix multiplication scheme contains the three rank-one tensors in the
first line, we can replace them by the two rank-one tensors in the second line
and thereby reduce the rank by one. This observation can be generalized as
follows.

######  Definition 2.

Let $n,m,p,r\in\mathbb{N}$ and let $S=\\{A^{(i)}\otimes
B^{(i)}\otimes\varGamma^{(i)}\mid i\in\\{1,\ldots,r\\}\\}$ be an
$(n,m,p)$-matrix multiplication scheme. We call $S$ _reducible_ if there is a
nonempty set $I\subseteq\\{1,\ldots,r\\}$ such that

  1. (1)

$\dim_{K}\langle A^{(i)}\rangle_{i\in I}=1$ and

  2. (2)

$\\{B^{(i)}\mid i\in I\\}$ is linearly dependent over $K$,

or analogously with $B,A$ or $A,\varGamma$ or $\varGamma,A$ or $B,\varGamma$
or $\varGamma,B$ in place of $A,B$.

######  Proposition 3.

Let $n,m,p,r\in\mathbb{N}$ and let $S$ be a reducible $(n,m,p)$-matrix
multiplication scheme of rank $r$. Then there exists an $(n,m,p)$-matrix
multiplication scheme of rank $r-1$.

###### Proof.

We prove the statement in the case that the conditions in Def. 2 hold for $A$
and $B$. In the other cases the proof works analogously. Since $\\{B^{(i)}\mid
i\in I\\}$ is linearly dependent, there is a $t\in I$ such that
$B^{(t)}=\sum_{i\in I\setminus\\{t\\}}\beta_{i}B^{(i)}$ for some $\beta_{i}\in
K$. Moreover, there are $\alpha_{i}\in K$ such that
$A^{(t)}=\alpha_{i}A^{(i)}$. Hence, we have

$\displaystyle\sum_{i\in I}A^{(i)}\otimes B^{(i)}\otimes\varGamma^{(i)}$
$\displaystyle=\sum_{i\in I\setminus\\{t\\}}A^{(i)}\otimes
B^{(i)}\otimes\varGamma^{(i)}+\alpha_{i}A^{(i)}\otimes\sum_{i\in
I\setminus\\{t\\}}\beta_{i}B^{(i)}\otimes\varGamma^{(t)}$
$\displaystyle=\sum_{i\in I\setminus\\{t\\}}A^{(i)}\otimes
B^{(i)}\otimes\varGamma^{(i)}+\sum_{i\in I\setminus\\{t\\}}A^{(i)}\otimes
B^{(i)}\otimes\alpha_{i}\beta_{i}\varGamma^{(t)}$ $\displaystyle=\sum_{i\in
I\setminus\\{t\\}}A^{(i)}\otimes
B^{(i)}\otimes(\varGamma^{(i)}+\alpha_{i}\beta_{i}\varGamma^{(t)})$

Therefore,

$\displaystyle S^{\prime}={}$ $\displaystyle\\{A^{(i)}\otimes
B^{(i)}\otimes\varGamma^{(i)}\mid i\in\\{1,\ldots,r\\}\setminus I\\}$
$\displaystyle{}\cup\\{A^{(i)}\otimes
B^{(i)}\otimes(\varGamma^{(i)}+\alpha_{i}\beta_{i}\varGamma^{(t)})\mid i\in
I\setminus\\{t\\}\\}$

is a multiplication scheme with rank $r-1$. ∎

We call a scheme $S^{\prime}$ constructed as above a _reduction_ of $S$.

Symmetries of the matrix multiplication tensor $\mathcal{M}_{n,m,p}$ give rise
to various ways to transform a given matrix multiplication scheme into another
one. For example, because of the identity
$(\mathbf{A}\mathbf{B})^{\top}=\mathbf{B}^{\top}\mathbf{A}^{\top}$, exchanging
each rank-one tensor $A\otimes B\otimes\varGamma$ by $B^{\top}\otimes
A^{\top}\otimes\varGamma^{\top}$ maps a correct scheme to another correct
scheme. A correct scheme is also obtained if we replace every rank-one tensor
$A\otimes B\otimes\varGamma$ by $B\otimes\varGamma\otimes A$. Finally, if
$U\in K^{m\times m}$ is invertible, then the identity
$\mathbf{A}\mathbf{B}=\mathbf{A}UU^{-1}\mathbf{B}$ implies that also replacing
every rank-one tensor $A\otimes B\otimes\varGamma$ by $AU\otimes
U^{-1}B\otimes\varGamma$ maps a correct scheme to another one. These
transformations generate the symmetry group of $\mathcal{M}_{n,m,p}$. For more
details on this group see [6, 13]. We can let the symmetry group act on the
set of matrix multiplications and call two schemes equivalent if they belong
to the same orbit.

Def. 2 is compatible with the action of the symmetry group. For permutations,
this is because the definition explicitly allows any two factors to take the
roles of $A$ and $B$, and linear dependence is preserved under transposition.
Likewise, if some matrices $B^{(i)}$ ($i\in I$) are linearly dependent, then
so are the matrices $VB^{(i)}W^{-1}$ ($i\in I$) for any invertible matrices
$V,W$. Therefore, we can extend Def. 2 from individual matrix multiplication
schemes to equivalence classes.

##  3\. The Flip Graph

As reducibility is preserved by the application of a symmetry, the only chance
to get from an irreducible to a reducible scheme is by a transformation that,
at least in general, does not preserve symmetry. Flips have this feature. The
idea is to subtract something from one rank-one tensor and add it to one of
the others. This can be done for any two rank-one tensors that share a common
factor. For example, we have

$\displaystyle A\otimes B\otimes\varGamma\ +\ A\otimes
B^{\prime}\otimes\varGamma^{\prime}$
$\displaystyle=A\otimes(B+B^{\prime})\otimes\varGamma\ +\ A\otimes
B^{\prime}\otimes(\varGamma^{\prime}-\varGamma).$

In contrast to a symmetry transformation, this transformation only affects two
elements of the multiplication scheme instead of all. Therefore, we can in
general expect the resulting scheme to be non-equivalent to the original one.

######  Definition 4.

Let $n,m,p,r\in\mathbb{N}$ and let $S,S^{\prime}$ be $(n,m,p)$-matrix
multiplication schemes of rank $r$. We call $S^{\prime}$ a _flip_ of $S$ if
there are

  1. (1)

$T_{1}=A\otimes B\otimes\varGamma\in S$,

  2. (2)

$T_{2}=A\otimes B^{\prime}\otimes\varGamma^{\prime}\in S$ and

  3. (3)

$T\in\\{A\otimes B\otimes\varGamma^{\prime},A\otimes
B^{\prime}\otimes\varGamma\\}$

such that $(S\setminus\\{T_{1},T_{2}\\})\cup\\{T_{1}+T,T_{2}-T\\}=S^{\prime}$.

The definition is meant to apply analogously for any permutation of $A,B$ and
$\varGamma$.

The union is always disjoint since we require $S$ and $S^{\prime}$ to be of
the same rank. Cases where $S^{\prime}$ would have a smaller rank than $S$
need not be included because in these cases $S^{\prime}$ is a reduction of
$S$. Note that flips are reversible because if
$S^{\prime}=(S\setminus\\{T_{1},T_{2}\\})\cup\\{T_{1}+T,T_{2}-T\\}$, then
$S=(S^{\prime}\setminus\\{T_{2}-T,T_{1}+T\\})\cup\\{(T_{2}-T)+T,(T_{1}+T)-T\\}$.

Flips are well-defined for equivalence classes of matrix multiplication
schemes in the following sense: If $S^{\prime}$ is a flip of $S$ and $g$ is an
element of the symmetry group, then $g(S)$ is a flip of $g(S^{\prime})$. This
is the case since Def. 4 applies for arbitrary permuations of $A,B,\varGamma$
and because the symmetry transformations act linearly on the individual
matrices.

Def. 4 introduces flips as rather specific ways of replacing two rank-one
tensors in a given scheme by some other rank-one tensors. However, it turns
out that if we only want to replace two rank-one tensors at a time, then there
is not much more we can do. Thm. 7 makes this more precise.

######  Lemma 5.

Let $U,V$ and $W$ be vector spaces. For $i=1,\dots,4$, let $A^{(i)}\in
U,B^{(i)}\in V,\varGamma^{(i)}\in W$ be such that

(1) $\displaystyle\begin{split}&A^{(1)}\otimes
B^{(1)}\otimes\varGamma^{(1)}+A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\\\
&=A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)}+A^{(4)}\otimes
B^{(4)}\otimes\varGamma^{(4)}\end{split}$

and

$\dim\langle A^{(1)},A^{(2)}\rangle=\dim\langle
B^{(1)},B^{(2)}\rangle=\dim\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=2.$

Then

$\displaystyle\bigl{\\{}A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)},\
A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\bigr{\\}}$
$\displaystyle=\bigl{\\{}A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)},\
A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}\bigr{\\}}.$

###### Proof.

Since $A^{(1)}$ and $A^{(2)}$, $B^{(1)}$ and $B^{(2)}$, and $\varGamma^{(1)}$
and $\varGamma^{(2)}$ are linearly independent, there are

$\displaystyle\alpha_{1},\alpha_{2},\alpha^{\prime}_{1},\alpha^{\prime}_{2},\beta_{1},\beta_{2},\beta^{\prime}_{1},\beta^{\prime}_{2},\gamma_{1},\gamma_{2},\gamma^{\prime}_{1},\gamma^{\prime}_{2}\in
K,$ $\displaystyle A,A^{\prime}$ $\displaystyle\in U\setminus\langle
A^{(1)},A^{(2)}\rangle,$ $\displaystyle B,B^{\prime}$ $\displaystyle\in
V\setminus\langle B^{(1)},B^{(2)}\rangle,$
$\displaystyle\varGamma,\varGamma^{\prime}$ $\displaystyle\in
W\setminus\langle\varGamma^{(1)},\varGamma^{(2)}\rangle$

such that

$\displaystyle A^{(3)}$
$\displaystyle=\alpha_{1}A^{(1)}+\alpha_{2}A^{(2)}+A,\qquad$ $\displaystyle
A^{(4)}$
$\displaystyle=\alpha^{\prime}_{1}A^{(1)}+\alpha^{\prime}_{2}A^{(2)}+A^{\prime},$
$\displaystyle B^{(3)}$ $\displaystyle=\beta_{1}B^{(1)}+\beta_{2}B^{(2)}+B,$
$\displaystyle B^{(4)}$
$\displaystyle=\beta^{\prime}_{1}B^{(1)}+\beta^{\prime}_{2}B^{(2)}+B^{\prime},$
$\displaystyle\varGamma^{(3)}$
$\displaystyle=\gamma_{1}\varGamma^{(1)}+\gamma_{2}\varGamma^{(2)}+\varGamma,$
$\displaystyle\varGamma^{(4)}$
$\displaystyle=\gamma^{\prime}_{1}\varGamma^{(1)}+\gamma^{\prime}_{2}\varGamma^{(2)}+\varGamma^{\prime}.$

After plugging these in (1) and equating coefficients we obtain the following
system of equations:

$\displaystyle\alpha_{1}\beta_{1}\gamma_{1}+\alpha^{\prime}_{1}\beta^{\prime}_{1}\gamma^{\prime}_{1}$
$\displaystyle=1,\qquad$
$\displaystyle\alpha_{1}\beta_{1}\gamma_{2}+\alpha^{\prime}_{1}\beta^{\prime}_{1}\gamma^{\prime}_{2}$
$\displaystyle=0,$
$\displaystyle\alpha_{1}\beta_{2}\gamma_{1}+\alpha^{\prime}_{1}\beta^{\prime}_{2}\gamma^{\prime}_{1}$
$\displaystyle=0,\qquad$
$\displaystyle\alpha_{1}\beta_{2}\gamma_{2}+\alpha^{\prime}_{1}\beta^{\prime}_{2}\gamma^{\prime}_{2}$
$\displaystyle=0,$
$\displaystyle\alpha_{2}\beta_{1}\gamma_{1}+\alpha^{\prime}_{2}\beta^{\prime}_{1}\gamma^{\prime}_{1}$
$\displaystyle=0,\qquad$
$\displaystyle\alpha_{2}\beta_{1}\gamma_{2}+\alpha^{\prime}_{2}\beta^{\prime}_{1}\gamma^{\prime}_{2}$
$\displaystyle=0,$
$\displaystyle\alpha_{2}\beta_{2}\gamma_{1}+\alpha^{\prime}_{2}\beta^{\prime}_{2}\gamma^{\prime}_{1}$
$\displaystyle=0,\qquad$
$\displaystyle\alpha_{2}\beta_{2}\gamma_{2}+\alpha^{\prime}_{2}\beta^{\prime}_{2}\gamma^{\prime}_{2}$
$\displaystyle=1.$

A straightforward computation confirms that these equations imply that either
$\alpha_{1}\beta_{1}\gamma_{1}=\alpha^{\prime}_{2}\beta^{\prime}_{2}\gamma^{\prime}_{2}=1$
and all other variables are $0$ or
$\alpha_{2}\beta_{2}\gamma_{2}=\alpha^{\prime}_{1}\beta^{\prime}_{1}\gamma^{\prime}_{1}=1$
and all other variables are $0$. It follows further that
$A,A^{\prime},B,B^{\prime},C,C^{\prime}$ need to be zero, which completes the
proof. ∎

######  Lemma 6.

Let $U,V$ be vector spaces. Let $B^{(1)},B^{(2)},B^{(3)},B^{(4)}\in U$ and
$\varGamma^{(1)},\varGamma^{(2)},\varGamma^{(3)},\varGamma^{(4)}\in V$ be such
that

$B^{(1)}\otimes\varGamma^{(1)}+B^{(2)}\otimes\varGamma^{(2)}=B^{(3)}\otimes\varGamma^{(3)}+B^{(4)}\otimes\varGamma^{(4)},$

$\dim\langle
B^{(1)},B^{(2)}\rangle=\dim\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=2$,
and $\varGamma^{(3)},\varGamma^{(4)}\neq 0$.

Then $\langle B^{(1)},B^{(2)}\rangle=\langle B^{(3)},B^{(4)}\rangle$ and
$\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=\langle\varGamma^{(3)},\varGamma^{(4)}\rangle$.

###### Proof.

Since $\varGamma^{(1)},\varGamma^{(2)},\varGamma^{(3)},\varGamma^{(4)}\neq 0$
the equality implies that $B^{(1)},B^{(2)},B^{(3)},B^{(4)}$ are linearly
dependent. Therefore, there exist $\mu,\nu,\lambda\in K$ such that
$B^{(1)}=\mu B^{(2)}+\nu B^{(3)}+\lambda B^{(4)}$. It follows

$B^{(2)}\otimes(\varGamma^{(2)}+\mu\varGamma^{(1)})=B^{(3)}\otimes(\varGamma^{(3)}-\nu\varGamma^{(1)})+B^{(4)}\otimes(\varGamma^{(4)}-\lambda\varGamma^{(1)}).$

Since $\varGamma^{(1)}$ and $\varGamma^{(2)}$ are linearly independent this
implies $B^{(2)}\in\langle B^{(3)},B^{(4)}\rangle$. For the same reason we
have $B^{(1)}\in\langle B^{(3)},B^{(4)}\rangle$ and since $B^{(1)}$ and
$B^{(2)}$ are linearly independent it follows $\langle
B^{(1)},B^{(2)}\rangle=\langle B^{(3)},B^{(4)}\rangle$. The equality
$\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=\langle\varGamma^{(3)},\varGamma^{(4)}\rangle$
is shown by the same argument. ∎

######  Theorem 7.

Let $U,V$ and $W$ be vector spaces. For $i=1,\dots,4$, let $A^{(i)}\in
U\setminus\\{0\\},B^{(i)}\in V\setminus\\{0\\},\varGamma^{(i)}\in
W\setminus\\{0\\}$ be such that

(2) $\displaystyle\begin{split}&A^{(1)}\otimes
B^{(1)}\otimes\varGamma^{(1)}+A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\\\
&=A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)}+A^{(4)}\otimes
B^{(4)}\otimes\varGamma^{(4)},\end{split}$

$\dim\langle
B^{(1)},B^{(2)}\rangle=\dim\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=2$,
and

$\displaystyle\bigl{\\{}A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)},\
A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\bigr{\\}}$
$\displaystyle\neq\bigl{\\{}A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)},\
A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}\bigr{\\}}.$

Then the following hold:

  1. (1)

$\dim\langle A^{(1)},A^{(2)},A^{(3)},A^{(4)}\rangle=1$

  2. (2)

$\langle B^{(1)},B^{(2)}\rangle=\langle B^{(3)},B^{(4)}\rangle$

  3. (3)

$\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=\langle\varGamma^{(3)},\varGamma^{(4)}\rangle$

###### Proof.

We start by showing the first claim. If $A^{(1)}$ and $A^{(2)}$ are linearly
independent, then it follows from Lemma 5 that

$\displaystyle\bigl{\\{}A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)},\
A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\bigr{\\}}$
$\displaystyle=\bigl{\\{}A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)},\
A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}\bigr{\\}}.$

Thus, $A^{(1)}$ and $A^{(2)}$ must be linearly dependent. So there exists
$\alpha\in K$ such that $A^{(2)}=\alpha A^{(1)}$. It follows

$\displaystyle
A^{(1)}\otimes(B^{(1)}\otimes\varGamma^{(1)}+\alpha(B^{(2)}\otimes\varGamma^{(2)}))$
$\displaystyle=A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)}+A^{(4)}\otimes
B^{(4)}\otimes\varGamma^{(4)}.$

This can only be the case if $A^{(3)}$ and $A^{(4)}$ or
$B^{(3)}\otimes\varGamma^{(3)}$ and $B^{(4)}\otimes\varGamma^{(4)}$ are
linearly dependent. If $B^{(3)}\otimes\varGamma^{(3)}$ and
$B^{(4)}\otimes\varGamma^{(4)}$ are linearly dependent, then the right side of
(2) has rank one, so the left side also have rank $1$. This would imply that
either $\dim\langle B^{(1)},B^{(2)}\rangle=1$ or
$\dim\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=1$. Therefore $A^{(3)}$ and
$A^{(4)}$ are linearly dependent and so $\dim\langle
A^{(1)},A^{(2)},A^{(3)},A^{(4)}\rangle=1$.

Using that the $A^{(i)}$ are constant multiples of each other, and that
$(\lambda A)\otimes B\otimes\varGamma=A\otimes(\lambda B)\otimes\varGamma$ for
all $\lambda\in K$, we may as well assume $A^{(1)}=A^{(2)}=A^{(3)}=A^{(4)}$.
The equality (2) then reduces to

$B^{(1)}\otimes\varGamma^{(1)}+B^{(2)}\otimes\varGamma^{(2)}=B^{(3)}\otimes\varGamma^{(3)}+B^{(4)}\otimes\varGamma^{(4)}.$

The remaining claims follow directly from Lemma 6. ∎

Informally, Thm. 7 says that if we want to replace two rank-one tensors
nontrivially by two others, then they must agree in one of the factors and
this factor cannot change. Additionally, the vector spaces generated by the
other factors must stay the same.

We now introduce the main concept of this paper.

######  Definition 8.

Let $n,m,p\in\mathbb{N}$ and let $V$ be the set of all orbits of
$(n,m,p)$-matrix multiplication schemes under the symmetry group and define

$\displaystyle E_{1}$ $\displaystyle=\\{(S,S^{\prime})\mid S^{\prime}\text{ is
a flip of }S\\}$ $\displaystyle E_{2}$ $\displaystyle=\\{(S,S^{\prime})\mid
S^{\prime}\text{ is a reduction of }S\\}.$

  1. (1)

The graph $G=(V,E_{1}\cup E_{2})$ is called the $(n,m,p)$-_flip graph_. The
edges in $E_{1}$ are called _flips_ and the edges in $E_{2}$ are called
_reductions._

  2. (2)

For a given $r\in\mathbb{N}$, the subgraph of $G$ consisting of all vertices
of rank at most $r$ is called the $(m,n,p)$-_flip graph_ of rank at most $r$.

  3. (3)

For a given $r\in\mathbb{N}$, the set $\\{S\in V:\operatorname{rank}(S)=r\\}$
is called the $r$th _level_ of $G$.

Note that flips always connect vertices belonging to the same level, whereas a
reduction always leads to a vertex belonging to a lower level. Also keep in
mind that if there is a flip from $S$ to $S^{\prime}$, then there is one from
$S^{\prime}$ to $S$. The flip graph may have loops, these correspond to flips
that accidentally turn a certain scheme into an equivalent one.

Since we are interested in schemes of low rank, we are interested in paths
containing reductions, because these lead us into lower levels. We have not
introduced any edges leading to higher levels, although that would be an easy
thing to do. For example, given a scheme $S$ containing a rank-one tensor
$A\otimes B\otimes\varGamma$, we can replace this tensor by the two tensors
$A\otimes B\otimes(\varGamma-\varGamma^{\prime})$ and $A\otimes
B\otimes\varGamma^{\prime}$, for arbitrary $\varGamma^{\prime}\in K^{p\times
n}$. The result is a scheme that admits a reduction to $S$. We could call this
step a split of $\varGamma$. A split produces a correct matrix multiplication
scheme as long as the original scheme does not already contain any of the
newly added elements. With this observation, we can show that the flip graph
is connected.

######  Theorem 9.

For every $n,m,p\in\mathbb{N}$, the $(n,m,p)$-flip graph is weakly connected,
i.e., the undirected graph obtained from it by replacing every reduction by a
bidirectional edge, is connected.

###### Proof.

For any given scheme $S_{0}$, we construct a path to the standard algorithm in
the underlying undirected graph. The first part of the path consists of
reductions to an irreducible scheme $S_{1}$. Then any two elements $A\otimes
B\otimes\varGamma,A^{\prime}\otimes B^{\prime}\otimes\varGamma^{\prime}\in
S_{1}$ have the property that $A\otimes B$ and $A^{\prime}\otimes B^{\prime}$
are linearly independent. This ensures that splits of $\varGamma$ lead to
pairwise distinct rank-one tensors. Next we repeatedly split $\varGamma$ for
every element to construct a scheme $S_{2}$ such that every element of $S_{2}$
can be written as $A\otimes B\otimes c_{i,j}$ for some $i,j\in\mathbb{N}$.

For any two elements $A\otimes B\otimes\varGamma,A^{\prime}\otimes
B^{\prime}\otimes\varGamma^{\prime}\in S_{2}$ where $A$ and $A^{\prime}$ are
linearly dependent and $\varGamma$ and $\varGamma^{\prime}$ are linearly
dependent there is a reduction that combines these two elements. We follow
such reductions until we get a scheme $S_{3}$ where any two elements $A\otimes
B\otimes\varGamma,A^{\prime}\otimes B^{\prime}\otimes\varGamma^{\prime}\in
S_{3}$ have the property that $A\otimes\varGamma$ and
$A^{\prime}\otimes\varGamma^{\prime}$ are linearly independent. Then we can
repeatedly split $B$ for every element to construct a scheme $S_{4}$ where
every element has the form $A\otimes b_{i,j}\otimes c_{k,l}$. We then use
reductions to combine all elements of $S_{4}$ with matching $b_{i,j}$ and
$c_{k,l}$. This way we get matrix multiplication scheme $S_{5}$ which for all
$i,j,k,l\in\mathbb{N}$ contains at most one element of the form $A\otimes
b_{i,j}\otimes c_{k,l}$. Therefore, $S_{5}$ must be the standard algorithm. ∎

We are interested in paths in the flip graph that lead to schemes of low rank.
Such paths are more likely to exist if there are many flips. Therefore, we
select a ground field $K$ for which we can expect the number of flips to be
large. As specified in Def. 4 and justified in Thm. 7, a flip is possible
whenever a scheme contains two rank-one tensors sharing a common factor. The
chances for a common factor are higher if the field $K$ is small, because the
smaller the field, the smaller the number of possible factors. For this
reason, we consider the ground field $K=\mathbb{Z}_{2}$ in the following
experiments. For this ground field Thm. 7 implies that the only way to replace
two rank-one tensors in a scheme is a flip.

######  Corollary 10.

Let $r\in\mathbb{N}$ and let $S$ and $S^{\prime}$ be two irreducible matrix
multiplication schemes of rank $r$ over $\mathbb{Z}_{2}$ that differ in
exactly two elements. Then $S^{\prime}$ is a flip of $S$.

###### Proof.

Let $A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)},A^{(2)}\otimes
B^{(2)}\otimes\varGamma^{(2)}\in S$ and $A^{(3)}\otimes
B^{(3)}\otimes\varGamma^{(3)},A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}\in
S^{\prime}$ be those elements. Then we have

$\displaystyle A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)}+A^{(2)}\otimes
B^{(2)}\otimes\varGamma^{(2)}$ $\displaystyle=A^{(3)}\otimes
B^{(3)}\otimes\varGamma^{(3)}+A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}$

and

$\displaystyle\bigl{\\{}A^{(1)}\otimes B^{(1)}\otimes\varGamma^{(1)},\
A^{(2)}\otimes B^{(2)}\otimes\varGamma^{(2)}\bigr{\\}}$
$\displaystyle\neq\bigl{\\{}A^{(3)}\otimes B^{(3)}\otimes\varGamma^{(3)},\
A^{(4)}\otimes B^{(4)}\otimes\varGamma^{(4)}\bigr{\\}}.$

Since $S$ is not reducible at least two of $\langle
A^{(1)},A^{(2)}\rangle$,$\langle B^{(1)},B^{(2)}\rangle$ and
$\langle\varGamma^{(1)},\varGamma^{(2)}\rangle$ have dimension two, say

$\dim\langle
B^{(1)},B^{(2)}\rangle=\dim\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=2.$

Then from Theorem 7 follows that $\dim\langle
A^{(1)},A^{(2)},A^{(3)},A^{(4)}\rangle=1$ and therefore we also have
$A^{(1)}=A^{(2)}=A^{(3)}=A^{(4)}$. Moreover, $\langle
B^{(1)},B^{(2)}\rangle=\langle B^{(3)},B^{(4)}\rangle$ and
$\langle\varGamma^{(1)},\varGamma^{(2)}\rangle=\langle\varGamma^{(3)},\varGamma^{(4)}\rangle$.
Because of $K=\mathbb{Z}_{2}$, this can only be if $B^{(3)}=B^{(1)}+B^{(2)}$
or $\varGamma^{(3)}=\varGamma^{(1)}+\varGamma^{(2)}$ and likewise for
$B^{(4)}$ and $\varGamma^{(4)}$. Thus, $S^{\prime}$ is a flip of $S$. ∎

##  4\. $2\times 2$ matrices and $3\times 3$ matrices

Figure 1. In the $(2,2,2)$-flip graph of rank at most 8, this figure shows the
component containing the standard algorithm. Flips are depicted by undirected
edges and reductions by directed edges.

The $(2,2,2)$-flip graph of rank at most 8 for $K=\mathbb{Z}_{2}$ is not too
big. Fig. 1 shows the connected component to which the standard algorithm
belongs. It has 272 vertices, each representing the orbit of one
multiplication scheme, and 1183 edges, 7 of which are reductions (shown by
green arrows). The component also contains Strassen’s algorithm. The distance
between the standard algorithm and Strassen’s algorithm is 8, a path is
highlighted in the figure. Although the standard algorithm allows many flips,
it only has one neighbor, because any two schemes obtained by a flip from the
standard algorithm are equivalent. The diameter of the component is 12.

Using SAT solvers as in [10, 9], we have tried to find out whether there are
other matrix multiplication schemes of rank at most 8. For $2\times 2$
matrices, modern SAT solvers have no trouble generating many multiplication
schemes in a short time. Strangely enough, while we found many solutions
belonging to the connected component shown in Fig. 1, we only found exactly
one solution (up to symmetries) that does not belong to this component:

$\displaystyle\mathcal{M}_{2,2,2}$
$\displaystyle=(a_{1,1}+a_{2,2})\otimes(b_{1,1}+b_{2,2})\otimes(c_{2,1})$
$\displaystyle+(a_{2,2})\otimes(b_{1,1}+b_{2,1})\otimes(c_{1,2}+c_{2,1}+c_{2,2})$
$\displaystyle+(a_{2,1}+a_{2,2})\otimes(b_{1,1})\otimes(c_{1,2}+c_{2,2})$
$\displaystyle+(a_{1,1})\otimes(b_{1,2}+b_{2,2})\otimes(c_{1,1})$
$\displaystyle+(a_{1,2})\otimes(b_{1,1}+b_{1,2}+b_{2,1}+b_{2,2})\otimes(c_{1,1}+c_{2,1}+c_{2,2})$
$\displaystyle+(a_{1,2}+a_{2,1})\otimes(b_{1,1}+b_{1,2})\otimes(c_{2,2})$
$\displaystyle+(a_{1,2}+a_{2,2})\otimes(b_{2,1}+b_{2,2})\otimes(c_{2,1}+c_{2,2})$
$\displaystyle+(a_{1,1}+a_{1,2})\otimes(b_{1,1}+b_{1,2}+b_{2,2})\otimes(c_{1,1}+c_{2,1}).$

This scheme has no neighbors and thus forms a connected component of its own.
We do not know whether the $(2,2,2)$-flip graph of rank at most 8 has any
further components.

For $3\times 3$-matrices and $K=\mathbb{Z}_{2}$, the flip graph is so large
that it is no longer possible to determine the entire component of the
standard algorithm in the $(3,3,3)$-flip graph of rank at most 27. Again, and
for the same reason as before, the standard algorithm itself has only one
neighbor. At distance 2, we found 600 vertices, at distance 3 there are about
20000, and at distance 4 nearly 600000. None of them is reducible. Computing
the whole neighborhood of distance 5 is infeasible.

With long random walks however, it is quite likely to encounter reducible
vertices. We employ the following simple procedure to search for reductions.

######  Algorithm 1.

Input: A matrix multiplication scheme $S$ and a limit $\ell$ for the path
length.
Output: A matrix multiplication scheme with rank decreased by one or $\bot$.

1if $S$ has no neighbours, return $\bot$

2for $i=1,\dots,\ell$, do:

3if $S$ is reducible, then return a reduction of $S$.

4if one of the neighbours of $S$ is reducible, then return a reduction of it.

5Set $S$ to a randomly selected neighbour of $S$.

6return $\bot$

An implementation of this procedure in C can explore paths of lengths $10^{8}$
within minutes and needs almost no memory.

Starting from the standard algorithm we easily find schemes of rank 23,
matching the record set by Laderman in 1976 [14], but we found no scheme of
rank 22. Restricting the lengths of the random walks to $10^{7}$, more than
95% of the walks reach a scheme of rank 23, and almost all a scheme of rank
24. Recall that along a random walk, the rank can only decrease but not
increase. In Fig. 2, we show for 10000 random walks after how many steps they
reach a scheme of a specific rank.

Figure 2. Sparsity of reduction steps. If a point $(x,y)$ belongs to a region
labeled $r$, then for $x$ random paths starting from the standard algorithms,
the $y$th vertex has rank $r$.

If we now focus on the flip graph of rank at most 23, it is feasible to
determine for a given vertex the entire connected component to which it
belongs. The schemes we reached by random walks from the standard algorithm
turned out to belong to 584 different connected components with altogether
64061 vertices. The components are quite diverse with respect to size and
symmetry; Fig. 3 shows three examples. The component on the top has 681
vertices and has no automorphisms. Some connected components are isomorphic to
each other, typically such components enjoy nontrivial symmetries. For
example, the component shown at the bottom right of Fig. 3 has an automorphism
group of order 576 and appears 32 times.

The small component shown on the left appears 39 times and has an automorphism
group of order 8. The triangular structure in this component appears often in
the flip graph. It originates from the two possibilities to choose $T$ for a
flip. Two flips of a scheme that use the same rank-one tensors in the flip
always are adjacent. The square structure in the middle appears whenever there
is an element that shares a different factor with each of two other elements
of a scheme.

There are also components consisting of a single vertex. Laderman’s scheme is
such an example.

Figure 3. Three example components of the $(3,3,3)$-flip graph of rank at most
23.

It seems that not all schemes of rank 23 can be reached from the standard
algorithm, because the 64000 solutions we were able to obtain by random paths
starting from the standard algorithm do not include all the 17000 solutions
found in [9] using SAT solving. Of course, given the size of the graph and the
lengths of the paths, it is virtually impossible to check whether there really
is no path or we were just not lucky enough to find it.

##  5\. Other formats

For larger matrix formats, it becomes harder to find random paths starting
from the standard algorithm that go all the way down to a scheme of low rank.
An adjusted search strategy that simultaneously considers many partial random
paths was found to work more efficiently. In this variant, we maintain a pool
of schemes of a certain rank $r$ from which we randomly choose starting
points, then do random walks starting from there until either a length limit
or a scheme of rank $r-1$ is encountered. In the latter case, the new scheme
is saved. The procedure is repeated until a prescribed number of schemes of
rank $r-1$ is reached. Then these schemes form the new pool of starting points
and the method is repeated until the desired target rank is reached.

######  Algorithm 2.

Input: A set $P$ of schemes of a certain rank, a path length limit $\ell$, a
pool size limit $s$, and a target rank $r$
Output: A set $Q$ of $s$ schemes of rank $r$

1if $P$ consists of schemes of rank $r$, return $P$.

2$Q=\emptyset$

3while $|Q|<s$ do:

4apply Alg. 1 to a random element of $P$ and $\ell$.

5if Alg. 1 returns a scheme, add it to $Q$.

6call the algorithm recursively with $Q$ in place of $P$.

For our experiments, we used as $P$ the set containing only the standard
algorithm, $\ell=10^{6}$ and $s=20000$. With these settings, we were able to
find schemes matching the best known rank bounds for all $(n,m,p)$ with $2\leq
n,m,p\leq 5$, except for $(n,m,p)=(5,5,5)$. For the latter case, starting from
the standard algorithm we only get down to rank 97 while Fawzi et al. [8]
discovered a scheme of rank 96 (valid mod 2). However, taking their scheme as
starting point of a random walk, we discovered schemes of rank 95 within
seconds. One of these schemes we announced in [12]. For $(n,m,p)=(4,4,5)$,
they give a scheme of rank 63, improving the previous record by one, while we
were able to find a scheme of rank 60 starting from the standard algorithm.
Also this scheme is only valid mod 2.

One of the remarkable outcomes of the recent work of Fawzi et al. [8] is an
apparent discrepancy of the rank depending on the characteristic of the ground
field. Their scheme for $(n,m,p)=(4,4,4)$ of rank 47 as well as their scheme
for $(n,m,p)=(5,5,5)$ of rank 96 are only valid in characteristic two and can
be shown not to be the homomorphic image of a scheme for $K=\mathbb{Q}$. As
our search in the flip graph uses $K=\mathbb{Z}_{2}$, the question is whether
our schemes are also restricted to ground fields of characteristic two. To
answer this question, we have applied Hensel lifting [18] to the schemes we
discovered.

A set
$S=\\{((\alpha^{(\ell)}_{i,j}))\otimes((\beta^{(\ell)}_{j,k}))\otimes((\gamma^{(\ell)}_{k,i})):\ell=1,\dots,r\\}$
of rank-one tensors is a matrix multiplication scheme if and only if the cubic
equations

$\sum_{\ell=1}^{r}\alpha^{(\ell)}_{i_{1},i_{2}}\beta^{(\ell)}_{j_{1},j_{2}}\gamma^{(\ell)}_{k_{1},k_{2}}=\delta_{i_{2},j_{1}}\delta_{j_{2},k_{1}}\delta_{k_{2},i_{1}}$

are satisfies for all $i_{1},i_{2},j_{1},j_{2},k_{1},k_{2}$, where $\delta$ is
the Kronecker delta function. These equations are known as the Brent equations
[3], and finding a matrix multiplication scheme is equivalent to solving these
equations.

Knowing a solution valid mod $2^{s}$ for some $s\in\mathbb{N}$, we can view it
as an approximation to order $s$ of a solution valid in the $2$-adic integers,
make an ansatz with undetermined coefficients for a refinement of this
approximation to order $s+1$, plug this ansatz into the Brent equations,
reduce mod $2^{s+1}$ and divide by $2^{s}$. This leads to a linear system over
$\mathbb{Z}_{2}$ for the undetermined coefficients in the ansatz, which can be
solved with linear algebra. If it has no solution, this proves that the
approximation does not admit any refinement to order $s+1$. If it does have a
solution, we pick one and proceed to refine. Once a decent approximation order
is reached (we generously used $s=100$ although much less would have been
sufficient in most cases), we can apply rational reconstruction [18] to find a
candidate solution with coefficients in $\mathbb{Q}$ or even $\mathbb{Z}$.
Whether the reconstruction was successful, i.e., whether the candidate
solution over $\mathbb{Q}$ or $\mathbb{Z}$ is indeed a solution, can be
checked easily by plugging it into the Brent equations.

Proceeding as described above, we can confirm the mismatch for
$(n,m,p)=(4,4,4)$ and $(n,m,p)=(5,5,5)$ observed by Fawzi et al. [8]: none of
our more than 100000 schemes of rank 47 for $(n,m,p)=(4,4,4)$ and none of our
more than 30000 schemes of rank 95 for $(n,m,p)=(5,5,5)$ can be lifted from
$\mathbb{Z}_{2}$ to $\mathbb{Z}_{4}$. However, we were able to lift a scheme
of rank 97 for $(n,m,p)=(5,5,5)$ from $\mathbb{Z}_{2}$ to $\mathbb{Z}$,
thereby breaking the record set by Smirnov and Sedoglavic [15] for this size.
Moreover, while none of our schemes of rank 60 for $(n,m,p)=(4,4,5)$ could be
lifted, we were able to lift some of the schemes of rank 62, thereby breaking
the record set by Fawzi et al. [8] for this size. For all other formats, we
found no improvements but were able to match the best known bounds on the
rank. An overview over the current state of affairs is given in Table 1.

$(n,m,p)$ | $K$ | previously best | our rank
---|---|---|---
|  | known rank |
$(2,2,2)$ | any | 7 [17] | 7
$(2,2,3)$ | any | 11 [11] | 11
$(2,2,4)$ | any | 14 [11] | 14
$(2,3,3)$ | any | 15 [11] | 15
$(2,2,5)$ | any | 18 [11] | 18
$(2,3,4)$ | any | 20 [11] | 20
$(3,3,3)$ | any | 23 [14] | 23
$(2,3,5)$ | any | 25 [11] | 25
$(2,4,4)$ | any | 26 [11] | 26
$(3,3,4)$ | any | 29 [16] | 29
$(2,4,5)$ | any | 33 [11] | 33
$(3,3,5)$ | any | 36 [16] | 36
$(3,4,4)$ | any | 38 [16] | 38
$(2,5,5)$ | any | 40 [11] | 40
$(3,4,5)$ | any | 47 [8] | 47
$(4,4,4)$ | $\mathbb{Z}_{2}$ | 47 [8] | 47
$(4,4,4)$ | any | 49 [17] | 49
$(3,5,5)$ | any | 58 [15] | 58
$(4,4,5)$ | $\mathbb{Z}_{2}$ | 63 [8] | 60
$(4,4,5)$ | any | 63 [8] | 62
$(4,5,5)$ | any | 76 [8] | 76
$(5,5,5)$ | $\mathbb{Z}_{2}$ | 96 [8] | 95
$(5,5,5)$ | any | 98 [15] | 97
Table 1. Comparison between best known rank and the rank we found

One scheme for each format and the implementation of the search procedure are
available at

https://github.com/jakobmoosbauer/flips.git.

The other schemes are available upon request.

##  6\. Open questions

The flip graph offers a new explanation for the existence of Strassen’s
algorithm and has led us to improved matrix multiplication schemes for some
formats. We believe that the flip graph is interesting in its own right and
deserves to be better understood.

For example, is not clear how well-suited the standard algorithm is as
starting point for the search procedure. Thm. 9 states that if we allow to use
reductions backwards, then every algorithm is reachable from the standard
algorithm. However, we found a $(2,2,2)$-matrix multiplication scheme of rank
8 that is not connected to the standard algorithm by a path that uses only
vertices of rank 8.

######  Question 1.

For $n,m,p\in\mathbb{N}$, is there a rank $r$ such that all vertices in level
$r$ of the $(n,m,p)$-flip graph are reachable from the standard algorithm?

If there are schemes of low rank which can not be reached from the standard
algorithm, they might become reachable if we add additional edges to the
graph. In Corollary 10 we show that, at least over $\mathbb{Z}_{2}$, the only
way to replace exactly two rank-one tensors in one step is a flip.

######  Question 2.

Under which condition can we replace more than two rows of a matrix
multiplication scheme at the same time, such that the resulting scheme is not
necessarily reachable by a sequence of flips?

Another way to add edges to the graph would be to add for every reduction also
the reverse edge. However, this would create a lot of additional edges to
higher levels. It is not clear at which points in the search procedure one
should go to a higher level and which of these edges to use.

######  Question 3.

How can we utilize edges leading to a higher level in the search procedure?

The search procedure would also benefit if we could determine whether two
vertices belong to the same connected component in the current level. This
would allow us to restrict the pool of schemes in Algorithm 2 such that there
are not too many vertices in the same component and thus the search
potentially covers a larger part of the graph.

######  Question 4.

Given two matrix mulatiplication schemes of the same format and rank, is there
an efficient way to determine whether they are connected within one level of
the flip graph?

More generally, in order to search for matrix multiplication schemes of low
rank, there might be a better way than following random paths in the graph.

######  Question 5.

Given a matrix multiplication scheme $S$, is there a systematic way to find
reduction edges that can be reached from $S$?

Finally, we observed that many of the connected components in the
$(3,3,3)$-flip graph of rank at most 23 are highly symmetric. Understanding
these symmetries would help understanding the structure of the flip graph and
might be useful in the search procedure.

######  Question 6.

What is the significance of the high symmetry in some of the large components
in the $(3,3,3)$-flip graph of rank at most 23?

Acknowledgement. We thank Martina Seidl for offering some of her computing
power for conducting the experiments reported in this paper and her student
Max Heisinger for valuable technical support with their system.

## References

  * [1] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proc. SODA’21, pages 522–539, 2021.
  * [2] Markus Bläser.  On the complexity of the multiplication of matrices of small formats.  J. Complexity, 19(1):43–60, 2003.
  * [3] Richard P. Brent.  Algorithms for matrix multiplication.  Technical report, Department of Computer Science, Stanford, 1970.
  * [4] Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi.  Algebraic complexity theory, volume 315.  Springer Science & Business Media, 2013.
  * [5] Nicolas T. Courtois, Gregory V. Bard, and Daniel Hulme.  A new general-purpose method to multiply $3\times 3$ matrices using only 23 multiplications.  Technical Report 1108.2830, ArXiv, 2011.
  * [6] Hans F. de Groote.  On varieties of optimal algorithms for the computation of bilinear mappings ii. optimal algorithms for $2\times 2$-matrix multiplication.  Theoretical Computer Science, 7(2):127–148, 1978.
  * [7] Ran Duan, Hongxun Wu, and Renfei Zhou.  Faster matrix multiplication via asymmetric hashing.  Technical Report 2210.10173, arXiv, 2022.
  * [8] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis, and Pushmeet Kohli.  Discovering faster matrix multiplication algorithms with reinforcement learning.  Nature, 610(7930):47–53, 2022.
  * [9] Marijn J. H. Heule, Manuel Kauers, and Martina Seidl.  New ways to multiply $3\times 3$-matrices.  J. Symbolic Comput., 104:899–916, 2021.
  * [10] Marijn J.H. Heule, Manuel Kauers, and Martina Seidl.  Local search for fast matrix multiplication.  In Proc. SAT’19, pages 155–163, 2019.
  * [11] J. E. Hopcroft and L. R. Kerr.  On minimizing the number of multiplications necessary for matrix multiplication.  SIAM Journal on Applied Mathematics, 20(1):30–36, 1971.
  * [12] Manuel Kauers and Jakob Moosbauer.  The FBHHRBNRSSSHK-algorithm for multiplication in $\mathbb{Z}_{2}^{5\times 5}$ is still not the end of the story.  Technical Report 2210.04045, arXiv, 2022.
  * [13] Manuel Kauers and Jakob Moosbauer.  A normal form for matrix multiplication schemes.  In Dimitrios Poulakis and George Rahonis, editors, Proc. CAI’20, pages 149–160, 2022.
  * [14] Julian D. Laderman.  A noncommutative algorithm for multiplying $3\times 3$ matrices using 23 multiplications.  Bull. Amer. Math. Soc., 82(1):126–128, 1976.
  * [15] Alexandre Sedoglavic and Alexey V. Smirnov.  The tensor rank of $5\times 5$ matrices multiplication is bounded by 98 and its border rank by 89.  In Proc. ISSAC’21, pages 345–351, 2021.
  * [16] Alexey V. Smirnov.  The bilinear complexity and practical algorithms for matrix multiplication.  Zh. Vychisl. Mat. Mat. Fiz., 53(12):1970–1984, 2013.
  * [17] Volker Strassen.  Gaussian elimination is not optimal.  Numer. Math., 13:354–356, 1969.
  * [18] Joachim von Zur Gathen and Jürgen Gerhard.  Modern Computer Algebra.  Cambridge Univ. Press, 3 edition, 2013.
  * [19] Shmuel Winograd.  On multiplication of $2\times 2$ matrices.  Linear Algebra and its Applications, 4(4):381–388, 1971.