Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Flip Graphs with Symmetry and New Matrix Multiplication Schemes

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Pith's one-line read This paper introduces a symmetry-constrained flip graph search and reports new matrix multiplication schemes with 93 multiplications for 5×5 matrices and 153 for 6×6 matrices over arbitrary fields.

desk verdict New matrix multiplication bounds from a symmetry-restricted flip graph; the theory is clean, but the schemes are not in the paper and the lifting evidence is empirical, so verification is needed. read the letter →

arxiv 2502.04514 v1 pith:ZPXZ3KIF submitted 2025-02-06 cs.SC

classification cs.SC MSC 15A6968Q2568W30
keywords matrixmultiplicationflipgraphalgorithmtensorranksymmetryconstraintsC3invarianceHenselliftingbilinearcomplexitybounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that forcing matrix-multiplication schemes to be invariant under a small symmetry group makes the flip-graph search much smaller while also making the final schemes easier to lift from arithmetic over $\mathbb{F}_2$ to true integer coefficients. On that basis it reports two new records: $5\times5$ matrices can be multiplied with 93 scalar multiplications and $6\times6$ matrices with 153, improving the previous bounds of 97 (or 94 over $\mathbb{F}_2$) and 160. This matters because these are concrete upper bounds on the rank of the matrix multiplication tensor, and the $6\times6$ scheme is atomic rather than a composition of smaller algorithms. A further improvement of two multiplications in the $5\times5$ case or one in the $6\times6$ case would beat the asymptotic exponent of the classical seven-multiplication 2×2 algorithm.

What carries the argument

The load-bearing object is the orbit flip: a flip applied to two full orbits of rank-one tensors inside a $G$-invariant scheme, with integer multipliers $\lambda,\lambda'$ inserted so that the two replacement terms again form full orbits. Theorem 4 shows this preserves $G$-invariance, so a random walk on the symmetric flip graph can move whole orbits in one step. Around this sit two supporting constructions: starting points built from diagonal partitions (which supply the $C_3$-invariant rank-one tensors that fix the missing diagonal entries), and a symmetry-preserving Hensel lifting that solves cyclic versions of the Brent equations modulo increasing powers of 2.

What would settle it

Substitute the lifted integer coefficients of the reported 93- and 153-multiplication schemes into the defining bilinear equations for 5×5 and 6×6 matrix multiplication and check that the difference tensor is exactly zero over the integers; if any entry is nonzero, or if the mod-$2^k$ lifting system has no solution for any reported scheme, then the arbitrary-ground-field claim is false.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central discovery is that the flip graph algorithm remains effective when the search is restricted to $G$-invariant schemes for $G=C_3$ or $G=C_3\times Z_2$: every flip, reduction, or plus-transition can be applied to whole orbits of rank-one tensors, so three (or six) rank-one tensors are moved at the cost of one. The authors prove that an orbit flip of a $G$-invariant scheme is again a $G$-invariant scheme (Theorem 4), and they exploit the preserved cyclic symmetry in the lifting step by solving a symmetrized version of the standard bilinear equations. Running this search over $\mathbb{F}_2$ with carefully chosen diagonal-partition starting points produces symmetric schemes of rank 93 for $n=5$ and 153 for $n=6$, and all such schemes found in the experiments lifted to integer coefficients, giving schemes valid over arbitrary ground fields.

Load-bearing premise

The reported schemes exist only as computer output in auxiliary files and are assumed to lift from $\mathbb{F}_2$ to integer coefficients; the paper states that the Hensel-lifting step is not guaranteed to converge, and the claim that the schemes work over arbitrary fields depends on that empirical convergence holding for every reported scheme.

Editorial extensions

If this is right

  • The rank bounds become $\operatorname{rank}(M_5)\le 93$ and $\operatorname{rank}(M_6)\le 153$ over arbitrary fields, improving the previous best bounds of 97 (or 94 over $\mathbb{F}_2$) and 160.
  • The 6×6 scheme is atomic, so it offers a new way to build larger schemes without composing smaller ones, as prior 6×6 bounds did.
  • A further drop to 91 multiplications for 5×5 or 152 for 6×6 would produce an algorithm asymptotically faster than the classical 2×2 algorithm, since $\log_5 91\approx 2.803$ and $\log_6 152\approx 2.804$.
  • Symmetry seems to correlate with liftability: all symmetric schemes found here lifted to $\mathbb{Z}$, whereas several previously discovered $\mathbb{F}_2$ schemes are provably non-liftable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not test larger symmetry groups; a natural extension is that larger finite subgroups of the symmetry group would shrink the search further and could make $n\ge7$ searches feasible.
  • The authors do not explore composing their atomic 6×6 scheme with small rectangular schemes; such compositions might improve bounds for larger sizes beyond the two record values.
  • The diagonal-partition starting points look like a transferable recipe: choose block-diagonal tensors that match the symmetry, let flips fill the rest; this recipe could be tried on rectangular formats or on other small groups.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This paper introduces a symmetry-restricted version of the flip graph algorithm for matrix multiplication schemes, working with G-invariant schemes for G = C3 or G = C3 × Z2. It defines orbit-level flips, reductions, and plus-transitions, proves in Theorem 4 that these operations preserve G-invariance when applied to full orbits, and describes a random-walk search. The authors report new upper bounds: rank ≤ 93 for 5×5 and rank ≤ 153 for 6×6 matrix multiplication, improving on 97 and 160 respectively, and state that the F2-found schemes lift to integer coefficients, hence hold over arbitrary ground fields. The search code and concrete schemes are available at a GitHub repository rather than in the paper.

Significance. If the reported schemes are correct, the paper provides a meaningful advance in explicit upper bounds for small matrix multiplication and a novel algorithmic idea: restricting the flip graph to symmetric schemes both reduces the search space and appears to make lifting from F2 easier. The proof of Theorem 4 is clean, and the search procedure is described in enough detail to be reimplemented. However, the central existence claims are not yet independently checkable from the manuscript because the schemes are not displayed and the integer lifting is supported only by an empirical statement in Section 6. These issues are fixable with exact certificates, so the significance is real but conditional.

major comments (3)
  1. [§6 (Lifting)] The sentence "There is no guarantee for the approximation to converge to a solution, but in our experiments all candidates converged to an integer solution within a few steps" is the only evidence for the lifting of the 93- and 153-multiplication schemes to Z. This is load-bearing for the abstract's claim that the schemes work over arbitrary ground fields. Please either prove convergence for the specific systems and then prove that the resulting coefficients are integers, or provide an exact integer certificate for each claimed scheme and state explicitly how equality over Z was verified.
  2. [§5 (Results) and §8 (Implementation)] The concrete schemes of ranks 93 and 153 are not included in the paper; the reader is referred to an unversioned GitHub repository. Because these schemes are the central object of the paper, a mismatch between the repository content and the reported numbers, or a bug in the solver, would invalidate both new bounds. Please include the schemes as supplementary material or as a machine-checkable certificate, and pin the exact version of the repository used for the reported results.
  3. [§6 (Lifting) and §9 (Conclusion)] The phrase "integer solution" after 2-adic lifting is ambiguous: an element of Z_2 is not an integer, and a solution with coefficients in Z_2 cannot be reduced modulo primes p ≠ 2 to give a scheme over arbitrary fields. The paper should explicitly verify that the lifted coefficients are in Z and that the defining identity M_n = sum of rank-one tensors holds over Z, not merely modulo 2^m. After such a verification, reduction modulo arbitrary primes is immediate, but this verification is currently absent.
minor comments (4)
  1. [Theorem 4 and Definition 5] The notation "G · A⊗B⊗C" is used both for the orbit as a set and for the formal sum of orbit elements, which makes the proof of Theorem 4 harder to follow; a separate notation for the formal orbit sum would improve clarity.
  2. [Algorithm 1] In Algorithm 1, line 13 sets m = ℓ + M immediately after resetting ℓ = 0; the intent is clear but the line is redundant, and the reset block could be rewritten for readability.
  3. [§5 (Results)] The comparison for n = 4 between the symmetric rank 49 and the non-symmetric rank 47 from [11] should state the ground field for both bounds, since ranks can differ between F2 and larger fields.
  4. [§2 (Matrix Multiplication and its Symmetry Group)] The display "GL ×3 n" is typeset in a confusing way; it should be written as GL(n)^{×3} or similar.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new 5x5 and 6x6 schemes are obtained by randomized search and then lifted, with the improvements benchmarked against independent previous bounds.

full rationale

The paper's derivation chain is self-contained with respect to its central claims. The new rank bounds are not obtained by fitting a parameter to the target answer or by defining a quantity in terms of the result. Section 5 describes concrete search runs: for n=5, starting from a diagonal partition and using the C3 symmetry, the search finds a rank-93 scheme; for n=6, using C3 x Z2 symmetry and the specified partition, it finds a rank-153 scheme. These schemes are then independently validated by a Hensel-lifting procedure in Section 6: the paper explicitly states that the convergence of the lifting is not guaranteed but that all candidates in the experiments converged to integer solutions. The previous bounds (97 for 5x5 from [16] and 160 for 6x6 from [21]) are external benchmarks, not inputs to the search. The self-citation to [16] is for the original flip-graph framework and the general Hensel-lifting idea, but it does not carry the load of the specific new schemes; the new results depend on the search and lifting runs described in the present paper. The only caveat is that the actual schemes are in a GitHub repository rather than displayed in the paper, but this is a reproducibility or verification concern, not a circularity concern. No step in the paper reduces by construction to its own input, and no load-bearing claim is justified solely by a self-citation.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim depends on the correctness of the reported computational artifacts (search code and lifted schemes) and on the empirical convergence of Hensel lifting. The search hyperparameters and starting point choices are hand-picked heuristics; they do not affect the validity of the final schemes, only the ability to find them.

free parameters (5)
  • Diagonal partition P for n=5 = {{1,5},{2,4},{3}}
    Chosen by trial and error to enable finding a rank-93 scheme; appears in Section 5.
  • Diagonal partition P for n=6 = {{1,2},{3,4},{5,6}}
    Chosen after analyzing a rank-157 scheme; see Section 7.
  • Flip limit L = 10**8 (n=5), 10**9 (n=6)
    Search hyperparameter; limits path length before termination (Algorithm 1).
  • Plus-transition parameter M = 5*10**4 (n=5), 5*10**5 (n=6)
    Search hyperparameter controlling how often plus-transitions are used (Algorithm 1).
  • Symmetry group G = C3 for n=5; C3 x Z2 for n=6
    Chosen based on symmetries observed in known schemes; see Sections 4 and 5.
assumptions (4)
  • domain assumption The flip graph algorithm and its transitions (flip, reduction, plus-transition) preserve the property of being a matrix multiplication scheme.
    Taken from Kauers and Moosbauer [16]; used throughout Section 3. The paper proves the symmetric analogue in Theorem 4.
  • ad hoc to paper Oracle for random flips: the random walk on the symmetric flip graph eventually reaches a scheme of the target rank with the given hyperparameters.
    The success of the search is empirical; no proof of connectivity or mixing is given. Stated in Sections 4 and 5 as experimental outcomes.
  • ad hoc to paper Hensel lifting converges to an integer solution for the reported schemes.
    Section 6 states 'There is no guarantee for the approximation to converge to a solution, but in our experiments all candidates converged to an integer solution within a few steps.' This is an empirical claim, not a theorem.
  • standard math The symmetry group actions S3 and GL(n)^3 and their semidirect product are the correct equivalence notion for matrix multiplication schemes.
    Established in de Groote [8,9] and used in Section 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Flip Graphs with Symmetry and New Matrix Multiplication Schemes." pith.science (2026). https://pith.science/paper/ZPXZ3KIF

@misc{pith2026250204514,
  author       = {Pith},
  title        = {Pith review of: Flip Graphs with Symmetry and New Matrix Multiplication Schemes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZPXZ3KIF}},
  note         = {Machine review of arXiv:2502.04514}
}
abstract

The flip graph algorithm is a method for discovering new matrix multiplication schemes by following random walks on a graph. We introduce a version of the flip graph algorithm for matrix multiplication schemes that admit certain symmetries. This significantly reduces the size of the search space, allowing for more efficient exploration of the flip graph. The symmetry in the resulting schemes also facilitates the process of lifting solutions from $F_2$ to $\mathbb{Z}$. Our results are new schemes for multiplying $5\times 5$ matrices using $93$ multiplications and $6\times 6$ matrices using $153$ multiplications over arbitrary ground fields.

Figures

Figures reproduced from arXiv: 2502.04514 by the authors.

Figure 1
Figure 1. The component of the C3 × Z2-symmetric (2, 2, 2) flip graph that contains the starting point with diagonal partition {{1, 2}}, marked in green. Vertices that can be reduced to Strassen’s algorithm are marked in red. Lemma 7. Let G = C3 or G = C3 ×Z2. Let S ∪T be the starting point for a diagonal partition P. Then S ∪ T is a G-invariant matrix multiplication scheme and the orbit of every element in S has size |G|. Pr… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation

    cs.DS 2025-08 reject novelty 6.0 of 10

    The paper claims a 44x44 base-case matrix multiplication algorithm with exponent 2.773203, beating Pan's 2.773372, but the proof of the key lemma is flawed.

  2. Exploring Commutative Matrix Multiplication Schemes via Flip Graphs

    cs.SC 2025-06 conditional novelty 6.0 of 10

    A commutative flip graph defined on a quotient tensor space recovers known commutative matrix multiplication bounds up to 5x5 without improving any of them.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · cited by 2 Pith papers

  1. [1]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2039. Society for Industrial and Applied Mathematics, 2025

  2. [2]

    Adaptive flip graph algorithm for matrix multiplication

    Yamato Arai, Yuma Ichikawa, and Koji Hukushima. Adaptive flip graph algorithm for matrix multiplication. In Pro- ceedings of the 2024 International Symposium on Symbolic and Algebraic Computation , ISSAC ’24, page 292–298, New York, NY, USA, 2024. Association for Computing Machinery

  3. [3]

    Landsberg, and Nick Ryder

    Grey Ballard, Christian Ikenmeyer, J.M. Landsberg, and Nick Ryder. The geometry of rank decompositions of matrix multiplication ii: 3 × 3 matrices. Journal of Pure and Applied Algebra , 223(8):3205–3224, 2019. 10 J. MOOSBAUER AND M. J. POOLE

  4. [4]

    Richard P. Brent. Algorithms for matrix multiplication. Technical report, Department of Computer Science, Stanford, 1970

  5. [5]

    V. P. Burichenko. Symmetries of matrix multiplication algorithms. i, 2015

  6. [6]

    On automorphism group of a possible short algorithm for multiplication of 3 × 3 matrices, 2022

    Vladimir Burichenko. On automorphism group of a possible short algorithm for multiplication of 3 × 3 matrices, 2022

  7. [7]

    Matrix multiplication via arithmetic progressions

    Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Com- putation, 9(3):251–280, 1990. Computational algebraic complexity editorial

  8. [8]

    de Groote

    Hans F. de Groote. On varieties of optimal algorithms for the computation of bilinear mappings i. the isotropy group of a bilinear mapping. Theoretical Computer Science, 7(1):1–24, 1978

Show all 24 references
  1. [9]

    de Groote

    Hans F. de Groote. On varieties of optimal algorithms for the computation of bilinear mappings ii. optimal algorithms for 2 × 2-matrix multiplication. Theoretical Computer Science, 7(2):127–148, 1978

  2. [10]

    Nazrul Islam, and ´Eric Schost

    Charles- ´Eric Drevet, Md. Nazrul Islam, and ´Eric Schost. Optimization techniques for small matrix multiplication. Theoretical Computer Science, 412(22):2219–2236, 2011

  3. [11]

    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 multiplicat...

  4. [12]

    Grochow and Cristopher Moore

    Joshua A. Grochow and Cristopher Moore. Matrix multiplication algorithms from group orbits, 2016

  5. [13]

    Marijn J. H. Heule, Manuel Kauers, and Martina Seidl. Local search for fast matrix multiplication. In Mikol´ aˇ s Janota and Inˆ es Lynce, editors,Theory and Applications of Satisfiability Testing – SAT 2019 , pages 155–163, Cham, 2019. Springer International Publishing

  6. [14]

    Heule, Manuel Kauers, and Martina Seidl

    Marijn J.H. Heule, Manuel Kauers, and Martina Seidl. New ways to multiply 3 × 3-matrices. J. Symbolic Comput. , 104:899–916, 2021

  7. [15]

    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

  8. [16]

    Flip graphs for matrix multiplication

    Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, ISSAC ’23, page 381–388, New York, NY, USA, 2023. Association for Computing Machinery

  9. [17]

    Some new non-commutative matrix multiplication algorithms of size (n, m, 6)

    Manuel Kauers and Jakob Moosbauer. Some new non-commutative matrix multiplication algorithms of size (n, m, 6). ACM Commun. Comput. Algebra , 58(1):1–11, January 2025

  10. [18]

    Laderman

    Julian D. Laderman. A noncommutative algorithm for multiplying 3 × 3 matrices using 23 multiplications. Bull. Amer. Math. Soc., 82(1):126–128, 1976

  11. [19]

    A non-commutative algorithm for multiplying (7 x 7) matrices using 250 multiplications

    Alexandre Sedoglavic. A non-commutative algorithm for multiplying (7 x 7) matrices using 250 multiplications. working paper or preprint, August 2017

  12. [20]

    Yet another catalogue of fast matrix multiplication algorithms

    Alexandre Sedoglavic. Yet another catalogue of fast matrix multiplication algorithms. https://fmm.univ-lille.fr/,

  13. [21]

    Alexey V. Smirnov. The bilinear complexity and practical algorithms for matrix multiplication. Zh. Vychisl. Mat. Mat. Fiz., 53(12):1970–1984, 2013

  14. [22]

    Gaussian elimination is not optimal

    Volker Strassen. Gaussian elimination is not optimal. Numer. Math. , 13:354–356, 1969

  15. [23]

    Cambridge Univ

    Joachim von Zur Gathen and J¨ urgen Gerhard.Modern Computer Algebra. Cambridge Univ. Press, 3 edition, 2013. Jakob Moosbauer, Department of Computer Science, University of W arwick, Coventry, United Kingdom Email address : jakob.moosbauer@warwick.ac.uk Michael J. Poole, Indepe...

  16. [2023]

    Accessed on June 11, 2023

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.