AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_mono

theoremverified

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$.

  1. 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`.

    line 3

      rcases h with ⟨L, hlen, hvalid⟩
  2. 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$).

    line 4

      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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it