AFTD Auto-Formalizing Theoretical Domains

eval_matrix3_decomposition_sum_left

theoremverified

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`.

  1. 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.

    lines 4–8

    uses eval_matrix3_decomposition, eval_matrix3_triad

      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]
  2. 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.

    line 9

    uses Finset.cons_induction

      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
  3. 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.

    line 10

      · simp [hzero]
  4. 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.

    lines 11–12

    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

/-- 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]
See it in the graphDiscuss this resultChallenge it