matrix3_tensor_rank_le_mono
For any commutative semiring R and natural numbers r₁ and r₂, if 3x3 matrix multiplication over R has tensor rank at most r₁ and r₁ ≤ r₂, then it has tensor rank at most r₂.
Statement
theorem matrix3_tensor_rank_le_mono {R : Type*} [CommSemiring R] {r₁ r₂ : ℕ} (h : matrix3_tensor_rank_le R r₁) (hle : r₁ ≤ r₂) : matrix3_tensor_rank_le R r₂
- Source
- step towards matrix3_tensor_rank_int_le_22
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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.
The proof, explained
By definition, a tensor rank bound of at most $r_1$ means there exists a decomposition into a list of at most $r_1$ rank-one triads that correctly computes the product of $3 \times 3$ matrices. Since $r_1 \le r_2$, the length of this same list is also at most $r_2$ by transitivity of inequality. Therefore, the identical list serves as a witness that the tensor rank is at most $r_2$.
We obtain a list $L$ of triads of length at most $r_1$ that validly decomposes $3 \times 3$ matrix multiplication.
By definition of `matrix3_tensor_rank_le R r₁`, there exists a list $L$ of matrix triads of length at most $r_1$ whose evaluation computes matrix multiplication. We unpack this existential hypothesis into the list $L$, the bound `hlen : L.length ≤ r₁`, and the validity property `hvalid`.
rcases h with ⟨L, hlen, hvalid⟩
The list $L$ witnesses that the tensor rank is at most $r_2$.
We supply $L$ as the witness for `matrix3_tensor_rank_le R r₂`. Its validity is already established by `hvalid`, and its length is at most $r_2$ by the transitivity of $\le$ applied to `hlen` ($L.\text{length} \le r_1$) and `hle` ($r_1 \le r_2$).
exact ⟨L, hlen.trans hle, hvalid⟩
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.
/-- Tensor rank upper bounds for 3x3 matrix multiplication are monotonic: if the rank is at most r₁ and r₁ ≤ r₂, then the rank is at most r₂. -/theorem matrix3_tensor_rank_le_mono {R : Type*} [CommSemiring R] {r₁ r₂ : ℕ} (h : matrix3_tensor_rank_le R r₁) (hle : r₁ ≤ r₂) : matrix3_tensor_rank_le R r₂ := by rcases h with ⟨L, hlen, hvalid⟩ exact ⟨L, hlen.trans hle, hvalid⟩