matrix3_tensor_rank_le_pred_of_shared_u_v
If a valid decomposition has length at most r and contains two triads sharing u and v, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1.
Statement
theorem matrix3_tensor_rank_le_pred_of_shared_u_v {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v) (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
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_shorter_valid_of_shared_u_vIf 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 u…
- 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…
The proof, explained
The theorem establishes that the tensor rank is at most $r - 1$ by obtaining a strictly shorter valid decomposition $L'$ using `matrix3_shorter_valid_of_shared_u_v`, which merges the two triads sharing $u$ and $v$. Since the original decomposition has length at most $r$, the strictly shorter decomposition $L'$ has length at most $r - 1$, serving as the required witness for the tensor rank bound.
There exists a valid decomposition L' whose length is strictly less than that of the given decomposition.
Applying `matrix3_shorter_valid_of_shared_u_v` to the decomposition and the hypotheses that $t_1$ and $t_2$ share their $u$ and $v$ components produces a valid decomposition $L'$ with length strictly less than that of the original list $L_1 ++ t_1 :: L_2 ++ t_2 :: L_3$.
uses
matrix3_shorter_valid_of_shared_u_vobtain ⟨L', hlt, hval'⟩ := matrix3_shorter_valid_of_shared_u_v L₁ L₂ L₃ t₁ t₂ hu hv hvalThe tensor rank of 3×3 matrix multiplication is at most r - 1.
To show that the tensor rank is at most $r - 1$, it suffices to provide a valid decomposition of length at most $r - 1$. The list $L'$ witnesses this: it is valid by the previous step, and its length satisfies $|L'| \le r - 1$ by linear arithmetic (`omega`) from $|L'| < \mathrm{length}(\dots) \le r$.
exact ⟨L', by omega, hval'⟩
matrix3_shorter_valid_of_shared_u_v- If a valid decomposition contains two triads sharing identical u and v matrices, there exists a strictly shorter valid decomposition.
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 u and v, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_shared_u_v {R : Type*} [CommSemiring R] (r : ℕ) (L₁ L₂ L₃ : List (Matrix3Triad R)) (t₁ t₂ : Matrix3Triad R) (hu : t₁.u = t₂.u) (hv : t₁.v = t₂.v) (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_u_v L₁ L₂ L₃ t₁ t₂ hu hv hval exact ⟨L', by omega, hval'⟩