AFTD Auto-Formalizing Theoretical Domains

eval_matrix3_decomposition_apply

theoremverified

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

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.

  1. 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.

    lines 2–3

    uses eval_matrix3_decomposition

      induction L with
      | nil => simp [eval_matrix3_decomposition]
  2. 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.

    lines 4–6

    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]
  3. 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.

    line 7

    uses eval_matrix3_triad, smul_eq_mul

        simp [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

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]
See it in the graphDiscuss this resultChallenge it