eval_matrix3_decomposition_apply
Entry (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 B_kl) times w_ij.
Statement
theorem eval_matrix3_decomposition_apply {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (A B : Matrix (Fin 3) (Fin 3) R) (i j : Fin 3) : eval_matrix3_decomposition L A B i j = (L.map fun t => (∑ k : Fin 3, ∑ l : Fin 3, t.u k l * A k l) * (∑ k : Fin 3, ∑ l : Fin 3, t.v k l * B k l) * t.w i j).sum
- Source
- step towards the 3x3 matrix-multiplication rank statements (arXiv:2610.01639): entrywise evaluation of a triad decomposition
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- eval_matrix3_decompositionGiven a commutative semiring R, a list L of Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_decomposition L A B is the sum…
- eval_matrix3_triadGiven a commutative semiring R, a triad t of type Matrix3Triad R, and 3x3 matrices A and B over R, eval_matrix3_triad t A B is the scalar…
- 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.
- Used by 3
- matrix3_valid_iff_trace_tensor_identityFor a finite indexed family of triads over any commutative semiring, validity of the decomposition whose output weights are the transposes…
- matrix3_tensor_rank_le_of_surjectiveIf f : R → S is a surjective homomorphism of commutative semirings and 3x3 matrix multiplication over R has a valid triad decomposition…
- matrix3_tensor_rank_le_23_of_comm_ringOver every commutative ring R, 3x3 matrix multiplication has a valid bilinear decomposition with 23 products (the classical…
The proof, explained
The theorem is proved by structural induction on the list L of triads. The base case for the empty list is immediate since both sides reduce to zero. In the inductive step, the decomposition and the scalar sum are split into the contribution of the head triad and the sum over the tail list. Applying the induction hypothesis cancels the tail terms, and unfolding the definition of a single triad evaluation shows that its (i, j) entry matches the required scalar product with w_ij.
The identity holds for the empty list L = [].
We proceed by structural induction on the list L. In the base case where L is empty, the matrix decomposition evaluates to the zero matrix (with (i, j) entry 0), and the sum over the empty list on the right-hand side is also 0.
uses
eval_matrix3_decompositioninduction L with | nil => simp [eval_matrix3_decomposition]
Assuming the identity holds for L, the goal for the non-empty list t :: L reduces to matching the head triad t.
Unfolding eval_matrix3_decomposition and applying List.map_cons, List.sum_cons, and Matrix.add_apply separates both the matrix evaluation at entry (i, j) and the scalar sum into a head term corresponding to t and a tail sum corresponding to L. Rewriting with the induction hypothesis ih equates the tail terms, leaving only the head triad terms to be reconciled.
uses
eval_matrix3_decomposition,List.map_cons,List.sum_cons,Matrix.add_apply| cons t L ih => simp only [eval_matrix3_decomposition, List.map_cons, List.sum_cons, Matrix.add_apply] at ih ⊢ rw [ih]The (i, j) entry of eval_matrix3_triad t A B matches the head term (∑ k l, t.u k l * A k l) * (∑ k l, t.v k l * B k l) * t.w i j, completing the proof.
By definition of eval_matrix3_triad, the triad evaluates to the product of the two Frobenius inner products scaled by the matrix t.w. Evaluating at index (i, j) converts scalar multiplication to ring multiplication via smul_eq_mul, which identically matches the remaining goal.
uses
eval_matrix3_triad,smul_eq_mulsimp [eval_matrix3_triad, smul_eq_mul]
eval_matrix3_decomposition- The evaluation of a list of triads on matrices A and B, defined as the sum over the list of each triad evaluated on A and B: (L.map (fun t => eval_matrix3_triad t A B)).sum.
List.map_cons- Mapping a function over a non-empty list applies the function to the head element and prepends the result to the mapped tail: List.map f (x :: xs) = f x :: List.map f xs.
List.sum_cons- The sum of a non-empty list is the head element added to the sum of the tail: (x :: xs).sum = x + xs.sum.
Matrix.add_apply- Entry (i, j) of the sum of two matrices is the sum of their (i, j) entries: (M + N) i j = M i j + N i j.
eval_matrix3_triad- The evaluation of a triad t = (u, v, w) on matrices A and B, defined as the scalar product (∑ u_kl A_kl) * (∑ v_kl B_kl) multiplying the matrix w.
smul_eq_mul- Scalar multiplication of ring elements agrees with multiplication in the ring: a • b = a * b.
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.
theorem eval_matrix3_decomposition_apply {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (A B : Matrix (Fin 3) (Fin 3) R) (i j : Fin 3) : eval_matrix3_decomposition L A B i j = (L.map fun t => (∑ k : Fin 3, ∑ l : Fin 3, t.u k l * A k l) * (∑ k : Fin 3, ∑ l : Fin 3, t.v k l * B k l) * t.w i j).sum := by induction L with | nil => simp [eval_matrix3_decomposition] | cons t L ih => simp only [eval_matrix3_decomposition, List.map_cons, List.sum_cons, Matrix.add_apply] at ih ⊢ rw [ih] simp [eval_matrix3_triad, smul_eq_mul]