Strassen’s algorithm via orbit flip graphs

Christian Ikenmeyer, Jakob Moosbauer · 2025

Read Strassen’s algorithm via orbit flip graphs by Christian Ikenmeyer, Jakob Moosbauer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05467.txt.

Introduction

Christian Ikenmeyer and Jakob Moosbauer give a strikingly short proof of a famous counting result in matrix multiplication. Their 2025 paper revisits Strassen's theorem that multiplying two-by-two matrices needs a tensor rank of at most seven, the fact behind the first fast multiplication algorithm. Standard proofs involve clever but heavy verification, checking that a proposed scheme really computes every entry.

Their proof needs none of that. It rests on properties of one specific group action of order six, combined with recent flip graph techniques that search among equivalent schemes while respecting symmetry. The argument is calculation-free and pattern-free: the structure of the symmetry group does the work. The authors offer it as a model of proving rank bounds by reasoning about orbits, rather than by exhibiting and checking an explicit decomposition.

Catalog record

CREATORChristian Ikenmeyer, Jakob Moosbauer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE7 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05467

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strassen’s algorithm via orbit flip graphs
Christian Ikenmeyer, Jakob Moosbauer

Abstract
We give a short proof for Strassen’s result that the rank of the 2 by 2 matrix multiplication tensor is at most 7. The proof requires no calculations and also no pattern matching or other type of nontrivial verification, and is based solely on properties of a specific order 6 group action. Our proof is based on the recent combination of flip graph algorithms and symmetries.



Let
\mathbb{F}
be any field, and let
\mathbb{F}^{2\times 2}
have the standard basis
\{e_{0,0},e_{0,1},e_{1,0},e_{1,1}\}
.
The
2\times 2
matrix multiplication tensor is defined as

M_{2}=\sum_{i,j,k=0}^{1}e_{i,j}\otimes e_{j,k}\otimes e_{k,i}\in{\textstyle\bigotimes}^{3}(\mathbb{F}^{2\times 2})
, see
[
BCS97
, (14.20)]
.
The
rank

R(t)

for
t\in{\textstyle\bigotimes}^{3}(\mathbb{F}^{2\times 2})

is defined as the smallest number
r\in\mathbb{N}
such that there exist
u_{i},v_{i},w_{i}\in\mathbb{F}^{2\times 2},i=1,\ldots,r
, with

t=\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes w_{i}
.
Strassen
[
Str69
]
proved that
R(M_{2})\leq 7
, and we reprove this result.

The cyclic group
C_{3}=\langle\pi\mid\pi^{3}=1\rangle
acts linearly on
{\textstyle\bigotimes}^{3}(\mathbb{F}^{2\times 2})
via
\pi(u\otimes v\otimes w)=w\otimes u\otimes v

and
\mathbb{F}
-linear extension.
For
i\in\{0,1\}
, let

i^{\prime}:=1-i
.
The cyclic group
C_{2}=\langle\tau\mid\tau^{2}=1\rangle
acts linearly on
{\textstyle\bigotimes}^{3}(\mathbb{F}^{2\times 2})
via

\tau(e_{i_{1},i_{2}}\otimes e_{j_{1},j_{2}}\otimes e_{k_{1},k_{2}})=e_{i^{\prime}_{1},i^{\prime}_{2}}\otimes e_{j^{\prime}_{1},j^{\prime}_{2}}\otimes e_{k^{\prime}_{1},k^{\prime}_{2}}

and
\mathbb{F}
-linear extension.
Both actions commute, so that we have an action of
G:=C_{3}\times C_{2}
.
We write
G\cdot t:=\sum_{g\in G}g(t)
, which is a notation introduced in
[
BILR19
]
.
For a standard basis vector
t
it is easy to visualize

G\cdot t=G\cdot\tau(t)
and
G\cdot t=G\cdot\pi(t)
: For
\tau
we
connect pairs of inverted indices
i
and
i^{\prime}
with red lines, and for
\pi
we
illustrate the cyclic position rotation with blue lines:

\displaystyle G\cdot e_{0,1}\otimes e_{1,1}\otimes e_{0,0}

\displaystyle=G\cdot e_{1,0}\otimes e_{0,0}\otimes e_{1,1}

and

\displaystyle G\cdot e_{0,1}\otimes e_{1,1}\otimes e_{0,0}

\displaystyle=G\cdot e_{0,0}\otimes e_{0,1}\otimes e_{1,1}

The proof of
R(M_{2})\leq 7
now goes as follows.
There are two different kinds of summands in the 8 summands of
M_{2}
: 6 of them form
G\cdot e_{1,0}\otimes e_{0,1}\otimes e_{1,1}
. For the remaining 2 summands, we can get their sum from a rank 1 tensor with 8 terms and subtracting the 6 superfluous terms as follows:

e_{0,0}\otimes e_{0,0}\otimes e_{0,0}+e_{1,1}\otimes e_{1,1}\otimes e_{1,1}\ =\ (e_{0,0}+e_{1,1})\otimes(e_{0,0}+e_{1,1})\otimes(e_{0,0}+e_{1,1})-G\cdot e_{0,0}\otimes e_{0,0}\otimes e_{1,1}.

So far, by naively looking at the summand structure, we have obtained a rank
1+6+6=13
decomposition for
M_{2}
.
We now observe:

M_{2}\,-\,(e_{0,0}+e_{1,1})\otimes(e_{0,0}+e_{1,1})\otimes(e_{0,0}+e_{1,1})

\displaystyle=G\cdot e_{1,0}\otimes e_{0,1}\otimes e_{1,1}

\displaystyle-G\cdot e_{0,0}\otimes e_{0,0}\otimes e_{1,1}

\displaystyle=G\cdot e_{1,0}\otimes e_{0,1}\otimes e_{1,1}

\displaystyle{}+\big(

\displaystyle-G\cdot e_{0,1}\otimes e_{1,1}\otimes e_{0,0}

\displaystyle+\hskip 4.5ptG\cdot e_{0,1}\otimes e_{1,1}\otimes e_{0,0}\big)

\displaystyle-G\cdot e_{0,0}\otimes e_{0,0}\otimes e_{1,1}

\displaystyle=\mathrlap{\big(G\cdot e_{1,0}\otimes e_{0,1}\otimes e_{1,1}}

\displaystyle-G\cdot e_{1,0}\otimes e_{0,0}\otimes e_{1,1}\big)

\displaystyle+\big(G\cdot e_{0,0}\otimes e_{0,1}\otimes e_{1,1}

\displaystyle-G\cdot e_{0,0}\otimes e_{0,0}\otimes e_{1,1}\big)

\displaystyle=\mathrlap{\hskip 42.67912ptG\cdot e_{1,0}\otimes(e_{0,1}-e_{0,0})\otimes e_{1,1}}

\displaystyle+\mathrlap{\hskip 42.67912ptG\cdot e_{0,0}\otimes(e_{0,1}-e_{0,0})\otimes e_{1,1}}

\displaystyle=\mathrlap{\hskip 128.0374ptG\cdot(e_{1,0}+e_{0,0})\otimes(e_{0,1}-e_{0,0})\otimes e_{1,1},}

which is of rank at most 6.
Hence,
M_{2}
has rank at most 7.

Context and related work

For
n\in\mathbb{N}
, let
M_{n}:=\sum_{i,j,k=0}^{n-1}e_{i,j}\otimes e_{j,k}\otimes e_{k,i}
.
The matrix multiplication exponent
\omega=\inf\{\log_{n}(R(M_{n}))\}
governs the running time of the algorithmic task of multiplying two matrices and of other tasks in linear algebra, for example solving systems of linear equations, see
[
BCS97
, §15.1, §16]
.
In order to understand
R(M_{n})
for large
n
, significant research effort has focused on understanding
R(M_{n})
for small values of
n
, with several papers focusing on
n=2

[
Bre70
,
Gas71
,
Fid72
,
BD73
,
Pat74
,
Laf75
,
Mak75
,
Yuv78
,
BC85
,
Cla88
,
Cha86
,
Ale97
,
GK00
,
Pat09
,
GM17
,
IL19
,
CILO19
]
, since no satisfying short proof of
R(M_{2})\leq 7
has been found.
The verification of these proofs usually requires simple but somewhat lengthy calculations, and careful attention to the details has to be paid.
The weaker analogous result for the tensor border rank
also gives
\omega\leq\log_{2}(7)
and
can be obtained from Lickteig’s analysis of defective secant varieties, see
[
Lic85
]
,
[
Lan08
, §3.8, §9]
, which is significantly more involved than our proof.

Our new proof of
R(M_{2})\leq 7
is so short that it can hopefully be used
successfully as a blueprint for proofs for other small
n
. In fact, it does
arise from a machinery for proofs for small
n
, the flip graph algorithm

[
KM23
]
.
R(M_{n})
for small values of
n
has been studied for a long time

[
HK71
,
Lad76
,
JM86
,
Mak87
,
DIS11
,
Smi13
,
Sed17
,
HKS19
,
HKS21
,
SS21
,
Smi21
,
FBH+22
,
Smi23
,
AIH24
,
KM25
,
Sed25
]
.
The recent flip graph algorithm works as follows: one starts with a simple but
expensive decomposition of
M_{n}
and reduces its rank via a series of
simplifications. Adding ideas from
[
BILR19
]
(tensor rank decompositions of

M_{3}
), this technique has recently been improved by considering the symmetry
groups
C_{3}
and
C_{3}\times C_{2}
to get new upper bounds on
R(M_{5})
and

R(M_{6})
, see
[
MP25
]
. Our proof can be interpreted as a refined version of
the output of this newest flip graph algorithm. Note that
[
BILR19
]
also
consider a group of order 6, but the group there is
C_{3}\rtimes C_{2}\simeq S_{3}
. The flip graph proof technique requires to specify a trivial but expensive solution,
a group (usually a subgroup of the symmetry group of
M_{n}
), and a sequence of
trivial simplifications. As a consequence, our proof generates 7
summands instead of starting with them and verifying their correctness.

[
dG78
]
showed that any rank 7 decomposition is equivalent to Strassen’s original decomposition.
It is
an open question which starting solutions and which groups can be used to get
satisfying short proofs for
M_{n}
,
n\geq 3

Read the complete text