eval_matrix3_decomposition_add_left
Given a commutative semiring R, a list L of Matrix3Triad R, and matrices A₁, A₂, and B, eval_matrix3_decomposition L (A₁ + A₂) B equals eval_matrix3_decomposition L A₁ B + eval_matrix3_decomposition L A₂ B.
Statement
theorem eval_matrix3_decomposition_add_left {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (A₁ A₂ B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L (A₁ + A₂) B = eval_matrix3_decomposition L A₁ B + eval_matrix3_decomposition L A₂ 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_triad_add_leftGiven a commutative semiring R, a triad t of type Matrix3Triad R, and matrices A₁, A₂, and B in Matrix (Fin 3) (Fin 3) R,…
- 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 1
- eval_matrix3_decomposition_sum_leftGiven 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)…
The proof, explained
The theorem is proved by induction on the list of triads L. In the base case, an empty list evaluates to zero on both sides, which is trivially additive. In the inductive step, the sum for the cons list splits into a head triad evaluation and a tail list decomposition; applying left-additivity of a single triad to the head and the induction hypothesis to the tail reduces the goal to an equality between two regroupings of the four resulting terms, which is solved by abelian monoid arithmetic.
The identity holds for the empty list: `eval_matrix3_decomposition [] (A₁ + A₂) B = eval_matrix3_decomposition [] A₁ B + eval_matrix3_decomposition [] A₂ B`.
We proceed by induction on the list of triads `L`. In the base case `L = []`, evaluating the decomposition on any input produces an empty sum, which is the zero matrix `0`. Both sides reduce to `0`, and `simp` simplifies the identity `0 = 0 + 0`.
uses
eval_matrix3_decompositioninduction L with | nil => simp [eval_matrix3_decomposition]
The identity holds for `t :: L'`: `eval_matrix3_decomposition (t :: L') (A₁ + A₂) B = eval_matrix3_decomposition (t :: L') A₁ B + eval_matrix3_decomposition (t :: L') A₂ B`.
In the inductive step, assume the claim holds for the tail `L'` as the induction hypothesis `ih`. Unfolding `eval_matrix3_decomposition` splits each decomposition sum into the head term for triad `t` plus the decomposition sum for `L'`. The head term at `A₁ + A₂` decomposes into a sum of two terms by left-additivity of a single triad (`eval_matrix3_triad_add_left`), while the tail sum decomposes into two terms by `ih`. Finally, `abel` closes the goal by rearranging the addition of these four matrix terms using commutativity and associativity.
uses
eval_matrix3_decomposition,eval_matrix3_triad_add_left| cons t L' ih => simp [eval_matrix3_decomposition, eval_matrix3_triad_add_left] abel
eval_matrix3_decomposition- Evaluates a triad decomposition list by mapping each triad to its evaluated matrix and summing the resulting list.
eval_matrix3_triad_add_left- Evaluation of a single matrix triad is additive in the first matrix argument: `eval_matrix3_triad t (A₁ + A₂) B = eval_matrix3_triad t A₁ B + eval_matrix3_triad t A₂ B`.
- The `simp` tactic in the inductive step automatically applies the induction hypothesis `ih` to rewrite the recursive evaluation on the tail list, because Lean 4 includes accessible hypotheses from the local context in the simplifier by default.
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.
/-- Left-additivity of triad decomposition evaluation. -/theorem eval_matrix3_decomposition_add_left {R : Type*} [CommSemiring R] (L : List (Matrix3Triad R)) (A₁ A₂ B : Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L (A₁ + A₂) B = eval_matrix3_decomposition L A₁ B + eval_matrix3_decomposition L A₂ B := by induction L with | nil => simp [eval_matrix3_decomposition] | cons t L' ih => simp [eval_matrix3_decomposition, eval_matrix3_triad_add_left] abel