eval_matrix3_decomposition_sum_right
Given a commutative semiring R, a finite set s, a list L of triads, a matrix A, and a family of matrices G, evaluating L on A and (∑ i ∈ s, G i) equals ∑ i ∈ s, eval_matrix3_decomposition L A (G i).
Statement
theorem eval_matrix3_decomposition_sum_right {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (A : Matrix (Fin 3) (Fin 3) R) (G : ι → Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L A (∑ i ∈ s, G i) = ∑ i ∈ s, eval_matrix3_decomposition L A (G i)
- 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_rightGiven a commutative semiring R, a list L of Matrix3Triad R, and matrices A, B₁, and B₂, eval_matrix3_decomposition L A (B₁ + 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.induction_on`. The base case of the empty set reduces to evaluating the decomposition on the zero matrix, which is zero. In the inductive step, the sum over insert a s is split using `Finset.sum_insert`, distributed across the addition using the right-additivity lemma `eval_matrix3_decomposition_add_right`, and closed using the induction hypothesis.
It suffices to prove the identity when s is empty and when a new element is inserted into s.
We invoke classical logic to obtain decidable equality on the index type ι, and set up an induction on the finite set s using the induction principle `Finset.induction_on`.
uses
Finset.induction_onclassical induction s using Finset.induction_on with
The identity holds when s is the empty set. automation
When s = ∅, the sum of matrices on the left is the zero matrix, and evaluating the decomposition on the zero matrix yields zero. On the right, the sum over the empty set is also zero. The simplifier unfolds the definitions of `eval_matrix3_decomposition` and `eval_matrix3_triad` and computes that both sides equal zero.
uses
eval_matrix3_decomposition,eval_matrix3_triad| empty => simp [eval_matrix3_decomposition, eval_matrix3_triad]The identity holds for insert a s, completing the induction.
Assuming a ∉ s and the induction hypothesis for s, we separate the a-term from both sums using `Finset.sum_insert`. The left-hand side becomes the evaluation on G(a) + ∑ i ∈ s, G(i). By right-additivity (`eval_matrix3_decomposition_add_right`), this decomposes into the evaluation on G(a) plus the evaluation on ∑ i ∈ s, G(i). Replacing the latter using the induction hypothesis matches the right-hand side.
uses
Finset.sum_insert,eval_matrix3_decomposition_add_right| insert a s ha ih => rw [Finset.sum_insert ha, Finset.sum_insert ha, eval_matrix3_decomposition_add_right, ih]
Finset.induction_on- The induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
eval_matrix3_decomposition- Evaluating a list of triads on matrices A and B computes the sum of the individual triad evaluations over the list.
eval_matrix3_triad- Evaluating a triad (u, v, w) on matrices A and B produces the scalar (∑ uᵢⱼ Aᵢⱼ)(∑ vᵢⱼ Bᵢⱼ) multiplied by w.
Finset.sum_insert- Splitting off an element from a sum over a finite set: if a ∉ s, then ∑ x ∈ insert a s, f x = f a + ∑ x ∈ s, f x.
eval_matrix3_decomposition_add_right- Evaluation of a triad decomposition is additive in its right matrix argument: eval L A (B₁ + B₂) = eval L A B₁ + eval L A B₂.
- In the base case (line 6), the simplifier closes the goal automatically by using the definition of triad evaluation together with the fact that an empty sum of matrices evaluates to the zero matrix.
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 right matrix argument. -/theorem eval_matrix3_decomposition_sum_right {R : Type*} [CommSemiring R] {ι : Type*} (s : Finset ι) (L : List (Matrix3Triad R)) (A : Matrix (Fin 3) (Fin 3) R) (G : ι → Matrix (Fin 3) (Fin 3) R) : eval_matrix3_decomposition L A (∑ i ∈ s, G i) = ∑ i ∈ s, eval_matrix3_decomposition L A (G i) := by classical induction s using Finset.induction_on with | empty => simp [eval_matrix3_decomposition, eval_matrix3_triad] | insert a s ha ih => rw [Finset.sum_insert ha, Finset.sum_insert ha, eval_matrix3_decomposition_add_right, ih]