Rank of 3×33\times 3 matrix multiplication over the two-element field

A bilinear algorithm multiplies two matrices by multiplying pairs of linear combinations of their entries. Over the field with two elements, how many such products are needed to multiply two 3×33\times 3 matrices?

Why it matters and what counts as progress

Why it matters: The minimum is the tensor rank. An upper bound gives an algorithm, and a matching lower bound shows that every bilinear algorithm over the field needs that many products.

What counts as progress: Construct an algorithm using fewer products or rule out a stated number of products. State the field and distinguish ordinary rank from border rank.

How the problem developed

  1. 1976 · A 23-product algorithm [1]

    Julian D. Laderman Gave a bilinear algorithm using 23 products. Its integer coefficients also work over the two-element field.

  2. October 2026 · Lower bound of 22 [2]

    Rudich and Rousseau Ruled out algorithms with fewer than 22 products over the two-element field.

  3. 19 Oct 2026 · Exact rank of 23 [3]

    Tejasvi Singh Tomar with generative AI tools Reported a matching lower bound and a Lean kernel proof in the revised manuscript.

AI contribution

The rank of 3×33\times 3 matrix multiplication over 𝔽2_{2} is 23

Tejasvi Singh Tomar

Tejasvi Singh Tomar reports that the exact bilinear tensor rank of 3×33\times 3 matrix multiplication over the two-element field is 23. Together with Laderman’s construction, the lower bound rules out every 22-product decomposition over F2\mathbb F_2 and every such bilinear algorithm with integer coefficients.

AI involvementAI-centered
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Laderman’s 23-product algorithm
  2. Rudich and Rousseau’s rank lower bound of 22
  3. The rank of 3×33\times 3 matrix multiplication over 𝔽2_{2} is 23
  4. Tomar’s Lean kernel proof archive
Publication history