matrix3_shorter_valid_of_shared_v_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 v and the same w, then there is a valid decomposition with strictly fewer triads (merging their u matrices).
Statement
theorem matrix3_shorter_valid_of_shared_v_w {R : Type*} [CommSemiring R] (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hv : t₁.v = t₂.v) (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_int_le_22
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- Used by 1
- matrix3_tensor_rank_le_pred_of_shared_v_wIf a valid decomposition has length at most r and contains two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication…
The proof, explained
The proof constructs an explicit shortened list of triads by replacing t₁ and t₂ with a single triad whose u-component is t₁.u + t₂.u and whose v and w components are the shared ones. This list is strictly shorter because two triads are merged into one. Its validity follows from the linearity of triad evaluation: when two triads agree on their v and w components, their evaluations sum linearly in the u-component, so the total sum of triad evaluations is preserved.
We witness the existence of a shorter valid decomposition by merging t₁ and t₂ into ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩.
We construct the candidate list L' = L₁ ++ ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), replacing the two separate triads t₁ and t₂ with a single merged triad and concatenating the remaining segments. This leaves two subgoals: showing that the new list is strictly shorter, and showing that it remains a valid decomposition.
refine ⟨L₁ ++ ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), ?_, ?_⟩The candidate list has strictly shorter length than the original list.
Simplification using List.length_append and List.length_cons expands the length of the new list to |L₁| + 1 + |L₂| + |L₃| and that of the original list to |L₁| + 1 + |L₂| + 1 + |L₃|, reducing the goal to |L₁| + |L₂| + |L₃| + 1 < |L₁| + |L₂| + |L₃| + 2, which holds trivially.
uses
List.length_append,List.length_cons· simp [List.length_append, List.length_cons]To establish validity, it suffices to show that evaluating the candidate list on arbitrary matrices A and B yields A * B.
By definition of is_valid_matrix3_decomposition, a list of triads is valid if its evaluation equals the matrix product A * B for all pairs of matrices A and B. We introduce arbitrary 3 × 3 matrices A and B.
· intro A BThe triads t₁ and t₂ can be expressed in constructor form as ⟨t₁.u, t₁.v, t₁.w⟩ and ⟨t₂.u, t₁.v, t₁.w⟩.
Decomposing t₁ into its constructor fields gives t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ definitionally. Similarly, decomposing t₂ and rewriting with the hypotheses t₁.v = t₂.v (hv) and t₁.w = t₂.w (hw) expresses t₂ using the v and w components of t₁.
have ht1 : t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ := by cases t₁; rfl have ht2 : t₂ = ⟨t₂.u, t₁.v, t₁.w⟩ := by cases t₂; simp [hv, hw]
The sum of the evaluations of t₁ and t₂ equals the evaluation of the merged triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ on (A, B).
Rewriting t₁ and t₂ with their explicit component forms, the result follows from the linearity of triad evaluation in the u-component, given by the second conjunct of matrix3_eval_triad_merge.
uses
matrix3_eval_triad_mergehave h1 : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B = eval_matrix3_triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ A B := by rw [ht1, ht2] exact (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.1
The evaluation of the candidate list on A and B equals A * B.
From the validity hypothesis h, A * B equals the evaluation of the original list. By unfolding eval_matrix3_decomposition and distributing the mapping and summation over list concatenation and cons (List.map_append, List.map_cons, List.sum_append, List.sum_cons), both list evaluations expand into sums of individual triad evaluations. Replacing the merged triad evaluation by the sum of evaluations of t₁ and t₂ via the previously established identity leaves identical terms on both sides, which match by associativity and commutativity of addition (ac_rfl).
uses
List.map_append,List.map_cons,List.sum_append,List.sum_conshave hh := h A B rw [← hh] unfold eval_matrix3_decomposition simp only [List.map_append, List.map_cons, List.sum_append, List.sum_cons] rw [← h1] ac_rfl
List.length_append- The length of the concatenation of two lists is the sum of their lengths: |as ++ bs| = |as| + |bs|.
List.length_cons- Prepending an element to a list increases its length by 1: |a :: as| = |as| + 1.
matrix3_eval_triad_merge- Triad evaluation is linear in each component when the other two are identical; in particular, evaluating ⟨u₁, v₁, w₁⟩ plus evaluating ⟨u₂, v₁, w₁⟩ equals evaluating ⟨u₁ + u₂, v₁, w₁⟩.
List.map_append- Mapping a function over the concatenation of two lists distributes over concatenation: map f (l₁ ++ l₂) = map f l₁ ++ map f l₂.
List.map_cons- Mapping a function over a cons list applies the function to the head: map f (a :: l) = f a :: map f l.
List.sum_append- The sum of elements in the concatenation of two lists is the sum of their individual sums: (l₁ ++ l₂).sum = l₁.sum + l₂.sum.
List.sum_cons- The sum of a cons list adds the head to the sum of the tail: (a :: l).sum = a + l.sum.
- In Lean, the triads t₁ and t₂ are explicitly eta-expanded into constructor form ⟨u, v, w⟩ (lines 11–12) so that the algebraic merge lemma matrix3_eval_triad_merge can syntactically pattern-match on constructor applications; on paper, this step is implicit.
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 v and w components. -/theorem matrix3_shorter_valid_of_shared_v_w {R : Type*} [CommSemiring R] (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hv : t₁.v = t₂.v) (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₂.u, t₁.v, t₁.w⟩ :: (L₂ ++ L₃), ?_, ?_⟩ · simp [List.length_append, List.length_cons] · intro A B have ht1 : t₁ = ⟨t₁.u, t₁.v, t₁.w⟩ := by cases t₁; rfl have ht2 : t₂ = ⟨t₂.u, t₁.v, t₁.w⟩ := by cases t₂; simp [hv, hw] have h1 : eval_matrix3_triad t₁ A B + eval_matrix3_triad t₂ A B = eval_matrix3_triad ⟨t₁.u + t₂.u, t₁.v, t₁.w⟩ A B := by rw [ht1, ht2] exact (matrix3_eval_triad_merge t₁.u t₂.u t₁.v t₂.v t₁.w t₂.w A B).2.1 have hh := h A B rw [← hh] unfold eval_matrix3_decomposition simp only [List.map_append, List.map_cons, List.sum_append, List.sum_cons] rw [← h1] ac_rfl