AFTD Auto-Formalizing Theoretical Domains

matrix3_eval_triad_merge

theoremverified

Two triads that agree in two of their three slots can be replaced by a single triad: if they share u and w their v's add, if they share v and w their u's add, and if they share u and v their w's add — in each case the sum of the two evaluations equals the evaluation of the merged triad, for all A and B.

Statement

theorem matrix3_eval_triad_merge {R : Type*} [CommSemiring R]
    (u₁ u₂ v₁ v₂ w₁ w₂ : Matrix (Fin 3) (Fin 3) R) (A B : Matrix (Fin 3) (Fin 3) R) :
    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₁, v₂, w₁⟩ A B
        = eval_matrix3_triad ⟨u₁, v₁ + v₂, w₁⟩ A B) ∧
    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₂, v₁, w₁⟩ A B
        = eval_matrix3_triad ⟨u₁ + u₂, v₁, w₁⟩ A B) ∧
    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₁, v₁, w₂⟩ A B
        = eval_matrix3_triad ⟨u₁, v₁, w₁ + w₂⟩ A B)
Source
step towards matrix3_tensor_rank_zmod2_le_22
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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.
  • 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…
Used by 3
  • matrix3_shorter_valid_of_shared_u_wIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same u…
  • matrix3_shorter_valid_of_shared_u_vIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same u…
  • matrix3_shorter_valid_of_shared_v_wIf a list of triads written as L₁ ++ t₁ :: L₂ ++ t₂ :: L₃ is a valid decomposition of matrix multiplication, and t₁ and t₂ have the same v…

The proof, explained

The theorem states that matrix triad evaluation is additive in each of its three component matrices when the other two components are held fixed. The proof splits the conjunction into the three separate merge identities (for the v, u, and w slots) and unfolds the definition of triad evaluation. Because triad evaluation consists of Frobenius inner products and scalar multiplication, distributivity of addition across summation, ring multiplication, and scalar multiplication normalizes both sides of each equation to the same expression.

  1. The goal reduces to proving each of the three merge identities independently.

    The statement is a conjunction of three merge formulas corresponding to adding the triads in the v, u, and w slots, respectively. Splitting the conjunction produces three separate subgoals, each asserting that the evaluation of a merged triad equals the sum of the evaluations of the two component triads.

    line 10

      refine ⟨?_, ?_, ?_⟩ <;>
  2. Triad evaluation distributes over addition in each of the three slots, establishing all three identities.

    For each subgoal, expanding the definition of eval_matrix3_triad reveals that the evaluation is a product of two Frobenius inner products scaling the third matrix. Because matrix addition is entrywise (Matrix.add_apply), finite summation distributes over addition (Finset.sum_add_distrib), ring multiplication distributes over addition (add_mul, mul_add), and scalar multiplication distributes over both scalar addition and matrix addition (add_smul, smul_add), the evaluation map is trilinear. Rewriting both sides with these distributivity rules simplifies them to identical expressions, closing all three goals simultaneously.

    lines 11–12

    uses eval_matrix3_triad, Matrix.add_apply, add_mul, mul_add, Finset.sum_add_distrib, add_smul, smul_add

        simp only [eval_matrix3_triad, Matrix.add_apply, add_mul, mul_add,
          Finset.sum_add_distrib, add_smul, smul_add]
eval_matrix3_triad
the evaluation of a triad t = ⟨u, v, w⟩ on matrices A and B, defined as (∑ i j, u i j * A i j) * (∑ i j, v i j * B i j) • w
Matrix.add_apply
the (i, j)-th entry of a matrix sum is the sum of the entries: (A + B) i j = A i j + B i j
add_mul
multiplication distributes over addition on the right: (a + b) * c = a * c + b * c
mul_add
multiplication distributes over addition on the left: a * (b + c) = a * b + a * c
Finset.sum_add_distrib
the sum of a pointwise sum over a finite set equals the sum of the sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x
add_smul
scalar multiplication distributes over addition of scalars: (r + s) • x = r • x + s • x
smul_add
scalar multiplication distributes over addition of vectors: a • (b₁ + b₂) = a • b₁ + a • b₂

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The three merge identities for triads: two triads agreeing in two slots have the evaluation of the triad obtained by adding the remaining slots. -/theorem matrix3_eval_triad_merge {R : Type*} [CommSemiring R]    (u₁ u₂ v₁ v₂ w₁ w₂ : Matrix (Fin 3) (Fin 3) R) (A B : Matrix (Fin 3) (Fin 3) R) :    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₁, v₂, w₁⟩ A B        = eval_matrix3_triad ⟨u₁, v₁ + v₂, w₁⟩ A B) ∧    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₂, v₁, w₁⟩ A B        = eval_matrix3_triad ⟨u₁ + u₂, v₁, w₁⟩ A B) ∧    (eval_matrix3_triad ⟨u₁, v₁, w₁⟩ A B + eval_matrix3_triad ⟨u₁, v₁, w₂⟩ A B        = eval_matrix3_triad ⟨u₁, v₁, w₁ + w₂⟩ A B) := by  refine ⟨?_, ?_, ?_⟩ <;>    simp only [eval_matrix3_triad, Matrix.add_apply, add_mul, mul_add,      Finset.sum_add_distrib, add_smul, smul_add]
See it in the graphDiscuss this resultChallenge it