eval_matrix3_decomposition_sum_left
Given a commutative semiring R, a finite set s, a list L of triads, a family of matrices F, and a matrix B, evaluating L on (∑ i ∈ s, F i) and B equals ∑ i ∈ s, eval_matrix3_decomposition L (F i) B.
Statement
theorem eval_matrix3_decomposition_sum_left {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (F : ι → Matrix (Fin 3) (Fin 3) R) (B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L (∑ i ∈ s, F i) B = ∑ i ∈ s, eval_matrix3_decomposition L (F i) B
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_decomposition_add_leftGiven a commutative semiring R, a list L of Matrix3Triad R, and matrices A₁, A₂, and B, eval_matrix3_decomposition L (A₁ + A₂) B equals…
- 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 1
- matrix3_valid_of_unit_checksIf a list L of triads over a commutative semiring R evaluates to matrix multiplication on all 81 pairs of matrix units, then L is a valid…
The proof, explained
The theorem is proved by finite set induction on s using `Finset.cons_induction`. An auxiliary induction on the list of triads shows that evaluation vanishes when the left matrix argument is zero, which closes the base case s = ∅. For the inductive step of adjoining an element a ∉ s, the sum separates into the term at a and the sum over s via `Finset.sum_cons`, distributes across the left argument by left additivity (`eval_matrix3_decomposition_add_left`), and recombines using the induction hypothesis and `Finset.sum_cons`.
Evaluating any triad decomposition on the zero matrix in the left argument yields the zero matrix.
We establish the auxiliary lemma `hzero` by induction on the list of triads L. For the base case of an empty list, the decomposition evaluates to zero by definition (`eval_matrix3_decomposition`). For the inductive step of a list t :: L, the evaluation unfolds into the triad evaluation of t on 0 plus the evaluation of L on 0. Because the Frobenius inner product of 0 with the triad matrix u is zero, the triad evaluation (`eval_matrix3_triad`) evaluates to zero, and the induction hypothesis ensures the remaining sum is zero as well.
uses
eval_matrix3_decomposition,eval_matrix3_triadhave hzero : ∀ L : List (Matrix3Triad R), eval_matrix3_decomposition L 0 B = 0 := by intro L induction L with | nil => simp [eval_matrix3_decomposition] | cons t L ih => simp [eval_matrix3_decomposition, eval_matrix3_triad]
It suffices to prove the equality for the empty set and show it is preserved when inserting a new element into a finite set.
We set up induction on the finite set s using `Finset.cons_induction`, specifying the motive that evaluating the triad decomposition on the sum over s equals the sum of the evaluations.
uses
Finset.cons_inductionrefine Finset.cons_induction (motive := fun s => eval_matrix3_decomposition L (∑ i ∈ s, F i) B = ∑ i ∈ s, eval_matrix3_decomposition L (F i) B) ?_ ?_ s
The identity holds for the base case s = ∅.
When s = ∅, the sum on both sides is empty and evaluates to 0. Evaluating the decomposition on the zero matrix yields 0 by the auxiliary lemma `hzero`, matching the empty sum on the right-hand side.
· simp [hzero]The identity is preserved when adjoining an element a ∉ s to s.
We introduce the new element a, the set s, the assumption a ∉ s, and the induction hypothesis ih. Using `Finset.sum_cons`, the sum ∑ i ∈ cons a s, F i decomposes into F a + ∑ i ∈ s, F i. By the left additivity of triad decomposition evaluation (`eval_matrix3_decomposition_add_left`), the evaluation on this sum splits into the evaluation on F a plus the evaluation on ∑ i ∈ s, F i. We then substitute the induction hypothesis ih to rewrite the second term as the sum of evaluations over s, and a final application of `Finset.sum_cons` recombines the terms into the sum of evaluations over cons a s.
uses
Finset.sum_cons,eval_matrix3_decomposition_add_left· intro a s ha ih rw [Finset.sum_cons ha, eval_matrix3_decomposition_add_left, ih, Finset.sum_cons ha]
eval_matrix3_decomposition- Evaluates a list of triads L on matrices A and B by summing the evaluations of each triad in L on A and B.
eval_matrix3_triad- Evaluates a single triad t = (u, v, w) on matrices A and B as the scalar multiple ((⟨u, A⟩ * ⟨v, B⟩) • w), where the matrix pairing is the entrywise Frobenius inner product.
Finset.cons_induction- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining an element not already in the set.
Finset.sum_cons- The sum of a function over a finite set with an adjoined element a ∉ s equals the value at a plus the sum over s.
eval_matrix3_decomposition_add_left- Evaluation of a triad decomposition distributes over addition in the left matrix argument: eval L (A₁ + A₂) B = eval L A₁ B + eval L 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.
/-- Evaluation of a triad decomposition distributes over finite sums in the left matrix argument. -/theorem eval_matrix3_decomposition_sum_left {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (F : ι → Matrix (Fin 3) (Fin 3) R) (B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L (∑ i ∈ s, F i) B = ∑ i ∈ s, eval_matrix3_decomposition L (F i) B := by -- `eval L · B` vanishes at `0`, so it is additive over finite sums of the left matrix. have hzero : ∀ L : List (Matrix3Triad R), eval_matrix3_decomposition L 0 B = 0 := by intro L induction L with | nil => simp [eval_matrix3_decomposition] | cons t L ih => simp [eval_matrix3_decomposition, eval_matrix3_triad] refine Finset.cons_induction (motive := fun s => eval_matrix3_decomposition L (∑ i ∈ s, F i) B = ∑ i ∈ s, eval_matrix3_decomposition L (F i) B) ?_ ?_ s · simp [hzero] · intro a s ha ih rw [Finset.sum_cons ha, eval_matrix3_decomposition_add_left, ih, Finset.sum_cons ha]