matrix3_tensor_rank_le_pred_of_shared_v_w
If a valid decomposition has length at most r and contains two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1.
Statement
theorem matrix3_tensor_rank_le_pred_of_shared_v_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w) (hlen : (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ≤ r) (hval : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) : matrix3_tensor_rank_le R (r - 1)
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- matrix3_shorter_valid_of_shared_v_wIf 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…
- 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…
- 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…
The proof, explained
The proof constructs a shorter valid decomposition by combining the two triads that share both their v and w factors, via the lemma matrix3_shorter_valid_of_shared_v_w. Since the original decomposition has length at most r, this strictly shorter decomposition has length strictly less than r, and hence at most r - 1. This shorter decomposition witnesses that the tensor rank is at most r - 1.
There exists a valid decomposition L' strictly shorter than the given decomposition L₁ ++ t₁ :: L₂ ++ t₂ :: L₃.
Because the two triads t₁ and t₂ in the decomposition share the same v and w matrices (hv and hw), they can be combined into a single triad by summing their u matrices. Invoking matrix3_shorter_valid_of_shared_v_w yields such a valid decomposition L' whose length is strictly smaller than the original list's length.
uses
matrix3_shorter_valid_of_shared_v_wobtain ⟨L', hLt, hval'⟩ := matrix3_shorter_valid_of_shared_v_w L₁ L₂ L₃ t₁ t₂ hv hw hvalThe tensor rank of 3x3 matrix multiplication over R is at most r - 1.
By definition, matrix3_tensor_rank_le R (r - 1) requires a valid decomposition of length at most r - 1. We provide L' as the witness: since its length is strictly less than that of the original decomposition, which itself is at most r (hlen), lt_of_lt_of_le gives length(L') < r. By Nat.le_sub_one_of_lt, this implies length(L') ≤ r - 1, which alongside the validity of L' concludes the proof.
uses
Nat.le_sub_one_of_lt,lt_of_lt_of_leexact ⟨L', Nat.le_sub_one_of_lt (lt_of_lt_of_le hLt hlen), hval'⟩
matrix3_shorter_valid_of_shared_v_w- If a valid matrix multiplication decomposition contains two triads with identical v and w matrices, there exists a strictly shorter valid decomposition.
lt_of_lt_of_le- Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.le_sub_one_of_lt- For natural numbers, if a < b, then a ≤ b - 1.
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 two triads sharing v and w, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_shared_v_w {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hv : t₁.v = t₂.v) (hw : t₁.w = t₂.w) (hlen : (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃).length ≤ r) (hval : is_valid_matrix3_decomposition (L₁ ++ t₁ :: L₂ ++ t₂ :: L₃)) : matrix3_tensor_rank_le R (r - 1) := by obtain ⟨L', hLt, hval'⟩ := matrix3_shorter_valid_of_shared_v_w L₁ L₂ L₃ t₁ t₂ hv hw hval exact ⟨L', Nat.le_sub_one_of_lt (lt_of_lt_of_le hLt hlen), hval'⟩