matrix3_eval_triad_merge
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.
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.
refine ⟨?_, ?_, ?_⟩ <;>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.
uses
eval_matrix3_triad,Matrix.add_apply,add_mul,mul_add,Finset.sum_add_distrib,add_smul,smul_addsimp 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
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.
/-- 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]