matrix3_tensor_rank_le_23_of_comm_ring
Over every commutative ring R, 3x3 matrix multiplication has a valid bilinear decomposition with 23 products (the classical 23-multiplication algorithm with integer coefficients 0, 1, -1); hence its rank over R is at most 23.
Statement
theorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23
- Formalizes
- A noncommutative algorithm for multiplying matrices using 23 multiplications (1976), as cited in Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers, arXiv:2610.01639, Sec. 1 and Sec. 7 (upper bound 23); the integer coefficients 0, 1, -1 make it valid over every commutative ring
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- matrix3_tensor_rank_leFor a commutative semiring R and a natural number r, matrix3_tensor_rank_le R r asserts that there exists a list L of elements of…
- eval_matrix3_decomposition_applyEntry (i, j) of the evaluation of a list of 3x3 triads on A and B is the sum, over the triads, of (sum of u_kl A_kl) times (sum of v_kl…
- Matrix3TriadGiven a type R, a Matrix3Triad R is a structure consisting of three 3-by-3 matrices with entries in R, labeled u, v, and w.
- is_valid_matrix3_decompositionGiven a commutative semiring R and a list L of Matrix3Triad R, is_valid_matrix3_decomposition L asserts that for all 3x3 matrices A and B…
- Used by 4
- matrix3_tensor_rank_z_le_23The tensor rank of 3x3 matrix multiplication over the integers is at most 23; that is, there exists a valid decomposition of 3x3 matrix…
- matrix3_tensor_rank_f2_le_23The tensor rank of 3x3 matrix multiplication over the field ZMod 2 is at most 23; that is, there exists a valid decomposition of 3x3…
- matrix3_unit_check_witnessesThe checker matrix3_unit_check returns true on the classical 23-triad decomposition of 3x3 matrix multiplication over ZMod 2 (so the…
- matrix3_unit_check_int_witnessesThe checker matrix3_unit_check_int returns true on the classical 23-triad integer decomposition and false on the empty list.
The proof, explained
The theorem shows that the tensor rank of 3×3 matrix multiplication over any commutative ring R is at most 23 by exhibiting Laderman's 1976 decomposition consisting of 23 explicit triads with coefficients in {-1, 0, 1}. Validity is verified entry-by-entry: after reducing to the 9 matrix positions, each entry simplifies to an algebraic identity in the coefficients of the input matrices, verified by ring normalization. Packaging this list along with its length equality proves the tensor rank bound.
An explicit list of 23 triads of 3×3 matrices is defined over any commutative ring R.
We construct Laderman's 23 triples of 3×3 matrices (u, v, w) with coefficients in {0, 1, -1}.
/-- An explicit list of 23 triads over any commutative ring; its 23 products compute the 3×3 matrix product. -/ def matrix3_triads_23 (R : Type*) [CommRing R] : List (Matrix3Triad R) := [ ⟨!![1, 1, 1; -1, -1, 0; 0, -1, -1], !![0, 0, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0]⟩, ⟨!![1, 0, 0; -1, 0, 0; 0, 0, 0], !![0, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 0, 0; 1, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 1, 0; 0, 0, 0], !![-1, 1, 0; 1, -1, -1; -1, 0, 1], !![0, 0, 0; 1, 0, 0; 0, 0, 0]⟩, ⟨!![-1, 0, 0; 1, 1, 0; 0, 0, 0], !![1, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 1, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 1, 1, 0; 0, 0, 0], !![-1, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 1, 0; 0, 1, 0; 0, 0, 0]⟩, ⟨!![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 1, 1; 1, 1, 0; 1, 0, 1]⟩, ⟨!![-1, 0, 0; 0, 0, 0; 1, 1, 0], !![1, 0, -1; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 1, 0, 1]⟩, ⟨!![-1, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 1]⟩, ⟨!![0, 0, 0; 0, 0, 0; 1, 1, 0], !![-1, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 1]⟩, ⟨!![1, 1, 1; 0, -1, -1; -1, -1, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 0], !![-1, 0, 1; 1, -1, -1; -1, 1, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0]⟩, ⟨!![0, 0, -1; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 1, 0; 1, -1, 0], !![0, 1, 0; 0, 0, 0; 1, 1, 0]⟩, ⟨!![0, 0, 1; 0, 0, 0; 0, 0, -1], !![0, 0, 0; 0, 1, 0; 0, -1, 0], !![0, 0, 0; 0, 0, 0; 1, 1, 0]⟩, ⟨!![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0], !![1, 1, 1; 1, 0, 1; 1, 1, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 0, 0; -1, 1, 0], !![0, 1, 0; 0, 0, 0; 0, 1, 0]⟩, ⟨!![0, 0, -1; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 1, 0, -1], !![0, 0, 1; 1, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, -1], !![0, 0, 0; 1, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; -1, 0, 1], !![0, 0, 1; 0, 0, 1; 0, 0, 0]⟩, ⟨!![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 1, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0], !![0, 0, 0; 0, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 1, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1]⟩ ]
The triad list matrix3_triads_23 has length 23.
The length of the list is 23 by definition (refl).
theorem matrix3_triads_23_length (R : Type*) [CommRing R] : (matrix3_triads_23 R).length = 23 := rfl
It suffices to show that for any two 3×3 matrices A and B and any indices i, j ∈ Fin 3, the (i, j)-th entry of the decomposition's evaluation matches (A * B) i j.
We introduce arbitrary matrices A and B, then use matrix extensionality to reduce the equality of the two 3×3 matrices to showing their entries agree at every row i and column j.
theorem matrix3_triads_23_valid (R : Type*) [CommRing R] : is_valid_matrix3_decomposition (matrix3_triads_23 R) := by set_option maxHeartbeats 1000000 in intro A B ext i j
The (i, j)-th entry of the decomposition is expanded as the sum of the triad products.
We rewrite the left-hand side using eval_matrix3_decomposition_apply, expressing the entry as the sum over all 23 triads of the scalar product of A with u, times the scalar product of B with v, scaled by the (i, j)-th entry of w.
uses
eval_matrix3_decomposition_applyrw [eval_matrix3_decomposition_apply]For each of the 9 index pairs (i, j), the evaluated decomposition equals the (i, j)-th entry of A * B. automation
We exhaust all 9 choices of (i, j) in Fin 3 × Fin 3. For each pair, simp unfolds the definition of the 23 triads, expands the sums over Fin 3 via Fin.sum_univ_three, and writes the right-hand side via Matrix.mul_apply; the ring tactic then confirms that the resulting polynomial identity in the matrix entries of A and B holds in the commutative ring R.
uses
Fin.sum_univ_three,Matrix.mul_applyfin_cases i <;> fin_cases j <;> simp [matrix3_triads_23, Fin.sum_univ_three, Matrix.mul_apply] <;> ringThe tensor rank of 3×3 matrix multiplication over R is at most 23.
We witness the definition of matrix3_tensor_rank_le using the explicit triad list matrix3_triads_23 R. Its length is at most 23 by le_of_eq applied to matrix3_triads_23_length, and its validity is given by matrix3_triads_23_valid.
uses
le_of_eq,matrix3_triads_23_length,matrix3_triads_23_validtheorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23 := ⟨matrix3_triads_23 R, le_of_eq (matrix3_triads_23_length R), matrix3_triads_23_valid R⟩
Matrix.mul_apply- The (i, j)-th entry of the matrix product A * B is the sum over k of A i k * B k j.
Fin.sum_univ_three- A sum of a function over the three elements of Fin 3 equals the sum of its values at 0, 1, and 2.
eval_matrix3_decomposition_apply- The (i, j)-th entry of the evaluated decomposition is the sum over all triads t in L of (∑ k l, t.u k l * A k l) * (∑ k l, t.v k l * B k l) * t.w i j.
le_of_eq- If a equals b, then a is less than or equal to b.
matrix3_triads_23_length- The explicit list of triads matrix3_triads_23 has length exactly 23.
matrix3_triads_23_valid- The explicit list of 23 triads correctly computes 3×3 matrix multiplication for any pair of matrices A and B.
- The validity check on lines 37-38 delegates the expansion and verification of 9 bivariate polynomial identities in 18 matrix entry variables across 23 triads to the `simp` and `ring` automation tactics.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- An explicit list of 23 triads over any commutative ring; its 23 products compute the 3×3 matrix product. -/def matrix3_triads_23 (R : Type*) [CommRing R] : List (Matrix3Triad R) := [ ⟨!![1, 1, 1; -1, -1, 0; 0, -1, -1], !![0, 0, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0]⟩, ⟨!![1, 0, 0; -1, 0, 0; 0, 0, 0], !![0, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 0, 0; 1, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 1, 0; 0, 0, 0], !![-1, 1, 0; 1, -1, -1; -1, 0, 1], !![0, 0, 0; 1, 0, 0; 0, 0, 0]⟩, ⟨!![-1, 0, 0; 1, 1, 0; 0, 0, 0], !![1, -1, 0; 0, 1, 0; 0, 0, 0], !![0, 1, 0; 1, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 1, 1, 0; 0, 0, 0], !![-1, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 1, 0; 0, 1, 0; 0, 0, 0]⟩, ⟨!![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0], !![1, 1, 1; 1, 1, 0; 1, 0, 1]⟩, ⟨!![-1, 0, 0; 0, 0, 0; 1, 1, 0], !![1, 0, -1; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 1, 0, 1]⟩, ⟨!![-1, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 1]⟩, ⟨!![0, 0, 0; 0, 0, 0; 1, 1, 0], !![-1, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 1]⟩, ⟨!![1, 1, 1; 0, -1, -1; -1, -1, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 0], !![-1, 0, 1; 1, -1, -1; -1, 1, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0]⟩, ⟨!![0, 0, -1; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 1, 0; 1, -1, 0], !![0, 1, 0; 0, 0, 0; 1, 1, 0]⟩, ⟨!![0, 0, 1; 0, 0, 0; 0, 0, -1], !![0, 0, 0; 0, 1, 0; 0, -1, 0], !![0, 0, 0; 0, 0, 0; 1, 1, 0]⟩, ⟨!![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 1, 0, 0], !![1, 1, 1; 1, 0, 1; 1, 1, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 1, 1], !![0, 0, 0; 0, 0, 0; -1, 1, 0], !![0, 1, 0; 0, 0, 0; 0, 1, 0]⟩, ⟨!![0, 0, -1; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 1, 0, -1], !![0, 0, 1; 1, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 1; 0, 0, -1; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, -1], !![0, 0, 0; 1, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 1, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; -1, 0, 1], !![0, 0, 1; 0, 0, 1; 0, 0, 0]⟩, ⟨!![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 1, 0, 0; 0, 0, 0], !![1, 0, 0; 0, 0, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 1; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0], !![0, 0, 0; 0, 1, 0; 0, 0, 0]⟩, ⟨!![0, 0, 0; 1, 0, 0; 0, 0, 0], !![0, 0, 1; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 1; 0, 0, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 1, 0, 0], !![0, 1, 0; 0, 0, 0; 0, 0, 0], !![0, 0, 0; 0, 0, 0; 0, 1, 0]⟩, ⟨!![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1], !![0, 0, 0; 0, 0, 0; 0, 0, 1]⟩ ]theorem matrix3_triads_23_length (R : Type*) [CommRing R] : (matrix3_triads_23 R).length = 23 := rfltheorem matrix3_triads_23_valid (R : Type*) [CommRing R] : is_valid_matrix3_decomposition (matrix3_triads_23 R) := by set_option maxHeartbeats 1000000 in intro A B ext i j rw [eval_matrix3_decomposition_apply] fin_cases i <;> fin_cases j <;> simp [matrix3_triads_23, Fin.sum_univ_three, Matrix.mul_apply] <;> ringtheorem matrix3_tensor_rank_le_23_of_comm_ring (R : Type*) [CommRing R] : matrix3_tensor_rank_le R 23 := ⟨matrix3_triads_23 R, le_of_eq (matrix3_triads_23_length R), matrix3_triads_23_valid R⟩