matrix3_shorter_valid_of_shared_u_w
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 w, then there is a valid decomposition with strictly fewer triads (namely L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃)).
Statement
theorem matrix3_shorter_valid_of_shared_u_w {R : Type*} [CommSemiring R] (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (hw : t₁.w = t₂.w) (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_zmod2_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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_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…
- 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…
- Used by 2
- matrix3_shorter_valid_of_shared_u_vIf 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…
- matrix3_tensor_rank_le_pred_of_shared_u_wIf a valid decomposition has length at most r and contains two triads sharing u and w, then the tensor rank of 3x3 matrix multiplication…
The proof, explained
The proof shows that any valid triad decomposition containing two triads t₁ and t₂ that share the same u and w components can be compressed into a strictly shorter valid decomposition by merging them into a single triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩. Because two list entries are replaced by one, the length strictly decreases. By bilinearity of triad evaluation (`matrix3_eval_triad_merge`), the evaluation of the merged triad equals the sum of the evaluations of t₁ and t₂, so the total evaluation sum over all triads is preserved and continues to compute A * B.
There exists a candidate decomposition L' = L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃) whose length is strictly less than that of the original list, leaving only its validity to be shown.
We provide L' as the witness. While the original list contains both t₁ and t₂ (separated by L₂), the candidate list L' combines them into a single merged triad ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩. Thus, L' has length |L₁| + 1 + |L₂| + |L₃|, which is strictly smaller than the original length |L₁| + 1 + |L₂| + 1 + |L₃|; this inequality is verified by simplification (`simp`).
refine ⟨L₁ ++ ⟨t₁.u, t₁.v + t₂.v, t₁.w⟩ :: (L₂ ++ L₃), by simp, ?_⟩
It suffices to show that evaluating the candidate decomposition on arbitrary 3 × 3 matrices A and B produces A * B.
By definition, a triad list is a valid decomposition if its evaluation on any pair of matrices A and B yields their matrix product A * B. We introduce arbitrary matrices A and B into the context.
intro A BThe sum of the evaluations of t₁ and t₂ on A and B equals the evaluation of the merged triad: eval(t₁, A, B) + eval(t₂, A, B) = eval(⟨t₁.u, t₁.v + t₂.v, t₁.w⟩, A, B).
The first clause of `matrix3_eval_triad_merge` asserts that evaluating two triads that agree in u and w and adding the results is equivalent to evaluating a single triad with the sum of their v components. Decomposing t₁ and t₂ into their components (`cases`), simplifying projections (`dsimp`), and substituting the hypotheses hu (t₁.u = t₂.u) and hw (t₁.w = t₂.w) aligns the triads with this lemma.
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₂.v, t₁.w⟩ A B := by have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).1 cases t₁ cases t₂ dsimp at hu hw ⊢ subst hu hw exact this
The evaluation of the candidate decomposition on A and B is rewritten as the sum of evaluations over L₁, t₁, t₂, L₂, and L₃.
Unfolding the definition `eval_matrix3_decomposition` expresses the evaluation as the sum of the evaluations of the list's triads. Using `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons`, the sum distributes over list concatenation and cons into terms for L₁, the merged triad, L₂, and L₃. Rewriting with `hmerge` in reverse replaces the merged triad's evaluation by eval(t₁, A, B) + eval(t₂, A, B).
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 target product A * B is rewritten as the sum of triad evaluations over L₁, t₁, L₂, t₂, and L₃ from the original decomposition.
Specializing the validity hypothesis h of the original list to matrices A and B yields eval_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃) A B = A * B. Distributing the list map and summation across the original decomposition via `eval_matrix3_decomposition`, `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons` expands A * B into the sum over L₁, t₁, L₂, t₂, and L₃. Rewriting by this identity substitutes the expanded sum for A * B in the goal.
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]
The evaluation of the candidate decomposition equals A * B.
Both sides of the equation are now sums of the exact same five matrix terms—the sum over L₁, the evaluation of t₁, the evaluation of t₂, the sum over L₂, and the sum over L₃—differing only in their grouping and order of addition. The `abel` tactic closes the goal by associativity and commutativity of addition in the abelian group of matrices.
abel
matrix3_eval_triad_merge- Evaluating two triads that share the same u and w matrices and adding the results is equal to evaluating the single triad formed by adding their v matrices (with analogous merge identities for shared v, w or shared u, v).
eval_matrix3_decomposition- The evaluation of a decomposition list on matrices A and B is defined as the sum of the evaluations of its constituent triads on A and B.
List.map_append- Mapping a function over the concatenation of two lists equals the concatenation of the results of mapping over each list separately.
List.map_cons- Mapping a function over a list with head a and tail l equals f(a) prepended to the result of mapping over l.
List.sum_append- The sum of elements in the concatenation of two lists equals the sum of the elements in the first list plus the sum of the elements in the second list.
List.sum_cons- The sum of elements in a list with head a and tail l equals a plus the sum of elements in l.
- The strict inequality on list lengths is discharged automatically inside line 8 by `simp`, which evaluates the lengths of the concatenated lists.
- The final algebraic equality in line 23 is closed by the `abel` tactic, which handles commutativity and associativity in abelian groups without requiring explicit rewrite steps.
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.
/-- A valid list containing two triads that share u and w can be replaced by a strictly shorter valid list (merge them and drop one product). -/theorem matrix3_shorter_valid_of_shared_u_w {R : Type*} [CommSemiring R] (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (hw : t₁.w = t₂.w) (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₂.v, 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₂.v, t₁.w⟩ A B := by have := (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).1 cases t₁ cases t₂ dsimp at hu hw ⊢ subst hu hw 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