AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_zero_u

theoremverified

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.

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

    line 8

      refine ⟨L₁ ++ L₂, ?_, ?_⟩
  2. 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.

    lines 9–10

    uses List.length_append, List.length_cons

      · simp only [List.length_append, List.length_cons] at hlen ⊢
        omega
  3. 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.

    lines 11–17

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

    lines 18–23

    uses eval_matrix3_decomposition, List.map_append, List.map_cons, List.sum_append, List.sum_cons

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

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