matrix3_tensor_rank_le_pred_of_zero_w
If a valid decomposition has length at most r and contains a triad with zero w matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1.
Statement
theorem matrix3_tensor_rank_le_pred_of_zero_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hw : t.w = 0) (hlen : (L₁ ++ t :: L₂).length ≤ r) (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) : matrix3_tensor_rank_le R (r - 1)
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 25 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.
- matrix3_eval_triad_zero_wEvaluating any triad whose w component is zero yields the zero matrix for all input matrices A and B.
- matrix3_tensor_rank_leFor a commutative semiring R and a natural number r, matrix3_tensor_rank_le R r asserts that there exists a list L of elements of…
- 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…
The proof, explained
To bound the tensor rank of 3x3 matrix multiplication by r - 1, we drop the triad t with w = 0 from the given valid decomposition of length at most r. The reduced decomposition L₁ ++ L₂ has length at most r - 1 by simple arithmetic. Furthermore, because any triad whose third matrix is zero evaluates to zero on all inputs, omitting t does not affect the evaluation, so L₁ ++ L₂ remains a valid decomposition.
The triad t has the form ⟨u, v, 0⟩ for some matrices u and v.
We decompose t into its components ⟨u, v, w⟩. The assumption hw : t.w = 0 simplifies to w = 0, and substituting this equality replaces w with the zero matrix.
rcases t with ⟨u, v, w⟩ simp only at hw subst hw
To show the tensor rank is at most r - 1, it suffices to show that the reduced list L₁ ++ L₂ has length at most r - 1 and is a valid decomposition.
By definition, the tensor rank bound is witnessed by any valid decomposition whose length does not exceed r - 1. We propose the concatenated list L₁ ++ L₂, which omits the zero triad t, as the witness. This splits the proof into two subgoals: bounding its length and verifying its validity.
refine ⟨L₁ ++ L₂, ?_, ?_⟩The length of L₁ ++ L₂ is at most r - 1.
Rewriting lengths using List.length_append and List.length_cons transforms the length hypothesis into |L₁| + (|L₂| + 1) ≤ r and the goal into |L₁| + |L₂| ≤ r - 1. Linear arithmetic over natural numbers (omega) closes the goal.
uses
List.length_append,List.length_cons· simp only [List.length_append, List.length_cons] at hlen ⊢ omega
The reduced decomposition L₁ ++ L₂ is a valid decomposition of matrix multiplication.
Let A and B be arbitrary 3x3 matrices. We first show that evaluating L₁ ++ L₂ on A and B yields the same result as evaluating the original decomposition L₁ ++ t :: L₂: unfolding eval_matrix3_decomposition as a sum of triad evaluations over the list using List.map_append, List.map_cons, List.sum_append, and List.sum_cons, the triad t = ⟨u, v, 0⟩ evaluates to the zero matrix by matrix3_eval_triad_zero_w, which drops out of the sum by zero_add. Rewriting with this equality, the evaluation of L₁ ++ L₂ on A and B equals that of the original decomposition, which evaluates to A * B by the assumption hval.
uses
List.map_append,List.map_cons,List.sum_append,List.sum_cons,matrix3_eval_triad_zero_w,zero_add· intro A B have key : eval_matrix3_decomposition (L₁ ++ L₂) A B = eval_matrix3_decomposition (L₁ ++ Matrix3Triad.mk u v 0 :: L₂) A B := by simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons, matrix3_eval_triad_zero_w, zero_add] rw [key] exact hval A B
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_cons- Prepending an element to a list increases its length by one.
List.map_append- Mapping a function over the concatenation of two lists equals concatenating the mapped lists.
List.map_cons- Mapping a function over a list with head a and tail l yields f(a) followed by the mapped tail.
List.sum_append- The sum of elements in the concatenation of two lists is the sum of the sums of the two lists.
List.sum_cons- The sum of elements in a list with head a and tail l equals a plus the sum of l.
matrix3_eval_triad_zero_w- Evaluating any triad whose third matrix w is zero on any pair of matrices produces the zero matrix.
zero_add- Zero is a left identity for addition: 0 + a = a.
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.
/-- If a valid decomposition has length at most r and contains a triad with zero w matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_zero_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hw : t.w = 0) (hlen : (L₁ ++ t :: L₂).length ≤ r) (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) : matrix3_tensor_rank_le R (r - 1) := by rcases t with ⟨u, v, w⟩ simp only at hw subst hw refine ⟨L₁ ++ L₂, ?_, ?_⟩ · simp only [List.length_append, List.length_cons] at hlen ⊢ omega · intro A B have key : eval_matrix3_decomposition (L₁ ++ L₂) A B = eval_matrix3_decomposition (L₁ ++ Matrix3Triad.mk u v 0 :: L₂) A B := by simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons, matrix3_eval_triad_zero_w, zero_add] rw [key] exact hval A B