💻 computer science

55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

This paper presents a new rank-23 algorithm for $3\times3$ matrix multiplication that reduces the required number of additions to 55 (totaling 78 scalar operations), thereby improving upon the previous state-of-the-art of 56 additions while maintaining validity over any associative ring through a construction based on Perminov's tensor and an optimized linear circuit.

Original authors: Samurdhi Karunaratne, Anushka Idamekorala

Published 2026-08-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Samurdhi Karunaratne, Anushka Idamekorala

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef trying to bake a massive, complex cake. The recipe requires you to mix dozens of ingredients together in very specific ways. In the world of computers, "mixing" ingredients is like multiplying numbers, and "baking the cake" is like multiplying two grids of numbers (matrices) to get a new result. For a long time, mathematicians thought the only way to do this was to follow the standard, slow recipe: multiply every single number and then add them up. But in the 1960s, a genius named Strassen discovered a magic trick. He realized that if you rearrange the order of your mixing, you could skip some of the heavy lifting. You could get the same delicious cake using fewer "multiplications," which are the most expensive and time-consuming steps in the kitchen.

However, there's a catch. While you can save on the expensive multiplications, you often have to do more "additions" (mixing bowls) to get the ingredients ready. Think of it like this: instead of just pouring flour into a bowl, you might have to chop, stir, and fold ingredients in a very specific dance before you can combine them. The goal for computer scientists has been to find the perfect dance routine that uses the absolute fewest steps possible. The paper you are about to read is about a team that found a new, slightly more efficient dance for a specific type of cake: a 3x3 matrix. They didn't change the number of heavy lifts (multiplications), but they managed to trim the number of mixing steps (additions) by one, shaving off a tiny but significant amount of work.

The New Record-Breaking Dance

This paper, written by Samurdhi Karunaratne and Anushka Idamekorala from Logical AI, announces a new record for multiplying two 3x3 grids of numbers. They have found a way to do it using only 55 additions and 23 multiplications.

To understand why this is a big deal, picture the previous best recipe. The current champion, created by a researcher named Sun, required 56 additions. The authors of this paper didn't invent a whole new way to multiply matrices; instead, they took an existing, public recipe (created by Perminov) that used 58 additions and 59 additions in earlier versions, and they optimized the "preparation" steps. They realized that by rearranging how the ingredients were pre-mixed, they could cut the total number of addition steps down to 55.

Here is how their new "kitchen" works, broken down into three simple stages:

Prepping the Left Ingredients: Before mixing, they take the first grid of numbers (let's call it the "Left" grid) and perform 13 simple addition or subtraction steps to create 23 special mixtures.
Prepping the Right Ingredients: They do the same for the second grid (the "Right" grid), using 14 steps to create its 23 special mixtures.
The Big Mix and Final Assembly: They multiply the matching mixtures from the Left and Right grids (23 multiplications in total). Then, they take those 23 results and perform 28 more addition steps to assemble the final 3x3 result.

When you add up the prep work (13 + 14) and the final assembly (28), you get exactly 55 additions. This is one fewer than the previous best, making it the most efficient known method for this specific type of calculation.

Why This Matters (and What It Doesn't)

You might wonder, "Is this the absolute best possible way to do it?" The authors are very careful to say: No, not necessarily. They have proven that for this specific arrangement of ingredients they chose, 55 is the best you can do. They used a rigorous mathematical search to prove that you cannot get away with fewer steps for this specific recipe. However, they admit that there might be a completely different recipe (a different arrangement of ingredients) that could be even faster. They haven't found it yet, and they aren't claiming to have solved the entire mystery of matrix multiplication forever.

They also clarify that this isn't just a lucky guess or a computer simulation that might be wrong. They have provided a "certificate" of truth. They wrote out the entire step-by-step recipe (called a "straight-line program") and ran it through multiple independent computer programs (written in Python and Node.js) to check every single one of the 729 mathematical rules that must be true for the recipe to work. Every single check passed. This means the math is solid, and the recipe works perfectly for any kind of number system, even the weird ones where the order of multiplication matters.

The AI Behind the Curtain

An interesting twist in this story is how the recipe was found. The authors reveal that a human researcher guided an AI system (specifically, an agent using OpenAI's GPT-5.6 Sol) to discover this. The human set the goal: "Find a way to beat the 56-addition record." The AI then explored the landscape of existing recipes, found Perminov's older 58-addition version, and realized that by tweaking the preparation steps, it could shave off three extra moves. The AI then double-checked its work, wrote the code, and verified the math. It's a perfect example of a human and a machine working together: the human provided the direction and the "why," while the AI handled the heavy lifting of searching through millions of possibilities to find the "how."

In the end, this paper is a small but precise victory. It shows that even in a field as old as matrix multiplication, there are still tiny, hidden efficiencies waiting to be discovered if you look closely enough. It's like finding a new, slightly shorter path through a familiar forest. You still end up in the same place, but you get there with just one less step.

Technical Summary: 55 Additions Suffice for 3 × 3 Matrix Multiplication at Rank 23

Problem Statement
The paper addresses the problem of minimizing the additive complexity (the number of additions and subtractions) required to multiply two arbitrary $3 \times 3$ matrices over an associative ring, given a fixed multiplicative rank of 23. While Strassen's algorithm established that matrix multiplication can be accelerated by reducing bilinear products, the multiplicative rank for general $3 \times 3$ matrices has remained at 23 since Laderman's 1976 discovery. Recent research has focused on reducing the number of scalar additions required to realize these rank-23 schemes. Prior to this work, the state of the art was 56 additions, achieved by Sun.

Methodology
The authors construct a new algorithm by optimizing the linear stages of a pre-existing tensor factorization. The methodology proceeds as follows:

Base Tensor: The construction utilizes Perminov's publicly released factorization, cr58_cn122, which originally required 58 additions (14 for the left input, 15 for the right input, and 29 for the output reconstruction).
Exact Synthesis of Factor Maps: The authors perform an exhaustive dependency search within the binary addition/subtraction straight-line program (SLP) model to optimize the three linear maps ( $U, V, W$ $U, V, W$ ) that transform the 9 input matrix entries into the 23 bilinear forms.
- They identify that for the fixed orientation of the tensor, the minimum number of gates required to generate the necessary output directions exceeds the theoretical lower bound based on distinct non-basis directions ( $d(F)$ ).
- Specifically, they prove that for the left factor ( $U$ ), the cost is 13 (one more than the floor of 12); for the right factor ( $V$ ), the cost is 14 (one more than the floor of 13); and for the output factor ( $W$ ), the cost is 14 (one more than the floor of 13).
Transposition Principle: To obtain the output reconstruction circuit (which maps 23 products back to 9 matrix entries), the authors transpose the optimized 14-addition circuit for $W$ . Using the linear-circuit transposition principle, a circuit with $L$ gates, $n$ inputs, and $m$ outputs transforms into a circuit for the transpose with $L + m - n$ gates. Applying this to the $W$ circuit ( $L=14, n=9, m=23$ ) yields a 28-gate output circuit.
Verification: The correctness of the algorithm is verified by checking all 729 Brent identities over the integers $\mathbb{Z}$ . The authors provide four independent verification methods, including Python and Node.js implementations, ensuring the result holds over any associative ring (commutative or not) since the coefficient alphabet is restricted to $\{-1, 0, 1\}$ .

Key Contributions

New Upper Bound: The paper presents a realization of $3 \times 3$ matrix multiplication using 23 scalar multiplications and 55 additions/subtractions, improving the previous record of 56.
Optimality Certificate: The authors provide a provably optimal linear circuit for the specific tensor orientation used. They demonstrate that for the fixed tensor cr58_cn122, the sum of the linear stage costs cannot be lower than 55 in the standard three-stage bilinear SLP model.
Exact Data Release: The paper includes the full straight-line program, the tensor factors, and a "frozen certificate" that allows for byte-for-byte regeneration and independent verification of the 729 identities.

Results
The resulting circuit anatomy is as follows:

Left Preprocessing (A): 13 additions (mapping 9 inputs to 23 forms).
Right Preprocessing (B): 14 additions (mapping 9 inputs to 23 forms).
Bilinear Layer: 23 multiplications.
Output Reconstruction: 28 additions (mapping 23 products to 9 outputs).
Total Linear Work: 55 additions.

The paper confirms that the algorithm applies to any associative ring because the coefficients are in $\{-1, 0, 1\}$ and the order of bilinear products is preserved.

Significance and Claims
The authors explicitly state that they do not claim 55 is the global minimum among all possible rank-23 decompositions, nor that it is optimal in circuit models allowing primitive operations other than addition/subtraction. However, within the specific model of a fixed tensor orientation and the standard three-stage bilinear straight-line program, 55 is the smallest addition count currently known.

The significance of the work lies in:

Incremental Improvement: It lowers the upper bound by one addition, continuing the trend of optimizing additive complexity for fixed multiplicative ranks.
Rigorous Verification: The result is backed by exact integer arithmetic and multiple independent implementations, avoiding reliance on numerical or randomized tests.
AI-Assisted Discovery: The paper discloses that the discovery was driven by a human-directed investigation using AI agents (OpenAI GPT-5.6 Sol and Codex) for search, synthesis, and verification. The human researcher defined the objectives and acceptance criteria, while the AI agents executed the circuit searches and generated the certificate. The authors emphasize that the mathematical validity rests entirely on the 729 exact identities and the printed straight-line program, not on the AI's involvement.

The New Record-Breaking Dance

Why This Matters (and What It Doesn't)

The AI Behind the Curtain

Technical Summary: 55 Additions Suffice for 3 × 3 Matrix Multiplication at Rank 23

More like this