matrix3_tensor_rank_le_pred_of_zero_v
If a valid decomposition has length at most r and contains a triad with zero v 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_v {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hv : t.v = 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_vEvaluating any triad whose v 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 show that the tensor rank of 3x3 matrix multiplication is at most r - 1, we drop the triad t from the decomposition L₁ ++ t :: L₂ to obtain L₁ ++ L₂. Because the v component of t is zero, t evaluates to the zero matrix on any input pair and contributes nothing to the sum. Removing t therefore decreases the length of the decomposition by one while preserving the evaluated product A * B.
It suffices to show that the concatenated list L₁ ++ L₂ has length at most r - 1 and forms a valid decomposition of 3x3 matrix multiplication.
By definition of matrix3_tensor_rank_le, the tensor rank is at most r - 1 if there exists a valid decomposition of length at most r - 1. We propose the list L₁ ++ L₂, obtained by dropping the triad t from the original decomposition, as the witness.
refine ⟨L₁ ++ L₂, ?_, ?_⟩The length of L₁ ++ L₂ is at most r - 1.
Rewriting with List.length_append and List.length_cons expands the original length bound |L₁ ++ t :: L₂| ≤ r to |L₁| + (|L₂| + 1) ≤ r. Linear integer arithmetic (omega) then proves that |L₁ ++ L₂| = |L₁| + |L₂| ≤ r - 1.
uses
List.length_append,List.length_cons· simp only [List.length_append, List.length_cons] at hlen ⊢ omega
For arbitrary matrices A and B, the validity of the shortened decomposition reduces to showing that the sum of triad evaluations over L₁ plus that over L₂ equals A * B.
We introduce arbitrary matrices A and B and specialize the validity of the original decomposition hval to them. Unfolding eval_matrix3_decomposition and distributing list mapping and summation across append and cons (via List.map_append, List.map_cons, List.sum_cons, and List.sum_append), the evaluation of L₁ ++ t :: L₂ is expressed as the sum over L₁ plus eval_matrix3_triad t A B plus the sum over L₂.
uses
List.map_append,List.map_cons,List.sum_cons,List.sum_append· intro A B have h := hval A B simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_cons, List.sum_append] at h ⊢
The triad t evaluates to the zero matrix on A and B.
Decomposing t into its components ⟨u, v, w⟩, the hypothesis hv becomes v = 0. Substituting v = 0, the lemma matrix3_eval_triad_zero_v shows that any triad with zero middle matrix evaluates to zero on any inputs A and B.
uses
matrix3_eval_triad_zero_vhave hzero : eval_matrix3_triad t A B = 0 := by cases t with | mk u v w => simp only at hv subst v exact matrix3_eval_triad_zero_v u w A B
The candidate decomposition L₁ ++ L₂ is valid, completing the proof.
Substituting eval_matrix3_triad t A B = 0 into the evaluated original decomposition replaces t's contribution with zero. Simplifying 0 + sum(L₂) to sum(L₂) shows that the shortened decomposition evaluates to A * B, as required.
rw [hzero] at h simpa using h
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 the concatenation of the mapped lists.
List.map_cons- Mapping a function over a list with a prepended element applies the function to the head and prepends it to the mapped tail.
List.sum_append- The sum of elements in the concatenation of two lists is the sum of the elements of the first list plus the sum of the elements of the second list.
List.sum_cons- The sum of a list with head a and tail l is a plus the sum of l.
matrix3_eval_triad_zero_v- Evaluating a 3x3 matrix multiplication triad whose second matrix component v is zero on any two matrices yields the zero matrix.
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 v matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_zero_v {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hv : t.v = 0) (hlen : (L₁ ++ t :: L₂).length ≤ r) (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) : matrix3_tensor_rank_le R (r - 1) := by refine ⟨L₁ ++ L₂, ?_, ?_⟩ · simp only [List.length_append, List.length_cons] at hlen ⊢ omega · intro A B have h := hval A B simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_cons, List.sum_append] at h ⊢ have hzero : eval_matrix3_triad t A B = 0 := by cases t with | mk u v w => simp only at hv subst v exact matrix3_eval_triad_zero_v u w A B rw [hzero] at h simpa using h