AFTD Auto-Formalizing Theoretical Domains

matrix3_tensor_rank_le_pred_of_zero_w

theoremverified

If a valid decomposition has length at most r and contains a triad with zero w 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_w {R : Type*} [CommSemiring R]
    (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R)
    (hw : t.w = 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_wEvaluating any triad whose w 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 bound the tensor rank of 3x3 matrix multiplication by r - 1, we drop the triad t with w = 0 from the given valid decomposition of length at most r. The reduced decomposition L₁ ++ L₂ has length at most r - 1 by simple arithmetic. Furthermore, because any triad whose third matrix is zero evaluates to zero on all inputs, omitting t does not affect the evaluation, so L₁ ++ L₂ remains a valid decomposition.

  1. The triad t has the form ⟨u, v, 0⟩ for some matrices u and v.

    We decompose t into its components ⟨u, v, w⟩. The assumption hw : t.w = 0 simplifies to w = 0, and substituting this equality replaces w with the zero matrix.

    lines 8–10

      rcases t with ⟨u, v, w⟩
      simp only at hw
      subst hw
  2. To show the tensor rank is at most r - 1, it suffices to show that the reduced list L₁ ++ L₂ has length at most r - 1 and is a valid decomposition.

    By definition, the tensor rank bound is witnessed by any valid decomposition whose length does not exceed r - 1. We propose the concatenated list L₁ ++ L₂, which omits the zero triad t, as the witness. This splits the proof into two subgoals: bounding its length and verifying its validity.

    line 11

      refine ⟨L₁ ++ L₂, ?_, ?_⟩
  3. The length of L₁ ++ L₂ is at most r - 1.

    Rewriting lengths using List.length_append and List.length_cons transforms the length hypothesis into |L₁| + (|L₂| + 1) ≤ r and the goal into |L₁| + |L₂| ≤ r - 1. Linear arithmetic over natural numbers (omega) closes the goal.

    lines 12–13

    uses List.length_append, List.length_cons

      · simp only [List.length_append, List.length_cons] at hlen ⊢
        omega
  4. The reduced decomposition L₁ ++ L₂ is a valid decomposition of matrix multiplication.

    Let A and B be arbitrary 3x3 matrices. We first show that evaluating L₁ ++ L₂ on A and B yields the same result as evaluating the original decomposition L₁ ++ t :: L₂: unfolding eval_matrix3_decomposition as a sum of triad evaluations over the list using List.map_append, List.map_cons, List.sum_append, and List.sum_cons, the triad t = ⟨u, v, 0⟩ evaluates to the zero matrix by matrix3_eval_triad_zero_w, which drops out of the sum by zero_add. Rewriting with this equality, the evaluation of L₁ ++ L₂ on A and B equals that of the original decomposition, which evaluates to A * B by the assumption hval.

    lines 14–20

    uses List.map_append, List.map_cons, List.sum_append, List.sum_cons, matrix3_eval_triad_zero_w, zero_add

      · intro A B
        have key : eval_matrix3_decomposition (L₁ ++ L₂) A B
            = eval_matrix3_decomposition (L₁ ++ Matrix3Triad.mk u v 0 :: L₂) A B := by
          simp only [eval_matrix3_decomposition, List.map_append, List.map_cons,
            List.sum_append, List.sum_cons, matrix3_eval_triad_zero_w, zero_add]
        rw [key]
        exact hval A B
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
List.length_cons
Prepending an element to a list increases its length by one.
List.map_append
Mapping a function over the concatenation of two lists equals concatenating the mapped lists.
List.map_cons
Mapping a function over a list with head a and tail l yields f(a) followed by the mapped tail.
List.sum_append
The sum of elements in the concatenation of two lists is the sum of the sums of the two lists.
List.sum_cons
The sum of elements in a list with head a and tail l equals a plus the sum of l.
matrix3_eval_triad_zero_w
Evaluating any triad whose third matrix w is zero on any pair of matrices produces the zero matrix.
zero_add
Zero is a left identity for addition: 0 + a = a.

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 w matrix, then the tensor rank of 3x3 matrix multiplication over R is at most r - 1. -/theorem matrix3_tensor_rank_le_pred_of_zero_w {R : Type*} [CommSemiring R]    (r : ℕ) (L₁ L₂ : List (Matrix3Triad R)) (t : Matrix3Triad R)    (hw : t.w = 0)    (hlen : (L₁ ++ t :: L₂).length ≤ r)    (hval : is_valid_matrix3_decomposition (L₁ ++ t :: L₂)) :    matrix3_tensor_rank_le R (r - 1) := by  rcases t with ⟨u, v, w⟩  simp only at hw  subst hw  refine ⟨L₁ ++ L₂, ?_, ?_⟩  · simp only [List.length_append, List.length_cons] at hlen ⊢    omega  · intro A B    have key : eval_matrix3_decomposition (L₁ ++ L₂) A B        = eval_matrix3_decomposition (L₁ ++ Matrix3Triad.mk u v 0 :: L₂) A B := by      simp only [eval_matrix3_decomposition, List.map_append, List.map_cons,        List.sum_append, List.sum_cons, matrix3_eval_triad_zero_w, zero_add]    rw [key]    exact hval A B
See it in the graphDiscuss this resultChallenge it