AFTD Auto-Formalizing Theoretical Domains

matrix3_shorter_valid_of_shared_u_v

theoremverified

If 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 and the same v, then there is a valid decomposition with strictly fewer triads (merging their w matrices).

Statement

theorem matrix3_shorter_valid_of_shared_u_v {R : Type*} [CommSemiring R]
    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)
    (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v)
    (h : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :
    ∃ L' : List (Matrix3Triad R),
      L'.length < (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ∧ is_valid_matrix3_decomposition L'
Source
step towards matrix3_tensor_rank_int_le_22
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • is_valid_matrix3_decompositionGiven a commutative semiring R and a list L of Matrix3Triad R, is_valid_matrix3_decomposition L asserts that for all 3x3 matrices A and B…
  • 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_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…
  • matrix3_eval_triad_mergeTwo 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…
  • 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…
Used by 1

The proof, explained

To construct a strictly shorter valid decomposition, we replace the two triads t₁ and t₂ with a single triad whose w component is t₁.w + t₂.w, retaining their shared u and v components. Because triad evaluation is additive in the w component when u and v match, the evaluation of this merged triad equals the sum of the evaluations of t₁ and t₂. Expanding both the shortened decomposition and the original valid decomposition into sums over their constituent triads reveals that they contain the exact same terms. By the commutativity and associativity of matrix addition, the shortened decomposition also evaluates to A * B, establishing its validity.

  1. There exists a candidate decomposition L' = L₁ ++ ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ :: (L₂ ++ L₃) whose length is strictly less than that of the original list. automation

    We propose replacing the two separate triads t₁ and t₂ with a single triad whose w component is their sum t₁.w + t₂.w, preserving their common u and v components. The candidate list replaces two elements with one, so its length is strictly smaller than the original list's length, which is verified automatically by simplification (`simp`).

    line 8

      refine ⟨L₁ ++ ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩
  2. To prove that the candidate decomposition is valid, it suffices to show that evaluating it on arbitrary matrices A and B produces A * B.

    By definition, a decomposition is valid if its evaluation on any pair of matrices A and B yields their product A * B. We introduce arbitrary 3x3 matrices A and B.

    line 9

      intro A B
  3. Evaluating the merged triad ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ on A and B equals the sum of the evaluations of t₁ and t₂ on A and B.

    By `matrix3_eval_triad_merge`, triad evaluation is linear in the w component when the u and v components agree. Unpacking the record fields of t₁ and t₂ and substituting the equality hypotheses t₁.u = t₂.u and t₁.v = t₂.v matches this lemma directly.

    lines 10–17

    uses matrix3_eval_triad_merge

      have hmerge : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B =
          eval_matrix3_triad ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ A B := by
        have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.2
        cases t₁
        cases t₂
        dsimp at hu hv ⊢
        subst hu hv
        exact this
  4. The evaluation of the shortened decomposition on A and B equals the sum of the evaluations of L₁, t₁, t₂, L₂, and L₃.

    We expand the definition of `eval_matrix3_decomposition` across list concatenations using `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons`. We then rewrite the evaluation of the merged triad into the sum of the evaluations of t₁ and t₂ using our merge identity.

    lines 18–20

    uses eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons

      simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append,
        List.sum_cons]
      rw [← hmerge]
  5. The evaluation of the shortened decomposition on A and B equals A * B, completing the proof. automation

    Since the original list is a valid decomposition, evaluating it on A and B produces A * B. Expanding that evaluation across list concatenations yields the exact same sum of triad evaluations as the shortened list, differing only in the grouping and order of summands. Replacing A * B with this sum, the goal reduces to an identity in the commutative additive group of matrices, closed automatically by `abel`.

    lines 21–25

    uses eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons

      have h_orig : eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B := h A B
      simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append,
        List.sum_cons] at h_orig
      rw [← h_orig]
      abel
matrix3_eval_triad_merge
Triad evaluation is additive in each of the three triad components (u, v, and w) when the other two components are held fixed; in particular, adding the w components of two triads with matching u and v yields the sum of their individual evaluations.
eval_matrix3_decomposition
Evaluating a triad decomposition on matrices A and B is defined as the sum of the evaluations of each triad in the list on A and B.
List.map_append
Mapping a function over the concatenation of two lists equals the concatenation of the mapped lists.
List.map_cons
Mapping a function over a list with head element a and tail l yields the head f(a) followed by the mapped tail.
List.sum_append
The sum of the elements in the concatenation of two lists is the sum of the first list plus the sum of the second list.
List.sum_cons
The sum of a list with head element a and tail l is a plus the sum of l.

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

/-- Valid 3x3 triad decompositions can be shortened by merging two triads sharing u and v components. -/theorem matrix3_shorter_valid_of_shared_u_v {R : Type*} [CommSemiring R]    (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R)    (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v)    (h : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) :    ∃ L' : List (Matrix3Triad R),      L'.length < (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ∧ is_valid_matrix3_decomposition L' := by  refine ⟨L₁ ++ ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩  intro A B  have hmerge : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B =      eval_matrix3_triad ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ A B := by    have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.2    cases t₁    cases t₂    dsimp at hu hv ⊢    subst hu hv    exact this  simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append,    List.sum_cons]  rw [← hmerge]  have h_orig : eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B := h A B  simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append,    List.sum_cons] at h_orig  rw [← h_orig]  abel
See it in the graphDiscuss this resultChallenge it