matrix3_tensor_rank_le_pred_of_zero_u
If a valid decomposition has length at most r and contains a triad with zero u 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_u {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hu : t.u = 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_uEvaluating any triad whose u 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 3×3 matrix multiplication is at most r - 1, we remove the triad t from the decomposition L₁ ++ t :: L₂ to form L₁ ++ L₂. Dropping one triad reduces the list length by 1, making it at most r - 1. Furthermore, because the u component of t is zero, t evaluates to zero on all input pairs, meaning its removal leaves the resulting matrix product unchanged.
To show that the tensor rank is at most r - 1, it suffices to show that L₁ ++ L₂ has length at most r - 1 and is a valid decomposition.
By definition of `matrix3_tensor_rank_le`, we provide the shortened list L₁ ++ L₂ (obtained by dropping the triad t) as a candidate witness. This splits the goal into verifying its length bound and verifying that it still computes matrix multiplication correctly.
refine ⟨L₁ ++ L₂, ?_, ?_⟩The length of L₁ ++ L₂ is at most r - 1.
Rewriting the lengths using `List.length_append` and `List.length_cons` simplifies the hypothesis (L₁ ++ t :: L₂).length ≤ r to |L₁| + |L₂| + 1 ≤ r. From this, linear arithmetic on natural numbers (`omega`) immediately implies |L₁| + |L₂| ≤ r - 1.
uses
List.length_append,List.length_cons· simp only [List.length_append, List.length_cons] at hlen ⊢ omega
For any input matrices A and B, the triad t evaluates to zero: eval_matrix3_triad t A B = 0.
Let A and B be arbitrary 3×3 matrices. By hypothesis, the u component of t is zero. By `matrix3_eval_triad_zero_u`, any triad of the form ⟨0, v, w⟩ evaluates to 0 on any matrices A and B, so t contributes zero.
uses
matrix3_eval_triad_zero_u· intro A B have ht : eval_matrix3_triad t A B = 0 := by have := matrix3_eval_triad_zero_u t.v t.w A B cases t dsimp at hu ⊢ subst hu exact this
The shortened list L₁ ++ L₂ is a valid decomposition of 3×3 matrix multiplication.
Validity of the original list L₁ ++ t :: L₂ means that its evaluation on A and B equals A * B. Unfolding `eval_matrix3_decomposition` and distributing the map and summation over list concatenation and cons (via `List.map_append`, `List.map_cons`, `List.sum_append`, and `List.sum_cons`), the original evaluation decomposes into the sum over L₁, plus the evaluation of t, plus the sum over L₂. Substituting the fact that t evaluates to 0, abelian group arithmetic (`abel`) establishes that the sum over L₁ ++ L₂ is identical to the original sum, which equals A * B.
uses
eval_matrix3_decomposition,List.map_append,List.map_cons,List.sum_append,List.sum_conshave h_orig := hval A B simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons] at h_orig ⊢ rw [ht] at h_orig rw [← h_orig] abel
eval_matrix3_decomposition- The evaluation of a list of triads on input matrices A and B is defined as the sum of the evaluations of the individual triads.
List.length_append- The length of the concatenation of two lists is the sum of their lengths: (as ++ bs).length = as.length + bs.length.
List.length_cons- Prepending an element to a list increases its length by one: (a :: as).length = as.length + 1.
List.map_append- Mapping a function over the concatenation of two lists distributes over concatenation: (l₁ ++ l₂).map f = l₁.map f ++ l₂.map f.
List.map_cons- Mapping a function over a list with a prepended element applies the function to the head: (a :: l).map f = f a :: l.map f.
List.sum_append- The sum of the concatenation of two lists is the sum of the elements in the first plus the sum of the elements in the second.
List.sum_cons- The sum of a list with a prepended element is the head plus the sum of the tail: (a :: l).sum = a + l.sum.
matrix3_eval_triad_zero_u- A 3×3 triad whose u matrix is zero evaluates to the zero matrix for any pair of input matrices A and B.
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 u matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_zero_u {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R) (hu : t.u = 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 ht : eval_matrix3_triad t A B = 0 := by have := matrix3_eval_triad_zero_u t.v t.w A B cases t dsimp at hu ⊢ subst hu exact this have h_orig := hval A B simp only [eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons] at h_orig ⊢ rw [ht] at h_orig rw [← h_orig] abel