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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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.
- [§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)
- [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.
- [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.
- [§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.
- [§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
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
free parameters (5)
- Diagonal partition P for n=5 =
{{1,5},{2,4},{3}}
- Diagonal partition P for n=6 =
{{1,2},{3,4},{5,6}}
- Flip limit L =
10**8 (n=5), 10**9 (n=6)
- Plus-transition parameter M =
5*10**4 (n=5), 5*10**5 (n=6)
- Symmetry group G =
C3 for n=5; C3 x Z2 for n=6
assumptions (4)
- domain assumption The flip graph algorithm and its transitions (flip, reduction, plus-transition) preserve the property of being a matrix multiplication scheme.
- 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.
- ad hoc to paper Hensel lifting converges to an integer solution for the reported schemes.
- standard math The symmetry group actions S3 and GL(n)^3 and their semidirect product are the correct equivalence notion for matrix multiplication schemes.
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
Forward citations
Cited by 2 Pith papers
-
Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
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.
-
Exploring Commutative Matrix Multiplication Schemes via Flip Graphs
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
-
[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
work page 2025
-
[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
work page 2024
-
[3]
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
work page 2019
-
[4]
Richard P. Brent. Algorithms for matrix multiplication. Technical report, Department of Computer Science, Stanford, 1970
work page 1970
-
[5]
V. P. Burichenko. Symmetries of matrix multiplication algorithms. i, 2015
work page 2015
-
[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
work page 2022
-
[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
work page 1990
- [8]
Show all 24 references
-
[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
1978
-
[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
2011
-
[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...
2022
-
[12]
Grochow and Cristopher Moore
Joshua A. Grochow and Cristopher Moore. Matrix multiplication algorithms from group orbits, 2016
2016
-
[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
2019
-
[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
2021
-
[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
1971
-
[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
2023
-
[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
2025
-
[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
1976
-
[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
2017
-
[20]
Yet another catalogue of fast matrix multiplication algorithms
Alexandre Sedoglavic. Yet another catalogue of fast matrix multiplication algorithms. https://fmm.univ-lille.fr/,
-
[21]
Alexey V. Smirnov. The bilinear complexity and practical algorithms for matrix multiplication. Zh. Vychisl. Mat. Mat. Fiz., 53(12):1970–1984, 2013
1970
-
[22]
Gaussian elimination is not optimal
Volker Strassen. Gaussian elimination is not optimal. Numer. Math. , 13:354–356, 1969
1969
-
[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...
2013
-
[2023]
Accessed on June 11, 2023
2023
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.