matrix3_shorter_valid_of_shared_u_v
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
- matrix3_tensor_rank_le_pred_of_shared_u_vIf a valid decomposition has length at most r and contains two triads sharing u and v, then the tensor rank of 3x3 matrix multiplication…
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.
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`).
refine ⟨L₁ ++ ⟨t₁.u, t₁.v, t₁.w + t₂.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩
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.
intro A BEvaluating 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.
uses
matrix3_eval_triad_mergehave 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
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.
uses
eval_matrix3_decomposition,List.map_append,List.map_cons,List.sum_append,List.sum_conssimp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons] rw [← hmerge]
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`.
uses
eval_matrix3_decomposition,List.map_append,List.map_cons,List.sum_append,List.sum_conshave 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.
- On line 8, the strict inequality between list lengths is proved automatically by `simp`.
- Lines 13–16 unpack the record structures of triads `t₁` and `t₂` into their explicit component matrices and substitute the equality hypotheses; on paper this structural matching is immediate.
- On line 25, the tactic `abel` closes the goal by automatically simplifying and reordering terms in the commutative additive group of matrices.
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.
/-- 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